Prof. Dr. Klaus Volbert

Letzte Aktualisierung: 09.02.2012

Algorithmen und Datenstrukturen (Sommersemester 2011, V4, Ü2, 8 ECTS-Punkte)

Folgende Themen werden in der Veranstaltung behandelt:

  • Komplexitätsanalyse
    • Modelle zur Laufzeit- und Speicherplatzanalyse
    • Best-, Average- und Worst Case Analyse
    • Komplexitätsklassen
    • Asymptotische Komplexität
    • Lösen von Rekursionsgleichungen
  • Entwurfsmethoden
    • Divide and Conquer
    • Dynamische Programmierung
    • Greedy-Algorithmen
    • Backtracking
  • Algorithmen für Standard-Probleme
    • Elementare, fortgeschrittene und schlüsselbasierte Sortierverfahren
    • Datenstrukturen zur Verwaltung von Mengen
      (z.B. binäre Suchbäume, balancierte Bäume, Queues, Hashing, Suche in Mengen und Zeichenketten, Graph-Algorithmen - z.B. Tiefen- und Breitensuche, kürzeste Wege, minimale Spannbäume)

Termine

Studiengang Informatik

  • Vorlesungen, Start: 15.03.2011:
    • Di. : 08:15 - 09:45, Raum U312
    • Do.: 13:30 - 15:00, Raum U312
  • Übungen, Start: 21.03.2011:
    • Gruppe 1: Mo.: 13:30 - 15:00, Raum E521 (Klaus Volbert)
    • Gruppe 2: Mo.: 13:30 - 15:00, Raum E513 (Andreas Wittmann)

Studiengang Technische Informatik

  • Vorlesungen, Start: 15.03.2011:
    • Di. : 10:00 - 11:30, Raum U411
    • Mo.: 15:15 - 16:45, Raum U411
  • Übungen, Start: 17.03.2011:
    • Gruppe 1: Do.: 17:00 - 18:30, Raum E521 (Klaus Volbert)
    • Gruppe 2: Do.: 17:00 - 18:30, Raum E513 (Andreas Wittmann)

Vorlesung

Die Vorlesung orientiert sich im Wesentlichen an "Introduction to Algorithms" von T. H. Cormen, C. E. Leisserson, R. L. Rivest und C. Stein.

Datum Thema Unterlagen
15.03.2011 Organisation, Einführung und Übersicht Vorlesung 1 (o.H.)
17./21.03.2011 Grundlagen (Begriffe und Beispiele) Vorlesung 2 (o.H.)
22.03.2011 Grundlagen (Komplexität) Vorlesung 3 (o.H.)
24./28.03.2011 Grundlagen (Komplexität, Rekursion) Vorlesung 4 (o.H.)
29.03.2011 Grundlagen (Komplexität, Rekursion) Vorlesung 5 (o.H.)
05.04.2011 Einfache Sortieralgorithmen Vorlesung 6 (o.H.)
07./11.04.2011 Fortgeschrittene Sortieralgorithmen Vorlesung 7 (o.H.)
12.04.2011 Fortgeschrittene und Spezielle Sortieralgorithmen Vorlesung 8 (o.H.)
14./18.04.2011 Dynamische Datenstrukturen (Listen, Stapel, Schlangen) Vorlesung 9 (o.H.)
19.04.2011 Dynamische Datenstrukturen (Bäume) Vorlesung 10 (o.H.)
28.04./02.05.2011 Suchalgorithmen (Wörterbücher) Vorlesung 11 (o.H.)
03.05.2011 Suchalgorithmen (AVL-Bäume) Vorlesung 12 (o.H.)
05./09.05.2011 Suchalgorithmen (RS-Bäume, B-Bäume) Vorlesung 13 (o.H.)
10.05.2011 Suchalgorithmen (B-Bäume, Hashing) Vorlesung 14 (o.H.)
12.05./16.05.2011 Suchalgorihtmen (Hashing) Vorlesung 15 (o.H.)
17.05.2011 Suchalgorihtmen (Hashing und Skip-Listen) Vorlesung 16 (o.H.)
19./23.05.2011 Suchalgorithmen (Skip-Listen und Textsuche) Vorlesung 17 (o.H.)
24.05.2011 Suchalgorithmen (Textsuche) und Graphalgorithmen (Einführung) Vorlesung 18 (o.H.)
26./30.05.2011 Graphalgorithmen (Breiten- und Tiefensuche, Top. Sortierung) Vorlesung 19 (o.H.)
31.05.2011 Graphalgorithmen (Minimale Spannbäume) Vorlesung 20 (o.H.)
06./07.06.2011 Graphalgorithmen (Minimale Spannbäume, Kürzeste Wege) Vorlesung 21 (o.H.)
07./09.06.2011 Graphalgorithmen (Kürzeste Wege) Vorlesung 22 (o.H.)
16./20.06.2011 Graphalgorithmen (Kürzeste Wege, Dynamische Programmierung) Vorlesung 23 (o.H.)
21.06.2011 Graphalgorithmen (Kürzeste Wege: All-Pairs-Shortest-Paths) Vorlesung 24 (o.H.)
27./28.06.2011 NP-Vollständigkeit (Begriffe) Vorlesung 25 (o.H.)
28./30.06.2011 NP-Vollständigkeit (Reduktionen) Vorlesung 26 (o.H.)
04./05.07.2011 Approximationsalgorithmen und Backtracking Vorlesung 27 (o.H.)

Übung

Die Übungsgruppeneinteilung erfolgt in der 1. Vorlesung. Jede Woche am Dienstag erscheint ein Übungsblatt mit 4 Aufgaben. Die Bearbeitung der Aufgaben kann und sollte schon vor der Übung starten. Sie wird dann in den Übungen fortgesetzt, so dass der Übungsgruppenleiter bei der Bearbeitung unterstützen kann. Der Umfang der Übungsaufgaben ist bewusst größer angelegt als der Umfang einer Übungseinheit. Die Bearbeitung aller Übungsaufgaben sollte nach einer Übungseinheit fertiggestellt werden (Nacharbeiten und Üben sind wichtig!), damit sie zu Beginn der folgenden Übungsstunde effizient besprochen werden kann. Jeder Studierende sollte die Chance zum Fragen und zum Präsentieren einer Lösung nutzen!

Eine regelmäßige und aktive Teilnahme an den Übungen ist Voraussetzung für die Teilnahme an einer Prüfung. Eine Abgabe der bearbeiteten Übungsaufgaben ist nicht erforderlich (freiwilliger Übungsbetrieb).

Prüfung

  • Art der Prüfung
    • schriftlich, 90 Minuten
  • Hilfsmittel
    • beidseitig handgeschriebenes DIN A4 Blatt
  • Relevante Themen
    • Gesamter Stoff der Vorlesung
    • Klausuraufgaben angelehnt an Übungsaufgaben
  • Voraussetzung zur Teilnahme an der Prüfung
    • Regelmäßige und aktive Teilnahme an den Übungen

Prüfungstermin

Dienstag, 09.07.2011, 10:45 - 12:15 Uhr, Räume U212 und U213

  • Notenliste (Zugriff nur im Uni-/Hochschulnetz möglich!)

Dienstag, 31.01.2012, 08:15 - 09:45 Uhr, Räume U311

  • Notenliste (Zugriff nur im Uni-/Hochschulnetz möglich!

Literatur

  • Cormen, T. H., Leisserson, C. E., Rivest, R.L., Stein, C.: Introduction to Algorithms, MIT Press, 2001
  • Kleinberg, J., Tardos, E.: Algorithm Design, Addison Wesley, 2005
  • Ottmann, T., Widmayer, P.: Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag, 2002
  • Pomberger, G., Dobler, H.: Algorithmen und Datenstrukturen, Pearson Studium 2008
  • Schöning, U.: Algorithmik, Spektrum Akademischer Verlag, 2001
  • Sedgewick, R.: Algorithmen in C++, Pearson Studium 2002
  • Solymosi, A., Grude, U.: Grundkurs Algorithmen und Datenstrukturen in JAVA: Eine Einführung in die praktische Informatik, Vieweg, 2008