Kolegové a kolegyně, obecné informace o přednášce Programování II (vztahující se k oběma skupinám) najdete na stránce kolegy Kryla. Jelikož informace platí pro obě skupiny, bylo by kontraproduktivní zveřejňovat je dvakrát.

Staré informace k zimnímu semestru.

Na přednáškách bylo probráno:

22. února:

• Organizační záležitosti (informace o zkoušce),
• algoritmy třídění:
  • Heapsort (třídění haldou),
  • Mergesort (třídění sléváním).
• Problém třídění porovnáním a důkaz dolního odhadu složitosti tohoto problému.
• Bucketsort (znám též jako Radixsort).
• Poznámka o vnitřním a vnějším třídění, na příslušné algoritmy ovšem už nezbyl čas.
• Všechny algoritmy byly včetně analýzy složitosti.
• Pozor, některé třídící algoritmy byly už v zimě!
• Slidy

• Třídění na vnějších pamětech (dokončení z minula).
• Organizace paměti počítače, pojem pointeru.
• Definice proměnné typu pointer (ukazatel), operátor stříšky a demonstrace jeho použití.
• Funkce new a dispose, pojem garbage a memory-leaku, povídání o garbage-collectoru a konstatování, že v Pascalu není.
• Struktury (records) a pointery na ně.
• Spojové seznamy - definice, základní typologie (spojové seznamy jednosměrné, obousměrné, cyklické, se zarážkami, tedy hlavou a ocasem).
• Demonstrace využití spojového seznamu k výpisu předem neznámého počtu čísel zadaných na vstupu. (Poznámka: Tento spojový seznam implementuje zásobník.)
• Slidy.

• Zopakování typologie spojových seznamů,
• fronta a zásobník (demonstrace implementace),
• prohození prvků ve spojovém seznamu,
• uspořádaný spojový seznam,
• implementace,
• jak reprezentovat (zakořeněné) stromy v Pascalu,
• binární vyhledávací strom,
• slidy.

• Binární vyhledávací strom,
• pojem vyváženosti, vyvážený binární vyhledávací strom,
• AVL-stromy,
• červeno-černé stromy (zmínka),
• A-B-stromy,
• A-sort.
• Slidy.

• Příklady využití spojových seznamů (reprezentace řídkých polynomů a matic),
• funkce memory-managementu na nízké úrovni,
• hashování,
• slidy.

• Dynamické programování,
• diskrétní simulace.
• Slidy.

12. dubna:

• Variant record (alias záznam s variantami),
• objektové programování (třídy a objekty, atributy, metody, modifikátory public, private a protected, konstruktory, destruktory a dědičnost).
• slidy.

• Objektové programování:
• Objekt self, operátor @,
• virtuální metody,
• čistě virtuální funkce (někdy abstraktní funkce), abstraktní třídy
• slidy.

• Soutěž Středník II bude 7. května!
• Odstranění rekurze,
• binární soubory,
• programování her (kombinatorická hra, hra s nulovým součtem, příklady her, strom hry, AND-OR-strom. Bude dokončeno příště.
• Slidy.

• Programování her (dokončení včetně masivního opakování z minula):
• strom hry, graf hry, hry s nulovým součtem, algoritmus MINIMAX, algoritmus NEGAMAX, alfa-beta prořezávání, heuristiky...
• Slidy.
• Příklad hry -- nimm na třech hromádkách v Javě pro mobilní telefony.

• Grafové algoritmy: Hledání nejkratší cesty (Dijkstrův, Bellman-Fordův a Floyd-Warshallův algoritmus), minimální kostry (Kruskalův, Borůvkův a Jarníkův algoritmus), podívání o maximální kostře a nejdelší cestě, topologické uspořádání, faktorová množina.
• Slidy.

• Předání funkce v parametru,
• opakování (mediánu lineárně a vnějšího třídění).
• Slidy.