Mikołaj Bojańczyk

Języki, automaty i obliczenia II • Advanced topics in automata


Wykład przestawia wybrane tematy o automatach. Większość wykładu oparta jest na skrypcie Automata Toobox. W razie konsultacji zapraszam na konsultacje do mnie oraz do Lorenza Clemente.


Zasady zaliczenia

Wykład zalicza się przez:

  • prace domowe (będą trzy serie)
  • egzamin ustny

Na podstawie powyższych można dostać ocenę maksymalną 5. Pojawią się też zadania gwiazdkowe, sowicie wynagradzane.


Spis wykładów

  1. 4 października: Algorytm Angluin. Materiał: rozdział 15 w książce Toolbox
  2. 11 października: Automaty ważone i liniowe. Materiał: rozdział 8 w książce Toolbox
  3. 18 października: Automaty wielomianowe. Materiał: rozdział 11 w książce Toolbox
  4. 25 października: Arytmetyka Tarskiego. Materiał: rozdział 10 w książce Toolbox. Treść tablicy na wykładzie
  5. 8 listopada: Automaty orbitowo skończone. Treść tablicy na wykładzie Materiał być może zbyt obfity: książka Slightly Infinite Sets
  6. 15 listopada: Przestrzenie wektorowe orbitowo skończone. Treść tablicy na wykładzie
  7. 22 listopada: Systemy dodawania wektorów. Materiał: rozdział 9 w książce Toolbox
  8. 29 listopada: Parsowania gramatyk w czasie mnożenia macierzy. Materiał: rozdział 12 w książce Toolbox
  9. 6 grudnia: Determinizacja ω-automatów.Materiał: rozdział 1 w książce Toolbox
  10. 13 grudnia: Gry nieskończone. Materiał: rozdział 2 w książce Toolbox
  11. 20 grudnia: Automaty min plus. Materiał: rozdział 4 w książce Toolbox
  12. 10 stycznia: Logika MSO. Materiał: rozdział 5 w książce Toolbox
  13. 17 stycznia: Szerokość drzewiasta i MSO. Materiał: rozdział 6 w książce Toolbox
  14. 24 stycznia: Pogadanka o współczesnych badaniach nad automatami.