JAO 2
Notatki
Na stronie Mikołaja Bojańczyka można znaleźć książkę, która obejmuje większość materiału. Materiały, które nie są zawarte w książce można znaleźć:
- dobry artykuł na temat automatów jednoznacznych
- moje notatki o automatach jednoznacznych
- moje notatki o problemie pokrywalności w ExpSpace
- artykuł na temat 4-VASSa z podwójnie wykładniczym najkrótszym biegiem (sekcja 5)
Materiały z tegorocznych ćwiczeń prowadzonych przez Janusza Schmude i Rafała Stefańskiego są tutaj.
Tu można znaleźć stare notatki z ćwiczeń (po angielsku)
a tu jeszcze starsze (z roku 2016/17).
Będę wdzięczny za informacje o błędach.
Plan przedmiotu
- Słowa skończone
- Automaty jednoznaczne
- Automaty ważone nad ciałem
- MSO = Reg
- Learning - algorytm Angluin
- Słowa nieskończone
- Determinizacja automatów na omega-słowach (2 wykłady)
- Gry nieskończone (2 wykłady)
- Distance automaty
- Systemy nieskończone
- Pokrywalność dla VASów
- Algorytm Rackoffa
- Podwójnie wykładniczy bieg w 4-VASSie
- Transducery
- Transducery jednokierunkowe
- Deterministyczne transducery dwukierunkowe
Zadania z gwiazdką
Dostępna jest druga seria zadań z gwiazdką.
- pierwsza seria zadań z gwiazdką (termin to 13.01.2020)
- druga seria zadań z gwiazdką (termin to 4.02.2020)
Dostępne są też rozwiązania zadań z gwiazdką
- rozwiązanie zadania 1 z serii 1 autorstwa Witalisa Domitrza
- rozwiązania zadań 2, 3 i 4 z serii 1 autorstwa Konrada Majewskiego
- rozwiązania zadań 5 i 6 z serii 1 autorstwa Mateusza Gienieczki
- bardzo polecam ciekawy artykuł autorstwa Mikołaj Bojańczyka "Star Height via Games", który był inspiracją do zadań 5 i 6
- rozwiązanie zadania 1 z serii 2 autorstwa Witalisa Domitrza
- rozwiązanie zadania 2 z serii 2 mojego autorstwa
System oceniania
Składa się z dwóch części: testowej oraz zadaniowej (podobnie jak na złożoności obliczeniowej). 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}. Na przykład jeśli ktoś dostanie ocenę 4 z egzaminu, rozwiąże jedno zadanie z gwiazdką rozwiązane przez 4 osoby (1 / 4 = 0.25) oraz drugie zadanie z gwiazdką rozwiązane przez 5 osób (1 / 5 = 0.2), to dostanie 4 + 0.2 + 0.25 = 4.45 zakrąglone do najbliższej oceny, czyli do 4.5.