gehalten von
Dr. M. Brinkmeier

auf Basis der Vorlesung von
Prof. Dr. M. Kunde

[Mitteilungen] [Inhalt] [Termine] [Scheinerhalt] [Literatur] [Materialien und Übungsblätter]

Mitteilungen

• Zu den Ergebnissen der Studentenbefragung
  
  
• 24.1.2006: Neu im Sortiment! Ein Archiv mit allen Handouts!
  
  
• 18.1.2006: Auf den Folien zur Matrizenmultiplikation hat der Fehlerteufel nochmal zugeschlagen. Auf Folie 17/35 muss die Formel für C_22 korrigiert werden. Korrekt ist: C_22 = A_21 B_12 + A_22 B_22! Die korrigierte Version ist jetzt online.
• 16.1.2006: Bei der Darstellung der Strassen-Multiplikation (Matrizen) hat sich auf Seite 22/35 ein Fehler in die Formeln eingeschlichen. Die korrigierte Version ist jetzt online.
  
• 12.1.2006: ACHTUNG! Die Übungen am 16. und 17.1. fallen, entgegen der Ankündigung in der Vorlesung, aus!
• 21.12.2005: Aufgabenblatt 6 gibt es im neuen Jahr!
• 7.12.2005: In Aufgabe 2 auf Blatt 5 hat sich ein Fehler eingeschlichen! Der erste Index des zweiten Summand unter Punkt (b) lautet k nicht i !
• 1.12.2005: Die Handouts für die topologische Sortierung sind massiv ergänzt worden!
  
• 25.10.2005: ACHTUNG! Die Dienstags Übung findet wie im Vorlesungsverzeichnis angegeben in Sr H 1510 statt!
  
• 24.10.2005: Auf der zweiten Seite des HEAPSORT Handouts wurde die Formulierung des Satzes korrigiert ("benachbarten" wurde gestrichen)
• 6.10.2005: Im Copy-Shop werden in den nächsten Tagen Exemplare des EA-Skriptes von Prof. M. Kunde verkauft (4,60 Euro das Stück).
  

Inhalt

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
• Mittwoch, 15:00-16:30 Uhr, Hs 4
• Donnerstag (ungerade Wochen), 15:00-16:30 Uhr, Hs 4
  
  
• Übungen
• Montag (ungerade Wochen), 11:00-12:30 Uhr, CC 308
• Dienstag (ungerade Wochen), 11:00-12:30 Uhr, H 1510
  
• Donnerstag (gerade Wochen), 15:00-16:30 Uhr, K 2039
  

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 13 (von 23) Vorlesungen erforderlich.
  
  
• Übungsprogramm: Insgesamt werden 6 Übungsblätter ausgegeben werden, die in Gruppen mit bis zu vier 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-6 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.
   

D.h. implizit, das aus einem der drei Blöcke (1/2, 3/4 oder 5/6) müssen mindestens zwei Aufgaben erfolgreich bearbeitet worden sein.

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

Die Übungsblätter werden jeweils in det Mittwochs-Vorlesung der ungeraden Wochen ausgeteilt. Außerdem werden sie auf dieser Seite als PDF und PS zur Verfügung gestellt.



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

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

• 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

Links

• Das Wörterbuch der Algorithmen und Datenstrukturen des NIST (National Institute of standards and Technology
  
  
  
• Die Fakultät für Informatik der Rautavistischen Universität Eschweilerhof (HoHoHo *<|:-)
  

Materialien und Übungsblätter