Automaty, logika i gry

Informacje ogólne

Kod przedmiotu:	1000-2M22ALG
Kod Erasmus / ISCED:	11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu:	Automaty, logika i gry
Jednostka:	Wydział Matematyki, Informatyki i Mechaniki
Grupy:	Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne:	(brak) Podstawowe informacje o zasadach przyporządkowania punktów ECTS: roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS; tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h; 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się; tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS; nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta. zobacz reguły punktacji
Język prowadzenia:	angielski
Kierunek podstawowy MISMaP:	informatyka matematyka
Rodzaj przedmiotu:	monograficzne
Założenia (lista przedmiotów):	Języki, automaty i obliczenia 1000-214bJAO Logika dla informatyków 1000-217bLOG
Skrócony opis:	Wykład opisuje związki pomiędzy logiką a automatami skończonymi. Punktem wyjścia jest klasyczne twierdzenie, że automaty skończone opisują dokładnie te języki, które można zdefiniować w logice monadycznej drugiego rzędu. Wykład omawia daleko idące rozszerzenia tego twierdzenia, dotyczące przede wszystkim obiektów nieskończonych, takich jak nieskończone słowa czy drzewa. Ważną rolę w teorii odgrywają pewne gry matematyczne, przede wszystkim tzw. gry parzystości, w których rozgrywka jest nieskończona.
Pełny opis:	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.
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 …
Efekty uczenia się:	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.
Metody i kryteria oceniania:	Egzamin z przedmiotu jest ustny. Poprzedzony będzie zadaniami domowymi, które umożliwiają podwyższenie oceny z egzaminu ustnego.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.