Übung zu Effiziente Algorithmen (SoSe 2010)
| Veranstalter | Karsten Klein, Bernd Zey |
| Modul | Modulhandbuch INF-BSc-221 (Bachelor Informatik / Angewandte Informatik) |
| Veranstaltungsnummer: | 040222 (lsf Eintrag zur Übung) |
| SWS | 2 |
Die Vorlesung zur Veranstaltung entspricht auch der auslaufenden Vorlesung “Effiziente Algorithmen und Komplexität” im Diplomstudiengang Informatik / Angewandte Informatik als Spezialvorlesung. Veranstaltungsnummer: 042807
Hinweise
Die Übungsgruppenverteilung ist nun online, siehe eakt2010-uebungsgruppenverteilung.pdf.
Anmeldungen zur Übung sind nur noch nach Rücksprache mit den Betreuern möglich.
Übungen, welche auf einen Feiertag fallen, werden eine Woche nach hinten verschoben (13.05. ⇒ 20.05. und 24.05. ⇒ 31.05.)
Zu den unten genannten Zeiten stehen die Betreuer jeweils für Fragen zu den Übungen, zum Stoff und zur Prüfungsvorbereitung zur Verfügung (genaueres zum Ablauf im internen Bereich der Übungsseiten im EWS).
Eine doppelte Anmeldung für die beiden EWS Arbeitsräume für EA und EA/KT ist nicht notwendig. Der Raum EA/KT war für die Diplom-Studenten gedacht, dies ist aber nur eine formale Unterteilung. In Kürze wird die Zuordnung in Übungsgruppen erfolgen und dann bekannt gemacht. Eventuell benutzen wir dazu aufgrund der hohen Zahl der Anmeldungen das Assess System, genaueres steht dann auch auf diesen Seiten und im EWS. Da im Moment noch nicht sicher ist, wieviele Gruppen zustandekommen und wann die zusätzlichen Übungstermine sind (müssen noch genehmigt werden), kann dies aber noch einige Tage dauern.
Ort und Zeit
- Vorlesung: Di+Do 12:15-13:45 Uhr in OH14 E23
- Übungen:
- Mo 12-14 Uhr (Raum OH14 104)
- Di 14-16 Uhr (Raum OH14 E02)
- Do 16-18 Uhr (Raum OH14 304)
- Fr 14-16 Uhr (Raum OH14 304)
- Beginn der Vorlesungen: Di 13.04.
- Beginn der Übungen: Di 26.04. s. Ankündigung in VO
Zusammenfassung
- Die in DAP 2 eingeführten Basistechniken werden vertieft und auf komplexere Probleme angewendet, hinzu kommen ausgewählte Probleme mit großen Anwendungsbereichen, weitergehende Aspekte wie Approximation und weitergehende Entwurfsmethoden wie primal-duale Ansätze. Themen, u.a.:
- Graphenalgorithmen, wie z.B. starker Zusammenhang in Graphen, Maximale Matchings, Netzwerkflussprobleme, Schnittprobleme (Min Cut vs. Max Cut), Travelling Salesman Problem
- Analysetechniken, wie z.B. Amortisierte Analyse von Algorithmen, Analyse randomisierter Algorithmen
- Optimierungstechniken, wie z.B. Lineare Programmierung, Approximationsschemata
- Hashing Verfahren, String Matching, Hidden-Markov-Modelle