Bi2011 Teoretické základy informatiky

Přírodovědecká fakulta
podzim 2007
Rozsah
2/2. 4 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
Vyučující
prof. RNDr. Jiří Hřebíček, CSc. (přednášející)
RNDr. Jaroslav Ráček, Ph.D. (přednášející)
Garance
prof. RNDr. Jiří Hřebíček, CSc.
RECETOX – Přírodovědecká fakulta
Kontaktní osoba: doc. Ing. Daniel Schwarz, Ph.D.
Rozvrh
Pá 9:00–10:50 F01B1/530, Pá 11:00–12:50 F01B1/530
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
Předmět je zacílen na základní pojmy související s teorií informace a poskytuje teoretický aparát pro pochopení faktů, vztahů a metod teoretické informatiky. Soustředí se zejména na oblasti logiky, grafů, automatů a formálních jazyků. Cílem je rozvinout schopnost abstrakce a studovat vybrané výpočetní modely.
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.
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 2008, 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.