UBKINSNK06 Teoretické základy informatiky

Filozoficko-přírodovědecká fakulta v Opavě
zima 2022
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.
Ústav bohemistiky a knihovnictví – Filozoficko-přírodovědecká fakulta v Opavě
Dodavatelské pracoviště: Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
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
    neurčeno
  • CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984. 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 2021, zima 2023, zima 2024.