Algoritmizace a programování
Ak. rok 2012/2013
© vbP
1. ze 44
Algoritmizace a programování Vladimír Beneš Petrovický K101 – katedra matematiky, statistiky a informačních technologií vedoucí katedry E-mail:
[email protected] Telefon: 251 114 534, 731 425 276 Konzultační hodiny: středa 14:00 – 16:00
Ak. rok 2012/2013
© vbP
2. ze 44
Algoritmizace a programování Hodinová dotace Prezenční studium 1 semestr
2/2
KZ
6 kreditů
12/4
KZ
6 kreditů
Kombinované studium 1 semestr
Ak. rok 2012/2013
© vbP
3. ze 44
Algoritmizace a programování Požadavky ke klasifikovanému zápočtu Prezenční studium Kombinované studium Kompletní vypracování dané úlohy (přihlášení v ISu) Analýza úlohy Algoritmizace Odladěný zdrojový kód programu v jazyce C++
Ak. rok 2012/2013
© vbP
4. ze 44
Algoritmizace a programování Studijní literatura Literatura základní HEROUT, Pavel. Učebnice jazyka C. České Budějovice : Kopp, 1997. ISBN 80-85828-21-9. BENEŠ, Vladimír. Algoritmizace a programování. Elektronická studijní opora. Praha : BIVŠ, 2011. PRATA, Stephen. Mistrovství v C++. Brno : Computer Press, 2004. ISBN 80-251-0098-7.
Literatura doporučená KADLEC, Václav. Učíme se programovat v jazyce C. Praha : Computer Press, 2002. ISBN 80-7226-715-9. MILKOVÁ, E. a kol. Algoritmy, základní konstrukce v příkladech a jejich vizualizace. Hradec Králové : Gaudeamus, 2010.
KNUTH, Donald, E. Umění programování.1. díl, Základní algoritmy. Brno : Computer Press, 2008,. ISBN 978-80-2512025-5. Ak. rok 2012/2013
© vbP
5. ze 44
Algoritmizace a programování
Obsah Algoritmizace Algoritmus Zápis algoritmu Některé základní algoritmy
Programování Historie jazyka C/C++ Syntaxe základních příkazů jazyka C++ Programovací prostředí Ladění úlohy Ak. rok 2012/2013
© vbP
6. ze 44
Algoritmizace a programování
I Algoritmizace
Ak. rok 2012/2013
© vbP
7. ze 44
Algoritmizace a programování
ALGORITMIZACE
Ak. rok 2012/2013
© vbP
8. ze 44
Algoritmizace a programování
Algoritmus
Algoritmus je základní matematický pojem. • Nelze jej tedy definovat. • Musíme se tedy uchýlit pouze k opisu. V případě PROGRAMOVÁNÍ jde o transformaci množiny vstupních dat na množinu výstupních dat.
Ak. rok 2012/2013
© vbP
9. ze 44
Algoritmizace a programování Algoritmus
Opisná „DEFINICE“ Je to postup, jak řešit danou úlohu pomocí počítače. Sestává z posloupnosti jednoduchých předem stanovených kroků (ekementárních operací, instrukcí) a vede od vstupních měnitelných údajů až k žádaným výstupním údajům (výsledku).
Ak. rok 2012/2013
© vbP
10. ze 44
Algoritmizace a programování Vlastnosti algoritmu
Je ELEMENTÁRNÍ Skládá se z konečného počtu jednoduchých (snadno realizovatelných) činností, které označujeme jako kroky.
Ak. rok 2012/2013
© vbP
11. ze 44
Algoritmizace a programování Vlastnosti algoritmu
Je DETERMINOVANÝ Po každém kroku lze určit, zda popisovaný proces skončil. Pokud neskončil, pak musí být dáno, kterým krokem má pokračovat.
Ak. rok 2012/2013
© vbP
12. ze 44
Algoritmizace a programování Vlastnosti algoritmu
Je KONEČNÝ Počet opakování jednotlivých kroků je vždy konečný. Algoritmus tedy musí skončit po konečném počtu kroků.
Poznámka: příklad s instrukcí
Ak. rok 2012/2013
1 GOTO 1
© vbP
13. ze 44
Algoritmizace a programování Vlastnosti algoritmu
Je REZULTATIVNÍ Vede ke správnému výsledku.
Ak. rok 2012/2013
© vbP
14. ze 44
Algoritmizace a programování Vlastnosti algoritmu
Je HROMADNÝ Algoritmus můžeme použít k řešení celé (velké) skupiny (třídy) podobných úloh. Poznámka: např. řešení kvadratické rovnice, soustavy lineárních algebraických rovnic
Ak. rok 2012/2013
© vbP
15. ze 44
Algoritmizace a programování Poznámka 1.
Pojem algoritmus se dá formalizovat např. pomocí matematické konstrukce označované jako • Turingův stroj • procesorová jednotka, tvořená konečným automatem, • program ve tvaru pravidel přechodové funkce, • pravostranně nekonečné páska pro zápis mezivýsledků.
• Churchova teze Ke každému algoritmu existuje ekvivalentní Thuringův stroj.
Ak. rok 2012/2013
© vbP
16. ze 44
Algoritmizace a programování Poznámka 2.
Pojem algoritmus se dá formalizovat např. pomocí matematické konstrukce označované jako nebo pomocí • teorie parciálně rekurzivních funkcí • v teorii vyčíslitelnosti se takto označují funkce v jistém smyslu „složitější“ než tzv. primitivně rekurzivní funkce
Ak. rok 2012/2013
© vbP
17. ze 44
Algoritmizace a programování Metoda SHORA DOLŮ a ZDOLA NAHORU
1. Daný problém musíme vyřešit. 2. Známe-li řešení, potřebujeme jej zapsat jako algoritmus 3. Postup řešení rozkládáme na jednodušší operace – elementární kroky tj. metoda SHORA DOLŮ Poznámka: řešení kvadratické rovnice (analýza a řešení) Ak. rok 2012/2013
© vbP
18. ze 44
Algoritmizace a programování Metoda SHORA DOLŮ a ZDOLA NAHORU Kromě metody SHORA DOLŮ se setkáváme i s metodou ZDOLA NAHORU: • Postupně z elementárních kroků vytváříme prostředky, které umožní zvládnout daný problém • Vytváříme nový procesor tím, že ho učíme nové operace Použijeme vyšší programovací jazyk (procedury, knihovna procedur nebo systém pro vytváření programů (CASE)) Ak. rok 2012/2013
© vbP
19. ze 44
Algoritmizace a programování Základní složky (konstrukce) algoritmu Posloupnost (sekvence) • tvořena jedním nebo několika kroky (provedou se právě jednou v daném pořadí) • nemusí jít o kroky elementární • dalším zjemňováním se mohou rozpadnout na součásti, které samy tvoří posloupnosti, cykly nebo podmínky Ak. rok 2012/2013
© vbP
20. ze 44
Algoritmizace a programování Základní složky (konstrukce) algoritmu Cyklus (iterace) • část algoritmu, která se opakuje dokud je splněna podmínka opakování • cyklus se vždy skládá z podmínky opakování a z těla cyklu (tj. operací, které se opakují) • vyhodnocení podmínky může být před provedením (v C while nebo for), resp. po skončení těla cyklu (v C do-while) nebo i uvnitř těla cyklu (podmíněný skok nebo kombinace podmínky a break) Ak. rok 2012/2013
© vbP
21. ze 44
Algoritmizace a programování Základní složky (konstrukce) algoritmu Podmíněná operace (selekce) • představuje vždy větvení algoritmu • tvořena podmínkou a 1, 2 nebo více výběrovými složkami • pokud je jedna ze složek vybrána, provede se jednou • v C příkazy if a switch (v kombinaci s příkazem break)
Ak. rok 2012/2013
© vbP
22. ze 44
Algoritmizace a programování Základní složky (konstrukce) algoritmu Podprogram • opakuje-li se určitá část algoritmu na několika místech (může používat různá data) • na elementární kroky ji rozložíme pouze jednou (např. narazíme-li na ni poprvé) • na ostatních místech se na ni odvoláme jako na • dílčí algoritmus nebo • podprogram (procedura, resp. funkce) Ak. rok 2012/2013
© vbP
23. ze 44
Algoritmizace a programování Algoritmus a data • struktura vstupních, výstupních, ale i vnitřních dat spoluurčuje strukturu programu • posloupnosti datových položek různých druhů odpovídá posloupnost různých příkazů Poznámka: Přirozeným prostředkem pro zpracování rekurzivních datových struktur (stromy nebo seznamy) jsou obvykle rekurzivní algoritmy! Ak. rok 2012/2013
© vbP
24. ze 44
Algoritmizace a programování Časová a paměťová náročnost algoritmů • potřebné množství operační paměti • doba pro provedení algoritmu • rozsah vstupních údajů • celkový počet elementárních operací (instrukcí) Poznámka: Ve skutečnosti zpravidla stačí orientovat se podle vybraných skupin instrukcí, které jsou časově nejnáročnější (if)! Ak. rok 2012/2013
© vbP
25. ze 44
Algoritmizace a programování Popis algoritmů Jazyk pro popis programů • Program Description Language (PDL) • slovní popis algoritmu, dnes velmi častý • „lehce“ upravený programovací jazyk, např. Pascal (Pseudopascal) Poznámka: • Tradičním jazykem pro popis algoritmů býval Algol 60. • Slovní popis programu se může stát základem dobrého komentáře k výslednému programu. Ak. rok 2012/2013
© vbP
26. ze 44
Algoritmizace a programování Popis algoritmů Strukturogramy • grafické znázornění algoritmu • tvarově i barevně odlišné znázornění (sekvence, iterace, selekce) Poznámka: • Základem obdélník; v záhlaví označení algoritmu nebo dílčí operace; uvnitř kroky, které algoritmus tvoří
Ak. rok 2012/2013
© vbP
27. ze 44
Algoritmizace a programování Popis algoritmů Vývojové diagramy • klasický prostředek (ČSN 36 4030, ÚNM, Praha 1974) • graficky náročné (úpravy hotových VD) Poznámka: Spíše než logickou strukturu programu zdůrazňují druh operací.
Ak. rok 2012/2013
© vbP
28. ze 44
Algoritmizace a programování Vývojové diagramy
mezní značka (začátek, resp. konec algoritmu) sekvence předem definovaná činnost (podprogram) selekce (rozhodování)
Ak. rok 2012/2013
© vbP
29. ze 44
Algoritmizace a programování Vývojové diagramy
iterace (začátek, resp. konec iteračního cyklu) vstup, resp. výstup dat spojka komentář (poznámka)
Ak. rok 2012/2013
© vbP
30. ze 44
Algoritmizace a programování Vývojové diagramy
• obrazce (značky) propojeny čarami (svisle, vodorovně) • implicitní směr shora dolů, zprava doleva, jinak šipky
Ak. rok 2012/2013
© vbP
31. ze 44
Algoritmizace a programování PŘÍKLAD
Výpočet kořenů (reálných i komplexních) kvadratické rovnice ax2 + bx + c = 0, Vstupní data: Výstupní data:
Ak. rok 2012/2013
kde a ≠ 0
a, b, c x1, x2 © vbP
32. ze 44
Algoritmizace a programování PŘÍKLAD
Analýza úlohy
Zápis algoritmu (VD)
Zdrojový kód v jazyce C++
Odladění programu (testování)
Ak. rok 2012/2013
© vbP
33. ze 44
Algoritmizace a programování Datové struktury
(Konstanta)
Proměnná
•
pojmenované místo v paměti počítače • vytvoření na základě deklarace identifikátor (symbolická adresa) typ (datový typ)
Ak. rok 2012/2013
© vbP
34. ze 44
Algoritmizace a programování Datové struktury
Proměnná - druhy proměnných
•
Globální proměnné • vytvoří se při spuštění programu • existuje po celou dobu běhu programu
Ak. rok 2012/2013
© vbP
35. ze 44
Algoritmizace a programování Datové struktury
Proměnná - druhy proměnných
•
Lokální proměnné • deklarované v procedurách, resp. funkcích • vznikají voláním podprogramu • zanikají při ukončení podprogramu • při rekurzivním volání se vytvoří zvláštní instance lokálních proměnných pro každou aktivaci
Ak. rok 2012/2013
© vbP
36. ze 44
Algoritmizace a programování Datové struktury
Proměnná - druhy proměnných
•
Dynamické proměnné • vznikají a zanikají za běhu programu dle potřeby na základě příkazů • prostor pro ně čerpá program z volné paměti • existence dynamických proměnných není vázána na začátek, resp. konec žádného podprogramu
Ak. rok 2012/2013
© vbP
37. ze 44
Algoritmizace a programování Datové struktury
• •
Ak. rok 2012/2013
Pole posloupnost proměnných stejného typu (homogenní skupina) v deklaraci pole určujeme • identifikátor pole jako celku • typ pole (jeho složek (prvků)) • počet složek (prvků) pole • jednotlivé prvky určujeme pomocí indexů © vbP
38. ze 44
Algoritmizace a programování Datové struktury
Pole
• • • •
jednorozměrná pole (vektory) dvourozměrná pole (matice) třírozměrná pole (kubické matice) …
Ak. rok 2012/2013
© vbP
1 index 2 indexy 3 indexy více indexů
39. ze 44
Algoritmizace a programování Datové struktury
Záznam (struktura)
•
nehomogenní skupina proměnných (složek) chápaných jako celek složky záznamu jsou v paměti uloženy za sebou (zpravidla v pořadí jako v deklaraci) práce se složkou záznamu pomocí kvalifikace, tj. jméno záznamu a jméno složky společně
• •
(jméno složky je relativní adresou vzhledem k počátku proměnné typu záznam) Ak. rok 2012/2013
© vbP
40. ze 44
Algoritmizace a programování Datové struktury
Objekt
•
v definici objektového typu specifikujeme atributy (datové složky) a metody (funkční a procedurální složky)
•
proměnná objektového typu je instance
Ak. rok 2012/2013
© vbP
41. ze 44
Algoritmizace a programování Datové struktury
Seznam (list) • • •
• • • Ak. rok 2012/2013
datová struktura – posloupnost složek složky uspořádány podle klíče (hodnota dat nebo hodnota funkce vypočítaná na základě těchto dat) složky nemusí ležet v paměti za sebou (ukazuje na ně ukazatel (pointer), resp. spojka (link)) seznam má hlavu (head) a ohon (tail) seznam je dynamická struktura může být jednosměrný, resp. obousměrný © vbP
42. ze 44
Algoritmizace a programování Datové struktury
Ak. rok 2012/2013
Strom B-strom (b-tree) Zásobník (stack) Fronta Tabulka Graf Množina
LIFO (Last In, First Out)
© vbP
43. ze 44
Děkuji za pozornost
Ak. rok 2012/2013
© vbP
44. ze 44