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

Są dwie oceny z przedziału 2–5: ustny i zadania domowe. Ostateczna ocena to średnia ważona: 2/3 * ustny + 1/3 * zadania.

Poniżej jest 11 tematów z pytaniami egzaminacyjnymi. Na egzaminy ustny można sobie wybrać podzbiór.

• na ocenę 5 trzeba się nauczyć 9 tematów
• na ocenę 4 trzeba się nauczyć 6 tematów
• na ocenę 3 trzeba się nauczyć 4 tematów

---

Spis wykładów i tematy egzaminacyjne

Algorytm Angluin.
Materiał: rozdział 15 w książce Toolbox.
Pytania na egzamin: • przedstaw algorytm Angluin

Automaty ważone i liniowe
Materiał: rozdział 8 w książce Toolbox
Pytania na egzamin: • pokaż, że automaty ważony i liniowe są równoważne • przedstaw algorytm równoważności dla tych automatów

Automaty wielomianowe
Materiał: rozdział 11 w książce Toolbox
Pytania na egzamin: • czym są automaty wielomianowe • jak rozstrzyga się ich równoważność

Arytmetyka Tarskiego
Materiał: rozdział 10 w książce Toolbox. Treść tablicy na wykładzie
Pytania na egzamin: udowodnij rozstrzygalność teorii pierwszego rzędu dla ciała liczb rzeczywistych

Zbiory orbitowo skończone.
Treść tablicy na wykładzie Materiał być może zbyt obfity: książka Slightly Infinite Sets 
Pytania na egzamin: co to jest zbiór orbitowo skończony • jak się rozstrzyga niepustość dla automatów orbitowo skończonych

Przestrzenie wektorowe orbitowo skończone
 Treść tablicy na wykładzie
Pytania na egzamin: co to jest przestrzeń wektorowa orbitowo skończona • udowodnij, że łańcuch podprzestrzeni są skończone

Systemy dodawania wektorów
Materiał: rozdział 9 w książce Toolbox
Pytania na egzamin: udowodnij nierozstrzygalność problemu stopu dla maszyn dwulicznikowych • udowodnij rozstrzygalność problemu “coverability” dla systemów dodawania wektorów

Parsowania gramatyk w czasie mnożenia macierzy
Materiał: rozdział 12 w książce Toolbox
Pytania na egzamin: przedstaw algorytm parsowania korzystający z mnożenia macierzy

Determinizacja ω-automatów
Materiał: rozdział 1 w książce Toolbox
Pytania na egzamin: przedstaw podstawowe modele automatów dla ω-słów, czyli deterministyczne/niedeterministyczne automaty z warunkiem Büchiego/Mullera/parzystości • udowodnij determinizację (do warunku Mullera)

Gry nieskończone
Materiał: rozdział 2 w książce Toolbox
Pytania na egzamin: udowodnij pozycyjną determinację gier z warunkiem parzystości

Twierdzenie Rabina 
Materiał: rozdział 5 w książce Toolbox
Pytania na egzamin: udowodnij twierdzenie Rabina, zakładając wyniki z dwóch poprzednich wykładów.