Startseite

Algorithmen und Datenstrukturen 2

Die Vorlesung Algorithmen und Datenstrukturen 2 ist eine Wahlpflichtveranstaltung für Studierende der Informatik, Wirtschaftsinformatik, Informations- und Systemtechnik; außerdem ist sie offen für interessierte Studierende anderer Studiengänge.

Algorithmen sind das methodische Herz der theoretischen und praktischen Informatik; Datenstrukturen ermöglichen die effiziente Umsetzung von Algorithmen und den effizienten Zugriff auf Input- und Outputdaten. In dieser weiterführenden Vorlesung werden die folgenden grundlegenden Begriffe erarbeitet:

  • Elementare Aspekte zu Heuristiken
  • Exakte Verfahren: Dynamic Programming, Branch-and-Bound
  • Approximationsalgorithmen
  • Komplexitätsaspekte
  • Hashing

Literatur

  • Skript: Zu dieser Vorlesung gibt es ein MANU-SKRIPT. (Stand: 21.06.21)
  • Achtung: Ein Skript ist kein Ersatz für den Besuch der Lehrveranstaltung!
  • Literaturempfehlung (englisch): Silvano Martello, Paolo Toth: Knapsack Problems (PDF!), Wiley and Sons, 1990
  • Literaturempfehlung (englisch): Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: Introduction to Algorithms, MIT Press, 2001
  • Literaturempfehlung (deutsch): Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: Algorithmen – Eine Einführung, Oldenbourg Wissenschaftsverlag, 2010

Hausaufgaben

Für alle Hausaufgaben gelten die Punkte auf dem Hinweiszettel. Die Abgaben müssen in diesem Semester wieder physisch erfolgen. Falls Sie aus einem bestimmten Grund in diesem Semester nicht vor Ort sein können, melden sie sich bitte frühzeitig bei Matthias Konitzny. Eine Liste mit den e-Mail-Adressen der Tutor*innen gibt es hier.

  • Blatt 1: HIER. Abgabe bis 17.05.22 16:00 Uhr
  • Blatt 2: HIER. Abgabe bis 01.06.22 12:00 Uhr (Rückgabe in den kleinen Übungen erst ab dem 15.06 wegen Exkursionswoche)
  • Blatt 3: HIER. Abgabe bis 22.06.22 12:00 Uhr (Entscheidungsbaum: PDF, IPE, SVG)
  • Blatt 4: HIER. Abgabe bis 06.07.22 12:00 Uhr (Python Template: HIER)
  • Blatt 5: HIER. Abgabe bis 20.07.22 12:00 Uhr (Python Template: HIER)

Präsenzblätter

Merkzettel: Pseudocode, Beweistechniken, Wachstum von Funktionen.

Diese Blätter werden nicht abgegeben und werden in den kleinen Übungen besprochen.

  • Blatt P0: HIER. (Besprechung 11.05.22-13.05.22)
  • Blatt P1: HIER. (Besprechung 25.05.22-27.05.22)
  • Blatt P2: HIER. (Besprechung 15.06.22-17.06.22)
  • Blatt P3: HIER. (Besprechung 29.06.22-01.07.22)
  • Blatt P4: HIER. (Besprechung 13.07.22-15.07.22)
  • Blatt P5: HIER. (Besprechung 27.07.22-29.07.22)

Vorlesungen

  • Online-Prüfung Informationen (Wiederholungsprüfung)
    Liebe Studierende, hier eine Reihe von Informationen zur Vorbereitung der AuD2-Prüfung am 25.02.22. Bitte lesen Sie diese sehr sorgfältig! Sollten …

    Online-Prüfung Informationen (Wiederholungsprüfung) Weiterlesen »

  • Vorlesung 13
    In dieser letzten Vorlesung des Semesters rekapitulieren wir noch einmal das Semester und geben ein paar Ausblicke in weiterführende Themen.
  • Vorlesung 12
    In dieser Vorlesung beschäftigen wir uns etwas näher mit Hashfunktionen und Lösungsstrategien für auftretende Probleme wie Kollisionen. Außerdem schauen wir uns weitere Anwendungen für Hashfunktionen an.
  • Übung 6
    In dieser Übung beschäftigen wir uns noch einmal mit Hashing, bevor wir einen kurzen Rückblick auf das vergangene Semester machen.
  • Vorlesung 11
    In dieser Vorlesung wenden wir uns dem Thema Hashing zu.
  • Vorlesung 10
    In dieser Vorlesung machen wir einen Exkurs und beschäftigen und mit Optimierungsmethoden für mehrdimensionales Packen.
  • Prüfung Informationen
    Wichtige Informationen zur Prüfung.
  • Übung 5
    In dieser Übung beschäftigen wir uns mit dem Approximationsalgorithmus Greedyk für das Knapsack-Problem. Außerdem schauen wir uns mit Vertex-Cover noch ein neues Problem an.
  • Vorlesung 9
    In dieser Vorlesung analysieren wir die Komplexität einiger uns bekannter Probleme und besprechen die daraus resultierenden Konsequenzen.
  • Vorlesung 8
    In dieser Vorlesung beginnen wir uns mit weiterführenden Aspekten zur Komplexität zu beschäftigen. Dabei lernen wir die verschiedenen Komplexitätsklassen kennen und diskutieren deren Eigenschaften und Beziehungen.