Předmět Úvod do informatiky (KIP / 6UVDI)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KIP / 6UVDI - Úvod do informatiky, Přírodovědecká fakulta, Ostravská univerzita v Ostravě (OU).

Materiál	Typ	Datum	Počet stažení

Obsah

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, vlastnosti5. 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 stroje7. 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é ekvivalence9. 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říklady11. 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

Získané způsobilosti

schopnost pochopit principy informatiky z pohledu teoretického základuchápat pojmy vyčíslitelnosti a složitosti algoritmů a aplikovat je na řešení příkladů

Literatura

http://www.cs.vsb.cz/jancar/HABIBALLA, H., PAVLISKA, V. Úvod do teoretické informatiky. elektronický učební materiál OU. 2009. Habiballa, H. Regulární a bezkontextové jazyky I. Ostravská Univerzita, 2003. Pavliska, Viktor. Vyčíslitelnost a složitost I. 2002. CHYTIL, Milan. Automaty a gramatiky. Praha, SNTL, 1984. KUČERA, L. Kombinatorické algoritmy. Praha, SNTL, 1983.

Požadavky

Zkouškový test na konci semestru, lze částečně nahradit projektem (zk. test - 100 b. max, projekt 80b. max.) - 61-75 b.: 3; 76-90 b.: 2; 91 a více b.: 1

Garant

doc. RNDr. PaedDr. Hashim Habiballa, PhD., Ph.D.

Vyučující

RNDr. Michal Janošek, Ph.D.RNDr. Michal Janošek, Ph.D.