Osnova sekce

  • Úvod

    Sbalit vše Rozbalit vše

  • Cvičení J. Bulín

  • Cvičení J. Mestek

    Informace ke cvičením Jakuba Mesteka -  úterý 9:00 v S7, pátek 10:40 v S7

  • Cvičení V. Majerech

  • Cvičení M. Vomlelová

  • Konečné automaty, regulární jazyky, Iterační (pumping) lemma

    • Studenti musí
      Označit jako hotovo

      V 2019 přednášce přeskočte úvod na 3m:41s, čas 1h:11m by se měl vejít do konce dnešní přednášky (koncem v čase 1h:03, tj. po součinovém automatu, přijdete jen o ten bankovní příklad).

      https://is.mff.cuni.cz/prednasky/prednaska/NTIN071/1

      Slajdy z doby přednášky jsou nazvány 'Tabule' a jsou ke stažení pod videem.

      Oprava: 9:07 Turingův stroj má sice oboustrannou pásku, ale to není důležité. Klíčové je, že na tu pásku může psát a pohybovat se po ní v libovolném směru.

    • Konečné automaty, PL pro regulární jazyky Test
      Studenti musí
      Označit jako hotovo
    • Slajdy 1 Soubor
      Studenti musí
      Označit jako hotovo

      Aktualizováno 18.2.2025.

  • Redukce a ekvivalence automatů

  • nedeterminismus, λ-NFA, množinové a řetězcové operace nad jazyky

  • Kleenova věta, regulární výrazy, Homomorfismus, inverzní homomorfismus

  • Příklad na homomorfizmy, Dvousměrné automaty, Mooreův a Mealyho stroj

  • Gramatiky, Chomského hierarchie, L3 a FA, lineání gramatiky, CFG

  • Chomského normální forma, Pumping lemma pro CFG

    Na konci 8. přednášky je "Pumping (iterační) lemma pro bezkontextové jazyky". Obě pumping lemmata a definice věcí v Chomského hierarchii považuji za nejdůležitější základ toho, co máte umět u zkoušky.

    Pokud si nejste jisti, že stihnete shlédnout toto video do konce, přeskočte na minutu 31., do minuty 31 je převod zásobníkového automatu na gramatiku. 

    Naopak 9. přednáška začíná opakováním Pumping lemmatu a dalšími příklady. Můžete se podívat nebo použít na zopakování po velikonocích.

    Řešení příkladu na konci přednášky není úplné. Rozdělení na vx nemůže obsahovat zároveň 0 a 2. Pokud obsahuje 0 nebo 2, poruší se rovnost počtu 0 a 2, jak je řešeno na přednášce.

    Je třeba ještě zvážit variantu, že vx neobsahuje ani 0 ani 2. Protože je vx neprázdné, obsahuje 1 a pumpováním se poruší rovnost počtu 0 a 1.

  • Zásobníkové automaty, přijímání stavem, prázdným zásobníkem, vztah s CFG

    • Na tabuli v 7. přednášce v čase 14:42 je chyba, v instrukci i,Z0 → ZZ0 má být i,Z0 → ZZZ0. Přijímáme první chybu, tedy slovo ie nemáme přijmout, teprve až je o jedno e navíc.

      Nakonci (min 23:18) poslení  e sebere Z  ( e,Z →λ) a pak λ krok do přijímajícího stavu (λ,Z0 → λ).

    • Zásobníkové automaty úvod Test
      Studenti musí
      Označit jako hotovo
    • Studenti musí
      Označit jako hotovo

      Ke vztahu bezkontextových gramatik a zásobníkových automatů se ještě vrátíme, nebylo dokončeno.

  • Deterministické PDA, Uzávěrové vlastnosti CFL, Dyckovy jazyky

    • Studenti musí
      Označit jako hotovo

      9. video přednáška 2019

      Prvních 15 min
      'opakování' pumping lemmatu a jeho použití. Kdo si je jistý, že ho umí, může přeskočit. Kdo ne, je důležité umět či se hlásit cvičícímu nebo mě že mu není jasné.
      0:15-0:35
      CYK - algoritmus náležení slova do jazyka; tato 'snadná' otázka u obecných gramatik a Turingových stromů už snadná nebude.
      0:35-0:43:28
      Deterministické zásobníkové automaty
      0:43:28- 0:54:40
      přeskočte, rozšiřující a zamotala jsem se tam. Pro hloubavé: prostřední varianta je správně: bez lambda transakcí, hranu vedu do sourozence cíle plus y přepíšu na z; Pak výsledek odpovídá slajdu.
      0:54:40-1:06
      Vajíčko: naučte se nazpaměť; pokud možno i s důkazy, že jazyky do tříd patří a do menších nepatří.
      1:06-1:10:43
      (Ne)jednoznačnost gramatik - můžete vynechat
      1:10:43
      Uzávěrové vlastnosti (první půl): Bezkontextové jazyky nejsou uzavřené na průnik, jsou na sjednocení, konkatenaci, průnik s regulárním jazykem.
      Pozn: 1:14:08 chybí pravá složená závorka na tabuli za {S->S1 S2
      na slajdu 190 opraven regulární jazyk F na R.
    • CYK, Uzávěrové vlastnosti, Determinizmus Test
      Studenti musí
      Označit jako hotovo

      Test možná předbíhá cvičení; teď můžete tipovat, je to ukázka úloh, které vás mohou potkat v závěrečném testu.

    • Studenti musí
      Označit jako hotovo

      10. video přednáška 2019

      Uzávěrové vlastnosti reguláních, bezkontextových a deterministických bezkontextových jazyků.

      (58:37: zůstanu s prázdým bufferem, nikoli zásobníkem)

    • Slajdy: Deterministické PDA, uzávěrové vlastnosti Soubor

  • Deterministické a nedeterministické Turingovy stroje, Gramatiky Typu 0 (obecné gramatiky)

    • Kontextové gramatiky, Lineárně omezené automaty Test
      Studenti musí
      Označit jako hotovo
    • Studenti musí
      Označit jako hotovo

      11 video-přednáška

      Je docela hutná. Nejdůležitější je znát všechny definice a věty (což není moc) a umět napsat Turingův stroj rozpoznávající daný jazyk.

    • Slajdy k přednášce Soubor
    • Slajdy 2025 Soubor

  • Diagonální jazyk, Univerzální TM, algoritmicky nerozhodnutelné problémy, Postův korespondenční problém

    • Studenti musí
      Označit jako hotovo

       12. video přednáška

      Kontextové a monotónní gramatiky a lineárně omezené automaty, diagonální a univerzální jazyk

      Důležité znát: definice, věty, umět napsat kontextovou/monotónní gramatiku k uvedeným a velmi podobným jazykům, případně popsat Turingův stroj dané jazyky přijímající (většinou mi stačí vámi vybraná metoda, zvlášť když znáte větu přijímá lin. omez. aut. právě když existuje kontextová gramatika.

      Diagonální a univerzální jazyk.

      Je toho hodně, jak jsem ostatně měla dojem v 1:08:17.  

      Opravy k řeči, slajdy jsou pokud vím dobře:

      8:45  a^nb^nC^n není bezkontextový, je kontextový.
      33:27 generuji monotónní gramatiku, kterou z předchozího umím přepsat na kontextovou.

      48:29 jsou rekruzivní, nejsou KONTEXTOVÉ, JSOU rekurzivně spočetné. Obrázek správně.
      58:43 přijímá nulu, ne prázný řetězec (to by musel přijmout po přečtení blank, 000)

      1:04-1:08:17 lze přeskočit, nevěřte mi že 1:08:17 přednáška končí ;-))

  • Problém zastavení, PCP, (Ne)rozhodnutelné problémy o CFG

    • Studenti musí
      Označit jako hotovo

      13. video přednáška Nerozhodnutelné problémy


      Důkazy propojují myšlenky dohromady, doporučuji shlédnout celé. To co bych ráda, abyste z přednášky znali, je v náledujcících minutách:
      0-7:00
      Nerozhodnutelné problémy, redukce problému
      12:45-22:46
      Problém zastavení (Halting problém), Postův korespondenční problém (PCP)
      1:01:14-1:25:17
      Věta: PCP je nerozhodnutelný. (důkaz před tím přeskočen)
      Rozhodnutelné a nerozhodnutelné problémy pro bezkontextové gramatiky.

    • Slajdy Nerozhodnutelné problémy Soubor

  • Časová složitost

  • Prostorová složitost

  • Archiv testů

    • Test 19.6. (pro zkoušku 20.6.)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      Jsem u přijímaček, na testy (12. úlohu apod.) se podívám pozdější odpoledne.

    • Test 15.6. (pro zkoušku 16.6.)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Test 12.6. (pro zkoušku 13.6.)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', do večera opravím.

    • Test 6.6. (pro zkoušku 7.6.)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', do večera opravím.

    • Individuální. Po dohodě. Test
    • Test 30.5. (pro zkoušku 31.5.)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Test 29.5. (pro zkoušku 30.5.)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Test 24.5. (pro termín 25.5.)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', do večera opravím.

    • Test 22.5. (pro termín 23.5.)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Test 17.5., ke zkoušce 18.5.

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Test 24.5. (pro termín 25.5.) (kopie)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', do večera opravím.

    • Test 6.6. (pro zkoušku 7.6.) (kopie)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Test 27.6. (pro zkoušku 28.6.)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      V prvních čtyřech otázkách při chybě jen u deterministických zásobníkových automatů uznávám 0.5 bodu za správně zodpovězený zbytek. Úlohu 12 opravím do večera.

    • Nevstupovat. Náhodný test pro případ, že bych zapomněla zadat test na konkrétní termín.
      Studenti musí
      Označit jako hotovo
    • Test 19.9. (pro zkoušku 20.9.)

      Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', do večera opravím.

    • Komplet náhodných kategorií Test

  • Cvičení P. Gregor

    • link na cvičení P. Gregora (procvičované příklady) URL
      Studenti musí
      Označit jako hotovo
    • Studenti musí
      Označit jako hotovo

      V LS 2022/23 cvičení probíhají ve čtvrtek od 14:00 (S10) a 15:40 (S6). Pro odevzdávání DU přes Moodle se přihlaste do příslušné skupiny.

    • DU1 ze 16.2. Úkol
    • DU2a z 23.2. Úkol
    • DU2b z 23.2. Úkol
    • DU3 z 9.3. Úkol
    • DU4 z 16.3. Úkol
    • oznámení Poznámky
    • DU5 z 30.3. Úkol
    • DU6 z 6.4. Úkol
    • DU7a ze 13.4. Úkol
    • DU7b ze 13.4. Úkol
    • DU8 z 27.4. Úkol
    • oznámení Poznámky