wykład

ćwiczenia

USOS

Ogłoszenia:

• Zamiast wykładu - lektura (6.02.2014).
• Pojawiła się pierwsza seria zadań (14.03.2014).
• Zmiana terminow spotkań (10.04.2014).
• Pojawiła się druga seria zadań (10.04.2014).
• Pojawiła się trzecia seria zadań (9.05.2014).
• Termin egzaminu ustnego: 6.06, zadania wywiesze 4.06 wieczorem (23.05.2014).
• Zadania egzaminacyjne wywieszone -- powodzenia! (4.06.2014).

Egzamin:

• piątek 6 czerwca 2014, godz. 10-12, s. 5730
• zadania
• zapisy na egzamin ustny

Zadania domowe:

• seria 1
• seria 2
• seria 3

Tematy:

• 28.02: wstęp, motywacja, modele i problemy algorytmiczne, granice rozstrzygalności
  
  
• 14.03: sieci Petriego: interakcja współbieżności, zależności i konfliktu; równoważne modele; przegląd podklas siec Petriego; przegląd problemów decyzyjnych
  • W. Reisig, Sieci Petriego, rozdz. 2, 5
  • W. Reisig, G. Rozenberg (ed) Lectures on Petri Nets I: Basic Models, rozdz. 1 (fragmenty)
  
  
• 28.03: algebra procesów CCS: współbieżność i komunikacja; bisymulacja jako semantyczna równoważność procesów; nierozstrzygalność algebry CCS
  • R. Milner, Communication and Concurrency, rozdz. 1, 2, 4, 5 (u mnie na półce, wersja elektroniczna jest tutaj)
  • Notatki z wykładu Wybrane zagadnienia teorii procesów współbieżnych, rozdz. 1, 2, 4-7
  • Bergstra, J., Ponse, A., Smolka, S., ed. Handbook of Process Algebra, rozdz. 1 (u mnie na półce)
  
  
• 25.04: dolna granica dla analizy sieci ogólnych, złożoność problemów decyzyjnych dla sieci elementarnych
  • J. Esparza, M. Nielsen, Decidability issues for Petri nets — a survey
  • J. Esparza, Decidability and complexity of Petri net problems — an introduction, czesc II
  
  
• 9.05: algorytm dla problemu pokrywalności; wzmianka nt. problemu osiągalności dla sieci Petriego; zbiory semi-liniowe; osiągalność dla sieci symetrycznych
  • J. Esparza, Decidability and complexity of Petri net problems — an introduction
  • C. Rackoff, The covering and boundedness problems for vector addition systems
  • J. Leroux, Vector Addition Systems Reachability Problem (A Simpler Solution)
  
  
• 23.05: algorytmy dla (podklas) sieci Petriego i algebry CCS: problem osiągalności i równoważności dla procesów bezkontekstowych
  • J. Esparza, Petri nets, commutative context-free grammars, and Basic Parallel Processes
  • Bergstra, J., Ponse, A., Smolka, S., ed. Handbook of Process Algebra, rozdz. 9 (u mnie na półce)
  • J. Srba, Roadmap of infinite results
  
  
• 30.05/6.06: egzamin

Zaliczenie:

• aby zaliczyć przedmiot należy uzyskać jedną trzecią punktów z zadań oraz zdać egzamin
• punkty uzyskane z zadań będą stanowić jedną trzecią oceny końcowej, a ocena z egzaminu dwie trzecie