11Y1TG / Obsah seminářů v LS 2021/22

Program seminářů je předběžný a bude postupně upravován, především podle výběru semestrálnách prací a data jejich prezentací.

Týden v semestru	Datum	Téma
1.	15.2.2022	Úvod - organizační záležitosti, opakování základních pojmů z algoritmizace. Úlohy teorie grafů, instance, zadání. Rozhodovací a optimalizační úlohy. text prezentace Co je algoritmus [PDF].
2.	22.2.2022	Prohledávání grafu, hledání do šířky, do hloubky, průchod bludištěm. text prezentace Prohledávání grafů [PDF].
3.	1.3.2022	Rovinné grafy. Eulerova věta. Kuratowského věta. text prezentace Rovinné grafy [PDF].
4.	8.3.2022	Barevnost grafu, nezávislost grafu.
5.	15.3.2022	Algoritmus pro barvení grafu. text prezentace Jak určit barevnost grafu [PDF].
6.	22.3.2022	Ještě jednou k algoritmu pro obarvení grafu.
7.	29.3.2022	Párování v obecném grafu.
8.	5.4.2022	Časová náročnost algoritmu, polynomiální úlohy. Přístup k řešení NP-těžkých úloh.
9.	12.4.2022	Párování v bipartitním grafu. Přiřazovací problém. Vzdálenost v grafu, excentricita. Diametr, rádius, centrum, periférie grafu. Dominance, minimální dominující množina. text prezentace Maximální párování v bipartitním grafu [PDF]. text prezentace Vzdálenost a dominance v grafu [PDF].
10.	19.4.2022	Prezentace semestrálních prací: Hamiltonovská kružnice a související problematika. Algoritmus minimax
11.	26.4.2022	Markovské řetězce.
12.	3.5.2022
13.	10.5.2022	Lokační úlohy. Atrakční obvod. Varianty lokačních úloh a přístupy k jejich řešení.
14.	17.5.2022	Prezentace semestrálních prací.