Friedhelm Meyer auf der Heide

Termine

Vorlesung (V2)

Mo 11.15 - 12.45    D2          F. Meyer auf der Heide

Übung (Ü2)

Di 09.15 - 10.45  1  E2.316     K. Salzwedel

Die Übung findet nur alle zwei Wochen statt!

Zur Vorlesung gibt es ein Script (siehe unten). Die Übungsblätter sind jeden zweiten Montag ab 11.00 Uhr im Netz vorhanden. Erlaubt und erwünscht sind Gruppenabgaben von bis zu drei Personen. Die Übungszettel sind jeweils zwei Wochen später bis spätestens Montag 11.00 Uhr in die dafür vorgesehenen Kästen im D-Flur auf Ebene 3 abzugeben. Alternativ können die Lösungen auch per E-Mail an kay@hni.upb.de, ebenfalls bis spätestens Montag 11.00 Uhr, geschickt werden. Ein genauer Terminplan der Ausgabe und Rückgabe der Übungszettel befindet sich weiter unten.

Aktuelles

• Die Vorlesung beginnt in der 1. Semesterwoche (10.04.00).
• Die erste Übung findet erst in der zweiten Semesterwoche (18.04.00) statt.
• 25.04.00: Vorlesung zum Übungstermin!
• Da keiner einen Einwand gegen eine Verlegung der Vorlesung am 25.04 hat, findet diese um 14.15 Uhr in H4 statt.
• In der Übung am 30.05.00 wird Ingo Rieping mich vertreten, da ich in zu dem Zeitpunkt in Schloss Dagstuhl weile.
• Entschuldigung für die verspätete Veröffentlichung des 5ten Blattes der Übungsserie!
• Zum n"achsten "Ubungstermin werde ich nicht anwesend sein, da ich einen Vortrag auf der SPAA 2000 zu halten habe. Die "Ubung wird vertreten durch Ulrich Rehberg vertreten werden.
• Weil sehr viele Anfragen bez"uglich der Aufgabe 20 gestellt wurden, habe ich noch einmal eine Musterl"osung angefertigt: Aufgabe 20
• Wichtig! In der zweiten Aufgabe der letzten "Ubungsserie wird ein Matching mit minimalem Gewicht gesucht.
• Die Listen für die Einschreibung zum Pr"ufung hängen in der Fürstenallee aus (an der gelben Wand vor F1.310). Jeder, der eine Prüfung ablegen möchte, möge sich dort bitte eintragen!

Inhalt der Vorlesung

Es werden u.a. folgende Themen behandelt:

• Graphenalgorithmen: All-Pair-Shortest-Path
  • All-Pair-Shortest-Path-Problem (APSP)
  • Floyd-Warshall-Algorithmus
    • Berechnung der konvexen Hülle
• Entwurfsmethoden für Algorithmen
  • Dynamisches Programmieren
  • Optimale binäre Suchbäume
  • Greedy-Algorithmen
    • Bruchteil-Rucksackproblem
    • Rucksackproblem
    • Binpacking
    • Prefixcodes nach Huffman
• Berechnung des Medians, k-Selektion
• Randomisierte Algorithmen
  • Grundbegriffe zu probabilistischen Algorithmen
  • Grundlegende randomiserte Algorithmen
• Ein randomisiertes W"orterbuch: Skip Listen
• Berechnung minimaler Schnitte in Graphen

Weitere Informationen zur Vorlesung

• Vorlesung 'Effiziente Algorithmen I' vom Wintersemester 1999
• Skript zu 'Effiziente Algorithmen I': Kapitel 1-3.
• Skript zu 'Effiziente Algorithmen II':
  • Vorwort
  • Kapitel 4
  • Kapitel 5
  • Kapitel 6
  • Kapitel 7
  • Kapitel 8
  • Kapitel 9
  • Grundlagen der Wahrscheinlichkeitstheorie
• Übungszettel
  • Blatt 1
  • Blatt 2
  • Blatt 3
  • Blatt 4
  • Blatt 5
  • Blatt 6
  • Blatt 7

Übungstermine

Woche	Montag	Dienstag
15	10.04. VL Ausgabe Blatt 1	--
16	17.04. VL Abgabe Blatt 1 Ausgabe Blatt 2	18.04. ÜB Besprechung Blatt 1
18	--	25.04. VL
18	--	02.05. ÜB Besprechung Blatt 2 Abgabe Blatt 2 Ausgabe Blatt 3
19	08.05. VL	--
20	15.05. VL Abgabe Blatt 3 Ausgabe Blatt 4	16.05. ÜB Besprechung Blatt 3
21	22.05. VL	--
22	29.05. VL Abgabe Blatt 4 Ausgabe Blatt 5	30.05. ÜB Besprechung Blatt 4
23	05.05. VL	--
24	--	13.06. ÜB Besprechung Blatt 5 Ausgabe Blatt 6 Abgabe Blatt 5
25	19.06. VL	--
26	26.06. VL Abgabe Blatt 6 Ausgabe Blatt 7	27.01. ÜB Besprechung Blatt 6
27	03.07. VL	--
28	10.07. VL Abgabe Blatt 7	11.07. ÜB BSP+RG Blatt 7

Literatur

• Allgemeine Literatur:
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest: Introduction to algorithms, The MIT electrical engineering and computer science series, 1998
  • T. Ottmann, P. Widmeyer: Algorithmen und Datenstrukturen, BI-Wissenschaftsverlag, 1996
  • A. V. Aho, J. D. Ullmann: Foundations of Computer Science Computer Science Press
  • Knuth: The Art of Computer Programming Addison-Wesley
  • K. Mehlhorn: Data Structures and Algorithms Springer
  • Graham, Knuth, Parashnik: Concrete Mathematics Addison-Wesley
  • C. H. Papadimitriou: «Computational complexity«, Addison-Wesley, 1994
• Algorithmische Geometrie:
  • M. de Berg, M. van Kreveld, M. Overmars und O. Schwarzkopf: «Computational Geometry. Algorithms and Applications«, Springer Verlag, 1997
  • R. Klein: «Algorithmische Geometrie«, Addison-Wesley, 1997
  • F. P. Preparata und M. I. Shamos: «Computational Geometry. An Introduction«, Springer Verlag, 1985
  • J-D. Boissonnat und M. Yvines: «Algorithmic Geometry«, Cambridge University Press, 1998
  • H. Edelsbrunner: «Algorithms in Combinatorial Geometry«, Springer Verlag, 1987
  • J. E. Goodman und J. O'Rourke, Hrsg.: «Handbook of Discrete and Computational Geometry«, CRC Press, 1997
  • K. Mulmuley: «Computational Geometry. An Introduction Through Randomized Algorithms«, Prentice Hall, 1994
  • J. O'Rourke: «Computational Geometry in C«, Cambridge University Press, 1994

Zur Vorlesung gibt es einen Semesterapparat in der Bibliothek, in dem einige der oben angegebenen Bücher zu finden sind.

---

Kay Salzwedel

Last modified: Thu Mar 30 11:33:42 MET 2000