Języki, automaty i obliczenia II

monograficzne

Automaty nad słowami nieskończonymi, drzewami i innymi strukturami wejściowymi. Niestandardowe mechanizmy kontroli: automaty ważone/probabilistyczne, stratne, współbieżne, czasowe. Związki pomiędzy automatami, grami i logikami. Algorytmiczna (nie)rozstrzygalność problemów decyzyjnych.

• Automaty na słowach nieskończonych, algorytm determinizacji.

• Gry nieskończone, determinacja skończenie-pamięciowa.

• Automaty a głębokość gwiazdkowa wyrażeń regularnych.

• Automaty na drzewach skończonych i nieskończonych.

• Rozstrzygalność monadycznej logiki drugiego rzędu na drzewach nieskończonych.

• Algorytmy na grafach o ograniczonej szerokości drzewiastej.

• Automaty modelujące obliczenia współbieżne: sieci Petriego.

• Maszyny stratne: rozstrzygalność przy użyciu dobrych quasi-porządków (ang. wqo).

• Automaty uwzględniające upływ czasu: automaty czasowe.

• Automaty probabilistyczne/ważone: rozstrzygalność problemu równoważności.

• Automaty wielomianowe: rozstrzygalność problemu równoważności przy użyciu twierdzenia Hilberta o bazie.

• Algorytm uczenia automatów skończonych.

• Funkcje obliczalne przez automaty skończone.

• Przykłady zaskakująco prostych problemów nierozstrzygalnych. Stopnie nierozstrzygalności.

• M. Bojańczyk, W.Czerwiński, An automata toolbox, https://www.mimuw.edu.pl/~bojan/paper/automata-toolbox-book, 2018.

• J. E. Hopcroft, R. Motwani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, Warszawa 2005.

• Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.

Wiedza

Student pogłębia wiedzę o klasycznych zagadnieniach obliczalności i poznaje kilka gałęzi współczesnej zaawansowanej teorii automatów.

Umiejętności

Student potrafi przechodzić pomiędzy różnymi reprezentacjami języków regularnych ze świadomością ograniczeń złożonościowych.

Student potrafi modelować proste własności systemów informatycznych za pomocą automatów, dobierając odpowiedni typ i mechanizm kontroli.

Student nabywa wprawy w rozpoznawaniu problemów nierozstrzygalnych i potrafi konstruować odpowiednie redukcje.

Kompetencje

Student rozumie narzędzia matematyczne wypracowane we współczesnej teorii automatów i potrafi z nich korzystać zarówno w samej informatyce, jak i w jej zastosowaniach

Egzamin ustny. Dodatkowo, możliwe podwyższenie oceny dzięki rozwiązaniu zadań gwiazdkowych. Każde zadanie warte jest 1 podzielone przez liczbę  studentów, którzy prawidłowo je rozwiązali.

Dla doktorantów: obowiązkowe wzięcie udziału w rozwiązywaniu zadań gwiazdkowych, albo zapoznanie się z najnowszą literaturą.