Algorytmika sieci Petriego 1000-2M20ALP
Plan przedmiotu będzie wyborem z następujących tematów, liczba wykładów
orientacyjna. Być może wykład zostanie wzbogacone o dodatkowe, ciekawe
wyniki.
1. Automaty z jednym licznikiem – problemy osiągalności, ograniczonej osiągalności i uniwersalności (2-3 wykłady)
2. Problemy ograniczoności i pokrywalności w VASSach (2 wykłady)
3. Lemat Steinitza i Z-VASSy (1 wykład)
4. Zbiory semiliniowe i dwuwymiarowe VASSy (2 wykłady)
5. Rozstrzygalność problemu osiągalności w VASSach (2 wykłady)
6. Niskowymiarowe VASSy (2 wykłady)
7. ExpSpace-trudność i Tower-trudność problemu osiągalności (2 wykłady)
8. Automaty z licznikiem i stosem (1 wykład)
9. Rozgłęzione VASSy – BVASSy (1 wykład)
10. Problem separowalności w podklasach VASSów (2 wykłady)
Rodzaj przedmiotu
Tryb prowadzenia
Założenia (opisowo)
Efekty kształcenia
Studenci poznają techniki projektowania i analizy asynchronicznych systemów współbieżnych. Umieją stosować metody matematyczne do analizy systemów (K_W02,K_U01). Mają wiedzę dotyczącą złożoności obliczeniowej oraz kombinatorycznej różnorodności problemów osiągalności w sieciach Petri.
Kryteria oceniania
W zależności od liczby studentów: końcowy egzamin ustny lub pisemny. W trakcie przedmiotu dostępne będą zadania z gwiazdką, których rozwiązanie może pozytywnie wpłynąć na ocenę końcową. W tym roku odbędzie się egzamin ustny, który będzie dotyczył głównie teoretycznych zagadnień poruszanych na wykładzie.
Literatura
- J. Esparza: Decidability and Complexity of Petri Net Problems - An Introduction.1996
- M. Blondin, A. Finkel, S. Goller, C. Haase, P. McKenzie, Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete, 2014
- J. Leroux, G. Sutre, P. Totzke, On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension, 2015
- inne współczesne artykuły naukowe dotyczące ostatnich osiągnięć związanych z sieciami Petri.
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: