====== Effiziente Algorithmen (SoSe 2011) ======

| Veranstalter | **[[staff:mutzel|Petra Mutzel]]** |
| Modul        | **[[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Bachelor_Inf/Informatikmodule/Informatik-Wahlpflichtmodule_Inf_AI/Katalog_algorithmisch-formale_Grundlagen/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=102209&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|040221]]** |
| EWS | **[[https://ews.tu-dortmund.de/cseGui/MainBrowser.jsp?PRTLT_ACT=Navigation&ButtonSelected=SearchLecture&search=true&searchIdent=lsf-102209|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.

=== Ort und Zeit ===

  * Vorlesung: 
    * Dienstag, 10:15-11:45 Uhr, OH14 E23
    * Donnerstag 12:15-13:45 Uhr, OH14 E23
  * Beginn der Vorlesungen: Di, 05.04.
  * Übungen: jede 2. Woche, dafür 3-stündig 
    * Termine: Montag, Dienstag, Mittwoch, Donnerstag, jeweils 14.00-17.00 Uhr
    * Beginn der Übungen: 18.04.
    * Informationen zu den Übungen finden Sie [[staff:zey/ea-ueb-2011|hier]]
=== Prüfungen ===

  * Achtung: Für alle Prüfungen gilt: rechtzeitige Anmeldung bei Ihren Prüfungsämtern notwendig

  * Bachelor Informatik / Angewandte Informatik
    * **Klausur**, 90 Minuten, keine Hilfsmittel
    * Klausurtermin: Montag 25.07.2011 von 8:00 -- 10:00 Uhr in EF50, HS1
    * Wiederholungstermin: Donnerstag 06.10.2011 von 15:00 -- 17:00 Uhr in EF50, HS1
    * Stoff der Vorlesung und der Übungen

  * Diplom Informatik / Angewandte Informatik
    * mündliche Prüfung, 20 Minuten
    * Stoff der Vorlesung und der Übungen

  * Master Datenwissenschaften
    * mündliche Prüfung, 20 Minuten
    * Stoff der Vorlesung und der Übungen

  * Lehramt
    *  mündliche Prüfung, 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
  * Analysetechniken, wie z.B. Amortisierte Analyse von Algorithmen, Analyse randomisierter Algorithmen
  * Optimierungstechniken, wie z.B. Lineare Programmierung, Approximationsschemata, parametrisierte Komplexität
  * Hashing Verfahren, String Matching

Weitere Informationen: s. [[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Bachelor_Inf/Informatikmodule/Informatik-Wahlpflichtmodule_Inf_AI/Katalog_algorithmisch-formale_Grundlagen/INF-BSc-221.pdf|Modulbeschreibung]].

=== Materialien ===

Die Vorlesungsfolien und begleitende Materialien sind im [[https://ews.tu-dortmund.de/cseGui/MainBrowser.jsp?PRTLT_ACT=Navigation&ButtonSelected=SearchLecture&search=true&searchIdent=lsf-102209|EWS Arbeitsraum]] zu finden.