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 Łukasza Orlikowskiego i Michała Skrzypczaka. Wszyscy mieszkamy w budynku CENT. Tutaj znajdują się zadania z ćwiczeń.
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 (dojdą jeszcze 2 tematy)
- Arytmetyka Presburgera
Pytania na egzamin: • udowodnij eliminację kwantyfikatorów w arytmetyce Presburgera • pokaż, że arytmetyka Presburgera definiuje dokładnie zbiory semiliniowe
- Arytmetyka Tarskiego
Pytania na egzamin: udowodnij rozstrzygalność teorii pierwszego rzędu dla ciała liczb rzeczywistych
- Systemy dodawania wektorów
Pytania na egzamin: udowodnij nierozstrzygalność problemu stopu dla maszyn dwulicznikowych • udowodnij rozstrzygalność problemu “coverability” dla systemów dodawania wektorów
- Automaty ważone i liniowe
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
Pytania na egzamin: • czym są automaty wielomianowe • jak rozstrzyga się ich równoważność
- Automaty rejestrowe i orbitowo skończone
Pytania na egzamin: co to jest zbiór orbitowo skończony • jak się rozstrzyga niepustość dla automatów orbitowo skończonych
- Prawa zero-jedynkowe
Pytania na egzamin: udowodnij prawo zero-jedynkowe dla logiki pierwszego rzędu • pokaż, że nieskończony graf losowy jest jeden
- Parsowania gramatyk w czasie mnożenia macierzy
Pytania na egzamin: przedstaw algorytm parsowania korzystający z mnożenia macierzy
- Algorytm Angluin.
Pytania na egzamin: • przedstaw algorytm Angluin
- Determinizacja ω-automatów
Pytania na egzamin: przedstaw podstawowe modele automatów dla ω-słów, czyli deterministyczne/niedeterministyczne automaty z warunkiem Büchiego oraz parzystości • udowodnij determinizację (do warunku parzystości)