Info:

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

Moodle page:

Moodle

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)