Teoretické základy informatiky

Dôležitý link

Google Meet odkaz na prednášky / cvičenia: https://meet.google.com/jse-gvnd-acq

Prednášajúci:Viliam Hromada
Cvičiaci:Viliam Hromada
Organizácia
Podmienky
Študijné materiály

Riadny termín skúšky z TZI

  • Riadny termín skúšky z TZI sa uskutoční 20. januára (streda) o 9:00. Bude trvať 2 hodiny.
  • Skúška bude písaná cez Akademický informačný systém. Je za 60 bodov.
  • Náplňou skúšky bude látka odprednášaná a odcvičená počas celého semestra.
  • Skúška bude pozostávať z 30 testových otázok. Každá otázka je za 2 body, vždy je správna len jedna odpoveď.
  • Na skúšku môžu ísť len tí študenti, ktorí počas semestra získali aspoň 20 bodov.
  • Ak by ste mali počas skúšky otázky k zadaniam úloh, budem k dispozícii na Google Meet https://meet.google.com/jse-gvnd-acq

Druhý test z TZI

  • Druhý test z TZI sa uskutoční 14. decembra (pondelok) o 13:00 (t.j. namiesto prednášky), t.j. v trinástom týždni semestra.
  • Test bude písaný cez Akademický informačný systém. Je za 20 bodov.
  • Náplňou testu bude látka odprednášaná a odcvičená po prvom teste do konca semestra, t.j. prednáška č. 6, 7, atď až do konca semestra.
  • Pred konaním testu bude možná konzultácia – očakávam, že sa na nej budete pýtať na konkrétne veci, ktorým nerozumiete. Nečakajte, že budem ešte raz opakovať už celú prednášanú látku! Konzultácia prebehne na odkaze https://meet.google.com/jse-gvnd-acq   t.j. tam, kde bývajú prednášky a cvičenia. Záznam z konzultácie bude k dispozícii hneď po jej skončení.
  • Konzultácia sa uskutoční v piatok 11.12. o 17:00.

Prvý test z TZI

  • Prvý test z TZI sa uskutoční 28. októbra (streda) o 15:00 (t.j. namiesto cvičenia), t.j. v šiestom týždni semestra.
  • Test bude písaný cez Akademický informačný systém. Je za 20 bodov.
  • Náplňou testu bude látka odprednášaná a odcvičená počas prvých 5 týždňov semestra.
  • Deň pred konaním testu, t.j. 27. októbra prednáška nebude! Namiesto nej bude 27.októbra v čase 17:00 – 19:00 možná konzultácia – očakávam, že sa na nej budete pýtať na konkrétne veci, ktorým nerozumiete. Nečakajte, že budem ešte raz opakovať už celú prednášanú látku! Konzultácia prebehne na odkaze https://meet.google.com/jse-gvnd-acq   t.j. tam, kde bývajú prednášky a cvičenia. Záznam z konzultácie bude k dispozícii hneď po jej skončení.

Organizácia predmetu

Predmet je členený do nasledujúcich aktivít:

  • Prednášky: 2 hodiny týždenne podľa rozvrhu, utorok 13 – 15h, C517
  • Cvičenie: 2 hodiny týždenne podľa rozvrhu, streda 15 – 17h, C517
  • Počas dištančnej výuky budú prednášky / cvičenia prebiehať na platforme Google Meet: https://meet.google.com/jse-gvnd-acq
  • Upozorňujem, že v zmysle študijného poriadku sú prednášky / cvičenia povinné! Preto bude na každej prednáške / každom cvičení zapísaná prezencia zúčastnených študentov!
  • Taktiež upozorňujem, že z prednášok a cvičení, bude vyhotovený videozáznam, ktorý bude k dispozícii pre študijné účely. Videozáznam bude nahrávkou príslušnej videokonferencie.
Konzultácie:

dohodou (mailom)

Diskusné fórum:

Nezabúdajte, že v AIS je pri predmete TZI vytvorené aj diskusné fórum, kde môžete klásť rôzne otázky!

Plán semestra

  1. Stručný úvod do dôkazov
  2. Deterministické a nedeterministické konečné automaty.
  3. Regulárne výrazy.
  4. Vlastnosti regulárnych jazykov.
  5. Bezkontextové gramatiky.
  6. Zásobníkové automaty.
  7. Vlastnosti bezkontextových jazykov.
  8. Turingove stroje.
  9. Nerozhodnuteľnosť.
Literatúra

Predmet bude vyučovaný podľa knihy „Introduction to Automata Theory, Languages and Computation“ od autorov Hopcroft, Motwani, Ullman. Konkrétne podľa jej posledného tretieho vydania.

Podmienky absolvovania

Počas semestra poslucháči absolvujú 2 testy, oba s bodovou hodnotou 20 bodov, t.j. v celkovom súčte 40 bodov.

Skúška bude mať bodovú hodnotu 60 bodov.

Na zisk zápočtu musí študent získať z dvoch testov dokopy aspoň 20 bodov. Pri výslednom bodovaní hodnotenia predmetu sa používa aktuálne platná stupnica FEI STU (A >= 92, 92 > B >= 83, 83 > C >=74, 74 > D >= 65, 65 > E >= 56, 56 > FX).

Termíny testov budú vždy upresnené minimálne s týždňovým predstihom.

Pozn.: Odhalené podvádzanie pri predmete bude penalizované podľa platného študijného poriadku.

Videá z prednášok a cvíčení:

Link na Google Drive s videami z prednášok a cvičení: https://drive.google.com/drive/folders/1kYyu1VXiwR72GTolFmxyJDGme_TfDEt_

Videá taktiež nájdete aj na mojom YouTube: https://www.youtube.com/channel/UCPyMdibG5R-gPEnyNQRp_Vg/videos

Prednášky pdf verzie

  1. prednáška, Úvodné slovo, dôkazy, pojmy abeceda, reťazec, jazyk.
  2. prednáška, Konečné automaty – úvod, deterministické konečné automaty.
  3. prednáška, Nedeterministické konečné automaty, konverzia DKA <-> NKA.
  4. prednáška, Praktické využitie konečných automatov, ε-NKA, ε-NKA <-> DKA.
  5. prednáška, Regulárne výrazy, ekvivalencia regulárnych výrazov a konečných automatov.
  6. prednáška, Vlastnosti regulárnych jazykov, minimalizácia konečných automatov.
  7. prednáška, Bezkontextové gramatiky.
  8. prednáška, Zásobníkové automaty, rozhodovacie problémy o bezkontextových jazykoch.
  9. prednáška, Turingove stroje.
  10. prednáška, Rozšírenia Turingovych strojov, vlastnosti RE jazykov.
  11. prednáška, Redukcie problémov, Riceova veta.

Cvičenia pdf verzie

  1. cvičenie – bolo nahradené prednáškou č. 1.
  2. cvičenie, Deterministické konečné automaty.
  3. cvičenie, Nedeterministické konečné automaty, konverzia DKA <-> NKA.
  4. cvičenie, ε-NKA, konverzia ε-NKA, <-> DKA.
  5. cvičenie, Regulárne výrazy, konverzia regulárnych výrazov na ε-NKA a naopak.
  6. cvičenie, Emptiness-problém, ekvivalencie stavov, minimalizácia DKA.
  7. cvičenie, Bezkontextové gramatiky, Zásobníkové automaty.
  8. cvičenie, Turingove stroje
  9. cvičenie, Rozšírenia Turingovych strojov, vlastnosti RE jazykov.
  10. cvičenie, Redukcie problémov, Riceova veta.