DVEW 2024

  • Info:

    Classes every Thursday 14:15-15-45 and 16:15-17:45 in room 2.063 (Otto-Hahn-Str. 12)

  • Moodle page:

    Moodle

JAiO 2021

  • Materiały i strona wykładu:

    Moodle

  • Tablice z zajęć:

    31 III 2021
    9 IV 2021
    16 IV 2021
    23 IV 2021
    30 IV 2021
    14 V 2021
    21 V 2021
    28 V 2021
    11 VI 2021

  • Polecane zadania (ze zbioru dostępnego tutaj):

    własności domknięcia języków regularnych: 26, 39, 40, 30, 32 (ostatnie dwa podobne do 29 z poprzednich zajęć)

    lemat o pompowaniu dla języków regularnych: 19 (nieco silniejsza wersja lematu), 20 (zmiana "2017" na "2021" poza estetyką nic nie zmienia), 21, 22

    minimalizacja i okolice: 48, 49, 51 (zadania fabularne), 52, 27 (można gołymi rękami)

    gramatyki bezkontekstowe: 84, 93, 98, 99

    pompowanie języków bezkontekstowych: 114, 107, 121, 115 (2) (co by było, gdybyśmy numery zmiennych kodowali unarnie, nie binarnie?), 153

    automaty ze stosem: 108, 143, 146, 154

    maszyny Turinga: 162, 160 (3), 167 (1), 165 (bezpośrednia konstrukcja maszyny deterministycznej - bez korzystania z determinizacji), 169

    złożoność obliczeniowa: 197, 196, NP-zupełny jest problem: dany graf, czy da się pokolorować wierzchołki na trzy kolory tak, by każdych dwóch sąsiadów miało inny kolor?, 200 (można czerpać inspirację z rozwiązania zadania 199 z wykładu)