Teoretické základy informatiky
doc. RNDr. Lucie Ciencialová, Ph.D.
Teoretické základy informatiky
doc. RNDr. Lucie Ciencialová, Ph.D.
Teoretické základy informatiky

FPF: UBKINSNK06 Teoretické základy informatiky (zima 2023)

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ů;

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á.

Sylabus předmětu

FPF: UIKSK33 Teoretické základy informatiky (zima 2023)

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ů;

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á.

Sylabus předmětu

FPF: UBKINSNP07 Teoretické základy informatiky (zima 2023)

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ů;

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á.

Sylabus 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. 

Osnova

  1. Abeceda, slovo,  jazyk
  2. Konečná reprezentace jazyků
  3. Gramatiky
  4. Konečné automaty a regulární jazyky
  5. Zásobníkové automaty
  6. Bezkontextové gramatiky a jazyky
  7. Úvod do teorie vyčíslitelnosti

Požadavky na studenta

Zkouška probíhá formou písemného testu, který obsahuje jak otázky na teorii tak příklady k vyřešení.

Literatura

Povinná:

  1. CIENCIALOVÁ, L., Teoretické základy informatiky. Opava 2014. ISBN: 978 – 80 –7510 – 130 – 3 

Doporučená:

  1. DEMLOVÁ, M. - KOUBEK, V. Algebraická teorie automatů. Praha: SNTL, 1990. 
  2. CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984. 
  3. GRUSKA, J. Foundations of Computing. London: International Thomson Computer Press, 1997. 
  4. MOLNÁR, Ľ. - ČEŠKA, M. - MELICHAR, B. Gramatiky a jazyky. Bratislava: Alfa, 1987. 
  5. HOPCROFT, J. E. - ULLMAN, J. D. Teória jazykov a automatov. Bratislava: Alfa, 1987.
Studijní opora
Kapitola obsahuje:
1
PDF
Předchozí
Následující

Předměty

  • FPF: UBKINSNK06 Teoretické základy informatiky (zima 2023)
  • FPF: UIKSK33 Teoretické základy informatiky (zima 2023)
  • FPF: UBKINSNP07 Teoretické základy informatiky (zima 2023)
Operace
Prohlédnout vše
Průvodce změnami Interaktivních osnov