Automaty nieskończone
Przedmiot prowadzimy wspólnie ze Sławomirem Lasotą. W każdym tygodniu jeden z nas prowadzi blok: wykład + ćwiczenia. Notatki z wykładów udostępniamy poniżej, natomiast zadania z ćwiczeń dostępne są tutaj.Wykłady
- Wykład 1 (wprowadzenie, automaty ze stosem: krótki bieg, obliczanie Reach): notatki
- Wykład 2 (PSpace-trudność niepustości ograniczonych 1-VASSów): notatki
- Wykład 3 (technika wqo, uniwersalność 1-VASSa): notatki
Plan przedmiotu (orientacyjny)
- Wprowadzenie (1 wykład)
- Automaty z jednym licznikiem (2 wykłady)
- Zbiory semiliniowe (1 wykład)
- Automaty ze stratnymi licznikami (1 wykład)
- Automaty z wieloma licznikami, czyli VASSy (3 wykłady)
- Automaty z rejestrami lub zegarami (2 wykłady)
- Systemy odwracalne (2 wykłady)
- Geometryczne podejście do VASSów (2 wykłady)
System oceniania
System składa się z dwóch części: egzaminu ustnego oraz zadań z gwiazdką. Jeśli ktoś dostanie z egzaminu ocenę x oraz y punktów z zadań z gwiazdką, to dostaje ocenę x+y zaokrągloną do najbliższej liczby ze zbioru {2, 3, 3.5, 4, 4.5, 5}.
Za każde zadanie z gwiazdką jest jeden punkt, do podziału na osoby, które rozwiązały to zadanie.
Zadania z gwiazdką
Planowane są dwie serie zadań z gwiazdką. Za każdy problem można dostać 1 punkt, który jest dzielony równo na osoby, które rozwiązały dany problem.