Bi2011 Teoretické základy informatiky

Přírodovědecká fakulta
podzim 2008
Rozsah
2/2. 4 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
Vyučující
RNDr. Jaroslav Ráček, Ph.D. (přednášející)
Garance
prof. RNDr. Jiří Hřebíček, CSc.
Katedra počítačových systémů a komunikací – Fakulta informatiky
Kontaktní osoba: RNDr. Jaroslav Ráček, Ph.D.
Rozvrh
Po 8:00–11:50 B411
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.
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.
Metody hodnocení
Přednášky, diskuse v hodině;
Závěrečná písemná zkouška.
Další komentáře
Předmět je vyučován každoročně.
Nachází se v prerekvizitách jiných předmětů
Předmět je zařazen také v obdobích podzim 2007 - akreditace, podzim 2010 - akreditace, podzim 2007, podzim 2009, podzim 2010, podzim 2011, podzim 2011 - akreditace, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019, podzim 2020, podzim 2021.