Rozšiřující seminář Algoritmy a datové struktury 1

Sylabus

Stromové datové struktury s vyhledáváním: binární vyhledávací stromy (BVS), vyvažované BVS (AVL-stromy a červeno-černé stromy), B-stromy Haldy: Standardní halda, binomiální (slučovatelná) halda, Fibonacciova halda. Standardní algoritmy pro třídění: bubblesort, mergesort, quicksort, heapsort. Algoritmy související s tříděním: vyhledávání mediánu (a k-tého prvku); obvody pro třídění a přepínání: bitonický obvod. Základní grafové algoritmy: vyhledávání v grafu a stromu (do hlouby, do šířky), nejkratší a extremální cesty (CPM, Dijkstra, Bellman-Ford), minimální kostry grafu (obecné schéma, implementace Jarník-Prim a Kruskal) Rozpis na jednotlivé lekce:

1. Binární vyhledávací stromy.

2. AVL-stromy.

3. Červeno-černé stromy.

4. B-stromy.

5. Standardní halda a heapsort, binomická halda.

6. Fibonacciova halda.

7. Bubblesort, mergesort, quicksort, vyhledávání mediánu a k-tého prvku.

8. Bitonické třídění.

9. Vyhledávání v grafu.

10. Nejkratší a extremální cesty - CPM, Dijkstra.

11. Nejkratší a extremální cesty - Bellman-Ford.

12. Minimální kostry grafu (obecné schéma, implementace Jarník-Prim a Kruskal).

13. Spektrální heuristika pro min-cut.

Anotace

Předmět navazuje na NTIN060 Algoritmy a datové struktury I, algoritmy vyučované v rámci ADS I ukazuje pod jiným úhlem pohledu a přináší některé další a pokročilejší metody. Algoritmy jsou presentovány pomoci vizualizací, které jsou vytvářeny tak, aby názorně osvětlily základní myšlenky, na kterých jsou algoritmy založeny.

Cílem předmětu je ukázat studentům algoritmy jako tvůrčí oblast informatiky a naučit je o chování a vlastnostech algoritmů přemýšlet exaktním způsobem.