Wintersemester 2007
Prof. Dr. Manfred Kunde

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

Mitteilungen

Die Studierenden mit den folgenden Matrikelnummern sind zur Klausur am 29.2.2008 zugelassen:
(Achtung! Hier hatte sich ein Fehler eingeschlichen. Die Klausur findet am 29. Februar statt, nicht am
29. März!)

4 SWS

23387 25187 26396 27143 28095
28331 28695 28955 29588 31440
3233132455 32666 34615 34912
36344 36349 36503 36918 37831
38229 39419 39491 39662 39689
39702 39815 40419

3 SWS

30304 30459 31212 32690 34719
34889 34891 34929 36447 36625
36638 36654 36840 36920 37982
38134 38240

Wiederholer und alle, die sich (unberechtigter Weide) nicht in dieser Liste wiederfinden, möchten sich bitte möglichst bald bei Michael Brinkmeier melden.

Inhalte

Die Vorlesung Effiziente Algorithmen beschäftigt sich mit dem Entwurf und der Analyse von grundlegenden Algorithmen aus verschiedenen Bereichen der Informatik.

1. Grundlagen der Analyse von Algorithmen
   
   
2. Sortieren
• Allgemeine Sortierverfahren und Ihre Laufzeit
• Bubble-Sort
• Merge-Sort
  
• Quick-Sort
• Heap-Sort
• Mittlere Laufzeit
  
• Untere Schranken für die Laufzeit von Sortierverfahren
• Sortierung strukturierter Schlüssel (Bucket-Sort)
  
  
3. Verwaltung von Mengen
• Union-Find-Datenstrukturen
• Prioritäts-Warteschlangen und Anwendungen
  
• Binomial-Queues
  
• Fibonacci-Heaps
• Amortisierte Analyse
  
  
4. Graphalgorithmen
• Datenstrukturen
• Topologische Sortierung
• Transitive Hülle
  
• Breiten- und Tiefensuche
• Kürzeste Wege
• Minimale/Maximale Spannbäume
  
  
5. Matrizenmultiplikation
   

Termine

• Vorlesungen (Prof. Dr. M. Kunde)
  
• Montag, 13:00-14:30 Uhr, HU-Hs
  
• Donnerstag (G), 15:00-16:30 Uhr, K-Hs2
  
  
• Übungen (Dr. M. Brinkmeier)
• Montag (G), 11:00-12:30, Sr K 2077
• Mittwoch (G), 15:00-16:30, Sr CC 308
  

Kriterien für den Scheinerhalt

Der Schein Effiziente Algorithmen kann in zwei Varianten erworben werden, einer vierstündigen (3V+1Ü) und einer dreistündigen (3V).

Übersicht über die Schein-Kriterien

Erläuterungen zu den Kriterien

• Anwesenheiten: Bei den ogen angegebenen Zahlen handelt es sich um die minimale Anzahl an Teilnahmen für die jeweilige Veranstaltungsform.
  
  
• Klausur: Die Klausur muss bestanden werden. Für die Zulassung zur Klausur ist die Teilnahme an mindestens 11 (von 22) Vorlesungen erforderlich.
  
  
• Übungsprogramm: Insgesamt werden 7 Übungsblätter ausgegeben werden, die in Gruppen mit bis zu zwei Mitgliedern bearbeitet werden können. Um das Übungsprogramm erfolgreich zu absolvieren, müssen die folgenden Kriterien erfüllt sein:
1. Mindestens vier Aufgaben der Übungsblätter 1-7 müssen erfolgreich bearbeitet worden sein.
2. Mindestens eine Aufgabe der Übungsblätter 1 und 2 muss erfolgreich bearbeitet worden sein.
3. Mindestens eine Aufgabe der Übungsblätter 3 und 4 muss erfolgreich bearbeitet worden sein.
4. Mindestens eine Aufgabe der Übungsblätter 5 und 6 muss erfolgreich bearbeitet worden sein.
   

Erfolgreich heisst dabei nicht vollständig richtig, sondern lediglich sinnvoll und im Wesentlichen korrekt.

Die Übungsblätter werden jeweils Mittwochs in den geraden Wochen als PDF zur Verfügung gestellt. Ihre Veröffentlichung wird über die ITI News bekannt gegeben.


• Scheinvariante: Die mögliche Scheinvariante wird, abhängig von den erbrachten Vorleistungen, vor der Klausur bekannt gegeben. D.h. insbesondere, dass Studierende, die nicht genügend Aufgaben gelöst haben, trotzdem den 3V Schein erhalten können.

Wiederholer

Für Studierende, die bereits zu einer "Effiziente-Algorithmen"-Klausur zugelassen waren und nicht bestanden haben, gibt es zwei Möglichkeiten:

• 3V+1Ü: Erfolgreiche Teilnahme an den Übungen und Klausur (Vorlesungsteilnahme entfällt)
• 3V: Teilnahme an der Klausur.

Literatur und Links

Die Vorlesung orientiert sich im Wesentlichen an den folgenden Büchern:

• Kurt Mehlhorn, Datenstrukturen und effiziente Algorithmen, Band 1 Sortieren und Suchen; EATCS Monographs on Theor. Comp. Sci., 1984 (englische Version)
• Ottmann und Widmayer, Algorithmen und Datenstrukturen; Spektrum Akad. Verlag, 1998
• Volker Heun, Grundlegende Algorithmen; Vieweg, 2003

Zusätzlich empfehlen wir:

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 2nd Edition; MIT Press, 2001
• Jon Kleinberg, Eva Tardos, Algorithm Design; Addison Wesley, 2005
• Robert Sedgewick, Algorithmen; Addison-Wesley, 2002
• Uwe Schöning, Algorithmik; Spektrum Akad. Verlag, 2001

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 Wintersemester 2006
• Die Homepage der Vorlesung im Wintersemester 2005
• Das Wörterbuch der Algorithmen und Datenstrukturen des NIST (National Institute of standards and Technology
  

Materialien und Übungsblätter

Dokumente zur Vorlesung

• Folien zur Vorlesung vom 29.10.2007
• Folien zur Vorlesung vom 01.11.2007
• Folien zur Vorlesung vom 05.11.2007
• Folien zur Vorlesung vom 12.11.2007
• Folien zur Vorlesung vom 15.11.2007
• Folien zur Vorlesung vom 19.11.2007
• Folien zur Vorlesung vom 26.11.2007
• Folien zur Vorlesung vom 29.11.2007
• Folien zur Vorlesung vom 03.12.2007
• Folien zur Vorlesung vom 10.12.2007
• Folien zur Vorlesung vom 13.12.2007
• Folien zur Vorlesung vom 17.12.2007
• Folien zur Vorlesung vom 07.01.2008
• Folien zur Vorlesung vom 10.01.2008
• Folien zur Vorlesung vom 14.01.2008
• Folien zur Vorlesung vom 21.01.2008
• Folien zur Vorlesung vom 24.01.2008
• Folien zur Vorlesung vom 28.01.2008
• Folien zur Vorlesung vom 04.02.2008
  

Übungsblätter

• Übungsblatt 1
  Schnelles Potenzieren, Größter gemeinsamer Teiler, Maxsort
  Abgabe: 24.10.2007, 10 Uhr, Briefkasten ITI

• Übungsblatt 2
  Maximum, BUBBLESORT, HEAPSORT, QUICKSORT
  Abgabe: 7.11.2007, 10 Uhr, Briefkasten ITI

• Musterlösung Aufgabe 3 a) [Passwort erforderlich]
  
• Heapsort, Bottom-Up Heapsort
  

• Übungsblatt 3
  Bucketsort, Untere Schranken für das Sortieren, Ordnungsstatistiken
  Abgabe: Do 22.11.2007, 10 Uhr, Briefkasten ITI

• Musterlösung Aufgabe 3 [Passwort erforderlich]
• Seite 1, Seite 2
  
• Musterlösung Aufgabe 5 [Passwort erforderlich]
• Seite 1, Seite 2, Seite 3
  
  
• Übungsblatt 4
  Heaps, Union-Find, Binomial-Queues
  Abgabe: Mi 5.12.2007, 10 Uhr, Briefkasten ITI
  
  
• Übungsblatt 5
  Fibonacci-Heaps, Kürzeste Wege
  Abgabe: Mi 19.12.2007, 10 Uhr, Briefkasten ITI
  
  
• Übungsblatt 6
  Minimale Spannbäume, Kürzeste Wege
  Abgabe: Do 17.1.2008, 10 Uhr, Briefkasten ITI

• Übungsblatt 7
  Maximale Flüsse, Matching
  Abgabe: entfällt