Wintersemester 2008/09
Prof. Dr. M.Kunde

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

Mitteilungen

Die Studierenden mit den folgenden Matrikelnummern sind zur Klausur EA zugelassen:

3SWS
====

25990   27143   34154   36477   36552
36840   37649   39588

4SWS
====

32776   36778   38003   38014   38032
38067   38069   38150   38197   38240
38299   38999   39282   39431   39673
39680   39774   39788   39912

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 und Varianten)
  
• Untere Schranken für die Laufzeit von Sortierverfahren
• Sortierung strukturierter Schlüssel (Bucket-Sort)
• Das Auswahlproblem
  
  
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. Maximale Flüsse
   
   
6. Matrizenmultiplikation
   
   • Strassen - Methode
   • Algebraisches Wegproblem
     
     

Termine

• Vorlesungen
  
• Dienstag,13:00-14:30 Uhr, HU-Hs
• Donnerstasg (G), 13:00-14:30 Uhr, Sr HU 211/212
  
  
• Übungen (Dr. M. Brinkmeier)
  
• Donnerstag (U), 15:00-16:30 Uhr, Sr HU 201
• Freitag (U), 13:00-14:30 Uhr, Ar HU 012
  

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.


• 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 2007
• 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