NMIN102 Programování 2

 

Obsah přednášky

Přednáška přímo navazuje na předmět NMIN101 Programování 1 ze zimního semestru. Její náplní je doplnění dalších prostředků programovacího jazyka, algoritmů a programovacích technik podle níže uvedeného seznamu. Hlavními tématy jsou dynamicky alokované proměnné a dynamické datové struktury, lineární spojové seznamy a stromové struktury, pokročilejší metody ukládání a vyhledávání dat (hešování, vyhledávací stromy, haldy, datové soubory), grafy a grafové algoritmy, dynamické programování. Předmět je zakončen zápočtem a zkouškou.

 

Zápočet

Přesné podmínky pro získání zápočtu stanovuje a kontroluje cvičící, který také zápočty samostatně uděluje (domácí úkoly, práce na cvičeních, písemky apod.). Jednou z podmínek získání zápočtu je vždy odladění zápočtového programu včetně vypracování písemné dokumentace k tomuto programu.

 

Zkouška

Zkouška zahrnuje učivo z obou semestrů základního kursu programování, tzn. z předmětů NMIN101 a NMIN102. K účasti na zkoušce není nutné předchozí získání zápočtu. Zkouška má písemnou a ústní část.

 

písemné části studenti řeší dvě úlohy. V první úloze technického charakteru je úkolem napsat jednoduchý program, proceduru nebo funkci v Pascalu, posuzuje se i syntaktická správnost zápisu. Úlohy jsou zaměřeny na zvládnutí práce s dynamickými datovými strukturami. Druhá úloha je rozsáhlejší, součástí jejího řešení je i přesnější formulace problému na základě obecného slovního zadání. Studenti nemusí programovat detailně celou úlohu, požaduje se návrh efektivního algoritmu, vhodné rozdělení úlohy na menší části, návrh jejich vzájemné komunikace, volba hlavních datových struktur, zapsání nejpodstatnějších částí algoritmu ve formě programu nebo stačí i vhodného pseudokódu a hrubý odhad časových a paměťových nároků výsledného programu.

 

ústní části zkoušky se požadují znalosti programovacího jazyka a algoritmů podle níže uvedeného seznamu (v rozsahu přednášek NMIN101 a NMIN102). Součástí zkoušky je také rozbor úloh z písemné části zkoušky formou diskuse nad zvolenými řešeními. Předpokládá se schopnost zvážit přednosti a nedostatky různých alternativních způsobů řešení.

 

 

Programovací jazyk Pascal

(nejde o detaily, ale o princip)

 

datové typy a reprezentace jejich hodnot v paměti

rozdíl mezi typem integer a real, char, pole záznam, znakový řetězec, výčtový typ, společné vlastnosti ordinálních typů, inicializované proměnné (strukturované konstanty)

 

jednoduché a strukturované příkazy

hierarchická stavba příkazů, podmínky, cykly, skoky

 

podprogramy

procedury a funkce, předávání parametrů hodnotou a odkazem (princip, rozdíly, použití), procedurální parametry

 

rekurze

přímá a nepřímá rekurze, direktiva forward, výhody a nevýhody použití rekurze

 

práce se soubory

textové a datové soubory, sekvenční a přímý přístup k souboru (seek), assign, různé způsoby otevření souboru, formátování textového výstupu

 

modulární programování

unity, části interface a implementation, uses, překlad Make a Build, standardní unity

 

staticky a dynamicky alokované proměnné

obsazení paměti a paměťová omezení, typ ukazatel, konstanta nil, alokace a uvolňování dynamicky alokovaných proměnných

 

objektové programování

zapouzdření, dědičnost, statické a virtuální metody (VMT tabulka), konstruktor a destruktor, veřejné a soukromé atributy objektů, abstraktní metody a objekty

 

 

Algoritmy a programovací techniky

 

efektivita algoritmů

asymptotická složitost, nejlepší, průměrný a nejhorší případ, konkrétní odhady složitosti jednoduchých algoritmů, složitost problému

 

základní číselné algoritmy

Euklidův algoritmus, test prvočíselnosti, Eratosthenovo síto, Hornerovo schéma, rozklad čísla na cifry, práce v pozičních číselných soustavách, aritmetika s vyšší přesností („dlouhá čísla“), vyhledávání v poli (sekvenční, binární, zarážka)

 

rekurze

rekurzivní formulace algoritmů, efektivita rekurzivních programů a její zvyšování, odstranění rekurze použitím zásobníku

 

prohledávání do hloubky a do šířky

backtracking, algoritmus vlny, ořezávání, heuristiky

 

dynamické programování, metoda „rozděl a panuj“

princip metod, příklady použití

 

programování her

strom hry, algoritmus minimaxu, statická ohodnocovací funkce, alfa-beta prořezávání

 

vnitřní třídění

třídicí algoritmy a horní odhad jejich složitosti – přímý výběr, přímé zatřiďování, bublinkové třídění, quicksort, mergesort, heapsort, přihrádkové třídění; složitost problému třídění (v nejhorším a průměrném případě)

 

hledání k-tého nejmenšího prvku

pomocí haldy, quickselect, lineární algoritmus

 

vnější třídění

odlišnost od úlohy vnitřního třídění, přímé a přirozené slučování, polyfázové třídění, způsoby zvyšování efektivity, zvětšování běhů předtříděním v haldě

 

lineární spojové seznamy

různé typy seznamů – obousměrné, cyklické, s hlavou, základní operace se seznamy, implementace zásobníku a fronty, práce s dlouhými čísly a polynomy, svépomocné dispose

 

stromy

binární stromy, obecné stromy a jejich různé reprezentace, binární vyhledávací stromy a operace s nimi, průchody binárním stromem a jejich souvislost s notacemi aritmetického výrazu

 

vyvážené stromy

postavení dokonale vyváženého binárního vyhledávacího stromu, prakticky užívané definice vyvážených stromů (AVL-stromy, B-stromy) – definice, algoritmy a jejich složitost

 

hešování

hešovací tabulka, hešovací funkce, kolize a metody jejich řešení; srovnání různých metod ukládání a vyhledávání dat z hlediska efektivity

 

aritmetické výrazy

algoritmy na vyhodnocení výrazu zapsaného v různých notacích – infix, prefix, postfix, převody mezi různými algebraickými notacemi výrazu

 

grafy

základní grafové pojmy, způsoby reprezentace grafu v programu, programová realizace vybraných grafových algoritmů – komponenty souvislosti (průchod do šířky a do hloubky, faktorové množiny), nejkratší cesta (průchod do šířky, Dijkstrův algoritmus včetně jeho modifikací, Floyd-Warshallův algoritmus), minimální kostra (hladový algoritmus, faktorové množiny), test bipartitnosti, ověření acykličnosti orientovaného grafu a topologické uspořádání

 

Literatura

[1] Pavel Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2007

učebnice přímo určená pro tento základní kurz programování, pokrývá většinu učiva algoritmů v obou semestrech (nevykládá syntaxi programovacího jazyka, ale obsahuje programové ukázky v Pascalu)

[2] Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů, CZ. NIC, z.s.p.o. Praha 2017, http://pruvodce.ucw.cz/

učebnice algoritmů pokrývá učivo algoritmů v obou semestrech (a obsahuje i řadu algoritmů dalších)

[3] Böhm, Lánský, Veselý a kol.: Programátorské kuchařky, Matfyzpress Praha 2011, http://ksp.mff.cuni.cz/kucharky/programatorske-kucharky.pdf

            studijní texty Korespondenčního semináře z programování MFF UK – stručný popis základních algoritmů a datových struktur z učiva obou semestrů

[4] Niklaus Wirth: Algoritmy a štruktúry údajov, ALFA Bratislava 1988

slovenský překlad klasické učebnice programování

[5] Ivan Libicher, Pavel Töpfer: Od problému k algoritmu a programu, Grada Praha 1992

sbírka obtížnějších řešených úloh s důrazem na porovnání efektivity různých algoritmů

[6] Pavel Satrapa: Pascal pro zelenáče, Neokortex Praha 2000

dobrá učebnice jazyka Pascal a jeho použití při tvorbě programů, namísto ní lze použít i jinou učebnici Pascalu

 

 

Sylabus přednášky na děkanátním serveru