Themen dieses Kurses

  • Allgemeines

    • Základní prostor pro diskusi.

  • Obecné

  • Cvičení J. Bulín

  • Cvičení T. Čelko

    Nicht verfügbar, es sei denn: Sie gehören zu cvičení T. Čelko
  • Cvičení V. Majerech

  • Cvičení M. Vomlelová

    Nicht verfügbar, es sei denn: Sie gehören zu cvičení M. Vomlelová (obě)
  • Konečné automaty, regulární jazyky, Iterační (pumping) lemma

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

  • 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

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

  • Deterministické a bezprefixové PDA

    • 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

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

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

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

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

  • Časová a prostorová složitost

  • Archiv testů

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Cvičení P. Gregor

    • Aufgabe icon
      DU1 ze 16.2. Aufgabe
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Aufgabe icon
      DU2a z 23.2. Aufgabe
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Aufgabe icon
      DU2b z 23.2. Aufgabe
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Aufgabe icon
      DU3 z 9.3. Aufgabe
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Aufgabe icon
      DU4 z 16.3. Aufgabe
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Journal icon
      oznámení Journal
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Aufgabe icon
      DU5 z 30.3. Aufgabe
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Aufgabe icon
      DU6 z 6.4. Aufgabe
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Aufgabe icon
      DU7a ze 13.4. Aufgabe
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Aufgabe icon
      DU7b ze 13.4. Aufgabe
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Aufgabe icon
      DU8 z 27.4. Aufgabe
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Journal icon
      oznámení Journal
      Nicht verfügbar, außer mindestens eine Bedingung ist erfüllt:
      • Sie gehören zu cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Sie gehören zu cvičení čt 15:40 - LS 2022/23 (Gregor)