Základy (teoretické) informatiky – KIP/7ZAIN, 2ZAIN, XZAIN, 6PUDI, UVDOI, 3UVDI, 66UDI
jako doplněk lze využít také materiály ke kurzům Vyčíslitelnost a složitost a Gramatiky a jazyky (Formální jazyky a gramatiky)
Speciální balíček multimediálních materiálů (www)
| Požadavky na studenta |
| V prezenčním studiu 2 testy za celkem 60 bodů a zkouškový test za 40 bodů na konci semestru. V kombinovaném a distančním studiu 4 korespondenční úkoly za celkem 100 bodů. |
| Přehled probírané látky |
| 1. Teoretická informatika – rozdělení, historie a účel. Přehled matematických metod a pojmů nutných ke studiu (množiny, relace atd.) 2. Teorie formálních jazyků a automatů, Vyčíslitelnost a složitost a Logika (základní seznámení, motivace pro studium, vztah k praktickým problémům informatiky) 3. Intuitivní výklad vybraných pojmů teorie formálních jazyků (opravdu jen základy např. funkce konečných automatů na příkladech z praxe apod. podrobnosti v následných kurzech) 4. Základní pojmy teorie vyčíslitelnosti – problém, rozhodnutelnost, částečná rozhodnutelnost, vlastnosti 5. Výpočetní model Turingova stroje a jeho vlastnosti – nerozhodnutelné problémy, převoditelnost problémů (zajímavé příklady z jiných disciplín TI – logika, formální jazyky atp.) 6. Výpočetní modely a jejich ekvivalence – Turingovy stroje vs. RAM stroje 7. Výpočetní modely a jejich ekvivalence – Částečně rekurzivní funkce, 8. Výpočetní modely a jejich ekvivalence – PL-programy, konstrukce algoritmů pro jednoduché problémy pomocí různých výpočetních modelů, demonstrace jejich vzájemné ekvivalence 9. Teorie složitosti algoritmů, Časová a prostorová složitost výpočtu, stroje a problému, odhady složitosti – praktické ukázky (řazení, vyhledávání, maticové a grafové algoritmy apod.), 10. Třídy složitosti a vztahy mezi nimi, zvládnutelné vs. nezvládnutelné problémy (PTIME vs. EXPTIME), příklady 11. Nedeterministický TS, simulace pomocí DTS a její časová složitost, P=NP problém, NP-úplnost a ukázky problémů 12. Polynomiální převoditelnost problémů a její využití 13. Abstraktní datové struktury a složitost |
| Literatura |
| Základní: HABIBALLA, H., PAVLISKA, V. Úvod do teoretické informatiky. elektronický učební materiál OU. , 2009. JANČAR, PETR Teoretická informatika. VŠB TU Ostrava http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm Rozšiřující: HABIBALLA, H. Regulární a bezkontextové jazyky I. Ostravská Univerzita, 2003.. PAVLISKA, VIKTOR. Vyčíslitelnost a složitost I. , 2002. Doporučená: CHYTIL, MILAN Automaty a gramatiky. Praha, SNTL, 1984. KUČERA, L. Kombinatorické algoritmy. Praha, SNTL, 1983. |