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

Aktuelles

  • 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: Je nach Anzahl der Teilnehmenden Klausur oder mündliche Prüfung

 


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

Planung

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 vorläufige 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
10. Fr 22.11.2019
11. Do 28.11.2019
12. Do 05.12.2019
13. Fr 06.12.2019
14. Do 12.12.2019
15. Do 19.12.2019
16. Do 09.01.2020
17. Fr 10.01.2020
18. Do 16.01.2020
19. Do 23.01.2020
20. Fr 24.01.2020
21. Do 30.01.2020
22. Do 06.02.2020
23. Fr 07.02.2020

 


Material

Material und Übungsblätter erhalten Sie per Uni2work


Klausur

Die erste Klausur findet am 18.02.2020 um 10:00 Uhr statt. Eine Anmeldung per uni2work ist bis 12.02.2020, 12:00 Uhr erforderlich.

Artikelaktionen


Funktionsleiste