Obsah kurzu

Kurz se zabývá technikami návrhu algoritmů. Jsou probrány základní techniky, jejichž princip je vysvětlen na příkladech známých algoritmů.

Seznam proběhlých přednášek
  1. Problémy, algoritmy, složitost: přehledová přednáška na úvod
  2. Rozděl a panuj. Rekurence.
  3. Násobení polynomů a rychlá fourierova transformace.
  4. Dynamické programování. Algoritmy pro úlohu batohu a problém nalezení nejkratších cest v grafu.
  5. Algoritmus pro úlohu obchodního cestujícího. Algoritmus pro editační vzdálenost řetězců.
  6. Greedy Algoritmy. Kruskalův algoritmus pro nalezení minimální kostry. Greedy algoritmus pro úlohu batohu
  7. Algoritmus pro problém nalezení Hufmannova kódu.
  8. Backtracking. Algoritmus pro generování základních kombinatorických struktur. Naivní algoritmus pro SAT problém
  9. Branch and bound. Algoritmus pro Set Cover problém. Algoritmus pro úlohu batohu
  10. Metoda iterativního zlepšování. Gradientní metoda. Problém uváznutí v lokálním minimu a metody jeho řešení. Demonstrace na problémech Vertex Cover a Max Cut
  11. Prioritní fronta implementovaná binomickou haldou
Seznam proběhlých cvičení
  1. Asymptotická notace, efektivní výpočet mocniny
  2. Řešení rekurencí, algoritmus pro nalezení mediánu v lineárním čase
  3. Problém nalezení počtu inverzí, problém nalezení vrcholu unimodální posloupnosti, rychlé násobení polynomů
  4. Problém nalezení nezávislé podmnožiny s nejvyšší cenou v lineárním grafu, Problém obrany Ráje před roboty
  5. Zamyšlení nad optimalitou algoritmů pro problém nalezení minimální kostry: řezová a cyklová vlastnost.
  6. Problém rychlého určení, zda-li hrana leží na minimální kostře. Problém plánovaní úloh ve vyhledávači El Goog.
  7. Algoritmus pro k-SAT problém.

Udělování zápočtu a zkouška

Písemka 29. 11. 2018 (opravná bude v zápočtovém týdnu). Potřeba je získat aspoň 6 bodů z maxima 10 bodů. Šlo získat bonusový bodík na cvičení. Studenti, kteří získají aspoň 3 body z písemek, budou mít šanci věc zachránit splněním obtížnějšího programovacího úkolu.

Tabulka s body po opravné zápočtové písemce [.pdf] Další aktualizace proběhne v týdnu po 6. lednu.

Zadání záchranného zápočtového úkolu [.zip].

Zkoušení bude ústní formou. Požadavky na zkoušku jsou dány obsahem přednášek, cvičení a materiálů dodaných ke kurzu. Je pořadována znalost základních pojmů, algoritmů a jejich analýzy, principu odvození algoritmů a (v některých případech) důkazů.

Materiály ke kurzu

Poznámky z přednášek: [pdf]. Kapitola k SAT [pdf]. Pokud v materiálu najdete chybu, dejte mi prosím vědět. Poznámky k binomial heaps [pdf]