Algorytmiczna teoria współbieżności

Informacje ogólne

Kod przedmiotu:	1000-2M13ATW
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:	Algorytmiczna teoria współbieżności
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) 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
Rodzaj przedmiotu:	monograficzne
Założenia (opisowo):	Charakter wykładu będzie przypominał JAiO, zatem dobra znajomość tego przedmiotu wydaje się kluczowa. Przydatny (choć nieobowiązkowy) może być wcześniejszy kontakt z programowaniem współbieżnym.
Skrócony opis:	Tworzenie systemów współbieżnych jest trudną sztuką, dlatego od zarania informatyki rozważa się różne modele matematyczne takich systemów oraz rozwija się metody ich analizy. Tematem wykładu będą algorytmy dla modeli systemów współbieżnych. Przykłady modeli to sieci Petriego i algebra procesów CCS. Przykładowe problemy: czy system się zatrzymuje? czy stan o danej własności jest osiągalny? czy dane dwa systemy są równoważne?
Pełny opis:	1.Wstęp, motywacja, przegląd modeli problemów algorytmicznych, granice rozstrzygalności (1 wykład). 2.Sieci Petriego: interakcja współbieżności, zależności i konfliktu; związek z teorią śladów (2 wykłady). 3.Dolna granica złożoności EXPSPACE dla analizy sieci Petriego (1 wykład) 4.Drzewa pokrycia, funkcje słabo obliczalne przez sieci Petriego (1 wykład) 5.Algebra procesów CCS: współbieżność i komunikacja (2 wykłady) 6.Bisymulacja jako semantyczna równoważność procesów (2 wykłady). 7.Nierozstrzygalność algebry CCS (1 wykład) 8.Problem osiągalności dla sieci Petriego (1 wykład) 9.Algorytmy dla sieci Petriego o ,,rozsądnej'' złożoności (1 wykład) 10.Wielomianowe algorytmy dla podklas sieci Petriego i algebry CCS: sieci ograniczone, procesy bezkontekstowe, automaty z jednym licznikiem (2 wykłady) 11.Wzmianka o innych modelach: automaty czasowe, stratne systemy kolejkowe (1 wykład)
Literatura:	1.Handbook of Process Algebra. Elsevier 2001. 2. R. Milner, Communication and Concurrency. Prentice-Hall 1995. 3.J. Esparza, M. Nielsen, Decidability Issues for Petri Nets - a survey. Bulletin of the EATCS 52:244-262 (1994). 4.J. Srba, Roadmap of Infinite Results. Bulletin of the EATCS 78: 163-175, 2002.
Efekty uczenia się:	Wiedza 1. Ma usystematyzowaną wiedzę w zakresie zjawisk zachodzących w systemach współbieżnych (K_W04, K_W05). 2. Ma ogólną wiedzę w zakresie modeli systemów współbieżnych i ich wzajemnej relacji (K_W02, K_W04, K_W05). 3. Ma podstawową wiedzę w zakresie złożoności obliczeniowej podstawowych problemów weryfikacyjnych (K_W05). 4. Rozumie korzyści płynące z formalnego modelowania zagadnień współbieżności oraz ograniczenia modeli formalnych (K_W02). Umiejętności 1. Potrafi formalizować opis systemu współbieżnego w wybranym modelu (K_U02, K_U06). 2. Potrafi opisać wybrane zagadnienia współbieżności w sposób zrozumiały dla niespecjalisty (K_U12). Kompetencje 1. Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia, w tym zdobywania wiedzy pozadziedzinowej (K_K01). 2. Potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania (K_K02).
Metody i kryteria oceniania:	Albo zaliczenie pisemne (przygotowanie notatek z któregoś z wykładów) albo egzamin ustny.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.