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 (technika wqo, uniwersalność 1-VASSa): notatki
- Wykład 3 (PSpace-trudność niepustości ograniczonych 1-VASSów): notatki
- Wykład 4 (regularna separowalność 1-VASSów): notatki
- Wykład 5 (automaty stratne): notatki (rozdział 1)
- Wykład 6 (pokrywalność w VASSach, ciekawe przykłady VASSów): notatki
- Wykład 7 (osiągalność w VASSach): notatki
- Wykład 8 (Ackermann-trudność osiągalności w VASSach): notatki, (tu w lepszej rozdzielczości)
- Wykład 9 (osiągalność w odwracalnych VASSach): notatki
- Wykład 10 (równoważności w systemach nieskończonych): notatki strona 1, strona 2, (tu w lepszej rozdzielczości)
- Wykład 11 (automaty rejestrowe): notatki, dodatkowo do wykładów 11 i 12 (rozdział 1)
- Wykład 12 (automaty rejestrowe c.d.): notatki
- Wykład 13 (równoważność DPDA cz. I): notatki
- Wykład 14 (równoważność DPDA cz. II): notatki (te same co dla poprzedniego wykładu), nagranie
Plan przedmiotu (orientacyjny)
- Wprowadzenie (1 wykład)
- Automaty z jednym licznikiem (3 wykłady)
- Automaty ze stratnymi licznikami (1 wykład)
- Automaty z wieloma licznikami, czyli VASSy (4 wykłady)
- Deterministyczne automaty ze stosem (2 wykłady)
- Automaty z rejestrami (2 wykłady)
- Modele jednoznaczne (1 wykład)
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.
Formuła egzaminu
Materiał z wykładu jest podzielony na cztery części:
- Automaty jednolicznikowe
- VAS
- Równoważności
- Automaty rejestrowe i stratne
Zadania z gwiazdką
Planowane są dwie serie zadań z gwiazdką.
- pierwsza seria zadań z gwiazdką (termin to 9.12.2022)
- druga seria zadań z gwiazdką (termin to 22.01.2023)
Kilka eleganckich rozwiązań zadań z pierwszej serii:
- Zadania 1 autorstwa Panów Borowskiego i Kamińskiego
- Zadania 2 autorstwa Pana Staniszewskiego
- Zadania 3 autorstwa Pana Kamińskiego
- Zadania 4 autorstwa Panów Borowskiego i Piotrowicza