Předmět Matematická informatika (AUIUI / AEMAI)

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 AUIUI / AEMAI - Matematická informatika, Fakulta aplikované informatiky, Univerzita Tomáše Bati ve Zlíně (UTB).

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

Obsah

- Pojem algoritmu, správnost a složitost algoritmu, základní rozdělění a vlastnosti.- Datové struktury, jazyk, abeceda, slovo, formální gramatika, Chomskeho hierarchie gramatik.- Teorie konečných automatů.- Turingův a Postův stroj.- Vyhledávání v textu: Základní pojmy z teorie jazyků, naivní algoritmus, metoda Aho-Crosickové, vyhledávací automat.- Verifikace algoritmů: Vývojové diagramy a Floydova metoda, parciální a totální správnost algoritmu, důkazy správnosti.- Kombinatorické algoritmy: Základní pojmy, variace, permutace, kombinace, úlohy z omezujícími podmínkami, kombinatorika rozkladů, rekurentní vzorce.- Grafy I: Základní pojmy, prohledávání grafů, orientované, neorientované a nejkratší cesty, algebraické souvislosti, toky v sítích.- Grafy II: Eulerovy tahy, Hamitonovské cesty cirkulace a potenciály.- Složitost problémů a převoditelnost I: Třídy složitosti, P, NP, NPC problémy.- Složitost problémů a převoditelnost II: Relativní složitost a převoditelnost problémů.- Komplexita a komplexní sítě I: Příklady komplexity, pravděpodobnost - ergodická teorie a informace v komplexních systémech.- Komplexita a komplexní sítě II: Komplexní sítě, míry komplexity.- Moderní teorie informatiky: Bioinformatika, kvantová teorie informace, "ne-Shanonovské" pojetí informace.

Získané způsobilosti

Student má znalosti o základech teoretické informatiky.Student se orientuje v teorii grafů, složitosti problémů, kombinatorických algoritmů, komplexity a verifikace algoritmůStudent chápe principy konečných automatů, Turingova stroje, vyhledávacích algoritmů a komplexních síti.Student dokáže naprogramovat základní vyhledávací algoritmy a oveřit časovou složitost algoritmů.

Literatura

Vaníček J., Papík M., Pregl R., Vaníček T. Teoretické základy informatiky. Alfa Publishing, 2006. Naim B.E. Complex Networks. Springer, 2004. ISBN 13: 978-354022354.Demel J. Grafy a jejich aplikace. Academia, 2002. Kučera L. Kombinatorické algoritmy. Praha, 1983. Nešetřil J. Teorie grafů. MS, Praha, 1979. Koubková A., Pavelka J. Uvod do teoretické informatiky. Matfyzpress, 2003.

Požadavky

Způsob zakončení předmětu - zkouškaDocházka: povinná z 80% na cvičeních, jinak nepovinná.Projekty: za každý projekt (úkol) je možné získat 5 bodů, minimum je 2.5 bodu, jinak ho musí student přepracovat, případně vypracovat náhradní projekt.Zápočet: Včasné odevzdání všech projektů a získaní minimálně 50% bodů z celkového počtu bodů za všechny projekty.Zkouška: znalost probrané látky z probíraných tematických okruhů, písemná práce.

Garant

doc. Ing. Roman Šenkeřík, Ph.D.

Vyučující

doc. Ing. Roman Šenkeřík, Ph.D.