====== Effiziente Algorithmen (SoSe 2018) ======

| Veranstalter | **[[staff:mutzel|Petra Mutzel]]** |
| 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=195260&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|040221]]** |
| Moodle | [[https://moodle.tu-dortmund.de/course/view.php?id=10951| Moodle Anmeldung]]|
| 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 [[staff:droschinsky/ea-ueb-2018|begleitende Übung]] ist für das Verständnis des Stoffes sehr wichtig.


=== Ort und Zeit ===

  * Vorlesung: 
    * Dienstag, 12:15-13:45 Uhr, OH14 E23
    * Donnerstag 12:15-13:45 Uhr, OH14 E23
  * Beginn der Vorlesungen: Dienstag, 10.04.2018
  * Übungen: siehe [[staff:droschinsky/ea-ueb-2018|begleitende Übungen]] 

=== Prüfungen ===

  * Für die Bachelor-Studierenden der Informatik und der Angewandten Informatik fand die Klausur statt am:
    * Freitag, dem 27. Juli 2018 von 14:30 - 16:00 Uhr in HG2 im Raum HS3)
    * Die Klausurergebnisse sind im [[https://moodle.tu-dortmund.de/course/view.php?id=10951|Moodle]] einsehbar.
    * Die Klausureinsicht fand am Dienstag, 14. August, von 10 bis 11 Uhr im Raum 202, OH 14, statt.

  * Die Wiederholungsklausur fand statt am:
     * Dienstag, dem 25. September 2018 von 12-13:30 Uhr im HG2 in Raum HS5*
     * Die Klausurergebnisse sind im [[https://moodle.tu-dortmund.de/course/view.php?id=10951|Moodle]] einsehbar.
     * Die Klausureinsicht findet am Montag, 22. Oktober, von 11 bis 12 Uhr im Raum 202, OH 14, statt.

  * Studierende anderer Fachrichtungen haben entweder mündliche Prüfungen (wie z.B. Diplom-Informatik) 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.

=== 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. [[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]].

=== Materialien ===

  * Die Vorlesungsfolien und begleitende Materialien finden Sie im Moodle-Arbeitsraum. 
  * Sie können oben den Arbeitsraum aufrufen, falls Sie für diesen Raum eingeschrieben sind.
  * Dazu müssen Sie sich anmelden.