UBKINSNK06 Teoretické základy informatiky

Filozoficko-přírodovědecká fakulta v Opavě
zima 2021
Rozsah
14 hod/sem. 6 kr. Ukončení: zk.
Vyučující
doc. RNDr. Luděk Cienciala, Ph.D. (přednášející)
doc. RNDr. Lucie Ciencialová, Ph.D. (přednášející)
doc. RNDr. Lucie Ciencialová, Ph.D. (cvičící)
Garance
doc. RNDr. Lucie Ciencialová, Ph.D.
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
Základními tématy předmětu jsou abstraktní stroje, formální gramatiky a jazyky, pojem vyčíslitelnosti a složitosti automatů, jazyků a výpočtů. Bude diskutováno chování individuálních objektů i fenoménů a důsledky spolupráce kolektivního chování objektů. Studenti se seznámí s Turingovým strojem, zásobníkovým automatem a konečným automatem, se vztahem strojů a formálních gramatik. Předmětem studia bude také omezení strojového přístupu a generativního přístupu k řešení úloh a související pojem (ne)rozhodnutelnosti.
Výstupy z učení
Student bude po absolvování předmětu schopen:
- vysvětlit rozdíl mezi generativním a strojovým přístupem k řešení úloh;
- definovat typy chomského gramatik;
- přiřadit k typům jazyků stroj, který je rozpoznává;
- analyzovat chování gramatik i strojů;
Osnova
  • 1. Abeceda, slovo, jazyk. Konečná reprezentace jazyků.
  • 2. Gramatiky.
  • 3. Konečné automaty a regulární jazyky.
  • 4. Zásobníkové automaty.
  • 5. Bezkontextové gramatiky a jazyky.
  • 6. Úvod do teorie vyčíslitelnosti.
Literatura
    povinná literatura
  • CIENCIALOVÁ, Lucie. Teoretické základy informatiky. Opava: Slezská univerzita v Opavě, 2014. ISBN 978-80-7510-130-3. info
    doporučená literatura
  • ČERNÁ, I, M KŘETÍNSKÝ a A KUČERA. Automaty a formální jazyky I. Brno: FI MU, 2002. info
Výukové metody
Přednáška s aktivizací
Přednáška s diskuzí
Metody hodnocení
Zápočet: písemný. Povinná účast na cvičeních min. 75 %. Zkouška: písemná.
Předmět je zařazen také v obdobích zima 2022, zima 2023, zima 2024.