Algorithmen und Berechnungskomplexität I

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	Folien zur Vorlesung 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	Skript Kapitel 21 und 23 in [CLRS]
1. Dezember	4.4 Kürzeste Wege 4.4.1 Single-Source Shortest Path Problem	Skript 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	Skript 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	Skript 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	Skript Kapitel 4.1 und 5.1 in [We2] Kapitel 1 in [Bl2]
12. Januar	5.2.1 Minimierung endlicher Automaten	Skript Kapitel 4.2 in [We2] Kapitel 1 in [Bl2]
17. Januar	5.2.2 Pumping-Lemma für endliche Automaten	Skript 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	Skript 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	Skript Kapitel 6 in [We2] Kapitel 1 in [Bl2]
26. Januar	5.4.2 Pumping-Lemma für kontextfreie Sprachen	Skript 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	Skript Kapitel 7 und 8 in [We2] Kapitel 1 in [Bl2]
2. Februar	5.5.3 Bottom-up Syntaxanalyse 5.5.4 Parsergenerierung mit JavaCC	Skript Kapitel 7 und 8 in [We2] Kapitel 1 in [Bl2] The JavaCC Tutorial

Ü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

Präsenzblatt (Besprechung in KW 42, keine Abgabe)
Übungsblatt 1 (Besprechung in KW 43, Abgabe am 20.10. in der Vorlesung)
Übungsblatt 2 (Besprechung in KW 44, Abgabe am 27.10. in der Vorlesung)
Übungsblatt 3 (Besprechung in KW 45, Abgabe am 03.11. in der Vorlesung)
Übungsblatt 4 (Besprechung in KW 46, Abgabe am 10.11. in der Vorlesung)
Übungsblatt 5 (Besprechung in KW 47, Abgabe am 17.11. in der Vorlesung)
Übungsblatt 6 (Besprechung in KW 48, Abgabe am 24.11. in der Vorlesung)
Übungsblatt 7 (Besprechung in KW 49, Abgabe am 01.12. in der Vorlesung)

Lösung zu Aufgabe 7.4
Übungsblatt 8 (Besprechung in KW 02, Abgabe am 13.12. in der Vorlesung)

Lösung zu Aufgabe 8.5
Übungsblatt 9 (Besprechung in KW 03, Abgabe am 12.01. in der Vorlesung)

Lösung zu Aufgabe 9.5
Probeklausur

Musterlösung zur Probeklausur
Übungsblatt 10 (Besprechung in KW 04, Abgabe am 19.01. in der Vorlesung)

Lösung zu Aufgabe 10.4 (c)
Übungsblatt 11 (Besprechung in KW 05, Abgabe am 26.01. in der Vorlesung)

Lösung zu Aufgabe 11.5

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

Die Vorlesung basiert in wesentlichen Teilen auf der folgenden Literatur:

[CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms.
ISBN: 978-0262533058, MIT Press, 3. Auflage, 2009.
[Vö] Berthold Vöcking. Skript zur Vorlesung "Berechenbarkeit und Komplexität".
Wintersemester 2009/10, RWTH Aachen.
[We] Ingo Wegener. Skript zur Vorlesung "DAP 2".
Sommersemester 2007, Universität Dortmund.
[We2] Ingo Wegener. Theoretische Informatik - eine algorithmenorientierte Einführung.
ISBN: 978-3835100336, Teubner Verlag, 3. Auflage, 2005.

Weiterführende Literatur:

[Bl] Norbert Blum. Algorithmen und Datenstrukturen: Eine anwendungsorientierte Einführung.
ISBN: 978-3486273946, Oldenbourg, 2004.
[Bl2] Norbert Blum. Einführung in Formale Sprachen, Berechenbarkeit, Informations- und Lerntheorie.
ISBN: 978-3486274332, Oldenbourg, 2006.
[MIT] Material zum Kurs "Introduction to Algorithms" am MIT.
[We3] Ingo Wegener. Kompendium Theoretische Informatik: Eine Ideensammlung.
ISBN: 978-3519021452, Teubner Verlag, 1996.

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.