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

Wiederholungsklausur

Am Freitag, den 16.2.2024 findet die Wiederholungsklausur statt, und zwar von 13 bis 15 Uhr im Raum PK 4.3. Bitte beachtet, dass um 13 Uhr die Bearbeitungszeit starten soll. Seid daher bitte spätestens um 12:45 Uhr vor Ort. Bringt neben Studierenden- und Lichtbildausweis bitte auch einen blauen oder schwarzen dokumentenechten Stift mit. Ihr braucht kein eigenes Papier mitzubringen. Falls ihr Papier brauchen solltet, händigen wir Euch vor Ort welches aus.

Klausur

Die Ergebnisse der Klausur findet ihr hier. Die Klausureinsicht findet am Donnerstag, den 17.08.2023 ab 13:00 Uhr im Raum IZ 305 statt.

Die Klausur findet ab 11:15 Uhr statt. Wir brauchen zwei Räume und teilen die Teilnehmer nach Nachnamen auf.
Und zwar findet die Klausur für alle, deren Nachname mit einem A, B oder C beginnt, im Raum SN 19.1 statt. Für alle anderen findet die Klausur im Audimax statt.

Literatur

  • Skript: Zu dieser Vorlesung gibt es ein MANU-SKRIPT. (Stand: 13.05.23)
  • 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 Phillip Keldenich.

Achtung: Die Hausaufgaben sind als Einzelabgaben einzureichen, d.h. jeder Studierende gibt eine eigene Abgabe ab.

  • Hausaufgabenblatt 1: Abgabe bis zum 10.05.2023 um 15:00 Uhr im Hausaufgabenabgabeschrank.
  • Hausaufgabenblatt 2: Abgabe bis zum 24.05.2023 um 15:00 Uhr im Hausaufgabenabgabeschrank.
  • Hausaufgabenblatt 3: Abgabe bis zum 14.06.2023 um 13:30 Uhr im Hausaufgabenabgabeschrank.
    Bitte beachtet die frühere Abgabeuhrzeit!
  • Hausaufgabenblatt 4: Abgabe bis zum 28.06.2023 um 13:30 Uhr im Hausaufgabenabgabeschrank.
  • Hausaufgabenblatt 5: Abgabe bis zum 12.07.2023 um 13:30 Uhr im Hausaufgabenabgabeschrank.
  • Hausaufgabenblatt 6: Abgabe bis zum 19.07.2023 um 13:30 Uhr im Hausaufgabenabgabeschrank.
    Alle Punkte sind Bonuspunkte; sie gehen wie normale Punkte in Euren Punktestand ein, erhöhen aber nicht in die zum Bestehen der Studienleistung notwendige Punktzahl. Achtung: nur eine Woche Bearbeitungszeit!

Präsenzblätter

Merkzettel: Pseudocode, Beweistechniken, Wachstum von Funktionen.

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

  • Präsenzblatt 1: Besprechung in den kleinen Übungen vom 02.05.2023-05.05.2023.
  • Präsenzblatt 2: Besprechung in den kleinen Übungen vom 16.05.2023-19.05.2023.
  • Präsenzblatt 3: Besprechung in den kleinen Übungen vom 06.06.2023-09.06.2023.
  • Präsenzblatt 4: Besprechung in den kleinen Übungen vom 20.06.2023-23.06.2023.
  • Präsenzblatt 5: Besprechung in den kleinen Übungen vom 04.07.2023-07.07.2023.
  • Präsenzblatt 6: Besprechung in den kleinen Übungen vom 18.07.2023-21.07.2023.

Vorlesungen

  • Übung 7
    In dieser Übung beschäftigen wir uns noch einmal mit Hashing, bevor wir einen kurzen Rückblick auf das vergangene Semester machen.
  • Vorlesung 13
    In dieser letzten Vorlesung des Semesters rekapitulieren wir noch einmal das Semester und geben ein paar Ausblicke in weiterführende Themen.
  • Übung 6
    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 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.
  • Vorlesung 11
    In dieser Vorlesung wenden wir uns dem Thema Hashing zu.
  • Ü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 10
    In dieser Vorlesung machen wir einen Exkurs und beschäftigen und mit Optimierungsmethoden für mehrdimensionales Packen.
  • Vorlesung 9
    In dieser Vorlesung analysieren wir die Komplexität einiger uns bekannter Probleme und besprechen die daraus resultierenden Konsequenzen.
  • Übung: Backtracking & Propagation/Exkurs SAT
    In dieser Übung haben wir uns mit Backtracking & Propagation als Ansatz zur Lösung schwerer Entscheidungsprobleme befasst.Dann haben wir in …

    Übung: Backtracking & Propagation/Exkurs SAT Weiterlesen »

  • 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.