Algorithmen und Berechnungskomplexität I

Die Klausureinsicht wird am 28. Februar 2017 zwischen 14:00 und 15:00 Uhr im LBH Raum E.08 stattfinden.

Termine

Art Wann Wo Beginn Dozent
V4 Dienstag 12:30 -14:00
Donnerstag 12:30 - 14:00
AVZ III / HS 1
AVZ III / HS 1
18. Oktober 2016 Röglin
Ü2 24. Oktober 2016 Glässer, Hoeckendorff, Klaassen, Plitt, Rademacher, Zaiser

Inhalt

In dieser Vorlesung werden wir uns mit dem Entwurf und der Analyse von Algorithmen beschäftigen. Ein Algorithmus ist eine Handlungsvorschrift zur Lösung eines Problems, die so präzise formuliert ist, dass sie von einem Computer ausgeführt werden kann. Algorithmen sind heute so allgegenwärtig, dass sie kaum wahrgenommen oder gewürdigt werden. Wie selbstverständlich nutzen wir Navigationsgeräte, um den besten Weg vom Start zum Ziel zu bestimmen, oder Suchmaschinen, um innerhalb kürzester Zeit riesengroße Datenmengen zu durchsuchen. Dass dies überhaupt möglich ist, liegt zum Teil an der immer besseren Hardware, zu einem viel größeren Teil liegt es aber an den cleveren Algorithmen, die für diese Anwendungen entwickelt wurden. In dieser Vorlesung werden wir Techniken zum Entwurf und zur Analyse von Algorithmen kennenlernen und diese nutzen, um effiziente Algorithmen für zahlreiche grundlegende Probleme zu entwerfen.

Datum Inhalt
18. Oktober 1 Einleitung
1.1 Grundbegriffe
1.2 Ein erstes Beispiel: Insertionsort
20. Oktober 1.2 Ein erstes Beispiel: Insertionsort (Fortsetzung)
1.3 Registermaschinen
1.4 Größenordnungen
2 Methoden zum Entwurf von Algorithmen
2.1 Divide-and-Conquer
25. Oktober 2.1.1 Mergesort
2.1.2 Strassen-Algorithmus
27. Oktober 2.1.3 Lösen von Rekursionsgleichungen
2.2 Greedy-Algorithmen
2.2.1 Optimale Auswahl von Aufgaben
3. November 2.2.2 Rucksackproblem mit teilbaren Objekten
8. November 2.3 Dynamische Programmierung
2.3.1 Berechnung optimaler Zuschnitte
10. November 2.3.2 Rucksackproblem
3 Sortieren
3.1 Quicksort
15. November 3.1 Quicksort (Fortsetzung)
3.2 Eigenschaften von Sortieralgorithmen
3.3 Untere Schranke für die Laufzeit vergleichsbasierter Sortieralgorithmen
3.4 Sortieren in Linearzeit
17. November 4 Dynamische Mengen
4.1 Felder und Listen
4.2 Suchbäume
22. November 4.2.1 AVL-Bäume
24. November 4.2.1 AVL-Bäume (Fortsetzung)
4.2.2 B-Bäume
29. November 4.2.2 B-Bäume (Fortsetzung)
4.3 Hashing
4.3.1 Hashfunktionen
4.3.2 Hashing mit verketteten Listen
1. Dezember 4.3.2 Hashing mit verketteten Listen (Fortsetzung)
4.3.3 Geschlossenes Hashing
6. Dezember 4.3.3 Geschlossenes Hashing (Fortsetzung)
5 Graphenalgorithmen
8. Dezember 5.1 Tiefen- und Breitensuche
5.1.1 Tiefensuche
13. Dezember 5.1.1 Tiefensuche (Fortsetzung)
5.1.2 Breitensuche
15. Dezember 5.1.2 Breitensuche (Fortsetzung)
5.2 Minimale Spannbäume
5.2.1 Union-Find-Datenstrukturen
20. Dezember 5.2.1 Union-Find-Datenstrukturen (Fortsetzung)
5.2.2 Algorithmus von Kruskal
22. Dezember 5.2.2 Algorithmus von Kruskal (Fortsetzung)
10. Januar 5.3 Kürzeste Wege
5.3.1 Grundlegende Eigenschaften von kürzesten Wegen
5.3.2 Single-Source Shortest Path Problem
12. Januar 5.3.2 Single-Source Shortest Path Problem (Fortsetzung)
5.3.3 All-Pairs Shortest Path Problem
17. Januar 5.3.3 All-Pairs Shortest Path Problem (Fortsetzung)
5.4 Flussprobleme
5.4.1 Anwendungsbeispiele
5.4.2 Algorithmus von Ford und Fulkerson
19. Januar 5.4.2 Algorithmus von Ford und Fulkerson (Fortsetzung)
24. Januar 5.4.3 Algorithmus von Edmonds und Karp
6 Lineare Programmierung
6.1 Grundlagen
6.1.1 Kanonische Form und Gleichungsform
26. Januar 6.1.2 Geometrische Interpretation
6.1.3 Algebraische Interpretation
31. Januar 6.1.3 Algebraische Interpretation (Fortsetzung)
7 Kontextfreie Sprachen
7.1 Sprachen und Grammatiken
7.2 Chomsky-Normalform und der Cocke-Younger-Kasami-Algorithmus
2. Februar 7.2 Chomsky-Normalform und der Cocke-Younger-Kasami-Algorithmus (Fortsetzung)
7.3 Pumping-Lemma für kontextfreie Sprachen

Übungen

Für den Erhalt des Übungsscheins müssen insgesamt mindestens 50% der zu erreichenden Punkte bei den Übungsaufgaben erreicht werden und Lösungen von zwei Aufgaben müssen im Laufe des Semesters erfolgreich in den Tutorien präsentiert werden. Eine Abgabe der Übungsaufgaben in Gruppen bis zu drei Studierenden ist möglich.

Die Abgabe erfolgt im entsprechend gekennzeichneten Briefkasten in der Römerstraße. Es werden nur Abgaben akzeptiert, bei denen auf der ersten Seite gut erkennbar die Nummer der Übungsgruppe notiert ist.

Nr. Wann Wo Tutor
1 Montag 8:15 - 9:45 AVZ III / A301 Florian Glässer
2 Montag 12:15 - 13:45 AVZ III / A6c Malte Klaassen
3 Montag 12:15 - 13:45 AVZ III / A7a Danny Rademacher
4 Montag 12:15 - 13:45 AVZ III / A7b Torben Plitt
5 Montag 14:15 - 15:45 AVZ III / A7a Danny Rademacher
6 Mittwoch 12:15 - 13:45 AVZ III / A7aTorben Plitt
7 Mittwoch 12:15 - 13:45 AVZ III / A301 Jan Hoeckendorff
8 Mittwoch 14:15 - 15:45 AVZ III / A301a Jan Hoeckendorff
9 Donnerstag 8:15 - 9:45 AVZ III / A7a Fabian Zaiser
10 Donnerstag 10:15 - 11:45AVZ III / A301 Fabian Zaiser
11 Freitag 10:15 - 11:45 AVZ III / A7a Florian Glässer
12 Freitag 12:15 - 13:45 AVZ III / A301 Malte Klaassen

Anmeldung zu den Übungen:

Die Anmeldung zu den Übungsgruppen erfolgt über das Tutorienvergabesystem (TVS). Eine einmalige Registrierung ist vom Netz der Universität Bonn aus erforderlich. Anschließend können Sie von überall auf das TVS zugreifen.

Die Verteilung der Übungsgruppen über das Tutorienvergabesystem ist abgeschlossen. Bei nachträglichen Anmeldungen und Fragen zum Übungsbetrieb wenden Sie sich bitten an Clemens Rösner (roesner@cs.uni-bonn.de).

Prüfungen

Die erste Klausur wird am 13. Februar 2017 zwischen 14:30 und 17 Uhr im Hauptgebäude der Universität stattfinden. Einlass ist ab ca. 14:15.
Raumverteilung:
Studenten mit Nachnamen A-G: Hörsaal I
Studenten mit Nachnamen H-Z: Hörsaal X

Die Nachklausur wird am 27. März 2017 zwischen 13 und 16 Uhr in der Römerstraße stattfinden.

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript.


Page Tools