Teorie složitosti 01TSLO (ZS 2022/2023)
| Kontakt: | jan [AT] ucw [DOT] cz
|
| Kancelář: | T-108a
|
Základní informace
Studijní materiály
Obsah přednášek
- W1: 23.9. - Úvodní přednáška
- W2: 30.9. - samostudium / připomenutí: třídící algoritmy [MV 3], haldy [MV 4.2], AVL-stromy a (a,b)-stromy [MV 8.1, MV 8.2, MV 8.3]
- W3: 7.10. - Rozděl & panuj - rekurze: mergesort, Karacubův algoritmus, Strassenův algoritmus, Master theorem
- W4: 14.10. - Algoritmus LinearSelect pro nalezení k-tého nejmenšího prvku, úvod do grafových algoritmů - BFS a DFS
- W5: 21.10. - DFS na hledání mostů a artikulací v neorientovaném grafu, Topologické uspořádání DAGu
- W6: 28.10. - státní svátek
- W7: 4.11. - haldové operace a k-regulární haldy
- W8: 11.11. - Dijkstra a Jarník-Prim, datová struktura pro Union/Find
- W9: 18.11. - děkanské volno
- W10: 25.11. - Výpočetní modely: Random Access Machine, (deterministický) Turingův stroj
- W11: 2.12. - Univerzální Turingův stroj, Nedeterministický Turingův stroj, třídy P a NP
- W12: 9.12. - Varianty SATu a NP-úplnost nezávislé množiny a hypergrafového párování
- W13: 16.12. - třídy EXP, NEXP, coNP, PSPACE a LOGSPACE a vzajemné vztahy, Savičova věta
- W14: 6.1. - diagonalizační argumenty, Halting problem, zmínka o datové struktuře pro LCA, zmínka o dvoj-DFS algoritmu pro silně souvislé komponenty
Domácí úlohy