Osnova témat

  • Úvod

    • Test 14.9.
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Vaše E-mailová adresa je akellich@seznam.cz
  • Obecné

  • Cvičení J. Bulín

    Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
    • Patříte k cvičení čt 9:00 - Bulín
    • Patříte k cvičení st 9:00 - Bulín
  • Cvičení P. Gregor

    • DU1 ze středy 3.3. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU1 z pátku 5.3. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • DU2 ze středy 10.3. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU2 z pátku 12.3. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • DU3 ze středy 17.3. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU3 z pátku 19.3. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • DU4 ze středy 24.3. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU4 z pátku 26.3. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • DU5 ze středy 31.3. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU6 ze středy 7.4. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU5 z pátku 9.4. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • DU7 ze středy 14.4. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU6 z pátku 16.4. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • DU8 ze středy 21.4. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU7 z pátku 23.4. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • DU9 ze středy 28.4. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU8 z pátku 30.4. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • DU10 ze středy 5.5. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU9 z pátku 7.5. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • DU10 z pátku 14.5. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • DU11 ze středy 19.5. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU11 z pátku 21.5. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • DU12 ze středy 26.5. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • DU12 z pátku 28.5. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
    • písemka ve středu 2.6. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 15:40 - Gregor
    • písemka v pátek 4.6. Úkol
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení pá 9:00 - Gregor
  • Cvičení D. Kuboň

    • Domácí úkol 2
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 14:00 - Kuboň
    • Domácí úkol 3
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 14:00 - Kuboň
    • Domácí úkol 4
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 14:00 - Kuboň
    • Domácí úkol 5
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 14:00 - Kuboň
    • Domácí úkol 6
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 14:00 - Kuboň
    • Domácí úkol 7
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 14:00 - Kuboň
    • Domácí úkol 8
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 14:00 - Kuboň
    • Domácí úkol 9
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 14:00 - Kuboň
    • Domácí úkol 10
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 14:00 - Kuboň
    • Domáci úkol 11
      Nedostupné Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení st 14:00 - Kuboň
  • 2.3. Konečné automaty, regulární jazyky, Iterační (pumping) lemma

  • Redukce a ekvivalence automatů

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

  • Deterministické a bezprefixové PDA

  • 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

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

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