Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Języki, automaty i obliczenia II

Informacje ogólne

Kod przedmiotu: 1000-2M15ZTA Kod Erasmus / ISCED: 11.3 / (0612) Database and network design and administration
Nazwa przedmiotu: Języki, automaty i obliczenia II
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

monograficzne

Skrócony opis:

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.

Pełny opis:

• 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.

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.

Efekty uczenia się:

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

Zajęcia w cyklu "Semestr zimowy 2020/21" (w trakcie)

Okres: 2020-10-01 - 2021-01-31
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Sławomir Lasota
Prowadzący grup: Sławomir Lasota, Radosław Piórkowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.