Section outline

  • Généralités

    Tout replier Tout déplier
    • Obecné Forum
      Students must
      Marquer comme terminé

      Základní prostor pro diskusi.

  • Obecné

  • Cvičení J. Bulín

  • Cvičení T. Čelko

    Non disponible à moins que : Vous soyez membre de cvičení T. Čelko

  • Cvičení V. Majerech

  • Cvičení M. Vomlelová

    Non disponible à moins que : Vous soyez membre de cvičení M. Vomlelová (obě)

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

    • Students must
      Marquer comme terminé

      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
      Students must
      Marquer comme terminé
    • Slajdy 1 (handouts) Fichier
      Students must
      Marquer comme terminé

      Upraveny požadavky ke zkoušce a na konci přidán algoritmus hledání dosažitelných stavů.

  • Redukce a ekvivalence automatů

    • Slajdy 2 Ekvivalentní stavy, Redukce automatu, nedeterministické FA Fichier
      Students must
      Marquer comme terminé

    • K videopřednášce:

      1. 26:37 'první dvě části xy', ne 'první dvě části xz',
      2. naopak 1:1730-1:19:15 zbytečně zmatkuji.
    • 2. přednáška Test
      Students must
      Marquer comme terminé

  • 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

  • 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
      Students must
      Marquer comme terminé
    • Students must
      Marquer comme terminé

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

  • Deterministické a bezprefixové PDA

    • Students must
      Marquer comme terminé

      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
      Students must
      Marquer comme terminé

      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.

  • 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.

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

    • Students must
      Marquer comme terminé

      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)

  • Uzávěrové vlastnosti bezkontextových jazyků, Dyckovy jazyky

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

    • Kontextové gramatiky, Lineárně omezené automaty Test
      Students must
      Marquer comme terminé
    • Students must
      Marquer comme terminé

      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.

  • Dělící čára minulosti a budoucnosti

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

    • Students must
      Marquer comme terminé

       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čí ;-))

    • Students must
      Marquer comme terminé

      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.

  • Časová a 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.
      Students must
      Marquer comme terminé
    • 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
      Students must
      Marquer comme terminé
    • Students must
      Marquer comme terminé

      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. Devoir
    • DU2a z 23.2. Devoir
    • DU2b z 23.2. Devoir
    • DU3 z 9.3. Devoir
    • DU4 z 16.3. Devoir
    • oznámení Journal
    • DU5 z 30.3. Devoir
    • DU6 z 6.4. Devoir
    • DU7a ze 13.4. Devoir
    • DU7b ze 13.4. Devoir
    • DU8 z 27.4. Devoir
    • oznámení Journal