Teoretická informatika - A7B33TIN, LS 2010/2011

Popis předmětu

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

Nové

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ášky

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]

Cvičení

Podrobnosti jsou na stránkách cvičení.

Bonusové úlohy

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

Literatura

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.

Hodnocení

  • 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:

body >=9089-8079-7069-6059-5049-0
známka A B C D E F

Písemka, ukázkové příklady: [pdf]

Diskusní fórum

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.

 
Groups:
courses/a7b33tin/start.txt · Last modified: 2013/10/04 13:02 (external edit)