Teoretické základy informatiky 2020/2021 – archív

Organizácia
Podmienky
Študijné materiály

Riadny termín skúšky z TZI v akademickom roku 2020/2021

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

Druhý test z TZI v akademickom roku 2020/2021

  • Druhý test z TZI sa uskutočnil 14. decembra (pondelok) 2020 o 13:00 (t.j. namiesto prednášky), t.j. v trinástom týždni semestra.
  • Test bol písaný cez Akademický informačný systém. Bol za 20 bodov.
  • Náplňou testu bola 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 bola možná konzultácia – očakával som, že sa na nej študenti pýtali na konkrétne veci, ktorým nerozumeli. Konzultácia prebehla na odkaze https://meet.google.com/jse-gvnd-acq   t.j. tam, kde bývali prednášky a cvičenia. Záznam z konzultácie bol k dispozícii hneď po jej skončení.
  • Konzultácia sa uskutočnila v piatok 11.12. o 17:00.

Prvý test z TZI v akademickom roku 2020/2021

  • Prvý test z TZI sa uskutočnil 28. októbra (streda) 2020 o 15:00 (t.j. namiesto cvičenia), t.j. v šiestom týždni semestra.
  • Test bol písaný cez Akademický informačný systém. Je za 20 bodov.
  • Náplňou testu bola 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 nebola. Namiesto nej bola 27.októbra v čase 17:00 – 19:00 možná konzultácia – očakával som, že sa na nej študenti budú pýtať na konkrétne veci, ktorým nerozumeli. Konzultácia prebehla na odkaze https://meet.google.com/jse-gvnd-acq   t.j. tam, kde bývali prednášky a cvičenia. Záznam z konzultácie bol k dispozícii hneď po jej skončení.

Organizácia predmetu v akademickom roku 2020/2021

Predmet bol č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 prednášky / cvičenia prebiehali na platforme Google Meet: https://meet.google.com/jse-gvnd-acq
  • V zmysle študijného poriadku boli prednášky / cvičenia povinné! Preto bola na každej prednáške / každom cvičení zapísaná prezencia zúčastnených študentov!
  • Z prednášok a cvičení bol vyhotovený videozáznam, ktorý bol k dispozícii pre študijné účely. Videozáznam bol nahrávkou príslušnej videokonferencie.
Konzultácie:

dohodou (mailom)

Diskusné fórum:

V AIS bolo pri predmete TZI vytvorené aj diskusné fórum, kde mohli študenti klásť rôzne otázky.

Plán semestra v akademickom roku 2020/2021

  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 bol 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 v akademickom roku 2020/2021

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

Skúška mala bodovú hodnotu 60 bodov.

Na zisk zápočtu musel študent získať z dvoch testov dokopy aspoň 20 bodov. Pri výslednom bodovaní hodnotenia predmetu sa použila 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 boli vždy upresnené minimálne s týždňovým predstihom.

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

Staré prednášky z roku 2020, 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.

Staré cvičenia z roku 2020, 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.