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

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

V písemné čá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í.
Na vypracování písemné práce mají studenti 3 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
(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, 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
• 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 - 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, způsoby alokace a uvolňování dynamicky alokovaných proměnných (New – Dipose, GetMem – FreeMem, Mark - Release)
• objektové programování, základní principy a realizace v Turbo 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
• Delphi (základy jazyka)
  programování řízené událostmi, objektový model, atributy (data, metody, vlastnosti), chránění atributů, třídové metody, výjimky

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
• dynamické programování, metoda “rozděl a panuj”
  princip metod, příklady použití
• vnitřní třídění
  konkrétní třídicí algoritmy a horní odhad jejich složitosti - 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í, polyfázové 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, 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.
• prakticky užívané definice vyvážených stromů
  AVL-stromy - definice, datová implementace, nejhorší případ, rotace, algoritmy vkládání a vypouštění, jejich složitost a typická implementace;
  B stromy - definice, datová implementace, algoritmy vyhledávání, vkládání a vypouštění, jejich složitost a typická implementace.
• 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.
  Strom hry, Shanonnova věta o existenci neprohrávající strategie pro jednoho z hráčů, algoritmus minima, jeho negamaxová implementace, horizont, statická ohodnocovácí funkce, alfa-beta-prořezávání jako metoda rychlejšího zjištění přesné minimaxové hodnoty, její použití jako heuristiky (metoda okénka, kaskádní varianta).
• diskrétní simulace
  Princip – události, procesy, simulační kalendář; modelování jednoduchých úloh