Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Teoria współbieżności
Tok studiów:
2014/2015
Kod:
IIN-1-407-s
Wydział:
Informatyki, Elektroniki i Telekomunikacji
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka
Semestr:
4
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
prof. dr hab. inż. Schaefer Robert (schaefer@agh.edu.pl)
Osoby prowadzące:
Krótka charakterystyka modułu

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Ma wiedze w zakresie podstawowych modeli współbieżności oraz ich własności, jak również co do podstawowych własności aplikacji współbieżnych. IN1A_W01 Egzamin
M_W002 Ma wiedze w zakresie podstawowych przykładów i zadań podlegających modelowaniu matematycznemu współbieżności oraz zna ich rozwiązania IN1A_W02 Egzamin
M_W003 Ma uporządkowaną wiedzę w zakresie podstaw budowy narzędzi do projektowania, implementacji i analizy systemów współbieżnych IN1A_W04 Egzamin
M_W004 Ma szczególną wiedze w zakresie modelowania systemów współbieżnych działających w środowisku rozproszonym IN1A_W10 Kolokwium
Umiejętności
M_U001 Potrafi samodzielnie pozyskiwać wiadomości z literatury w zakresie modeli współbieżności oraz środowisk programowania systemów współbieżnych IN1A_U01 Zaliczenie laboratorium
M_U002 Potrafi wykorzystać modele współbieżności dla analizy i projektowania systemów IT IN1A_U07 Egzamin
M_U003 Potrafi oceniać istniejące oprogramowanie działające współbieżnie i równolegle. IN1A_U07 Zaliczenie laboratorium
M_U004 Potrafi posłużyć się odpowiednim środowiskiem programistycznym lub zintegrowanym dla implementacji symulacji modeli współbieżności IN1A_U08 Zaliczenie laboratorium
Kompetencje społeczne
M_K001 a świadomość i potrzebę stałego dokształcania się w zakresie modeli nowych modeli współbieżności i ich zastosowań w IT IN1A_K01 Zaliczenie laboratorium
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Ma wiedze w zakresie podstawowych modeli współbieżności oraz ich własności, jak również co do podstawowych własności aplikacji współbieżnych. + - - - - - - - - - -
M_W002 Ma wiedze w zakresie podstawowych przykładów i zadań podlegających modelowaniu matematycznemu współbieżności oraz zna ich rozwiązania + - - - - - - - - - -
M_W003 Ma uporządkowaną wiedzę w zakresie podstaw budowy narzędzi do projektowania, implementacji i analizy systemów współbieżnych + - - - - - - - - - -
M_W004 Ma szczególną wiedze w zakresie modelowania systemów współbieżnych działających w środowisku rozproszonym + - - - - - - - - - -
Umiejętności
M_U001 Potrafi samodzielnie pozyskiwać wiadomości z literatury w zakresie modeli współbieżności oraz środowisk programowania systemów współbieżnych - - + - - - - - - - -
M_U002 Potrafi wykorzystać modele współbieżności dla analizy i projektowania systemów IT - - + - - - - - - - -
M_U003 Potrafi oceniać istniejące oprogramowanie działające współbieżnie i równolegle. - - + - - - - - - - -
M_U004 Potrafi posłużyć się odpowiednim środowiskiem programistycznym lub zintegrowanym dla implementacji symulacji modeli współbieżności - - + - - - - - - - -
Kompetencje społeczne
M_K001 a świadomość i potrzebę stałego dokształcania się w zakresie modeli nowych modeli współbieżności i ich zastosowań w IT + - - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

  1. Podstawy matematyczne teorii współbieżności, systemy relacyjne i PO-sety, łańcuchy, lemat K-Z i pewnik wyboru (2 godź.).
  2. Model Lamporta, definicje programowania seryjnego i współbieżnego (2 godź.).
  3. Warunek stopu i częściowa poprawność, żywotność, bezpieczeństwo i sprawiedliwość (2 godź.).
  4. Kontekst implementacyjny przetwarzania współbieżnego, narzędzia systemu operacyjnego, środowiska wieloprocesorowe, środowiska message-passing, środowiska wirtualne, systemy wieloagentowe (2 godź.).
  5. Ślady Dekerta-Mazurkiewicza, postać normalna Foaty, graf zależności (2 godź.).
  6. Systemy rozproszone modelowane przez ślady, komunikacja FIFO i CO, twierdzenie Charon o jedyności reprezentacji, szeregowania sub-optymalne dla śladów (2 godź.).
  7. Problem czasu w systemach rozproszonych, czas ścienny, algorytm poprawiania czasu lokalnego Lamporta, czas wektorowy (2 godź.).
  8. Elementy CSP – współbieżne wykonanie procesów (2 godź.).
  9. Alternatywa dozorowana, tablice dozorów, konstrukcja pętli, równoległe wykonanie instrukcji, komunikacja blokująca, spotkania, przykłady (2 godź.).
  10. Sieci Petri, wiadomości podstawowe, sieci miejsc i tranzycji, sieci uogólnione (2 godź.).
  11. Żywotność, sprawiedliwość i bezpieczeństwo sieci Petri (2 godź.).
  12. Reprezentacja algebraiczna, niezmienniki miejsc i tranzycji (2 godź.).
  13. Grafy osiągalności, interpretacja warunku żywotności, algorytmy znajdowania blokad i pułapek (2 godź.).
  14. Elementy analizy systemów z ograniczeniami czasowymi, Time-Restricted Petri Nets (2 godź.).
  15. Podsumowanie korzyści i możliwości teoretycznej analizy współbieżności systemów na etapie projektowania i śledzenia. Inne modele współbieżności – modele lingwistyczne (2 godź.).

Ćwiczenia laboratoryjne:

  1. Zapoznanie się ze współbieżnością procesów z wykorzystaniem mechanizmu wątków w Javie; tworzenie wątków, architektura JVM, cykl życia i stany wątku, szeregowanie wątków (5 godź.).
  2. Zapoznanie się z monitorami w Javie: mechanizm działania, wykorzystanie do zapewnienia synchronizacji przy dostępie do zasobów. Zapoznanie się z problemem wzajemnego wykluczania: zasób, sekcja krytyczna, operacje niepodzielne, semafory, operacje P i V. Zapoznanie się z problemem synchronizacji z rozwiązaniem wykorzystującym mechanizm zamków (monitorów): operacje na zamku, zmienne warunkowe, operacje await/Signac (5 godź.).
  3. Zapoznanie się z problemem dostępu do elementów struktur danych; drobnoziarniste operacje na strukturach danych. Zapoznanie się z problemem synchronizacji współbieżnych struktur danych. Zapoznanie się z problemem synchronizacji współbieżnych procesów w systemach z rozproszoną pamięcią (5 godź.).
  4. Zastosowanie mechanizmów komunikacji asynchronicznej oraz dopasowywania wzorca komunikatów w języku Erlang do zaimplementowania semafora licznikowego oraz rozwiązania klasycznego problemu współbieżnego czytelników i pisarzy. Zastosowanie mechanizmów komunikacji asynchronicznej oraz dopasowywania wzorca komunikatów w języku Erlang do zaimplementowania semafora licznikowego oraz rozwiązania klasycznego problemu współbieżnego czytelników i pisarzy (5 godź.).
  5. Zapoznanie z zastosowaniem teorii śladów. Zapoznanie z modelowaniem zdarzeń jako produkcji w gramatyce. Zapoznanie z zastosowaniem teorii śladów w celu projektowania współbieżnych algorytmów algebry liniowej. Zapoznanie z nowoczesnymi algorytmami współbieżnymi rozwiązywania układów równań liniowych. Szeregowanie wątków zgodnie z klasami Foaty (5 godź.).
  6. Zapoznanie z zastosowaniem teorii sieci Petrii na przykładzie modelowania algorytmu generacji siatek elementów trójkątnych. Zapoznanie z zastosowaniem gramatyki grafowej do modelowania wątków. Modelowanie algorytmu generacji siatek elementów prostokątnych. Zapoznanie ze środowiskiem programu pipe2 (5 godź.).

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 100 godz
Punkty ECTS za moduł 4 ECTS
Udział w wykładach 28 godz
Samodzielne studiowanie tematyki zajęć 29 godz
Udział w ćwiczeniach laboratoryjnych 28 godz
Przygotowanie sprawozdania, pracy pisemnej, prezentacji, itp. 15 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:
  1. Aby uzyskać pozytywną ocenę końcową niezbędne jest uzyskanie pozytywnej oceny z ćwiczeń oraz egzaminu.
  2. Obliczamy średnią arytmetyczną z ocen zaliczenia i egzaminów uzyskanych we wszystkich terminach.
  3. Wyznaczmy ocenę końcową na podstawie zależności:
    if sr>4.75 then OK:=5.0 else
    if sr>4.25 then OK:=4.5 else
    if sr>3.75 then OK:=4.0 else
    if sr>3.25 then OK:=3.5 else OK:=3
  4. Jeżeli pozytywną ocenę z ćwiczeń i egzaminu uzyskano w pierwszym terminie oraz ocena końcowa jest mniejsza niż 5.0 to ocena końcowa jest podnoszona o 0.5
Wymagania wstępne i dodatkowe:

Algebra

Zalecana literatura i pomoce naukowe:
  1. Roscoe A., W.; The Theory and Practice of Concurrency. Prentice Hall 1998.
  2. Weiss Z., Gruźlewicz T.; Programowanie współbieżne i rozproszone w przykładach i zadaniach. WNT 1994.
  3. Starke P., H.; Sieci Petri, podstawy, zastosowania, teoria. PWN 1987.
  4. Iszkowski W., Maniecki M.; Programowanie współbieżne. WNT 1982.
  5. Charron B, Delporte-Gallet C, Fauconnier H; How to model a distributed computation, Instute Blaise Press, Paris, 1993.
  6. Diekert V., Rosenberg G. (eds.); The Book of Traces. World Scientific 1995.
  7. Tsai J.J.P., Yaodong Bi, Yang S.J.H., Smith R.,A.,W.; Distributed Real-Time Systems, John Willey 1996.
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak