Automaty, logika i gry 1000-2M22ALG
Wykład podąża według programu i slajdów przedstawionych na stronie
https://www.mimuw.edu.pl/~bojan/2020-2021-2/automata-logic-and-games
1. Automaty i logika monadyczna dla słów skończonych
2. Półgrupy i kompozycjonalność dla logiki
3. Logika pierwszego rzędu i pokrewne
4. Słowa nieskończone i automaty Büchiego na nich
5. Determinizacja automatów na słowach nieskończonych
6. Gra i ich determinacja
7. Automaty alternujące oraz logika temporalna LTL
8. Algorytmy rozwiązujące gry parzystości
9. Drzewa skończone
10. Drzew nieskończone
11. Twierdzenie Rabina
12. Logiki temporalne i struktury Kripkego
13. Rachunek mi
14. Grafy
15. Transdukcje
Przedmiot jest przeznaczony również dla doktorantów.
Kierunek podstawowy MISMaP
informatyka
Rodzaj przedmiotu
Założenia (lista przedmiotów)
Efekty kształcenia
Wykład ma być obszernym wprowadzeniem do współczesnych badań dotyczących automatów i logiki. Dzięki wykładowi student powinien zapoznać się z teorią używaną w tych badaniach, wraz z powiązaniami z pozornie odległymi zagadnieniami takimi jak teoria gier czy topologia.
Kryteria oceniania
Egzamin z przedmiotu jest ustny. Poprzedzony będzie zadaniami domowymi, które umożliwiają podwyższenie oceny z egzaminu ustnego.
Literatura
Podstawowym materiałem będą slajdy
https://www.mimuw.edu.pl/~bojan/2020-2021-2/automata-logic-and-games
Uzupełniającym materiałami są:
* Wolfgang Thomas. Languages, Automata and Logic
* Mikołaj Bojańczyk i Wojciech Czerwiński. An automata toolbox
* Mikołaj Bojańczyk. Recognisable languages …
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: