Fakultät für Informatik
Lehrstuhl für Algorithm Engineering (Ls11)
Home Kontakt Deutsch English
Vorlesung SS09: Datenstrukturen, Algorithmen und Programmierung (DAP) 2

Datenstrukturen, Algorithmen und Programmierung 2 (DAP 2)

Vorlesung im Modul INF-BA-104

Sommersemester 2009

Prof. Dr. Petra Mutzel


Termine

Dienstag 12.15 - 14.00 Uhr Campus Nord HG 3 / Audimax
Donnerstag 14.15 - 16.00 Uhr Campus Nord HG 2 / HS1

Beginn: 14.4.2009

DAP2-Kalender


Aktuelles
Die Klausurergebnisse der 2. Klausur hängen am Lehrstuhl 11 aus: OH14, 2. Obergeschoss, Glaskasten gegenüber der Eingangstür.

Die Klausureinsicht für die 2. Klausur findet am 17.11.2009, 9-11 Uhr in OH14, Raum 202 statt.

Informationen zur Scheinvergabe und Klausur
Fragen zur Klausuranmeldung oder Scheinvergabe können an diese E-Mail-Adresse gerichtet werden:
dap2klausur2009 ls2.cs.tu-dortmund.de


top

Begleitende Veranstaltungen


Auch interessant: Linux-Kurs

top

Teilnahmevoraussetzungen

Voraussetzung für die Teilnahme an dieser Veranstaltung ist der Leistungsnachweis des Programmierpraktikums zu DAP1.

Voraussetzung für die Teilnahme an der Modulprüfung (Klausur) ist die erfolgreiche Teilnahme an der Übung zu DAP2.


top

Inhalt

In der Vorlesung DAP1 stand der Entwurf von Software, also Programmierung und Eigenschaften von Programmen, im Vordergrund. Ein Softwareprodukt ist aber erst dann rundum gut, wenn es effizient arbeitet. Daher behandeln wir in der Vorlesung DAP2 Datenstrukturen und Entwurfsmethoden für effiziente Algorithmen.

Naive Lösungen algorithmischer Probleme können praktisch nutzlos sein, da die benötigten Ressourcen an Rechenzeit und/oder Speicherplatz nicht zur Verfügung stehen. Mit Hilfe des Einsatzes geeigneter Datenstrukturen und algorithmischer Methoden lassen sich viele algorithmische Probleme effizienter lösen. Diese Effizienz kann sich im praktischen Gebrauch erweisen und zuvor mit Experimenten belegt werden; besser ist jedoch ein Produkt mit Gütegarantie. Dies bedeutet den formalen Beweis, dass die Datenstruktur oder der Algorithmus das Gewünschte leistet, und die Abschätzung der benötigten Ressourcen. Daher gehören zu dieser Vorlesung stets auch Korrektheitsbeweise und Analysen.

Wie entwirft man nun für ein gegebenes Problem einen effizienten Algorithmus? Zunächst benötigen wir grundlegende Kenntnisse Über das Gebiet, aus dem das Problem stammt. Dieses Wissen kann in späteren Spezialvorlesungen erlernt werden, oder es wird direkt bei der Bearbeitung des Problems erworben. In dieser grundlegenden Vorlesung werden wir nur solche Probleme behandeln, für die derartige Spezialkenntnisse nicht erforderlich sind. Darüber hinaus ist der Entwurf effizienter Algorithmen ein Handwerk, wobei Meisterleistungen nur mit viel Erfahrung, dem richtigen Gefühl für das Problem und einer Portion Intuition, manchmal auch Glück, erbracht werden. Ziel unserer Vorlesung muss es also sein, das notwendige Handwerkszeug bereitzustellen und dieses praktisch zu erproben.

Die von uns behandelten Probleme sind so ausgewählt, dass es sich einerseits um wichtige und interessante Probleme handelt und andererseits bei der Lösung dieser Probleme allgemeine Prinzipien und Methoden erlernt werden können.


top

Skript und Folien

Die aktuelle Version des Vorlesungsskriptes zu DAP2 ist nun verfügbar.

Die Vorlesungsfolien erscheinen vorlesungsbegleitend auf dieser Webseite.
Die Vorlesungsfolien gibt es als pdf-Dateien, jeweils mit 1 Folie oder 6 Folien pro Seite.

1 14.04.2009 Einführung [1 Folie/Seite] [6 Folien/Seite] Version vom 14.04.2009
2 16.04.2009 Asymptotische Schranken [1 Folie/Seite] [6 Folien/Seite] Version vom 19.05.2009
3 21.04.2009 Abstrakte Datentypen und Datenstrukturen [1 Folie/Seite] [6 Folien/Seite] Version vom 24.04.2009
4 23.04.2009 Einführung Sortieren [1 Folie/Seite] [6 Folien/Seite] Version vom 28.04.2009
5 28.04.2009 MergeSort, QuickSort [1 Folie/Seite] [6 Folien/Seite] Version vom 28.04.2009
6 30.04.2009 QuickSort, HeapSort (Animation) [1 Folie/Seite] [6 Folien/Seite] Version vom 18.05.2009
7 05.05.2009 HeapSort, Priority Queues [1 Folie/Seite] [6 Folien/Seite] Version vom 05.05.2009
8 12.05.2009 Lineare Sortierverfahren [1 Folie/Seite] [6 Folien/Seite] Version vom 19.05.2009
9 14.05.2009 Externe Sortierverfahren [1 Folie/Seite] [6 Folien/Seite] Version vom 14.05.2009
Binäre Suche [1 Folie/Seite] [6 Folien/Seite] Version vom 14.05.2009
10 19.05.2009 Binäre Suche [1 Folie/Seite] [6 Folien/Seite] Version vom 19.05.2009
11 26.05.2009 Binäre Suchbäume [1 Folie/Seite] [6 Folien/Seite] Version vom 27.05.2009
12, 13 28.05./02.06.2009 Binäre Suchbäume, AVL-Bäume (Animation) [1 Folie/Seite] [6 Folien/Seite] Version vom 29.05.2009
13, 14 02./04.06.2009 B-Bäume, Dictionaries [1 Folie/Seite] [6 Folien/Seite] Version vom 09.06.2009
15, 16 09./16.06.2009 Skiplisten [1 Folie/Seite] [6 Folien/Seite] Version vom 27.06.2009
16, 17 16./18.06.2009 Hashing [1 Folie/Seite] [6 Folien/Seite] Version vom 30.06.2009
17 18.06.2009 Graphen Motivation [1 Folie/Seite] [6 Folien/Seite] Version vom 30.06.2009
18 23.06.2009 Graphen, BFS [1 Folie/Seite] [6 Folien/Seite] Version vom 23.06.2009
19 25.06.2009 Graphen, DFS [1 Folie/Seite] [6 Folien/Seite] Version vom 25.06.2009
20 30.06.2009 Kruskal, Spannbäume [1 Folie/Seite] [6 Folien/Seite] Version vom 30.06.2009
21 02.07.2009 Prim, MST [1 Folie/Seite] [6 Folien/Seite] Version vom 03.07.2009
22 07.07.2009 Kürzeste Wege [Animiertes Beispiel] [1 Folie/Seite] [6 Folien/Seite] Version vom 09.07.2009
23 09.07.2009 Optimierung [1 Folie/Seite] [6 Folien/Seite] Version vom 09.07.2009
24 14.07.2009 Heuristiken, Approximation [1 Folie/Seite] [6 Folien/Seite] Version vom 16.07.2009
25 16.07.2009 Enumeration, Branch and Bound, Dynamische Programmierung [1 Folie/Seite] [6 Folien/Seite] Version vom 27.07.2009
26 23.07.2009 Verbesserungsheuristiken [1 Folie/Seite] [6 Folien/Seite] Version vom 27.07.2009

top

Klausur

Die Klausur ist eine schriftliche Fachprüfung, die zum erfolgreichen Abschluss des Moduls bestanden werden muss. Wir bieten dazu zwei Termine an.

  • 1. Termin: 31.07.2009
  • 2. Termin: 05.10.2009

Fragen zur Klausuranmeldung, Scheinvergabe oder den Übungstests können bitte an diese E-Mail-Adresse gerichtet werden:
dap2klausur2009 ls2.cs.tu-dortmund.de

Ergebnisse der 1.und 2. Klausur

Die Klausurergebnisse hängen am Lehrstuhl 11 aus: OH14, 2. Obergeschoss, Glaskasten gegenüber der Eingangstür.

Die Klausureinsicht zur 1. Klausur fand am 18.08.2009, 9-12 Uhr, in OH14 Raum 202 statt.




2. Klausur

Zur Teilnahme an der Klausur ist eine Anmeldung erforderlich.
Die Anmeldung ist ab sofort bis zum 21.09.2009 möglich.
Die Anmeldung erfolgt in der Regel über das BOSS-System oder das QISPOS-System.
Folgende Modalitäten und Zuständigkeiten gelten für die einzelnen Studiengänge. Sind keine Anmeldefristen angegeben, werden diese von den einzelnen Fakultäten festgelegt, Anmeldeschluss ist normalerweise 14 Tage vor der Klausur.
Fragen oder Probleme bitte an dap2klausur2009 ls2.cs.tu-dortmund.de melden.
  • Informatik AI/KI Bachelor: BOSS System (Team1)
  • Informatik AI/KI Diplom: BOSS System oder QISPOS-System (Team1)
  • IKT/ET Bac/Diplom: Schriftlich bei der Prüfungsverwaltung. (Team3)
  • Physik Bac/Diplom: Dekanat Physik
  • Datenanalyse und Datenmanagement / Statistik Bac/Diplom: Prüfungsamt Statistik
  • Mathematik Bac/Diplom: BOSS System. (Team4)
  • Lehramt BfP: BOSS System. (Team5)
  • Lehramt alte LPO: Dekanat Informatik

Die zweite Klausur findet am 05.10.2009, 10:15 - 11:45 Uhr (90 Minuten) statt. Bitte seien Sie bereits um 10.00 Uhr anwesend.
Es sind keine Hilfsmittel erlaubt.

Die Klausur behandelt den Stoff der Vorlesung und Übungen. Ausgeschlossen wird dabei das Thema "Externe Sortierverfahren" (Kapitel 3.3). Für die Klausur am 31.07.2009 ist außerdem das Kapitel 7 ausgeschlossen, es wird allerdings in der Klausur am 05.10.2009 geprüft.

Raumzuordnung für 2. Klausur

Matrikelnummer Hörsaal
60000 - 117999, Schülerstudenten HG2, HS5
118000 - 133000 HG2, HS6

top

Literatur

Als weiterführende Literatur empfehlen wir eines der folgenden Bücher:

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Algorithmen - Eine Einführung (2. Auflage, Oldenbourg Verlag 2007)
Dieses Buch gilt als Standardwerk auf dem Gebiet Datenstrukturen und Algorithmen. Es erklärt die Themen sehr schön und ausführlich und kann auch über den Stoffumfang von DAP2 hinweg als Nachschlagewerk dienen.

Robert Sedgewick: Algorithmen (2. Auflage, Pearson Studium 2002)
Sehr anschauliches und gut zu lesendes Buch. Sowohl auf Deutsch als auch auf Englisch erhältlich. Diese (aktuelle) Ausgabe beschreibt die Algorithmen - so wie wir es auch in der Vorlesung tun werden - mittels Pseudocode, und umfasst den gesamten Stoffumfang.
Es existieren vom selben Autor auch sehr ähnliche Werke für bestimmte Programmiersprachen, z.B. "Algorithmen in C++". Diese sind in 2 Bände (Band 1 = Teil 1-4, Band 2 = Teil 5) geteilt; in der Vorlesung behandeln wir den Stoff aus beiden Bänden.

T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen (4. Auflage, Spektrum Akademischer Verlag 2002)
Bietet ebenfalls einen sehr anschaulichen Einstieg in die Thematik.

A. Levition: Introduction to the Design and Analysis of Algorithms (2nd Edition, Addison Wesley 2006)
Dieses Buch legt den Schwerpunkt auf den Entwurf von Algorithmen und beschreibt verschiedene Entwurfstechniken ausführlich an Hand von Algorithmen, die die jeweilige Technik benutzen.

<webmaster  ls11.cs.tu-dortmund.de>
Die Universität übernimmt keine Haftung für den Inhalt verlinkter externer Internetseiten