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

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 / UVDOI - Ú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ákladu- chá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šku student absolvuje v souladu s platným Studijním řádem, zejména s důrazem na č. 32 a čl. 33 Studijního a zkušebního řádu OU.Hodnocení: prakticky orientované testy celkem 60 bodů, teoretický zkouškový test 40 bodů. Celkově lze získat 100 bodů, pro úspěšné zvládnutí zkoušky je třeba získat celkem alespoň 51 bodů.

Garant

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

Vyučující

doc. RNDr. PaedDr. Hashim Habiballa, PhD., Ph.D.doc. RNDr. PaedDr. Hashim Habiballa, PhD., Ph.D.Mgr. Matěj HirešRNDr. Michal Janošek, Ph.D.RNDr. Martin Kotyrba, Ph.D.Mgr. Zuzana Potyšová