Algorithmen und Berechnungskomplexität I

Termine

Art Wann Wo Beginn LP Dozent
V4
Montag 11 (c.t.) - 13
Mittwoch 11 (c.t.) - 13
AVZ III / HS 1
AVZ III / HS 1
11. Oktober 2010 5 Röglin
Ü2 Termine 18. Oktober 2010 3 Brunsch, Gödde, Vößing

Inhalt

In der Vorlesung werden grundlegende Datenstrukturen eingeführt und es werden wichtige Techniken zum Entwurf von Algorithmen vorgestellt. Im zweiten Teil der Vorlesung werden die Grenzen der Algorithmik beleuchtet. Es wird diskutiert, welche Probleme überhaupt berechenbar sind und welche Probleme effizient gelöst werden können.

Unten folgt eine genaue Inhaltsangabe der einzelnen Vorlesungstermine:

Datum Inhalt Literatur
11. Oktober
Organisatorisches, Ausblick
1. Grundlagen
1.1 Einführung
1.2 Insertion Sort
Kapitel 1.1 und 1.2 in [CLRS]
13. Oktober
1.3 Größenordnungen
1.4 Registermaschinen
Kapitel 1.3 in [CLRS]
Kapitel 1.2.2 in [Vö]
18. Oktober
2. Dynamische Mengen
2.1 Arrays und Listen
2.2 Bäume
2.2.1 Binäre Suchbäume
Kapitel 10.1, 10.2, 10.4 in [CLRS]
Kapitel 12.1 - 12.3 in [CLRS]
Kapitel 1 - 1.2.1 in [Bl]
20. Oktober
2.2.2 AVL-Bäume
Kapitel 3.6 in [We]
Kapitel 1.2.2 in [Bl]
25. Oktober
2.2.3 B-Bäume
Kapitel 3.5 in [We]
Kapitel 18 in [CLRS]
Kapitel 1.2.3 in [Bl]
27. Oktober
2.3 Hashing
Kapitel 3.2 in [We]
Kapitel 11 bis 11.4 in [CLRS]
Kapitel 1.3 in [Bl]
3. November
2.3.1 Hashing mit verketteten Listen
2.3.2 Hashfunktionen
siehe oben
8. November
2.3.3 Hashing mit offener Adressierung
siehe oben
10. November
3. Sortieren
3.1 Insertion Sort
3.2 Quick Sort
Kapitel 4.2 und 4.4 in [We]
Kapitel 7 in [CLRS]
15. November
3.3 Heap Sort
Kapitel 4.5 in [We]
Kapitel 6 in [CLRS]
17. November
3.4 Untere Schranke für allgemeine Sortierverfahren
3.5 Radix Sort
Kapitel 4.6 und 4.7 in [We]
Kapitel 8 in [CLRS]
22. November
4 Elementare Graphalgorithmen
4.1 Datenstrukturen für Graphen
4.2 Tiefen- und Breitensuche
Kapitel 2.6 in [We]
Kapitel 22 in [CLRS]
Kapitel 2 in [Bl]
24. November
Fortsetzung von 4.2
siehe oben
29. November
4.3 Minimale Spannbäume
Kapitel 21 und 23 in [CLRS]
1. Dezember
4.4 Kürzeste Wege
4.4.1 Single-Source Shortest Path Problem
Kapitel 24 in [CLRS]
Kapitel 4.3.1 in [Bl]
6. Dezember Fortsetzung von 4.4.1 siehe oben
8. Dezember Dies Academicus
13. Dezember
4.4.2 All-Pairs Shortest Path Problem
Kapitel 25 in [CLRS]
Kapitel 4.3.3 in [Bl]
15. Dezember Probeklausur
20. Dezember
4.5 Flussprobleme
4.5.1 Algorithmus von Ford und Fulkerson
4.5.2 Algorithmus von Edmonds und Karp
Kapitel 26 in [CLRS]
Kapitel 4.5 in [Bl]
22. Dezember Vorlesung entfällt wegen verlängerter Vorlesung am 20. Dezember
10. Januar
5 Automatentheorie und formale Sprachen
5.1 Sprachen, Grammatiken und die Chomsky-Hierarchie
5.2 Endliche Automaten
Kapitel 4.1 und 5.1 in [We2]
Kapitel 1 in [Bl2]
12. Januar
5.2.1 Minimierung endlicher Automaten
Kapitel 4.2 in [We2]
Kapitel 1 in [Bl2]
17. Januar
5.2.2 Pumping-Lemma für endliche Automaten
Kapitel 4.3 in [We2]
Kapitel 1 in [Bl2]
19. Januar
5.2.3 Nichtdeterministische endliche Automaten
5.3 Reguläre Sprachen, endliche Automaten und reguläre Ausdrücke
Kapitel 4.4 und 5.3 in [We2]
Kapitel 1 in [Bl2]
24. Januar
5.4 Kontextfreie Sprachen
5.4.1 Chomsky-Normalform und der Cocke-Younger-Kasami-Algorithmus
Kapitel 6 in [We2]
Kapitel 1 in [Bl2]
26. Januar
5.4.2 Pumping-Lemma für kontextfreie Sprachen
Kapitel 6 in [We2]
Kapitel 1 in [Bl2]
31. Januar
5.5 Kellerautomaten und Syntaxanalyse
5.5.1 Nichtdeterministische Kellerautomaten
5.5.2 Deterministisch kontextfreie Sprachen
Kapitel 7 und 8 in [We2]
Kapitel 1 in [Bl2]
2. Februar
5.5.3 Bottom-up Syntaxanalyse
5.5.4 Parsergenerierung mit JavaCC
Kapitel 7 und 8 in [We2]
Kapitel 1 in [Bl2]

Übungen

Wann Wo Tutor
1 Montag 13 (c.t.) - 15 AVZ III / A7a Johannes Vößing
2 Mittwoch 13 (c.t.) - 15 AVZ III / A7a Johannes Vößing
3 Donnerstag 11 (c.t.) - 13 AVZ III / A7a Tobias Brunsch
4 Donnerstag 13 (c.t.) - 15 AVZ III / A301 Tobias Brunsch
5 Freitag 11 (c.t.) - 13 AVZ III / A7a Kai Gödde
6 Freitag 13 (c.t.) - 15 AVZ III / A301 Kai Gödde

Übungszettel


Klausuren

Art Wann Wo
Probeklausur Mittwoch, 15. Dezember 2010, 11:15 - 12:45 Uhr AVZ III / HS 1
Klausur Donnerstag, 10. Februar 2011, 9:30 - 11:30 Uhr Hauptgebäude, Hörsaal X
Nachklausur Donnerstag, 24. März 2011, 10:15 - 12:15 Uhr Hauptgebäude, Hörsaal I
Zweite Nachklausur Freitag, 20. Mai 2011, 12:30 - 14:30 Uhr AVZ III / Raum 6B

Ein Ferientutorium zur Vorbereitung auf die Nachklausur fand vom 14. bis zum 18. März statt.


Literatur

Zu Teilen der Vorlesung gibt es ein Skript: Die Vorlesung basiert in wesentlichen Teilen auf der folgenden Literatur: Weiterführende Literatur: Des Weiteren gibt es auf dieser Seite eine Vorlesungsmitschrift von Tobias Hartmann. (Sollten Ihnen die Zugangsdaten nicht bekannt sein, so hilft die Fachschaft sicher gerne weiter.) Beachten Sie bitte, dass es sich hierbei nicht um ein offizielles Skript handelt, sondern um eine private Vorlesungsmitschrift.