Teoretická informatika - A7B33TIN, LS 2010/2011

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).

• Celkem bude zadáno 8 příkladů, které budou pokrývat všechny tematické celky probírané na přednáškách (kromě tahových her, tuto látku si procvičíte při vypracování semestrální práce).
• Povolené jsou jakékoliv tištěné nebo psané materiály a kalkulačka (naopak mobily a notebooky jsou zakázané).
• Vzhledem k délce zkoušky je doporučené i občerstvení.
• Podmínkou úspěšného složení zkoušky je získání alespoň 25-ti bodů ze 60-ti možných.

Přednášející: Daniel Průša

Přednášky jsou 2 hodiny týdně, zde je rozvrh.

Plán přednášek:

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.

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).

• Josef Kolář: Teoretická informatika, Česká informatická společnost, Praha, 2004.

Jako alternativa mohou být použity následující dva zdroje. Oba jsou dostupné on-line.

• Jakub Černý: Základní grafové algoritmy, MFF UK, Praha, 2010, [pdf]. Studijní materiál relevantní k první polovině A7B33TIN. Vysvětluje základní grafové pojmy a algoritmy jako hledání nejkratší cesty, minimální kostry, toky v sítích. Obsahuje též kapitoly o časové složitosti a některých programovacích technikách.
• Petr Jančar: Teoretická informatika, VŠB - Technická univerzita Ostrava, 2007, [pdf]. Učební text pokrývající témata, která budeme probírat ve druhé polovině A7B33TIN: konečné automaty, regulární jazyky, bezkontextové jazyky, Turingovy stroje, základy teorie složitosti a vyčíslitelnosti.

• Za cvičení až 40 bodů.

• Za zkoušku až 60 bodů.

• Navíc lze získat několik bodů za bonusové úlohy zadávané na přednášce.

Součet bodů určuje známku podle následující tabulky:

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.