Kolegové a kolegyně, obecné informace o přednášce Programování 2 (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:

20. ú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
• Všechny algoritmy byly včetně analýzy složitosti.
• Pozor, některé třídící algoritmy byly už v zimě!
• Slidy

• Dolní odhad třídění porovnáním,
• Bucketsort,
• třídění na vnějších pamětech.
• 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.
• Slidy.

• 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.)
• 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í,
• Slidy.

• Dynamické programování,
• grafove algoritmy,
• Slidy.

17. dubna slidy

24. dubna slidy

1. a 8. kvetna prednasky odpadly.

15. kvetna slidy

22. kvetna zastupoval kolega Kryl.