Sidebar
Algorithmen und Berechnungskomplexität I
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 / A7a | Torben 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:45 | AVZ 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äsenzblatt (Besprechung in KW 43, keine Abgabe)
- Übungsblatt 1 (Besprechung in KW 44, Abgabe bis 25.10., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 2 (Besprechung in KW 45, Abgabe bis 03.11., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 3 (Besprechung in KW 46, Abgabe bis 08.11., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 4 (Besprechung in KW 47, Abgabe bis 15.11., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 5 (Besprechung in KW 48, Abgabe bis 22.11., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 6 (Besprechung in KW 49, Abgabe bis 29.11., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 7 (Besprechung in KW 50, Abgabe bis 06.12., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 8 (Besprechung in KW 51, Abgabe bis 13.12., 12:30 Uhr, im Briefkasten in der Römerstraße)
Hinweise zum Dateiformat
Ue8_A1a.txt, Ue8_A1b.txt, Ue8_sample.txt, Ue8_exercise.txt - Übungsblatt 9 (Besprechung in KW 2, Abgabe bis 20.12., 12:30 Uhr, im Briefkasten in der Römerstraße)
Hinweise zum Dateiformat
Ue9_small.txt, Ue9_medium.txt, Ue9_large.txt - Übungsblatt 10 (Besprechung in KW 3, Abgabe bis 10.01., 12:30 Uhr, im Briefkasten in der Römerstraße)
Hinweise zum Dateiformat
Ue10_small.txt, Ue10_medium.txt, Ue10_large.txt - Übungsblatt 11 (Besprechung in KW 4, Abgabe bis 17.01., 12:30 Uhr, im Briefkasten in der Römerstraße)
Hinweise zum Dateiformat
Ue11_small.txt, Ue11_medium.txt, Ue11_large.txt - Übungsblatt 12 (Besprechung in KW 5, Abgabe bis 24.01., 12:30 Uhr, im Briefkasten in der Römerstraße)
Hinweise zum Dateiformat
Ue12a.txt, Ue12b.txt, Ue12c.txt - Probeklausur (Besprechung in KW 6, Keine Abgabe)
Literatur
Die Inhalte der Vorlesung finden sich in diesem Skript.