Uniwersytet Warszawski - Centralny System Uwierzytelniania

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:	Grupa przedmiotów obieralnych dla informatyki magisterskiej- specjalność Automaty, logika, złożoność Przedmioty obieralne dla informatyki i ML Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne:	6.00 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
Wymagania (lista przedmiotów):	Języki, automaty i obliczenia 1000-214bJAO
Założenia (lista przedmiotów):	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 pisemny. Poprzedzony będzie dwoma seriami zadań domowych. W razie chęci poprawienia oceny możliwy będzie egzamin ustny.

Zajęcia w cyklu "Semestr zimowy 2025/26" (w trakcie)

Okres:	2025-10-01 - 2026-01-25	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN WYK CW WT ŚR CZ PT
Typ zajęć:	Ćwiczenia, 30 godzin więcej informacji Wykład, 30 godzin więcej informacji
Koordynatorzy:	Michał Skrzypczak
Prowadzący grup:	Michał Skrzypczak
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Przedmiot - Egzamin Wykład - Egzamin

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