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

• Die Ergebnisse der Wiederholungsklausur sind da! Ihr könnt sie HIER ansehen. Die Klausureinsicht findet am 16.02.2018 (10:00 bis 10:30) im Raum IZ 319 statt.
• Die Wiederholungsklausur findet am 09.02.2017, von 8:30 bis 10:30 Uhr, statt. Bitte seid 15 Minuten vorher da! Die Klausur findet im Raum SN 23.1 statt. Mitzubringen sind:
  • Ein gültiger Studentenausweis (mit Bild)
  • Ein dokumentenechter Stift, bitte nicht in Rot
  • Wer mag ein Wörterbuch (auf Papier und ohne Notizen)
  • Sonst sind keine Hilfsmittel erlaubt!
• Die Ergebnisse der Klausur sind da! Ihr könnt sie HIER ansehen. Die Klausureinsicht findet am 11.08.2017 (13:00 bis 15:00) im Raum IZ 313 statt.
• Die Klausur findet am 31.07.2017, von 8:30 bis 10:30 Uhr, statt. Bitte seid 15 Minuten vorher da! Die Raumaufteilung wird spätestens am 30.7. bekanntgegeben. Mitzubringen sind:
  • Ein gültiger Studentenausweis (mit Bild)
  • Ein dokumentenechter Stift, bitte nicht in Rot
  • Wer mag ein Wörterbuch (auf Papier und ohne Notizen)
  • Sonst sind keine Hilfsmittel erlaubt!
  Die Raumaufteilung ist wie folgt:
  • Informatik + W.Informatik mit Matrikelendziffern 00 bis 39 im Raum PK 11.1
  • Informatik + W.Informatik mit Matrikelendziffern 40 bis 63 im Raum PK 11.2
  • Informatik + W.Informatik mit Matrikelendziffern 65 bis 99 im Raum PK 11.3
  • Physiker und ISTler schreiben im IZ 313 (Besprechungsraum der Algorithmik)
  Falls sich jemand in dieser Aufteilung nicht wiederfindet oder sich nicht sicher ist, in welchem Raum er/sie schreibt, dann schreibt einfach eine Mail mit eurer Matrikelnummer an Dr. Arne Schmidt.
• Studienleistung erfolgreich erbracht (ohne Gewähr). Zu sehen sind die letzten vier Stellen der Matrikelnummer.
• Aufgrund des TDSE wird die Vorlesung vom 13.07.17 auf den 12.07.17, 15 Uhr, vorverlegt.
• Aufgrund des TDSE wird die große Übung vom 12.07.17 auf den 05.07.17 vorverlegt werden.
• Aufgrund des TDSE wird die kleine Übung vom 13.07.17 (Gruppe 5) auf den 06.07.17 vorverlegt.
• Um Missverständnisse zu vermeiden, wurde der Text zu Aufgabe 1a) noch einmal ein wenig abgeändert. Der Branch-and-Bound-Algorithmus soll mit dem optionalen Teil aus Algorithmus 1.19 (siehe 7. Vorlesung) benutzt werden. (Stand: 08.06.2017)
• Es gab eine kleine Änderung an Blatt 4 (Hinweise zu Aufgabe 1a). Bitte ladet Euch das Blatt erneut herunter. (Stand: 02.06.17)
• Die kleine Übung vom 25.05.17 (Gruppe 5) wird aufgrund des Feiertages auf den 01.06.17 verschoben.
• Falls Ihr das Knapsack-Programm unter Windows kompilieren wollt, müsst ihr ggf "*;." (mit Anführungsstriche!) anstatt *:. wie bei Linux benutzen.
• Es gab einen Fehler in den Instanzen für das Programm. Bitte ladet euch die aktuelle Version der Instanzen runter: Instanzen (Stand: 24.04.17)

Material

Vorlesungsnotizen

• Vorlesung 1 vom 13.04.17
• Vorlesung 2 vom 20.04.17
• Zusatz: Beweisdetails Satz 1.5
• Vorlesung 3 vom 27.04.17
• Vorlesung 4 vom 04.05.17
• Vorlesung 5 vom 11.05.17
• Vorlesung 6 vom 18.05.17
• Vorlesung 7 vom 01.06.17
• Vorlesung 8 vom 15.06.17
• Vorlesung 9 vom 22.06.17
• Vorlesung 10 vom 29.06.17
• Vorlesung 11 vom 06.07.17

Große Übung

• 1. Übung: Organisation, Wiederholung AuD I, und Hausaufgaben. Folien: Gibt es hier.
• 2. Übung: Reduktionen, Lösungsansätze für schwere Probleme. Folien: Gibt es hier.
  Ein Artikel über verschiedene Reduktionen. Auch unsere Probleme tauchen dort auf (Fact 5 bis Fact 11).
• 3. Übung: Dynamic Programing, MCM, und LCS. Notizen: Gibt es hier.
• 4. Übung: Branch and Bound, Knapsack, Euklidisches TSP. Notizen: Gibt es hier.
• 5. Übung: Euklidisches TSP. Notizen:Gibt es hier (Dieselben Notizen wie in der 4. Übung).
• 6. Übung: Greedy_k, Komplexität. Notizen:Gibt es hier.
• 7. Übung: Klausuraufgaben. Notizen: N/A

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 Dienstag, 02.05.17, 13:15 Uhr durch Einwurf im Kasten. Abgaben des Programmierteils: Per Mail an den Tutor mit der gleichen Abgabefrist. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
• 2. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Montag, 15.05.17, 13:15 Uhr durch Einwurf im Kasten. Abgaben des Programmierteils: Per Mail an den Tutor mit der gleichen Abgabefrist. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
• 3. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Montag, 29.05.17, 13:15 Uhr durch Einwurf im Kasten. Abgaben des Programmierteils: Per Mail an den Tutor mit der gleichen Abgabefrist. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
• 4. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Montag, 19.06.17, 13:15 Uhr durch Einwurf im Kasten. Abgaben des Programmierteils: Per Mail an den Tutor mit der gleichen Abgabefrist. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
• 5. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Montag, 03.07.17, 13:15 Uhr durch Einwurf im Kasten. Abgaben des Programmierteils: Per Mail an den Tutor mit der gleichen Abgabefrist. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.

• Mai Hellman: hellman@ibr.cs.tu-bs.de
• Yannic Lieder: lieder@ibr.cs.tu-bs.de
• Moritz Pfister: mpfister@ibr.cs.tu-bs.de
• Micha Horlboge: horlboge@ibr.cs.tu-bs.de
• Sören van der Wall: svanderw@ibr.cs.tu-bs.de
• Dennis Luck: dluck@ibr.cs.tu-bs.de

Klausuren

Mailingliste

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