Předmět poskytuje základní přehled o pojmech a úlohách teorie grafů, zaměřuje se především na algoritmické otázky a řešení grafových problémů, přičemž významně využívá znalostí z programovacích technik. Přehledově jsou zahrnuty další tři tematické okruhy: teorie formálních jazyků (konečné automaty, gramatiky, regulární a bezkontextové jazyky), výpočetní složitost (třídy složitosti P a NP, NP-úplnost) a vyčíslitelnost (nerozhodnutelné problémy).
Další termímy zkoušek: pátek 7.6. v 10:00 a pondělí 10.6. v 10:00. Začátek u mě v pracovně v G105.
Výsledky písemné zkoušky ze dne 31.5. jsou v upload systému.
Termín písemné zkoušky je stanoven na pátek 31.5. od 9:30 do 11:45 v E-128 (časový limit je tedy 2 hodiny a čtvrt).
Přednášející: Daniel Průša
Přednášky jsou 2 hodiny týdně, zde je rozvrh.
Plán přednášek:
| Týden | Datum | Přednáší | Obsah přednášky |
|---|---|---|---|
| 1 | 15.02. | Průša | Úvod, stručný přehled témat předmětu [pdf]. Neorientované a orientované grafy - základní pojmy [pdf]. Reprezentace grafu v paměti. |
| 2 | 22.02. | Průša | Průchod grafem do šířky a do hloubky. Aplikace. [pdf] |
| 3 | 01.03. | Průša | Hledání nejkratší cesty a minimální kostry v ohodnoceném grafu. [pdf] |
| 4 | 08.03. | Průša | Toky v sítích. [pdf] |
| 5 | 15.03. | Průša | Úvod do teorie formálních jazyků. Konečné automaty. [pdf] |
| 6 | 22.03. | Zimmermann | Principy algoritmů na hraní tahových her. [pdf] |
| 7 | 29.03. | — | Děkanský den. |
| 8 | 05.04. | Průša | Redukce automatu, nedeterminismus, regulární výrazy. [pdf] |
| 9 | 12.04. | Průša | Bezkontextové gramatiky. [pdf] |
| 10 | 19.04. | Průša | Zásobníkové automaty. [pdf] |
| 11 | 26.04. | Průša | Výpočetní modely (Turingův stroj, RAM). [pdf] |
| 12 | 03.05. | Průša | Nerozhodnutelné problémy. [pdf] |
| 13 | 10.05. | — | Samostatná práce na semestrální úloze. |
| 14 | 17.05. | Průša | Třídy P a NP, NP-úplné problémy. [pdf] |
Podrobnosti jsou na stránkách cvičení.
Bonusové úlohy jsou zadávány na přednášce. Jejich odevzdání není povinné, získané body se ale započítávají pro určení výsledné známky.
Vypracované řešení odevzdávejte ve formě pdf (nebo .zip v případě, že součástí jsou i zdrojové kódy) do upload systému, paralelka “1 - Patek 09:15 - 10:45”. Neopisujte, v případě zjištění plagiátů přijdou dotyčné osoby o všechny body za bonusové úlohy.
| Číslo | Zadáno | Termín odevzdání | Popis | Body |
|---|---|---|---|---|
| 1 | 22.02. | 08.03. (23:59 hod.) | Plánování vycházkové trasy centrem města: [zadání], [data1], [data2]. | 3 |
| 2 | 08.03. | 22.03. (23:59 hod.) | Trasa centrem města ještě optimálněji. Tok v rozšiřující se síti. [zadání] | 3 |
| 3 | 05.04. | 19.04. (23:59 hod.) | Konečné automaty a regulární výrazy. [zadání] | 3 |
| 4 | 19.04. | 03.05. (23:59 hod.) | Konstrukce bezkontextové gramatiky a zásobníkového automatu. [zadání] | 3 |
| 5 | 03.04. | 17.05. (23:59 hod.) | Počítání na Turingově stroji. [zadání] | 3 |
Doporučenou literaturou k předmětu jsou skripta doc. Koláře. Obsahují téměř vše, co bude na přednáškách probíráno (výjimkou jsou bezkontextové jazyky - ty jsou popsány v učebním textu, který uvádíme v dalším odstavci).
Jako alternativa mohou být použity následující dva zdroje. Oba jsou dostupné on-line.
Součet bodů určuje známku podle následující tabulky:
| body | >=90 | 89-80 | 79-70 | 69-60 | 59-50 | 49-0 |
|---|---|---|---|---|---|---|
| známka | A | B | C | D | E | F |
Písemka, ukázkové příklady: [pdf]
Pokud máte dotazy k probírané látce, můžete (mimo jiné) využít diskusní fórum, které pravidelně čte přednášející i cvičící. Zároveň mohou být nápomocni i ostatní studenti.