Algorithmen und Datenstrukturen II

Qualifikationsziele: Die Absolventen dieses Moduls kennen die weiterführenden Algorithmen und Datenstrukturen der Informatik. Sie sind in der Lage, auch für komplexere Probleme eine algorithmische Lösung zu formulieren und algorithmische Lösungen in ihrer Leistungsfähigkeit einzuschätzen. Die Inhalte sind:

• Weiterführende Komplexitätsaspekte
• Elementare Aspekte zu Heuristiken, exakten Verfahren und Approximationsalgorithmen
• Enumerationsverfahren
• Probabilistische Ansätze
• Fortgeschrittene Datenstrukturen

Aktuelles

• Wiederholungsklausur: Die Wiederholungsklausur findet am 14.02.2020 von 11:30 Uhr bis 13:30 Uhr statt. Bitte seid 15 Minuten vorher anwesend. Raumaufteilung wir an dieser Stelle einen Tag vor der Klausur bekanntgegeben. Mitzubringen sind:
  • Ein gültiger Studentenausweis (plus gültiger Lichtbildausweis, falls kein Foto auf dem Studentenausweis vorhanden ist)
  • Ein dokumentenechter Stift (kein Rot!)
  • Ein Wörterbuch, falls nötig (auf Papier, ohne Notizen)
  Andere Hilfsmittel sind nicht erlaubt; eigenes Papier wird nicht benötigt.
• Klausurergebnisse: HIER
• Klausureinsicht:
  Die Klausureinsicht findet am Dienstag, den 20.08.2018 zwischen 14:00 Uhr und 16:00 Uhr im Raum IZ 313 statt. Mitzubringen sind:
  • Ein gültiger Studentenausweis
  • Ein gültiger Lichtbildausweis, falls euer Studentenausweis kein Foto besitzt
• Klausur: Die Klausur findet am 09.08.2019 von 8:30 Uhr bis 10:30 Uhr statt. Bitte seid 15 Minuten vorher anwesend. Raumaufteilung:
  • Nachnamen A-H: PK 2.1
  • Nachnamen I-Z: PK 2.2
  Mitzubringen sind:
  • Ein gültiger Studentenausweis (plus gültiger Lichtbildausweis, falls kein Foto auf dem Studentenausweis vorhanden ist)
  • Ein dokumentenechter Stift (kein Rot!)
  • Ein Wörterbuch, falls nötig (auf Papier, ohne Notizen)
  Andere Hilfsmittel sind nicht erlaubt; eigenes Papier wird nicht benötigt.
• Es gab eine kleine Korrektur auf Blatt 5 Hausaufgabe 1b. Bitte ladet euch das Blatt erneut herunter (Stand: 09.07.19, 21:44)
• Es gab eine kleine Korrektur auf Blatt 2, Aufgabe 2: Falls beide Spieler den gleichen Gesamtwert erhalten, gewinnt Alice. Bitte ladet euch das Blatt erneut herunter. (Stand: 13.05.19, 16:19 Uhr)

Material

Vorlesungsnotizen

• Vorlesung 1 (17.04.19): Einführung in das Rucksackproblem
• Vorlesung 2 (24.04.19): Greedy Algorithmen
• Vorlesung 3 (08.05.19): Dynamic Programming für Subset Sum
• Vorlesung 4 (15.05.19): Dynamic Programming für Maximum Knapsack
• Vorlesung 5 (22.05.19): Branch-and-Bound
• Vorlesung 6 (29.05.19): Approximation für Maximum Knapsack
• Vorlesung 7 (05.06.19): Einführung in Komplexitätstheorie I
• Vorlesung 8 (19.06.19): Einführung in Komplexitätstheorie II
• Vorlesung 9 (26.06.19): Graphenprobleme
• Vorlesung 10 (03.07.19): Hashing I
• Vorlesung 11 (10.07.19): Hashing II
• Vorlesung 12 (17.07.19): Zusammenfassung

Große Übung

• Übung 0 (18.04.19): Organisation, Wiederholung (Sortieren, Laufzeiten, Pseudocode)
• Übung 1 (25.04.19): Greedy für Hörsaalproblem-Varianten
  
  Weitere Links

  Wikipedia zu Matroiden (deutsch), Matroiden (englisch)
• Übung 2 (09.05.19): Dynamic Programming, Longest Common Subsequence
• Übung 3 (23.05.19): Branch-and-Bound, Euklidisches TSP
• Übung 4 (06.06.19): 3-Dimensional Matching
  
  Weitere Links (in der Übung angesprochene Probleme)

  The Open Problems Project zu Sum of Square Roots,
  "Schwere" Nintendo Spiele
• Übung 5 (27.06.19): Reduktionen, Hamiltonkreis Problem, TSP
• Übung 6 (11.07.19): Hashing, Modulo, Wiederholung
  Weitere Links

  Notizen

Hausaufgaben

• 0. Hausaufgabenblatt
  Für dieses Blatt gibt es keine Abgabe. Bitte bereitet die Aufgaben trotzdem für die erste kleine Übung vor, damit die Inhalte des Blattes besprochen werden können.
• 1. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Donnerstag, 09.05.19, 13:15 Uhr durch Einwurf im Kasten. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
• 2. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Donnerstag, 23.05.19, 13:15 Uhr durch Einwurf im Kasten. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
  
• 3. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Donnerstag, 06.06.19, 13:15 Uhr durch Einwurf im Kasten. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
  
• 4. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Donnerstag, 27.06.19, 13:15 Uhr durch Einwurf im Kasten. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
  
• 5. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Donnerstag, 11.07.19, 13:15 Uhr durch Einwurf im Kasten. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
  

Klausuren

Mailingliste

Es gibt eine Mailingliste zu dieser Vorlesung. Bitte meldet euch da an, denn wir werden sie nutzen, um kurzfristig Informationen zu verteilen. Bei technischen Schwierigkeiten wendet euch bitte an Arne Schmidt.