Úvod do teoretickej informatiky

UTI LS 20256 | Ut 13:10 - 14:40 | F1-321

Základné info

  • účasť na cvičeniach je dobrovoľná,
  • úlohy sa odovzdávajú na cvičeniach
  • reklamácie opráv na/po cvičeniach/mailom,
  • konzultácie po dohode (osobnej alebo mailom) - či už máte problém s nejakým príkladom z cvičení, či literatúry, alebo máte problém s domácou úlohou

Študijné materiály

Zopár linkov alebo kníh, ktoré môžu poslúžiť pri príprave na predmet a na skúšku, ale aj pri domácich úlohách. (Pozn. treba vedieť vybrať, čo sme preberali, prípadne si dať pozor na iné značenie. Knižky sú k dispozícii v knižnici, ale dajú sa aj vyygoogliť.)

  • stránka predmetu
  • J. Hromkovič - Theoretical computer science
  • B. Rovan, M. Forišek - Skriptá k FOJA
  • P. Jančár - Skriptá k TI z Ostravy
  • J. Hopcroft, et al - Introduction to Automata Theory, Languages, and Computation
  • R. P. Grimaldi - Discrete and Combinatorial Mathematics, An Applied Introduction (Kapitola 6)
  • Fun (alebo čo radšej neskúsať) - Dôkazy 1, dôkazy 2
  • JFLAP - aplikácia na vytváranie a experimentovanies s DKA, NKA, TS, ale aj gramatikami a regulárnymi výrazmi

Príklady z cvičení

... sem postupne budú pribúdať príklady z cvičení (hviezdičkou sú označené príklady, ktoré sme na cvikách nestihli, alebo nedokončili)

  1. Cvičenie 1 - abecedy, slová, počty a vytváranie slov podľa pravidiel, počty podslov (prefixov, sufixov)
  2. Cvičenie 2 - jazyky
  3. Cvičenie 3 - homomorfizmus, automaty, KL množiny
  4. Cvičenie 4 - modulárna konštrukcia automatov (upravené 31.3. - oprava prechodu v automate v úlohe 2, časť (iv))
  5. Cvičenie 5 (17.3.2026) - bolo s Dr. Bezákovou v miestnosti M-XII
  6. Cvičenie 6 - dôkaz neregulárnosti jazykov
  7. Cvičenie 7 - opakovanie na 1. písomku
    8. ...