Algorytmika sieci Petriego
Wykłady
- Wykład 1 (wprowadzenie, osiągalność dla OCNów, wstęp do wqo): notatki, nagranie
- Wykład 2 (wstęp do wqo, tw. Ramseya, uniwersalność 1-VASSów, lemat Königa, szybko rosnące funkcje): notatki, nagranie
- Wykład 3 (równoważność VASów i VASSów, roztrzygalność skończoności i pokrywalności): notatki, nagranie
- Wykład 4 (pokrywalność w ExpSpace, osiągalność Z-VASSów, małe rozwiązania układów równań): notatki, nagranie
- Wykład 5 (rozwiązania układów równań c.d., osiągalność w VASSach - część I): notatki z równań, notatki z osiągalności, nagranie
- Wykład 6 (osiągalność w VASSach - część II): notatki, nagranie
- Wykład 7 (osiągalność w VASSach - część III): notatki, nagranie
- Wykład 8 (historia badań, ExpSpace-trudność osiągalności): notatki, nagranie
- Wykład 9 (nieskowymiarowe VASSy, dwa przykłady): notatki, nagranie
- Wykład 10 (Tower-trudność osiągalności): notatki, nagranie
- Wykład 11 (semiliniowość relacji osiaganości w 2-VASSach): notatki, nagranie
- Wykład 12 (pokrywalność dla 1-GVASów): notatki, nagranie
- Wykład 13 (regularna separowalność VASSów): notatki, nagranie
Dodatkowe materiały
- moje notatki o problemie pokrywalności w ExpSpace
- bardzo dobre notatki Sławomira Lasoty nt osiągalności w VASSach
Plan przedmiotu (orientacyjny)
- Automaty z jednym licznikiem – problemy osiągalności, ograniczonej osiągalności i uniwersalności (2 wykłady)
- Problemy ograniczoności i pokrywalności w VASSach (1 wykład)
- Lemat Steinitza i Z-VASSy (1,5 wykładu)
- Rozstrzygalność problemu osiągalności w VASSach (2,5 wykładu)
- Historia badań i ExpSpace-trudność problemu pokrywalności (1 wykład)
- Niskowymiarowe VASSy (1 wykład)
- Tower-trudność problemu osiągalności (1 wykład)
- Zbiory semiliniowe i dwuwymiarowe VASSy (1 wykład)
- Automaty z licznikiem i stosem (1 wykład)
- Regularna separowalność automatów z jednym licznikiem (1 wykład)
Zadania z gwiazdką
Planowane są dwie serie zadań z gwiazdką. Dostępna jest pierwsza seria zadań z gwiazdką.
- pierwsza seria zadań z gwiazdką (termin to 18.12.2020)
- druga seria zadań z gwiazdką (termin to 5.02.2021)
System oceniania
System składa się z dwóch części: egzaminu ustnego oraz zadań z gwiazdką. Jeśli ktoś dostanie z egzaminu ocenę x oraz y punktów z zadań z gwiazdką, to dostaje ocenę x+y zaokrągloną do najbliższej liczby ze zbioru {2, 3, 3.5, 4, 4.5, 5}.
Za każde zadanie z gwiazdką jest jeden punkt, do podziału na osoby, które rozwiązały to zadanie.
Egzamin będzie trwał około 45 minut. Materiał jest podzielony na cztery działy. Każdy wskazuje swój ulubiony dział. Potem losuje się trudniejsze pytanie z ulubionego działu oraz dwa łatwiejsze pytania z pozostałych działów. Lista pytań (z podziałem na łatwe i trudne) będzie znana wcześniej. Za dobre odpowiedzi na 3 pytania dostaje się ocenę 5, na 2 pytania ocenę 4, na 1 pytanie ocenę 3.
Na przykład jeśli ktoś dostanie ocenę 4 z egzaminu, rozwiąże jedno zadanie z gwiazdką rozwiązane przez 4 osoby (1 / 4 = 0.25) oraz drugie zadanie z gwiazdką rozwiązane przez 5 osób (1 / 5 = 0.2), to dostanie 4 + 0.2 + 0.25 = 4.45 zakrąglone do najbliższej oceny, czyli do 4.5.
Podział materiału
Materiały wykładu został podzielony na cztery działy:
- Dział I: technika wqo + pokrywalność + Z-VASSy (wykłady od 1-go do połowy 5-go)
- Dział II: algorytm osiągalności dla VASSów (wykłady od połowy 5-go do 7-go)
- Dział III: dolne ograniczenia + przykłady trudnych VASSów (wykłady od 8-go do 10-go)
- Dział IV: 2-VASSy + VASSy ze stosem + reg-separowalność 1-VASSów
Dział I
Podstawowe pytania:
- Podstawowe pojęcia
- Najkrótszy bieg dla OCN-ów jest sześciennej długości + dowód
- Niekończone twierdzenie Ramseya + dowód
- Lemat Königa + dowód
- Rozstrzygalność skończoności i pokrywalności dla VASSów
- Rozstrzygalność osiągalności w Z-VASSach (zakładając lemat Pottiera)
- Lemat o równoważnych sformułowaniach wqo + dowód
- Twierdzenie Rackoffa o 2-exp biegu + dowód
- Lemat Pottiera o małych rozwiązaniach układów równań + dowód
Dział II
Podstawowe pytania:
- Struktura dowodu
- Definicja uogólnionego VASSa
- Definicja Θ1 oraz Θ2 w uogólnionym VASSie
- Warunek wystarczający dla osiągalności w jednej składowej + dowód
- Krok dekompozycji (co się dzieje gdy Θ1 lub Θ2 nie są spełnione)
- Sprawdzanie, czy Θ1 oraz Θ2 są spełnione
Dział III
Podstawowe pytania:
- 3-VASS o najkrótszym biegu wykładniczym
- Szkic dowodu ExpSpace-trudności osiągalności
- Szkic dowodu Tower-trudności osiągalności
- 4-VASS o najkrótszym biegu podwójnie wykładniczym
- Dowód ExpSpace-trudności
- Dowód Tower-trudności bez kroku z testów wielkości k do testów wielkości k!
- Dowód Tower-trudności: przejście z testów wielkości k do testów wielkości k!
Dział IV
Podstawowe pytania:
- Sformułowanie faktu o semiliniowej relacji osiągalności w 2-VASSach i o Linear Path Schemach
- Rozstrzygalność dla VASSów ze stosem i VASSów z testem na zero: co wiadomo o rozstrzygalnościach
- Szkic dowodu rozstrzygalności reg-separowalności dla 1-VASSów
- Dowód semiliniowości dla 2-VASSów: 3 typy biegów, jak z tego wynika twierdzenie, szkic dowodu dla typów I i III
- Dowód, że istnieje mały certyfikat pokrywalności dla 1-GVASów
- Dowód, że reg-separowalność 1-VASSów A i B jest równoważna rozłączności ich n-aproksymacji