Języki, automaty i obliczenia II 1000-2M15ZTA
• 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.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
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
Kryteria oceniania
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ą.
Literatura
• 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.
Uwagi
|
W cyklu 2024Z:
Zajęcia w grupie 2 odbywają się po angielsku. |
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: