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

Algorithmen und Datenstrukturen II

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

  • 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 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)
  • 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).
  • 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.
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, Sommersemester 2017

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 02.08.2017, 08:21 von Arne Schmidt
printemailtop