TU BRAUNSCHWEIG
| Carl-Friedrich-Gauß-Fakultät | Informatik
Informatikzentrum

Algorithmen und Datenstrukturen II

SemesterSommersemester 2017 [ Andere Semester: · Sommer 16 · Sommer 15 · Sommer 13 ]
Modulnr.INF-ALG-23
Veranst.Nr.INF-ALG-042, INF-ALG-043, INF-ALG-044
Studieng.Bachelor Wirtschaftsinformatik, Bachelor Informations-Systemtechnik, Bachelor Informatik
IBR Gruppe(n)ALG (Prof. Fekete)
ArtVorlesung/Übung
Dozent
PhotoProf. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Raum 335
Assistent
PhotoArne Schmidt
Wissenschaftlicher Mitarbeiter
aschmidt[[at]]ibr.cs.tu-bs.de
+49 531 3913115
Raum 319
LP5
SWS2+1+1
Ort & Zeit Vorlesung: Donnerstag, 15:00 - 16:30, PK 2.2
Große Übung: Mittwoch, 15:00 - 16:30, PK 2.2 (14-tägig)
Kleine Übung:
GruppeTermin (14-tägig)RaumTutorTeilnehmer
1Montag, 09:45 - 11:15 IZ 305Mai HellmannTXT
2Mittwoch, 08:00 - 09:30 IZ 358Yannic LiederTXT
3Mittwoch, 09:45 - 11:15 IZ 358Moritz PfisterTXT
4Mittwoch, 13:15 - 14:45 IZ 358Micha HorlbogeTXT
5Donnerstag, 13:15 - 14:45 IZ 358Sören van der WallTXT
6Freitag, 11:30 - 13:00 IZ 358Dennis LuckTXT
Eine nach Namen sortierte Liste der Teilnehmer mit Gruppennummer findet sich hier. Eine Übersicht der Termine aller Vorlesungen, großer und kleiner Übungen, sowie Aus-, Ab- und Rückgabe der Hausaufgaben ist im Semesterplan zusammengestellt. Änderungen vorbehalten.
Beginn Erste Vorlesung: 13.04.17
Erste große Übung: 19.04.17
Erste kleine Übung: 24.-28.04.17
Voraussetzungen Keine
SpracheDeutsch
Scheinerwerb Studienleistung: Mindestens 50 Prozent der Hausaufgaben
Prüfungsleistung: Klausur am Ende des Semesters
Anmeldung
Die Anmeldung für die Übungsgruppen ist abgelaufen. Falls Du Dich dennoch für die Übungsgruppen anmelden möchtest, schreibe eine kurze Mail an Arne Schmidt mit vollem Namen, Matrikelnummer, Studiengang und Wunschtermin. Je nach Belegung der Gruppen kann es jedoch passieren, dass du der leersten Gruppen zugewiesen wirst.
Inhalt

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

  • Aufgrund des TDSE muss die kleine Übung vom 13.07.17 (Gruppe 5) auf den 06.07.17 VORverlegt werden.
  • 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)
  • Es gab einige Leute, die sich nicht sicher sind, wie man die Algorithmen in dem Programm schreibt. Ihr könnt euch hier ein Beispiel anschauen (Greedy für Fractional Knapsack).

Material

Vorlesungsnotizen

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

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.
Hier sind die Javavorlage und Instanzen für den Programmierteil. (Hinweis: Die commons-lang und commons-math müssen nicht benutzt werden, können aber an der einen oder anderen Stelle behilflich sein. Nähere Hinweise dazu gibt es dann in den Blättern.)
Die Mail-Adressen der Tutoren sind:

Klausuren

Sommersemester 2013, Sommersemester 2015, Sommersemester 2016

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 Arne Schmidt.


aktualisiert am 23.06.2017, 10:22 von Arne Schmidt
printemailtop