NMIN102 Programování 2

 

školní rok 2017/2018

 

21. 2. 2018

Halda, operace na haldě, lineární sestrojení haldy, heapsort.

Programy: operace s haldou.

Dolní odhad složitosti problému třídění.

Přihrádkové třídění, víceprůchodové.

Program: přihrádkové třídění

PREZENTACE

 

28. 2. 2018

Rekurzivní třídění – quicksort (možnost odstranění rekurze), mergesort.

Programy: quicksort (dva způsoby realizace), mergesort.

Nalezení K-tého nejmenšího prvku – modifikace heapsortu, quickselect, lineární algoritmus.

Program: K-tý nejmenší

Vnější třídění, způsoby zvyšování efektivity.

Prodloužení předtříděných úseků pomocí haldy.

Programy: slévání setříděných souborů (dvě verze), vnější třídění.

PREZENTACE

 

7. 3. 2018

Binární (datové) soubory – vlastnosti, operace, použití.

Hospodaření s pamětí – alokace statická, na zásobníku a na haldě.

Dynamicky alokované proměnné, typ ukazatel, nil.

Alokační procedury new, dispose, mark, release.

PREZENTACE

 

14. 3. 2018

Dynamické datové struktury, příklady použití.

Lineární spojové seznamy – reprezentace.

Operace s lineárními spojovými seznamy – průchod, vyhledávání hodnot, vytvoření seznamu, přidání prvku, odebrání prvku, zrušení prvku, zrušení seznamu, obrácení pořadí prvků.

Svépomocné dispose.

PREZENTACE

 

21. 3. 2018

Druhy spojových seznamů – obousměrné, cyklické, s hlavou.

Příklady použití lineárních spojových seznamů – zásobník a fronta, dlouhá čísla, polynomy.

Dynamické pole, GetMem/FreeMem.

Binární stromy – reprezentace, průchod do hloubky a do šířky, příklady použití.

Dynamická reprezentace obecného stromu a grafu, průchod.

Písmenkový strom (trie).

Další dynamické datové struktury.

PREZENTACE

 

28. 3. 2018

Počítačová simulace, princip, spojitá a diskrétní simulace.

Simulační model, procesy a jejich stavy, události, simulační kalendář.

Příklady úloh na počítačovou simulaci a možné způsoby jejich řešení.

Programová realizace simulačního modelu.

Příklad: auta s pískem.

PREZENTACE

 

4. 4. 2018

Dynamické programování – princip, příklady: trojúhelník čísel, počet cest městem, nejdelší vybraná rostoucí podposloupnost, nejdelší společná vybraná podposloupnost, maximální vybraný palindrom.

PREZENTACE

 

11. 4. 2018

Dynamické programování – další příklady: součin řady matic, minimální triangulace, problém batohu.

Floydův-Warshallův algoritmus.

Programy: optimalizace součinu matic (backtracking resp. dynamické programování), triangulace mnohoúhelníka (jen hodnota resp. výpis vybraných diagonál), problém batohu.

PREZENTACE

 

18. 4. 2018

Reprezentace grafu v programu.

Programová realizace základních grafových algoritmů

- souvislost a komponenty souvislosti (prohledávání grafu nebo faktorové množiny)

- existence cyklu v neorientovaném grafu

- kostra a minimální kostra (Kruskalův algoritmus, v náznaku Jarníkův a Borůvkův)

- bipartitnost grafu (prohledávání s označováním vrcholů dvěma barvami)

Programy: komponenty souvislosti grafu,minimální kostra, test bipartitnosti.

PREZENTACE

 

25. 4. 2018

Informace o zkouškách – termíny, přihlašování, průběh zkoušky, požadavky.

Programová realizace základních grafových algoritmů

- existence cyklu v orientovaném grafu a topologické upořádání (topologické třídění)

- nejkratší cesta v neohodnoceném grafu (prohledávání do šířky a zpětný chod).

- nejkratší cesta v ohodnoceném grafu (Dijkstrův algoritmus a jeho modifikace, více kritérií).

Programy: topologické třídění, nejkratší cesta v neohodnoceném grafu, Dijkstrův algoritmus.

PREZENTACE

 

2. 5. 2018

Reprezentace aritmetického výrazu binárním stromem, vyhodnocení.

Notace aritmetického výrazu – prefix, infix, postfix.

Vyhodnocení výrazu zapsaného v postfixu a prefixu.

Algoritmus přímého převodu infixu na postfix.

Konstrukce binárního stromu ze zápisu výrazu.

Programy: vyhodnocení výrazu zapsaného v postfixu (2 verze), převod z infixu do postfixu (2 verze).

Binární vyhledávací strom – princip, operace.

Vyvážené stromy – dokonale vyvážené stromy, AVL-stromy.

Konstrukce dokonale vyváženého binárního vyhledávacího stromu.

Rotace v AVL-stromech, přidání a odebrání hodnoty.

PREZENTACE 

 

9. 5. 2018

Obecné vyhledávací stromy, B-stromy – definice, operace, použití.

Metody ukládání a vyhledávání dat – shrnutí.

Hešování, návrh hešovací funkce, řešení kolizí.

Vývoj programovacích jazyků a stylů.

Modulární programování, vyváření a použití vlastních jednotek.

Práce s moduly v IDE BP/FP.

PREZENTACE

 

16. 5. 2018

Rektorský den

 

23. 5. 2018

Objektové programování – principy, význam a použití, příklady.

Třídy a objekty, metody.

Zapouzdření, atributy přístupu.

Dědičnost, virtuální metody, VMT, konstruktor, destruktor.

Polymorfismus.

Abstraktní třídy a metody.

Objektový návrh programu, příklady.

PREZENTACE