====== 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í: [[http://cmp.felk.cvut.cz/~prusapa1|Daniel Průša]] Přednášky jsou 2 hodiny týdně, zde je [[http://www.feld.cvut.cz/cz/education/rozvrhy-ng/public/cz/predmety/13/99/p1399706.html|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 {{01_Uvod.pdf|[pdf]}}. Neorientované a orientované grafy - základní pojmy {{01_grafy-pojmy.pdf|[pdf]}}. Reprezentace grafu v paměti. | | 2 | 22.02. | Průša | Průchod grafem do šířky a do hloubky. Aplikace. {{:courses:a7b33tin:02_pruchod_grafem.pdf|[pdf]}} | | 3 | 01.03. | Průša | Hledání nejkratší cesty a minimální kostry v ohodnoceném grafu. {{:courses:a7b33tin:03_ohodnocene_grafy.pdf|[pdf]}} | | 4 | 08.03. | Průša | Toky v sítích. {{:courses:a7b33tin:04_toky_v_sitich.pdf|[pdf]}} | | 5 | 15.03. | Průša | Úvod do teorie formálních jazyků. Konečné automaty. {{:courses:a7b33tin:05_jazyky_automaty.pdf|[pdf]}} | | 6 | 22.03. | Zimmermann | Principy algoritmů na hraní tahových her. {{:courses:a7b33tin:05_tahove_hry.pdf|[pdf]}} | | 7 | 29.03. | --- | //Děkanský den.// | | 8 | 05.04. | Průša | Redukce automatu, nedeterminismus, regulární výrazy. {{:courses:a7b33tin:07_regularni_vyrazy.pdf|[pdf]}} | | 9 | 12.04. | Průša | Bezkontextové gramatiky. {{:courses:a7b33tin:08_gramatiky.pdf|[pdf]}} | | 10 | 19.04. | Průša | Zásobníkové automaty. {{:courses:a7b33tin:09_zasobnikove_automaty.pdf|[pdf]}} | | 11 | 26.04. | Průša | Výpočetní modely (Turingův stroj, RAM). {{:courses:a7b33tin:10_turingovy_stroje.pdf|[pdf]}} | | 12 | 03.05. | Průša | Nerozhodnutelné problémy. {{:courses:a7b33tin:11_nerozhodnutelnost.pdf|[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. {{:courses:a7b33tin:12_np-uplnost.pdf|[pdf]}} | ==== Cvičení ==== Podrobnosti jsou na [[.:lab|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 [[https://cw.felk.cvut.cz/upload | 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: {{:courses:a7b33tin:bonus1.pdf|[zadání]}}, {{:courses:a7b33tin:data1.txt|[data1]}}, {{:courses:a7b33tin:data2.txt|[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. {{:courses:a7b33tin:bonus2.pdf|[zadání]}} | 3 | | 3 | 05.04. | 19.04. (23:59 hod.) | Konečné automaty a regulární výrazy. {{:courses:a7b33tin:bonus3.pdf|[zadání]}} | 3 | | 4 | 19.04. | 03.05. (23:59 hod.) | Konstrukce bezkontextové gramatiky a zásobníkového automatu. {{:courses:a7b33tin:bonus4.pdf|[zadání]}} | 3 | | 5 | 03.04. | 17.05. (23:59 hod.) | Počítání na Turingově stroji. {{:courses:a7b33tin:bonus5.pdf|[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, {{http://kam.mff.cuni.cz/~kuba/ka/ka.pdf|[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, {{http://www.elearn.vsb.cz/archivcd/FEI/TI/ti-text.pdf|[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 |>=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: {{:courses:a7b33tin:priklady_001.pdf|[pdf]}} ==== Diskusní fórum ==== Pokud máte dotazy k probírané látce, můžete (mimo jiné) využít [[https://cw.felk.cvut.cz/forum|diskusní fórum]], které pravidelně čte přednášející i cvičící. Zároveň mohou být nápomocni i ostatní studenti.