Úvod do teoretickej informatiky

UTI LS 2021 | Ut 13:10 - 14:40 | Str 14:50 - 16:20

Základné info

  • účasť na cvičeniach je dobrovoľná,
  • úloha sa odovzdáva v Moodli
  • 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í, literatúry alebo s DÚ

Š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ť.)

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}

Spätná väzba k cvičeniam - môžete anonymne písať akékoľvek pripomienky, nápady, kritiku, či pochvalu k cvičeniam. Vopred ďakujem za akýkoľvek feedback.

  1. Cvičenie 1 - abecedy, slová, počty a vytváranie slov podľa pravidiel, počty podslov (prefixov, sufixov) (EDIT 23.2. opravená chyba v sume na str. 4)
  2. Cvičenie 2 - generovanie slov, jazyky, operácie na jazykoch
  3. Cvičenie 3 - jazyky, homomorfizmus, úvod k deterministickým automatom (definícia, výpočet na slove)
  4. Cvičenie 4 - automaty, KL množiny, dôkaz správnosti automatov
  5. Cvičenie 5 - modulárna konštrukcia, minimálny počet stavov automatu, úvod k léme 3.12
  6. Cvičenie 6 - dôkazy neregulárnosti jazykov, úvahy o (ne)regulárnych jazykoch
  7. Cvičenie 7 - úvod k nedeterministickým konečným automatom
  8. Cvičenie 8 - NKA, normálový tvar NKA, spájanie automatov
  9. Cvičenie 9 - úvod k deterministickým obyčajným Turingovým strojom
  10. Cvičenie 10 - deterministické obyčajné aj viacpáskové Turingove stroje
  11. Cvičenie 11 - deterministické a nedeterministické Turingove stroje
  12. Cvičenie 12 - opakovanie - NKA, TS.