E2011 Teoretické základy informatiky

Přírodovědecká fakulta
podzim 2022
Rozsah
2/2/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
Vyučující
RNDr. Miroslav Kubásek, Ph.D. (přednášející)
RNDr. Martin Komenda, Ph.D., MBA (přednášející)
prof. RNDr. Ladislav Dušek, Ph.D. (přednášející)
Garance
prof. RNDr. Ladislav Dušek, Ph.D.
RECETOX – Přírodovědecká fakulta
Kontaktní osoba: RNDr. Miroslav Kubásek, Ph.D.
Dodavatelské pracoviště: RECETOX – Přírodovědecká fakulta
Rozvrh
Čt 13:00–16:50 F01B1/709
Předpoklady
! Bi2011 Teor. zákl. informatiky
Nejsou, jedná se o základní kurz.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
Hlavní cíle kurzu jsou:
rozumět základům logiky, grafů, automatů a formálních jazyků;
rozvinout schopnost abstrakce.
Výstupy z učení
Student bude po absolvování předmětu schopen: porozumět základům logiky; grafů; automatů a formálních jazyků.
Osnova
  • Číselné soustavy.
  • Výrokový počet, Booleova algebra.
  • Predikátový počet.
  • Základní pojmy z teorie grafů.
  • Eulerovské a hamiltonovské grafy, stromy.
  • Kostra grafu, hledání optimální cesty.
  • Konečné automaty.
  • Zásobníkové automaty.
  • Gramatiky a jazyky, Chomského klasifikace.
  • Vztah konečných automatů a regulárních jazyků.
  • Vztah zásobníkových automatů a bezkontextových jazyků.
  • Základní metody syntaktické analýzy bezkontextových jazyků.
  • Lineárně ohraničené automaty.
  • Turingovy stroje.
Literatura
  • Fuchs, E.: Diskrétní matematika a Teorie množin pro učitele (CD-ROM). Masarykova univerzita, Brno, 2000.
  • Fuchs, E.: Diskrétní matematika pro učitele. Masarykova univerzita, Brno, 2001.
  • Kolář, J., Štěpánková, O., Chytil, M.: Logika, algebra, grafy. SNTL, Praha, 1989.
  • Molnár, L', Češka, M., Melichar, B.: Gramatiky a jazyky. Alfa, Bratislava, 1987.
  • Štěpán, J.: Formální logika. FIN, Olomouc, 1995.
Výukové metody
V semestru podzim 2020 se bude jednat o kombinaci teoretických přednášek, které budou nahrávány a poskytnuty v ISu a praktických cvičení, které budou probíhat on-line či prezenčně, dle aktuálních možností, omezení a domluvy.
Metody hodnocení
Přednášky, diskuse v hodině;
Závěrečná písemná zkouška.
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích podzim 2023, podzim 2024.