====== Effiziente Algorithmen (SoSe 2014) ======

| Veranstalter | **[[staff:gutwenger|Carsten Gutwenger]]** |
| 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=138387&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|040221]]** |
| EWS | [[https://ews.tu-dortmund.de/ngGui/signon/lsf-138387|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 [[http://ls11-www.cs.tu-dortmund.de/staff/schaefer/ea-ueb-2014|begleitende Übung]] ist für das Verständnis des Stoffes sehr wichtig.


=== Ort und Zeit ===

  * Vorlesung: 
    * Dienstag, 10:15-11:45 Uhr, **SRG1 1.001**
    * Donnerstag 12:15-13:45 Uhr, **OH14 E23**
  * Beginn der Vorlesungen: Dienstag, 08.04.2013 (KW15)
  * Übungen: siehe [[staff:schaefer/ea-ueb-2014|begleitende Übungen]] 
  * Übungsklausur: 3. Juli (Donnerstag, im Rahmen der Vorlesung)


=== 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: Mo 21.07.2014 (11:00-12:30), EF50 HS3
      * Klausurergebnisse: {{:staff:schaefer:aushang_ergebnisse_1.pdf|Download (PDF)}}
      * Klausureinsicht: Mi 10.09.2014 von 10:00 bis 11:00 Uhr in OH14 Raum 202
    * Wiederholungstermin: Mo 15.09.2014 (08:00-09:30), EF50 HS2
      * Klausurergebnisse: {{:staff:schaefer:aushang_ergebnisse_2.pdf|Download (PDF)}}
      * **Klausureinsicht: Mo 03.11.2014 von 10:00 bis 11:00 Uhr in OH14 Raum 202**
    * 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. [[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]].


=== Gliederung ===

Die Vorlesung ist wie folgt in Kapitel und Abschnitte gegliedert (die Gliederung wird synchron zur Vorlesung ergänzt):

  - Einführung (VO 1)
  - Tiefensuche und 2-Zusammenhang (VO 2)
    - Tiefensuche (Wdh. aus DAP 2)
    - Zweizusammenhang
  - Starke Zusammenhangskomponenten (VO 3)
    - Tiefensuche in gerichteten Graphen
    - Starker Zusammenhang
  - Maximale Matchings in Graphen (VO 4-5)
    - Matchings in bipartiten Graphen
    - Matchings in allgemeinen Graphen
  - Flüsse in Graphen (VO 6-10)
    - Das Flussproblem
    - Der Algorithmus von Ford und Fulkerson
    - Das Max-Flow / Min-Cut Theorem
    - Der Algorithmus von Dinic
    - Der Algorithmus von Malhotra et al.
    - Der Goldberg-Tarjan Algorithmus
  - Amortisierte Analyse (VO 11-12)
    - Potenzialmethode
    - Kostenverteilung
    - Kontenmethode
    - Union/Find mit Pfadkompression
  - String Matching (VO 12-16)
    - Einleitung und naiver Algorithmus
    - String Matching mit DEAs
    - Algorithmus von Knuth, Morris, Pratt
  - Approximationsalgorithmen (VO 17)
    - Grundbegriffe
    - FPTAS für das Rucksackproblem
  - Das Traveling Salesman Problem (VO 18)
    - Motivation & Grundlagen
    - Approximationen für das metrische TSP
  - Analyse randomisierter Algorithmen für Erfüllbarkeitsprobleme (VO 19-20)
    - Randomisierte Algorithmen
    - Approximation für MAX-k-SAT
    - Randomisiertes Runden
  - Schnittprobleme (VO 21-22)
    - Max Cut
    - Ein randomisierter Min-Cut Algorithmus
    - Fast Min-Cut
  - Hashing (VO 23-24)
    - Universelles Hashing
    - Statisches perfektes Hashing
    - Cuckoo Hashing
  - Skiplisten (VO 25)
    - Perfekte Skiplisten
    - Randomisierte Skiplisten