Department of Computer Science
Chair of Algorithm Engineering (Ls11)
Home Contact Deutsch English
menu-en
Vorlesung WS08/09: Algorithmen und Datenstrukturen

Algorithmen und Datenstrukturen

Vorlesung im Modul INF-MA-241
(Basismodul Master, Spezialvorlesung Diplom)

Wintersemester 2008/09

Prof. Dr. Petra Mutzel


Siehe auch: Übung zu Algorithmen und Datenstrukturen

Termine

Di 12:15 - 14:00, OH14 Raum 304
Do 12:15 - 14:00, OH14 Raum 304

Beginn: 14.10.2008

Teilnahmevoraussetzungen

Voraussetzung für die Teilnahme an dieser Veranstaltung sind:

  • Allgemein: Gründliche Kenntnisse der mathematischen Pflichtveranstaltungen
  • Speziell: Gründliche Kenntnisse der Inhalte von DAP 2 und GTI im BA-Studiengang Informatik oder Angewandte Informatik

Inhalt

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

Prüfungen

  • Studienleistungen: aktive Teilnahme an den Übungen
  • Prüfungsform: mündliche Prüfung

Folien der Vorlesungen

Einführung (14.10.): [1 Folie/Blatt] [6 Folien/Blatt]
Fibonacci-Heaps (16./21./23.10.): [1 Folie/Blatt] [6 Folien/Blatt]
Externe Array-Heaps (23./28./30.10.): [1 Folie/Blatt] [6 Folien/Blatt]
Amortisierte Analyse von Algorithmen (30.10.): [1 Folie/Blatt] [6 Folien/Blatt]
Suffix Arrays (Teil 1) (11.11.): [1 Folie/Blatt] [6 Folien/Blatt]
Suffix Arrays (Teil 2) (13.11.): [1 Folie/Blatt] [6 Folien/Blatt]
String Matching (4./18./25./27.11.): [1 Folie/Blatt] [6 Folien/Blatt]
The GNU libstdc++ parallel mode (20.11.): [1 Folie/Blatt]
Lineare Programmierung: Einführung (27.11.): [1 Folie/Blatt] [6 Folien/Blatt]
Simplex-Algorithmus (2.-16.12.): [1 Folie/Blatt] [6 Folien/Blatt]
Dualität (18.12.): [1 Folie/Blatt] [6 Folien/Blatt]
Approximationsalgorithmen (18.12./8.1.): [1 Folie/Blatt] [6 Folien/Blatt]
2-Zusammenhang und starker Zusammenhang (15.1.): [1 Folie/Blatt] [6 Folien/Blatt]
Mehrdimensionale Suchstrukturen (20.-29.1.): [1 Folie/Blatt] [6 Folien/Blatt]
Dynamische Algorithmen für kürzeste Wege (3./5.2.): [1 Folie/Blatt] [6 Folien/Blatt]

Skriptausschnitte

Kapitel 2: Externspeicher-Algorithmen
Kapitel 3: Suchen in Texten / String Matching
Kapitel 4: Lineare Programmierung und kombinatorische Optimierung
(geht teilweise über den Stoff der Vorlesung hinaus)
DAP2: Optimierung
(Optimierungskapitel aus dem Skript zu DAP2)
Imprint
<webmaster  ls11.cs.tu-dortmund.de>
The university does not accept liability for the contents of linked external internet sites