Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

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.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.3.0-2b06adb1e (2024-03-27)