Vorlesung der Arbeitsgruppe Theoretische Informatik im Wintersemester 2000/2001

`` Entwurf und Analyse von Algorithmen ''

Günter Rote, Astrid Kaffanke Christian Knauer

Überblick

Der Entwurf von Algorithmen bildet einen Kernbereich der Informatik. Diese Vorlesung ist eine einführende Veranstaltung zur Algorithmik und Grundlage für die meisten anderen Veranstaltungen in der Theoretischen Informatik. Inhalt ist der Entwurf und die Analyse von Algorithmen und Datenstrukturen für viele grundlegende Probleme wie Suchen, Sortieren, Graphenprobleme, Arithmetik, geometrische Probleme, usw.

Inhalt der Vorlesung (zeitlich).

Scheinerwerb

Die Scheine werden benotet. Die Note ergibt sich aus der in den Übungen erzielten Punktezahlen (40%) sowie aus den Punktezahlen aus zwei Klausuren (60%) -- eine nach der Hälfte und eine am Ende des Semesters. Die beiden Klausuren können am Anfang des nächsten Semesters wiederholt werden. Um einen Schein zu erwerben, müssen folgende Anforderungen erfüllt werden:

• Aktive und regelmäßige Teilnahme an den Übungen.
• Auf mindestens 80% der Übungszettel sind jeweils mindestens 25% der Punkte zu erreichen.
• Insgesamt sind mindestens 60% aller Punkte zu erreichen.
• Insgesamt sind mindestens 50% der Punkte von praktischen Übungsaufgaben zu erreichen.
• In jeder Teilklausur sind mindestens 40% der Punkte zu erreichen.
• Im Tutorium ist die Lösung von mindestens zwei Aufgaben an der Tafel vorzustellen.

Übungsbetrieb

Für die Bearbeitung der Übungsaufgaben sind grundlegende Kenntnisse der Programmiersprache Java erforderlich, wie sie z.B. im Vorlesungszyklus "Algorithmen und Programmierung I-III" oder in dem Kurs "Programmieren mit Java" vermittelt werden.

Die Übungen finden am Mittwoch und Donnerstag von 8³⁰ - 10⁰⁰ (Astrid Kaffanke) und am Freitag von 16¹⁵ - 17⁴⁵ (Christian Knauer) im Raum SR 039 im Informatikgebäude in der Takustraße 9 statt. Der Übungsbetrieb beginnt am 25.10.

Die Übungsaufgaben können in Gruppen zu maximal zwei Personen bearbeitet werden. Die Übungszettel werden jeweils am Donnerstag in der Vorlesung ausgegeben und sind bis zum darauffolgenden Donnerstag zu bearbeiten.

Implementierungen im Rahmen der praktischen Übungsaufgaben müssen in der Programmiersprache Java erstellt werden. Die Abgabe dieser Aufgaben erfolgt per email an den jeweiligen Tutor. Dabei bitte nur lauffähigen und compilierbaren Quellcode schicken. Besteht die Implementierung aus mehreren Dateien, sind diese -- unter Beibehaltung der Verzeichnisstruktur -- in ein Archiv (tar,tgz,zip) zu verpacken.

• 1. Aufgabenblatt vom 19. Oktober.
• 2. Aufgabenblatt vom 25. Oktober.
• 3. Aufgabenblatt vom 2. November.
• 4. Aufgabenblatt vom 6. November.
• 5. Aufgabenblatt vom 13. November.
• 6. Aufgabenblatt vom 20. November.
• 7. Aufgabenblatt vom 27. November.
• 8. Aufgabenblatt vom 4. Dezember.
• 9. Aufgabenblatt vom 11. Dezember.
• 10. Aufgabenblatt vom 18. Dezember.
• 11. Aufgabenblatt vom 8. Januar.
• 12. Aufgabenblatt vom 15. Januar.
• 13. Aufgabenblatt vom 22. Januar.
• 14. Aufgabenblatt vom 29. Januar.

Literatur

Die folgenden Bücher stehen im Handapparat zur Vorlesung:

• Alfred V. Aho, John E. Hopcroft und Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
• Thomas H. Cormen, Charles E. Leiserson und Ronald L. Rivest. Introduction to Algorithms. MIT Press/McGraw-Hill, 1990.
• Donald E. Knuth The Art of Computer Programming, Band 1-3. Addison-Wesley, 1998.
• Thomas Ottmann und Peter Widmayer. Algorithmen und Datenstrukturen. Spektrum, 1996.

Materialien zur Vorlesung

• Zu dem Buch von Cormen, Leiserson und Rivest gibt es eine Liste der bekannten Fehler.