Požadavky ke zkoušce z předmětu PRM045
Programování II

Zkouška má písemnou a ústní část.

• V první části studenti řeší během jedné hodiny jednodnoduchou úlohu na práci s ukazateli a spojovými datovými strukturami.
  Úlohy nejsou algoritmicky náročné. Požadují se globální deklarace typů a podprogramy realizující požadované akce nad daty těchto typů. I když to není hlavní aspekt hodnocení, měl by tento příklad být i syntakticky správný. Několik ukázkových zadání.
• V druhé části studenti řeší rozsáhlejší úlohu, která je nějakým způsobem náročná.
  Součástí jejího řešení je 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 a naprogramování nejpodstatnějších částí. Míra v jaké se požaduje blízkost ke kódu v Pascalu bude u každého zadání upřesněna.
  Na vypracování druhé části mají studenti 2 1/2 hodiny

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

Programovací jazyk Pascal - tato část je definitivní
(implementace Turbo Pascal verze 7 - nejde přitom o detaily, ale o principy)

• datové typy a reprezentace jejich hodnot v paměti
  rozdíl mezi typem integer a real, pole, záznam, záznam s variantami (dnes je lepší používat ke stejným účelům dědění v objektovém programování), znakový řetězec, množina, výčtový typ, inicializované proměnné (strukturované konstanty)
• předávání parametrů podprogramům
  předávání parametrů hodnotou a odkazem (princip, rozdíly, použití), procedurální parametry
• 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 - reset, rewrite, append, formátování textového výstupu
• 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 (New – Dispose)
• objektové programování, základní principy a realizace v Borland Pascalu
  zapouzdření, dědičnost; statické a virtuální metody; implementace virtuálních metod - existence VMT tabulky, konstruktor, 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
• 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
• metoda “rozděl a panuj”
• dynamické programování
  princip metody, příklady použití (např. hledání optimálního uzávorkování součinu n matic, maximální společný podřetězec, optimální binární vyhledávací strom, optimální rozložení písmen na klávesy mobilu)
• vnitřní třídění
  konkrétní třídicí algoritmy a odhady jejich složitosti (časové a paměťové) - třídění přímým výběrem, přímé zatřiďování, bublinkové třídění, quicksort, třídění sléváním, 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
  modifikace quicksortu, pomocí haldy, 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í, idea polyfázového třídění, způsoby zvyšování efektivity, zvětšování běhů předtříděním v haldě
• stromy
  binární stromy, obecné stromy a jejich různé reprezentace,kanonická reprezentace obecného stromu (lesa) pomocí binárního stromu, binární vyhledávací stromy a operace s nimi, průchody binárním stromem a jejich souvislost s algebraickými notacemi, postavení dokonale vyváženého stromu.
• vyvážené stromy
  AVL-stromy - definice, datová implementace, nejhorší případ, rotace, algoritmy vkládání a vypouštění, jejich složitost a typická implementace; B-stromu a operace na nich
• hašování
  hašovací tabulka, haš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
• 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), nejkratší cesty (průchod do šířky, Dijkstrův algoritmus včetně jeho modifikací, Floyd-Warshallův algoritmus), minimální kostra grafu (hladový algoritmus, faktorové množiny), ověření acykličnosti grafu a topologické třídění
• programování her
  Pozice, tah, graf hry, vyhrané a prohrané pozice a jejich zjišťování v konkrétních jednoduchých hrách;
  Strom hry, Shanonnova věta o existenci neprohrávající strategie pro jednoho z hráčů, algoritmus minimaxu, jeho negamaxová implementace, minimax jako heuristika - horizont, statická ohodnocovací funkce, tiché pozice; alfa-beta metoda jako efektivní způsob nalezení přesné minimaxové hodnotay; alfa-beta jako heuristika, metoda okénka, kaskádní varinata.