Links und Funktionen
Sprachumschaltung
Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2019/20 / 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., Do 12-14, Fr 10-12, Sabel; Übungen 2-std., Di 16-18, Sabel
Inhalt | Organisation | Zeit und Ort | Material| Klausur 

Aktuelles

  • Nachholprüfungen
    Als Ersatz für die nicht stattgefundene Nachholklausur im letzten Wintersemester werden mündliche Online-Prüfungen angeboten. Details dazu sind im uni2work veröffentlicht.

  • Verschiebung der Nachholklausur am 19.3.

    Die Nachholklausur am 19.3. ist abgesagt und auf einen späteren, noch unbestimmten Zeitpunkt, verschoben, da gemäß der Mitteilung des Bayerischen Staatsministeriums für Wissenschaft und Kunst vom 11.03.2020, studienbegleitende Prüfungen, wann immer das möglich, aufgrund der Ausbreitung des neuen Coronavirus SARS-CoV-2 verschoben werden sollen.

    Wir werden rechtzeitig über Uni2work und auf dieser Webseite zur Veranstaltung über einen neuen Termin informieren.

  • Die Ergebnisse der Klausur vom 18.02.2020 sind im Uni2work veröffentlicht.
    Die Klausureinsicht findet am Freitag 21.02.2020 von 10-12 Uhr in Raum L109 in der Oettingenstr. 67 statt.
    Notenspiegel zur Klausur:

    Note 1.0 1.3 1.7 2.0 2.3 2.7 3.0 3.3 3.7 4.0 5.0
    Anzahl 14 5 5 1 4 3 3 2 3 0 3
    Notenschnitt: 2,09
  • Die Erläuterungen zur Implementierung von STM Haskell und orElse-Auswertungen wurden in Folien und Skript überarbeitet.
  • Der Termin für die Nachhol-Klausur steht fest: 19.03.2020 um 14:00 Uhr
  • Der Termin für die Erst-Klausur steht fest: 18.02.2020 um 10:00 Uhr.
  • Email-Verteiler für die Veranstaltung (geht an David Sabel und David Tellenbach) angelegt:

  • Veranstaltung im Uni2work angelegt
    Ein 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")
  • Vorlesung und Übung:  Prof.Dr. David Sabel
  • Korrektur: David Tellenbach
  • Prüfung: 90-minütige Klausur
  • Email-Verteiler (geht an alle Organisierenden):

 

Zeit und Ort (geplant)

VeranstaltungZeitOrtBeginn
Vorlesung Do, 12-14 HGB, A125 17.10.2019
Vorlesung Fr, 10-12 (zweiwöchig) Leo 13, 3232 18.10.2019
Übung Di, 16-18 Uhr Prof. Huber-Pl 2 (V), Lehrturm V005 22.10.2019

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. Do 16.10.2019 Organisatorisches, Einführung, Motivation,
Begriffe der Nebenläufigen Programmierung
2. Fr 18.10.2019 Modellannahmen (inbes. Interleaving- und Fairness-Annahme),
das Mutual-Exklusion-Problem, Algorithmen von Dekker, Peterson und Kessels
3. Do 24.10.2019 Mutual-Exklusion bei n Prozessen: Lamports (schneller) Algorithmus und
der Bakery-Algorithmus
4. Fr 25.10.2019 Drei Komplexitätsresultate, Stärkere Speicheroperationen
5. Do 31.10.2019 Stärkere Speicheroperationen, Mutual Exklusion Algorithmen mit stärkeren
Speicheroperationen (Mutual Exklusion Algorithmen mit Test-und-Set-Bit,
Ticket-Algorithmus mit RMW-Objekt)
6. Do 07.11.2019 Der MCS-Algorithmus. Konsensusproblem, Konsensuszahl, Konsensushierarchie.
Threads erzeugen in Java
7. Fr 08.11.2019 Prozessmodell, Programmierprimitive: Semaphore, Mutual Exclusion mit Semaphore,
Anwendungsbeispiele: Erzeuger-Verbraucher-Probleme mit beliebig großem Puffer und
mit beschränkt großem Puffer, speisende Philosophen, das Sleeping-Barber-Problem
8. Do 14.11.2019 Lösungen mit Semaphore zum Cigarette-Smoker-Problem, zu Barrieren und zum
Readers-and-Writers-Problem, Monitore
9. Do 21.11.2019 Semantik der Condition Queues mit verschiedenden Prioritäten für Signal-, Wait- und
Entry-Queue, Lösungen mit Monitoren zum Erzeuger-Verbraucher-Problem, zum Problem
der Speisenden Philosophen, dem Sleeping-Barber-Problem, dem Readers-and-Writers-
Problem, Monitore in Java, Kanäle (Einführung)
10. Fr 22.11.2019 Synchrone Kanäle und Anwendungen, Programmierung in Go, Tuple Spaces (Linda-Modell)
11. Do 28.11.2019 Anwendungsbeispiele für Tuple Spaces, Deadlocks bei mehreren Ressourcen, Deadlock-
Behandlung, Notwendige Bedingungen für einen Deadlock, Deadlock-Verhinderung,
2-Phasen-Sperrprotokoll mit und ohne Time-Stamping
12. Do 05.12.2019 Deadlock-Vermeidung, Bankiers-Algorithmus, (Software) Transactional Memory: Motivation,
Basisprimitive (atomic, abort, retry, orElse)
13. Fr 06.12.2019 Software Transactional Memory: Eigenschaften von STM-Systemen, Korrektheitskriterien
von STM-Systemen, TL2-Algorithmus
14. Do 12.12.2019 Haskell: Einführung und I/O-Programmierung
15. Do 19.12.2019 Haskell: IORefs, Concurrent Haskell (forkIO, MVars), Implementierung von Kanälen mit MVars
16. Do 09.01.2020 Concurrent Haskell: Beispiele, Nichtdeterministische Operatoren, Futures, Async-Bibliothek
17. Fr 10.01.2020 Concurrent Haskell: Futures. STM-Haskell: Einführung, Kanalkodierung
18. Do 16.01.2020 STM-Haskell: Implementierung im GHC, Semantik: Einführung, Lambda-Kalkül
19. Do 23.01.2020 Lambda-Kalkül, pi-Kalkül (Syntax, Strukturelle Kongruenz)
20. Fr 24.01.2020 Turing-Mächtigkeit des pi-Kalküls, Guarded choice, asynchroner pi-Kalkül,
polyadischer pi-Kalkül, Rekursive Definition vs. Replikation
21. Do 30.01.2020 Verhaltensgleichheit im pi-Kalkül (starke (volle) Bisimilarity, (volle) Bisimilarity,
barbed Kongruenz, may- und should-testing Äquivalenz), CHF (Einleitung)
22. Do 06.02.2020 Der CHF-Kalkül: Syntax, operationale Semantik, Kontextuelle Gleichheit,
Korrektheit von Programmtransformationen
23. Fr 07.02.2020 Wiederholung und Fragestunde

 

Material

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

Klausur

Die erste Klausur findet am 18.02.2020 um 10:00 Uhr in Raum B 001 (Oettingstr. 67) statt. Eine Anmeldung per uni2work ist bis 12.02.2020, 12:00 Uhr erforderlich.

Nachholklausur

Die Nachholklausur am 19.3. ist abgesagt und auf einen späteren, noch unbestimmten Zeitpunkt, verschoben, da gemäß der Mitteilung des Bayerischen Staatsministeriums für Wissenschaft und Kunst vom 11.03.2020, studienbegleitende Prüfungen, wann immer das möglich, aufgrund der Ausbreitung des neuen Coronavirus SARS-CoV-2 verschoben werden sollen.

Wir werden rechtzeitig über Uni2work und auf der Webseite zur Veranstaltung über einen neuen Termin informieren.

Artikelaktionen

Funktionsleiste