Algorithmen und Datenstrukturen
(Wintersemester 2015/16)

Veranstalter: Frank Heitmann
Zeit und Ort: Mittwoch 9-12 in Hörsaal A, Chemie

Aktuelles:

[20.10.15] Die Lecture2Go-Vorlesung ist schon seit einigen Tagen online. Link ist unten.

Folien:

Im Wintersemester 2016/17 startet ein neuer Durchgang mit dann neuen Veranstaltern und neuen Materialien! Hier die zum letzten Durchgang:

Errata:
- Ein Errata zur Tiefensuche: PDF
- aud_v4.pdf, Folie 40. Ein Binärbaum ist vollständig, wenn jeder Knoten (bis auf die Blätter) genau zwei Kinder hat und alle Blätter die gleiche Tiefe haben.
Foliensatz 1 (VL 14.10). Kapitel 1. Algorithmen & Algorithmenanalyse
Foliensatz 2 (VL 21.10). Kapitel 2. Korrektheit von Algorithmen und Laufzeitanalyse rekursiver Algorithmen (mittels Rekurrenzgleichungen)
Foliensatz 3 (VL 28.10). Kapitel 3. Divide & Conquer
Foliensatz 4 (VL 4.11). Kapitel 4. Neue Datenstrukturen, besseres (?) Sortieren
Die Vorlesung war in drei Teile gegliedert. Man kann die Foliensätze gut der Reihe nach durchnehmen. Um den (den meisten bekannten) Teil mit den Datenstrukturen nach hinten zu schieben, war das Vorgehen in der Vorlesung etwas sprunghaft. Wir sind so vorgegangen:
- aud_v4, Folie 1+2, 35-40 (um die nötigen Bäume einzuführen)
- aud_v4_2, Folie 1-89 (hin zu HeapSort)
- aud_v4_3, Folie 1-23 (Warteschlangen mit Heaps)
- aud_v4_2, Folie 88-97 (Zusammenfassung 1)
- aud_v4_3, Folie 24-28 (Zusammenfassung 2)
- aud_v4 (die den meisten schon bekannten Datenstrukturen)
Hier nun die einzelnen Foliensätze:
- Teil 1. Datenstrukturen
- Teil 2. Heaps und HeapSort
- Teil 3. Heaps und Prioritätswarteschlangen
Foliensatz 5 (VL 11.11, Teil 1). Kapitel 5. Sortieren - (k?)eine untere Schranke
Foliensatz 6 (VL 11.11, Teil 2). Kapitel 6. Komplexitätstheorie. Einführung in P und NP
Foliensatz 7 (VL 18.11). Kapitel 6.2. Komplexitätstheorie. P, NP und NPC
Falls ihr etwas Nachholbedarf zum Thema Aussagenlogik habt, habe ich euch hier einen kleinen Foliensatz zusammengeschoben, der das für uns wichtigste wiederholt. Ihr braucht hier streng genommen nur die Folien 1-25 (für Syntax und Semantik), die Folien 55 und 56 (für Definition der KNF) und die Folie 74 (nochmal die Nennung der wichtigen NP-vollständigen Probleme der Aussagenlogik). Die anderen Folien sind aber auch interessant, insb. wenn ihr mit dem Beweisen Probleme habt, da hier Beweise in einem einfachen Setting geübt werden können (gemeint sind die Beweise der Aussagen auf Folie 45).
- Aussagenlogik. Syntax & Semantik
Foliensatz 8 (VL 25.11). Kapitel 7. Dynamische Mengen, das Suchproblem & Binäre Suchbäume
Foliensatz 9 (VL 02.12). Kapitel 8. Graphen
- Teil 1. Breiten- und Tiefensuche
- Teil 2. Anwendung der Tiefensuche
Foliensatz 10 (VL 9. und 16.12). Kapitel 9. Minimale Spannbäume und Kürzeste Pfade
Foliensatz 11 (VL 6.1). Kapitel 10. Flüsse
Foliensatz 12 (VL 20.1). Kapitel 11. Zusammenfassung

Übungsaufgaben zur Prüfungsvorbereitung

Im Wintersemester 2016/17 startet ein neuer Durchgang mit dann neuen Veranstaltern und neuen Materialien!

Kommentare/Inhalte:

Die Modellierung eines Problems und die Entwicklung von Algorithmen zur Lösung dieses Problems mit dem Computer sind zentraler Bestandteil der Informatik. Unabhängig von einer späteren Ausrichtung in theoretischer, praktischer oder anwendungsbezogener Informatik sind fundamentale Kenntnisse in dem Prozess des Algorithmenentwurfs unabdingbar. Im Rahmen dieser Veranstaltung werden Entwurfsprinzipien für effiziente Algorithmen und Datenstrukturen vermittelt. Dabei werden eine Reihe von grundlegenden Algorithmen und Datenstrukturen vorgestellt, die zur Lösung häufig auftretender Teilprobleme komplexer Fragestellungen gewinnbringend eingesetzt werden können. Themen in der Vorlesung sind unter anderem:

Rechnermodelle und Komplexitäsmaße
Komplexitäsanalyse von iterativen und rekursiven Algorithmen
Elementare Datenstrukturen wie z.B. Listen, Stapel, Schlangen, Bäume
Dynamische Datenstrukturen: Hashing, (balancierte) Suchbäume
Algorithmen für Suchen und Sortieren
Graphalgorithmen
Algorithmische Entwurfsmethoden wie dynamische Programmierung, Backtracking, Branch & Bound
Umgang mit schwierigen Problemen

Dabei steht neben der Vorstellung der Funktionsweise eines Algorithmus stets auch Betrachtungen zu seiner Laufzeit, seines Speicherbedarfs und seiner Korrektheit im Zentrum der Vorlesung.

Lernziel:

Grundlagen und Faktenwissen im Bereich Algorithmen und Datenstrukturen
Sicherer Umgang mit Entwurfsmethoden für effiziente Algorithmen und Datenstrukturen
Selbstständiges Aneignen von neuen Algorithmen, Datenstrukturen und Analysemethoden
Selbstständiges kreatives Entwickeln von Algorithmen und Datenstrukturen

Vorgehen:

Vorlesung mit Übungen.

Literatur:

Den umfangreichen Klassiker gibt es auf deutsch und englisch:

Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 3nd Edition, MIT Press 2009
Cormen, Leiserson, Rivest, Stein: Algorithmen - Eine Einführung, Oldenbourg Verlag, 2010

Ein neuerer Klassiker, auch sehr umfangreich, nur auf englisch:

Jon Kleinberg, Eva Tardos: Algorithm Design, Addison-Wesley 2005.

Und zwei einführende, populärwissenschaftliche Bücher zum zwischendurch lesen:

Berthold Vöcking et al: Taschenbuch der Algorithmen. Springer, 2008.
MacCormick: 9 Algorithms that changed the future. Princeton University Press, 2012

Imprint/Disclaimer

Last Change: 12:41 10/06/2016

Algorithmen und Datenstrukturen (Wintersemester 2015/16)