Do zakończenia pandemii koronawirusa tradycyjne konsultacje są zawieszone, zachęcam do zadawania pytań drogą mailową oraz umawiania się na konsultacie za pośrednictwem wideorozmowy lub czatu.

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