====== Effiziente Algorithmen (SoSe 2020) ======

| 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=219171&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|040221]]** |
| Moodle | [[https://moodle.tu-dortmund.de/course/view.php?id=18682|Moodle Anmeldung]]  |
| SWS | 4 VO + 2 UE |

Die Veranstaltung entspricht auch dem Modul MD V "Effiziente Algorithmen" im Master Datenwissenschaften.

Die [[ ea2020uebung |begleitende Übung]] ist für das Verständnis des Stoffes sehr wichtig.


=== Ort und Zeit ===

  * Vorlesung: 
    * <del>Dienstag, 12:15-13:45 Uhr, OH14 E23</del>
    * <del>Donnerstag 14:15-15:45 Uhr, OH14 E23</del>
  * **Beginn der Vorlesungen: Dienstag, 21.04.2020**
  * **Update 16.04.**: Aufgrund der Corona-Pandemie findet keine Präsenz-Vorlesung statt. Stattdessen wird eine Online-Vorlesung angeboten: im Moodle finden Sie Lehr-Videos zu den einzelnen Kapiteln der Vorlesung. 
  * **Wichtig** Bitte melden Sie sich im Moodle zu dieser Veranstaltung an!
    * Im Moodle sind alle Materialien
    * Nur dadurch bietet sich die Möglichkeit, alle Studierende der Veranstaltung per eMail zu erreichen
  * Übungen: siehe [[ ea2020uebung |begleitende Übungen]] 

=== Prüfungen ===

  * Für die Bachelor-Studierenden der Informatik und der Angewandten Informatik findet die Klausur statt am:
    *  	Dienstag, 21.07.2020, 13:30-15:30 Uhr
  * Die Wiederholungsklausur findet statt am:
    * 	Montag, 07.09.2020, 08:00-10:00 Uhr
        * Termin: Montag, 07.09.2020, Beginn des Einlasses: 13:15 Uhr, Beginn der Klausur: 14:00 Uhr
        * Nach 13:45 Uhr kein Einlass mehr!
        * Orte: **Audimax** und **M E29** (Achtung: Raumänderung)
        * Mitzubringen:
            * Studierendenausweis und amtlicher Lichtbildausweis
            * Mund-Nase-Bedeckung 
            * Ausgefülltes Personenkontaktdaten-Blatt ([[http://www.cs.tu-dortmund.de/nps/de/Corona-Pandemie/_Internes/Internes/Hygienekonzepte/Formulare/Kontaktdaten_Klausuren/Formular_Personenkontaktdaten_Klausuren-2020-07-29.pdf|hier]])
            * Dokumentenechter Stift (schwarz oder blau)

  * 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.

=== 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, siehe [[https://moodle.tu-dortmund.de/course/view.php?id=18682|Moodle Anmeldung]]. 
  * Zum Arbeitsraum müssen Sie sich anmelden. Hierzu benötigen Sie ein Passwort, das Sie in der Vorlesung erhalten! Bitte fragen Sie nicht per eMail nach dem Passwort.