Sommersemester 2007
Prof. Dr. Manfred Kunde

[Mitteilungen] [Inhalte] [Termine] [Scheinerhalt] [Literatur] [Materialien]

Mitteilungen

• 9.7.2007: Die Übungen in der 28. KW fallen aus! Stattdessen findet am 10.7. um 13:00 Uhr im Helmholtz-Hörsaal eine Konsultation/Frage-Stunde statt!
  
  
• 29.6.2007: Die Übungem am Mo 2.7. und am Do 5.7. fallen aus. Stattdessen wird *eine* große Übung am Di 3.7. im Helmholtz-Hörsaal (H-Hs) stattfinden.
  
• 28.6.2007: Die heutige Übung muss leider ausfallen! Musterlösungen für Blatt 10 werden in den nächsten Tagen online gestellt.
  
• 27.6.2007: Blatt 11 wurde aktualisiert!
  
• 25.6.2007: Vorraussichtlich werden die Vorlesungen bis Ende des Semesters von Dr. M. Brinkmeier gehalten.
  
• 14.6.2007: Die Übung am 14.6. (15 Uhr) fällt aus!
  
• 12.4.2007: Übungsblatt 2 ist online!
  
• 5.4.2007: Übungsblatt 1ist online!
  
• 4.4.2007: Die Übungen beginnen am 10.4.!
  
• 4.4.2007: Diese Seite wurde freigeschaltet!
  

Inhalte

In der Vorlesung werden grundlegende Prinzipien für den Entwurf und die Analyse von Algorithmen und Datenstrukturen besprochen. Dazu gehören insbesondere die Analyse der Laufzeit und der Korrektheit des Ergebnisses. Die vorgestellten Techniken werden an konkreten Algorithmen aus verschiedenen Bereichen erläutert.

Übersicht über die geplanten Themen

• Grundlegende Techniken (z.B. Iteration und Rekursion)
• Analyse von Algorithmen (z.B. Korrektheit, Laufzeitverhalten sowie asymptotische Notationen)
  
• Grundlegende Datentypen und Datenstrukturen (Stacks, Queues, Listen, Binärbäume,...), einschließlich Implementierung und Analyse
• Balancierte Suchbäume und einfache Hashverfahren
• Sortierverfahren (Insertion-Sort, Mergesort, Heapsort, Bubblesort, Quicksort, Bucketsort, Radixsort)
• Grundbegriffe der Graphentheorie sowie grundlegende Algorithmen für Graphen:
• Breiten- und Tiefensuche
• Zusammenhangskomponenten
• Minimale Spannbäume
• Detektion von Kreisen
• Algorithmenparadigmen:
• Greedy
• Divide-and-Conquer
• Dynamische Programmierung
• Backtracking
• Branch-and-Bound
• Priority Queues (Vorrangswarteschlangen)

Termine

Die Übungen beginnen am 10.4.2007 !

Kriterien für den Scheinerhalt

Am Ende des Semesters muß eine Prüfungsklausur bestanden werden. Die Dauer hängt von der Art des Studienganges ab:

• Bachelor: 90 Minuten
• Diplom: 80 Minuten
  

Voraussichtlich wird die tatsächliche Dauer der Klausur für alle Studenten 90 Minuten betragen. Die Studierenden eines Diplom-Studienganges müssen jedoch eine Aufgabe weniger bearbeiten.

Das Übungsprogramm ist obligatorisch. Es wird jede Woche Übungszettel geben, die in den Übungen besprochen werden.

Literatur und Links

Begleitend zur Vorlesung empfehlen wir die folgenden Bücher und Skripte:

• Dietzfelbinger, Algorithmen und Datenstrukturen, Skript, TU Ilmenau, 2005
  
  
• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 2nd Edition; MIT Press, 2001
• Ottmann und Widmayer, Algorithmen und Datenstrukturen; Spektrum Akad. Verlag, 1998
• Robert Sedgewick, Algorithmen; Addison-Wesley, 2002
• Uwe Schöning, Algorithmik; Spektrum Akad. Verlag, 2001
• Kurt Mehlhorn, Datenstrukturen und effiziente Algorithmen, Band 1 Sortieren und Suchen; EATCS Monographs on Theor. Comp. Sci., 1984 (englische Version)
• Jon Kleinberg, Eva Tardos, Algorithm Design; Addison Wesley, 2005
• Volker Heun, Grundlegende Algorithmen; Vieweg, 2003

Die Bücher befinden sich teilweise in größerer Zahl in der Bibliothek und können dort entliehen werden.

Links

• Die Homepage der Vorlesung im Sommersemester 2006
• Die Homepage der Vorlesung im Sommersemester 2005
  
  
• Das Wörterbuch der Algorithmen und Datenstrukturen des NIST (National Institute of standards and Technology

Materialien und Übungsblätter