HEINZ NIXDORF INSTITUT
Universität-GH Paderborn
Theoretische Informatik
AG Meyer auf der Heide

Effiziente Algorithmen I

WS 99/00

Friedhelm Meyer auf der Heide

Termine

Vorlesung (V2)
Übung (Ü2)

Zur Vorlesung gibt es eine Mitschrift (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 inri@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 abschließende Punkteliste.
Ab sofort kann man sich am Aushang der Arbeitsgruppe Meyer auf der Heide (vor Raum F1.310) für die Fachprüfung nach DPO 4 eintragen.
Termine sind: 21.02., 13.03. und 03.04.
Anmeldeschluss ist der 11.02.!

Vortrag als Download

Hier könnt ihr den Vortrag vom 29.11. herunterladen:

Die Powerpoint-Datei mit Zip komprimiert (500 kB) - hier fehlen die Filme.
Powerpoint-Datei zusammen mit den beiden Filmen mit Zip komprimiert (11,4 MB).
Die Dateien unkomprimiert: Powerpoint-Datei (700 kB), Film 1 (5,8 MB), Film 2 (7,4 MB).

Inhalt der Vorlesung

Es werden u.a. folgende Themen behandelt:

Algorithmische Geometrie
- Range Searching
Graphenalgorithmen:
- Netzwerk-Fluss-Algorithmen
- Matching Algorithmen
Wörterbücher:
- Universelles Hashing
- Perfektes Hashing

Weitere Informationen zur Vorlesung

Skript zur Vorlesung: Kapitel 1-3.
Übungsblätter: Präsenzübungsblatt, Blatt 1, Blatt 2, Blatt 3, Blatt 4, Blatt 5, Blatt 6 (Eine Lösung von Aufg. 21: C-Quellcode, C-Quellcode in Postscript, Ausgabe, Ausgabe in Postscript), Blatt 7.

Termine

Woche	Montag	Donnerstag
42	18.10. VL Ausgabe Präsenzblatt	21.10. ÜB Besprechung Präsenzblatt Ausgabe Blatt 1
43	25.10. VL	-
44	01.11. keine VL Rückgabe Blatt 1 Ausgabe Blatt 2	04.11. ÜB Besprechung Blatt 1
45	08.11. VL	-
46	15.11. VL RG Blatt 2 AG Blatt 3	18.11. ÜB BSP Blatt 2
47	22.11. VL	-
48	29.11. VL RG Blatt 3 AG Blatt 4	02.12. ÜB BSP Blatt 3
49	06.12. VL	-
50	13.12. VL RG Blatt 4 AG Blatt 5	16.12. ÜB BSP Blatt 4
51	20.12. VL	-
2	10.01. VL RG Blatt 5 AG Blatt 6	13.01. ÜB BSP Blatt 5
3	17.01. VL	-
4	24.01. VL RG Blatt 6 AG Blatt 7	27.01. ÜB BSP Blatt 6
5	31.01. VL	-
6	07.02. VL RG Blatt 7	10.02. ÜB BSP 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.

Ingo Rieping

Last modified: Thu Feb 10 11:33:42 MET 2000