Effiziente Algorithmen (SoSe 2013)
| Veranstalter | Petra Mutzel |
| Modul | INF-BSc-221 (Bachelor Informatik / Angewandte Informatik) |
| Veranstaltungsnummer | 040221 |
| EWS | EWS-Arbeitsraum |
| SWS | 4 VO + 2 UE |
Die Veranstaltung entspricht auch der auslaufenden Vorlesung “Effiziente Algorithmen und Komplexitätstheorie” im Diplomstudiengang Informatik / Angewandte Informatik als Wahlpflichtveranstaltung sowie dem Modul MD V “Effiziente Algorithmen” im Master Datenwissenschaften. Die begleitende Übung ist für das Verständnis des Stoffes sehr wichtig.
Ort und Zeit
- Vorlesung:
- Dienstag, 10:15-11:45 Uhr, OH14 E23
- Donnerstag 12:15-13:45 Uhr, OH14 E23
- Beginn der Vorlesungen: Dienstag, 09.04.2013 (KW15)
- Übungen: siehe begleitende Übungen
- Übungsklausur: 18.06.2013 (während der Vorlesungszeit)
Prüfungen
- Achtung: Für alle Prüfungen gilt:
- rechtzeitige Anmeldung bei Ihren Prüfungsämtern notwendig
- Ausweise mitbringen (Immatrikulationsnachweis und ID oder Pass)
- keine Hilfsmittel erlaubt
- Bachelor Informatik / Angewandte Informatik / Master Datenwissenschaften
- Klausur, 90 Minuten, keine Hilfsmittel
- Klausurtermin: 23.07.2013 10-12 Uhr
- Klausureinsicht: 20.08.2013 12-13 Uhr / OH14 R202
- Wiederholungstermin: 07.10.2013 12-14 Uhr
- Klausureinsicht: 16.10.2013 14-15 Uhr / OH14 R202
- Stoff der Vorlesung und der Übungen
- Diplom Informatik / Angewandte Informatik
- mündliche Prüfung, 20 Minuten
- Stoff der Vorlesung und der Übungen
- Lehramt
- mündliche Prüfung oder Klausur, 20 oder 45 Minuten, je nach Prüfungsordnung und Prüfungsanmeldung
- Stoff der Vorlesung und der Übungen
- Sonstige Studiengänge / Nebenfächer auf Anfrage
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, Vertex Cover, MaxSAT
- Analysetechniken, wie z.B. Amortisierte Analyse von Algorithmen, Analyse randomisierter Algorithmen
- Optimierungstechniken, wie z.B. Lineare Programmierung, Approximationsgüte und -schemata
- Hashing Verfahren, Skiplisten, String Matching
Weitere Informationen: s. Modulbeschreibung.
Materialien
Die Vorlesungsfolien und begleitende Materialien finden Sie im EWS-Arbeitsraum.