Algorytmika sieci Petriego
Informacje ogólne
Kod przedmiotu: | 1000-2M20ALP |
Kod Erasmus / ISCED: |
11.303
|
Nazwa przedmiotu: | Algorytmika sieci Petriego |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | angielski |
Rodzaj przedmiotu: | monograficzne |
Założenia (opisowo): | Zakładana jest znajomość algebry liniowej w zakresie przestrzeni i podprzestrzeni liniowych, rozwiązywania układów równań liniowych. |
Tryb prowadzenia: | w sali |
Skrócony opis: |
Wykład dotyczy jednego z podstawowych modeli obliczeń: sieci Petriego (i prawie równoważnego modelu Vector Addition Systems with States - VASS) oraz jego ograniczeń i rozszerzeń. Zamierzam przedstawić ciekawe matematycznie konstrukcje algorytmiczne i dolne granice złożoności. Skupię się na jednym z centralnych problemów: problemie osiągalności, przy czym nie będzie on jedynym tematem. Głównym celem przedmiotu jest przedstawienie aktualnego stanu badań w dziedzinie z naciskiem na najciekawsze konstrukcje używające oryginalnych matematycznie narzędzi. |
Pełny opis: |
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) |
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. |
Efekty uczenia się: |
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. |
Metody i 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. |
Właścicielem praw autorskich jest Uniwersytet Warszawski.