Kolegové a kolegyně, obecné informace o přednášce Programování 2 jakož i informace týkající se první poloviny semestru najdete na stránkách kolegy Töpfera.

Já jsem začal přednášet od sedmého týdne a od té doby jsme probrali toto:

• 31. března: Dynamické programování. Předvedli jsme si myšlenkové schéma jak se od algoritmu využívajícího rekurzi dostat k algoritmu vyplňujícímu tabulku. Předvedli jsme si příklady v podobě algoritmů počítajících Fibonacciho čísla, počet platných uzávorkování pomocí n párů závorek, počet rozkladů na součty posloupností kladných neklesajích čísel a výpočet kombinačního čísla. Promítány byly tyto slidy.
• 7. dubna: Dynamické programování (nejdelší rostoucí podposloupnost, závorkování matic (pro účely násobení), celočíselný problém batohu), předání funkce v parametru. Slidy.
• 14. dubna: Grafové algoritmy I: Reprezentace grafu, základní algoritmy využívající prohledání do hloubky a šířky (souvislost, acykličnost, strom, vyšetření komponent), Dijkstrův algoritmus. Slidy.
• 21. dubna: Grafové algoritmy II: Nejkratší cesta (Dijkstrův algoritmus dokončen, Bellman-Fordův algoritmus, Floyd-Warshallův algoritmus hledání nejkratších cest mezi všemi páry vrcholů), minimální kostra (Kruskalův algoritmus - zapletl jsem se v důkazu, měl jsem vzít první místo, kde se ty dvě kostry liší a ukázat, že alternativní kostru změnit v Kruskalovskou bez váhy cílové kostry), modifikace problémů a vliv těchto modifikací na řešitelnost (maximální kostra, nejdelší cesta či nejkratší cesta v obecně ohodnoceném grafu, anebo dokonce jen v grafu, kde všechny hrany mají délku -1). Slidy.
• 28. dubna: Dokončení důkazu korektnosti Kruskalova algoritmu. Objektové programování I:
  • Pojem třídy a objektu,
  • pojem atributů a metod,
  • syntaktické prostředky jazyka Pascal pro definici a využití tříd a objektů,
  • ochrana prvků třídy a objektu (klíčová slova public, private, protected),
  • pointery na objekty,
  • konstruktory, destruktory, rozšířená syntax funkce new,
  • myšlenka dědičnosti v objektovém programování, definice synovských tříd (smysl a význam).
  Během přednášky jsem vytvořil tento zdrojový text s příklady a promítal takovéhle slidy.
• 5. května (pražského povstání): Dokončení objektového programování: virtuální metody a rozdíl oproti metodám nevirtuálním, tabulka virtuálních metod (a poznámka, že je inicializována konstruktorem), pojem abstraktní třídy a čistě virtuální funkce (s komentářem, že tyto dvě položky nemají syntaktickou oporu v Pascalu). Začátek teorie her: Pojem kombinatorické hry, příklady kombinatorických a nekombinatorických her. Shannonova věta (i s důkazem). Slidy.
• 12. května: Hry (graf hry, strom hry, and-or-strom, hry s ohodnocením, minimax, negamax, statická ohodnocovací funkce, horizont, heuristiky (alfa-beta prořezávání, alfa-beta prořezávání jako heuristika). K alfa-beta prořezávání se ještě vrátíme příští přednášku. Implementace v pseudokódu, ilustrace fungování. Slidy.
• 19. května: Závěr kurzu. Vrátili jsme se k alfa-beta prořezávání a ukázali si vyhodnocení stromu hry Nimu se 6 prvky (kdy smíme odebrat 1, 2 nebo 3). Prošli jsme požadavky ke zkoušce, při čemž se ukázalo, že jsme omylem překočili hashování. Hashování bylo předneseno (řekli jsme si, co je hashovací funkce, kolize a několik způsobů jejich řešení a že hashování lze využít k organizaci dat tvořících velké univerzum ve výrazně menším poli). Nenapadlo mě poznamenat, že hashování bychom mohli použít například při vyhodnocování hry k organizaci již analyzovaných stavů hry (abychom nemuseli tentýž stav zbytečně analyzovat vícekrát). Závěrečné poznámky (konkrétně o tom, že pro případné zájemce o druhácké informatické předměty je určeno Objektově orientované programování vyučované v zimním semestru).