Uniwersytet Warszawski, Wydział Nauk Ekonomicznych - Centralny System Uwierzytelniania
Strona główna

Automaty nieskończone

Informacje ogólne

Kod przedmiotu: 1000-2M22AN
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 nieskończone
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obieralne dla informatyki
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

Rodzaj przedmiotu:

monograficzne

Wymagania (lista przedmiotów):

Języki, automaty i obliczenia 1000-214bJAO

Założenia (lista przedmiotów):

Złożoność obliczeniowa 1000-218bZO

Skrócony opis:

Algorytmiczna analiza automatów o nieskończenie wielu stanach: automaty ze stosem, sieci Petriego, automaty nad alfabetem nieskończonym.

Pełny opis:

Nieskończoność przestrzeni stanów jest wszechobecna w informatyce teoretycznej, prowadzi do niej np. nieograniczona głębokość stosu czy nieograniczona współbieżność. Często lepiej rozważać zbiór stanów, który jest nieskończony, niż sztucznie go ograniczać do zbioru skończonego ale astronomicznie wielkiego. Tak jest w m.in. przypadku automatów ze stosem, automatów rejestrowych, automatów czasowych czy sieci Petriego. Mimo nieskończonej przestrzeni stanów, istnieją tu algorytmy rozstrzygające istotne problemy decyzyjne, takie jak osiągalność albo równoważność. Przyjrzymy się najciekawszym problemom w tej dziedzinie, w szczególności rozstrzygalności osiągalności w sieciach Petriego. Wspomnimy też o ciekawych problemach, które pozostają wciąż otwarte.

Opowiemy o tematach wybranych spośród:

1. Zbiory semiliniowe, ich własności i zastosowania

2. Techniki oparte o wqo

3. Problemy decyzyjne dla 1-wymiarowych VASS

4. Stratne automaty licznikowe

5. Pokrywalność i osiągalność w VASS

6. Systemy odwracalne

7. Równoważności w systemach nieskończonych

8. Równoważność językowa deterministycznych automatów ze stosem

9. Separowalność w systemach nieskończonych

10. Automaty z rejestrami lub z zegarami

Literatura:

Świeża literatura naukowa. W szczególności:

J. Fearnley, M. Jurdziński, Reachability in two-clock timed automata is PSPACE-complete, ICALP 2013.

Petr Jancar, Bisimulation Equivalence of 1st Order Grammars, ICALP 2014.

Roadmap of infinite results, http://www.brics.dk/~srba/roadmap/roadmap.pdf

S. Lasota, I. Walukiewicz, Alternating Timed Automata. ACM Transactions on Computational Logic 9(2), 2008.

W. Czerwiński, Ł. Orlikowski, Reachability in Vector Addition Systems is Ackermann-complete, FOCS 2021.

S.Lasota, VASS reachability in three steps, 2020.

Jan A. Bergstra, Alban Ponse, and Scott A. Smolka, ed., Handbook of Process Algebra, Elsevier, 2001.

W. Czerwinski, S. Lasota, R. Meyer, S. Muskalla, K. N. Kumar, P. Saivasan:

Regular Separability of Well-Structured Transition Systems. CONCUR 2018

Efekty uczenia się:

Wiedza

Student pogłębia wiedzę o klasycznych zastosowaniach teorii automatów.

Umiejętności

Student umie rozpoznać granice obliczalności różnych wariantów modeli.

Student potrafi modelować różne problemy za pomocą odpowiednich automatów.

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

Metody i kryteria oceniania:

Zadania gwiazdkowe i egzamin ustny.

W przypadku zaliczania przedmiotu przez doktoranta, dodatkowym elementem zaliczenia będzie rozwiązanie przynajmniej jednego zadania z gwiazdką bądź zapoznanie się z oryginalnym, będącym blisko aktualnego frontu badań, artykułem naukowym i rozmowa z wykładowcą na temat tego artykułu.

Zajęcia w cyklu "Semestr zimowy 2024/25" (jeszcze nie rozpoczęty)

Okres: 2024-10-01 - 2025-01-26
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Wojciech Czerwiński, Sławomir Lasota
Prowadzący grup: Wojciech Czerwiński, Sławomir Lasota
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, Wydział Nauk Ekonomicznych.
ul. Długa 44/50
00-241 Warszawa
tel: +48 22 55 49 126 https://www.wne.uw.edu.pl/
kontakt deklaracja dostępności mapa serwisu USOSweb 7.0.4.0-3 (2024-06-10)