====== Algorithmen und Datenstrukturen (WS 2010/2011) ======
| Veranstalter | **[[staff:mutzel|Petra Mutzel]]** |
| Modul | **[[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Modulhandbuch_Master_Informatik/Basismodule/Forschungsbereich_Algorithmen_und_Komplexitaet/INF-MSc-241.pdf|Modulhandbuch INF-MSc-241]]** (Master Informatik / Angewandte Informatik) |
| Schwerpunktgebiet | 4, 6, 7 (Diplom Informatik / Angewandte Informatik)|
| EWS | **[[https://ews.tu-dortmund.de/cseGui/MainBrowser.jsp?-Main=Lectures&PRTLT_ACT=Main&SelAct=1&Lect=lsf-93242 | Arbeitsraum ]]** |
| Veranstaltungsnummer: | **[[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&publishid=93242&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung| 041235 (lsf Eintrag zur Vorlesung)]]** |
| SWS | 4 |
=== Ort und Zeit ===
* Vorlesung: Dienstag + Donnerstag 12:15-13:45 Uhr in OH14, Raum 104
* **Raumänderung: ** nun in Raum
OH16 U08
* Beginn der Vorlesungen: Di 12.10.
* Informationen zu den Übungen finden Sie [[staff:zey/aud-uebung-1011|hier]]
* Beginn der Übungen: voraussichtlich Di 26.10., siehe Ankündigung in der Vorlesung. Die Anmeldung zu den Übungen erfolgt ebenfalls in der Vorlesung
=== Materialien ===
Alle Materialien sind im internen Bereich des [[https://ews.tu-dortmund.de/cseGui/MainBrowser.jsp?-Main=Lectures&PRTLT_ACT=Main&SelAct=1&Lect=lsf-93242 | EWS-Arbeitsraums ]] zu finden. Für den internen Bereich ist eine separate Anmeldung und Freischaltung notwendig.
=== Zusammenfassung ===
Diese Vorlesung mit der begleitenden Übung gibt einerseits die Grundlagen für die meisten weiterführenden Spezialvorlesungen im Bereich Algorithmische und formale Grundlagen, zum anderen behandelt sie weiterführende und komplexere Algorithmen und Datenstrukturen. Sie kann als Weiterführung von DAP2, mit fast leerer Überschneidung zu Effiziente Algorithmen gesehen werden. Im Einzelnen werden die folgenden Themen behandelt:
* Komplexe Datenstrukturen und deren Analyse, wie z.B. Fibonacci-Heaps
* Strings, z.B. Suffix Trees, Suffix Arrays, Pattern Matching
* Lineare Programmierung: Modellierung, Dualität, Simplexalgorithmus
* Ganzzahlige Lineare Programmierung: z.B. Gomory
* Kombinatorische Optimierung, z.B. primal-duale Algorithmen, Branch-and-Cut
* Approximationsalgorithmen, z.B. Set Cover
* Graphenalgorithmen: z.B. Flussalgorithmen, Minimaler Schnitt, bipartites Matching
* Geometrische Algorithmen: z.B. konvexe Hülle
* Analysemethoden, wie z.B. amortisierte Analyse