Links und Funktionen
Sprachumschaltung
Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2020/21 / Algorithmik und Komplexität: Prinzipien, Algorithmen und Modelle der Nebenläufigen Programmierung
Inhaltsbereich

Algorithmik und Komplexität: Prinzipien, Algorithmen und Modelle der Nebenläufigen Programmierung

Vorlesung, 3-std., Mi 10-12, Fr 10-12, Sabel; Übungen 2-std., Di 16-18, Sabel
Inhalt | Organisation | Zeit und Ort | Material | Klausur 

Aktuelles

  • Stand vom 25.01.2021: Für die Prüfung am 24.02.2021 (ursprünglich als Präsenzklausur geplant) wird aufgrund der aktuellen Corona-Lage zur Zeit die Möglichkeit einer Online-Prüfung als Online-Hausarbeit geprüft, daher ist die Anmeldung noch nicht geöffnet.
  • Online oder Präsenz? Vorlesung und Übung finden online (virtuell) statt. Die Vorlesung findet asynchron statt (d.h. als vorab aufgezeichnete ScreenCasts), während die Übung synchron (“live”) via Zoom stattfindet.

  • Für Fragen, Anregungen und Diskussionen zur Veranstaltung kann der Zulip-Chat des Instituts für Informatik im Stream TCS-20W-PAMNP-VL benutzt werden.

  • Eine Anmeldung zur Veranstaltung im Uni2work ist für die Teilnahme erforderlich.

Inhalt

In der Veranstaltungen werden die folgenden Themen behandelt.

  • Grundlegende Probleme der Nebenläufigen Programmierung und deren algorithmische Lösung, insbesondere Synchronisation und wechselseitiger Ausschluss bei verschiedenen Annahmen über Speicheroperationen
  • Konsensus und das Konsensusproblem
  • gebräuchliche Konstrukte der Nebenläufigen Programmierung;
  • Zugriff auf mehrere Ressourcen, Deadlock-Verhinderung und Deadlock-Vermeidung
  • moderne Ansätze zur nebenläufigen Programmierung wie transaktionaler Speicher, Tuple-Spaces, etc.
  • Nebenläufige Programmierung in modernen Programmiersprachen wie z.B. Java und Haskell und evtl. weitere Programmiersprachen.
  • Semantische Modelle nebenläufiger Programmiersprachen insbesondere der pi-Kalkül als Message-Passing-Modell und der CHF-Kalkül als Shared-Memory-Modell.


Organisation

  • Umfang: 3+2 Semesterwochenstunden (6 ECTS für Modul "Algorithmik und Komplexität", kann als Vertiefende Themen im Bachelorstudiengang angerechnet werden)
  • Vorlesung und Übung:  Prof.Dr. David Sabel
  • Prüfung: wird noch bekannt gegeben

Zeit und Ort (geplant)

VeranstaltungZeitOrtBeginn
Vorlesung Mi 10-12 Uhr Online 04. November
Vorlesung Fr 10-12 Uhr Online 06. November
Übung Di, 16-18 Uhr Online 10. November

Protokoll

Da die Vorlesung trotz der zwei wöchentlichen Vorlesungstermine insgesamt nur den Umfang von 3 SWS hat, findet die Vorlesung nicht an allen Freitagsterminen statt. Der Zeitplan für die Vorlesungen ist unten angegeben. Die Übungen finden durchgehend wöchentlich statt.

Datum
Inhalte
1. 04. November 2020 Organisatorisches, Einführung, Motivation,
Begriffe der Nebenläufigen Programmierung
2. 06. November 2020 Das Mutual-Exclusion-Problem und Lösungen für 2 Prozesse
3. 11. November 2020 Das Mutual-Exclusion-Problem bei n Prozessen
4. 18. November 2020 Drei Komplexitätsresultate zum Mutual-Exclusion-Problem, stärkere Speicherprimitive
5. 20. November 2020 Mutual-Exclusion-Algorithmus mit Test-and-set-bit, Ticket-Algorithmus, 
MCS-Queue-Algorithmus, das Konsensusproblem und die Konsensuszahl
6. 25. November 2020 Erweitertes Prozessmodell, Semaphore, Semaphore in Java,
Anwendungsbeispiele mit Semaphore
7. 02. Dezember 2020 Weitere Anwendungsbeispiele, Semaphore in Java, Monitore
8. 04. Dezember 2020 Formale Modellierung der Condition Variablen bei Monitoren,
Anwendungsbeispiele mit Monitoren, Monitore und Java, Kanäle (Einleitung)
9. 09. Dezember 2020 Synchrone Kanäle und Anwendungen, Programmierung in Go,
Tuple Spaces (das Linda-Modell)
10. 16. Dezember 2020 Anwendungen mit Tuple Spaces, Deadlocks bei mehreren Ressourcen,
Deadlock-Behandlung, Notwendige Bedingungen für einen Deadlock,
Deadlock-Verhinderung, 2-Phasen-Sperrprotokoll mit und ohne Time-Stamping
11. 18. Dezember 2020 Total-Order-Theorem, Deadlock-Vermeidung, Bankier-Algorithmus,
Software Transactional Memory (Einleitung und Übersicht)
12. 23. Dezember 2020 Software Transactional Memory: Eigenschaften von STM-Systemen,
Korrektheitsbegriffe, der TL2-Algorithmus
13. 13. Januar 2021 Ein- und Ausgabe in der funktionalen Programmiersprache Haskell, nebenläufiges
Programmieren mit Concurrent Haskell
14. 15. Januar 2021 Concurrent Haskell: Implementierung von Kanälen mit MVars, nichtdeterministische
Operationen, Futures, die Async-Bibliothek
15. 20. Januar 2021 Software Transactional Memory in Haskell
16. 27. Januar 2021 Semantik: Einführung und der Lambda-Kalkül als Beispiel
17. 29. Januar 2021 Der Pi-Kalkül: Syntax und Semantik des synchrones pi-Kalküls
18. 03. Februar 2021 Der Pi-Kalkül: Asynchroner Pi-Kalkül, Polyadischer Pi-Kalkül,
Rekursion statt Replikation
19. 10. Februar 2021

Verhaltensgleichheit im Pi-Kalkül, der CHF-Kalkül (Einführung)
Fragestunde live ab 11 Uhr in Zoom! (vorgezogen von Freitag)
20. 12. Februar 2021 Der CHF-Kalkül (halbe Vorlesung)

Klausur

Informationen zur Klausur werden hier bekannt gegeben.
Aktueller Stand om 25.01.2021: Für die Prüfung am 24.02.2021 (ursprünglich als Präsenzklausur geplant) wird aufgrund der aktuellen Corona-Lage zur Zeit die Möglichkeit einer Online-Prüfung als Online-Hausarbeit geprüft, daher ist die Anmeldung noch nicht geöffnet.

Der Termin für die Nachholklausur (Zeitraum 21.3-01.04.2021) wird noch geplant.


 

Material

Material und Übungsblätter erhalten Sie per Uni2work.
Zum Backup ist das wesentliche Material auch nochmal hier aufgeführt:


Artikelaktionen

Funktionsleiste