====== Effiziente Algorithmen (SoSe 2021) ====== | Veranstalter | **[[staff:zey|Dr. Bernd Zey]]** | | Modul | **[[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Bachelor_Inf/INF/INF-WP/WP_algform/INF-BSc-221.pdf|INF-BSc-221]]** (Bachelor Informatik / Angewandte Informatik) | | Veranstaltungsnummer | **[[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&publishid=235720&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|040221]]** | | Moodle | [[https://moodle.tu-dortmund.de/course/view.php?id=26243|Moodle]] | | SWS | 4 VO + 2 UE | Die Veranstaltung entspricht auch dem Modul MD V "Effiziente Algorithmen" im Master Datenwissenschaften. Die [[ ea2021uebung |begleitende Übung]] ist für das Verständnis des Stoffes sehr wichtig. === Ort und Zeit === * Ort: voraussichtlich online (Zoom oder BBB) * Zeiten * Dienstag 10:15-11:45 Uhr * Donnerstag 14:15-15:45 Uhr === Materialien === * Alle Materialien sind im Moodle-Raum zu finden: [[https://moodle.tu-dortmund.de/course/view.php?id=26243|Moodle]] === Prüfungen === * Für die Bachelor-Studierenden der Informatik und der Angewandten Informatik: Klausur, 90 Minuten, 2 Termine * Studierende anderer Fachrichtungen haben entweder mündliche Prüfungen oder auch Klausur. Die genauen Konditionen werden in der Vorlesung bekannt gegeben (s. Folien). Im Falle einer Klausur findet diese zeitgleich mit den obigen Klausuren statt. Bitte beachten Sie die Anmeldefristen für die Prüfungen beim Prüfungsamt, die für Klausuren sehr früh sind (i.d.R. 2 Wochen vorher). === Thematische 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. Die Themen lauten u.a.: * Graphenalgorithmen, wie z.B. starker Zusammenhang in Graphen, Maximale Matchings, Netzwerkflussprobleme, Schnittprobleme (Min Cut und Max Cut), Traveling 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. [[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Bachelor_Inf/INF/INF-WP/WP_algform/INF-BSc-221.pdf|Modulbeschreibung]].