| Kontakt: | jan [AT] ucw [DOT] cz
|
| Kancelář: | T-108a
|
Základní informace
Pá 11:30 - 14:30 prezenčně: T-112 / online: Zoom (heslo: [prezenční místnost])
Studijní materiály
Obsah přednášek
- 2.10.2020 - Rozděl & Panuj #1 [MV 10.2, 10.3] ; Xournal LOG
- 9.10.2020 - Rozděl & Panuj #2 [MV 10.4, 10.5, 10.8] ; Xournal LOG
- 16.10.2020 - Grafové algoritmy: DFS, reprezentace grafů, hledání mostů [MV 5.3, 5.6, 5.7] ; Xournal LOG
- 23.10.2020 - Grafové algoritmy: BFS, Dijkstra [MV 5.2, 6.1, 6.2] ; Xournal LOG
- 30.10.2020 - Grafové algoritmy: MST (Jarnik-Prim) a datové struktury (halda) [MV 7.2, 3.2] ; Xournal LOG
- 6.11.2020 - Grafové algoritmy: MST (Kruskal) a datové struktury (Union-Find) [MV 7.4] ; Xournal LOG
- 13.11.2020 - Výpočetní modely: Random Access Machine, (deterministický) Turingův stroj [MV 2.5] [AB 1.2, 1.3] ; Xournal LOG
- 20.11.2020 - Samostudium – Turingovy stroje: [AB] Claims 1.8, 1.9, 1.11 + Theorems 1.13, 1.17
- 27.11.2020 - Nedeterministický Turingův stroj, třídy P a NP, NP-úplnost [AB 2.1, 2.2] ; Xournal LOG
- 4.12.2020 - SATisfiability a NP-úplné problémy [AB 2.3, 2.4] ; Xournal LOG
- 11.12.2020 - EXP, NEXP, coNP, PSPACE a LOGSPACE a vzajemné vztahy, Savičova věta [AB 2.6, 4.1, 4.2] ; Xournal LOG
- 18.12.2020 - Samostudium – [AB] Theorems 3.1, 3.2, 3.3, 3.4
- 8.1.2021 - Translační lemma, Polynomiální hierarchie
Domácí úlohy
- Rozděl & Panuj: [MV str. 247, cv. 3] ; [MV str. 248, cv. 1] ; [MV str. 257, cv. 4]
- DFS, BFS, Dijkstra: [MV str. 116, cv. 1] ; [MV str. 127, cv. 2] ; [MV str. 145, cv. 2]
- MST, haldy: [MV str. 91, cv. 6] ; [MV str. 165, cv. 3] ; [MV str. 174, cv. 2]
- Turingovy stroje, NP: [AB p1.23, cv. 8] ; [AB p2.23, cv. 1] ; [AB p2.25, cv. 15]
- Polynomialní hiearchie: [AB p2.26, cv. 21] ; [AB p5.10, cv. 1] ; [AB p5.10, cv. 8]