Effiziente Algorithmen

Ludwig-Maximilians-Universität München
Institut für Informatik
Lehr- und Forschungseinheit für Datenbanksysteme

University of Munich
Institute for Computer Science
Database and Information Systems

Effiziente Algorithmen im SS 2000

- Einführung
- Suchverfahren
- Sortierverfahren
- Graphalgorithmen
- algorithmische Methoden und Techniken
- ausgewählte Themen

Hinweise zur Vorlesung: Der Umfang der Vorlesung beträgt 4 + 2 Semesterwochenstunden und wird vom Dozenten Dr. Martin Ester vorgetragen. Sie richtet sich an Studenten mit Hauptfach Informatik, Computerlinguistik und der Mathematik (mit Nebenfach: Informatik). Die benötigten Vorkenntnisse sind Einführung in die Informatik I und II.
Hinweise zum Übungsbetrieb: Zur Vorlesung werden 2-stündige Übungen angeboten, in denen der Stoff vertieft und eingeübt wird. Die Übungsleiter sind Mihael Ankerst und Bernhard Braunmüller, unter Mithilfe von Irina Gotlibovych, Matthias Renz und Michael Passer. Die gestellten Aufgaben sind allein oder in 2-er Gruppen zu bearbeiten. Die Übungsblätter werden auf dieser Internetseite jeweils Mittwochs (beginnend mit dem 1. Blatt am 03.05.) als PDF-Datei abgelegt und müssen jeweils spätenstens bis zum darauffolgenden Mittwoch, 9 Uhr (beim 1. Blatt am 10.05.) im Übungskasten Prof. Dr. Kriegel (Oettingenstr. 67, Raum 0.31, Garderobe beim Haupteingang) abgegeben werden. Die Lösungen sind immer mit diesem ausgefüllten Deckblatt abzugeben. In Kürze wird die Gruppeneinteilung bekanntgegeben.
Hinweise zur Klausur: Am Ende des Semesters wird eine Klausur durchgeführt, bei deren Bestehen ein Schein ausgegeben wird. Als Voraussetzung zur Teilnahme an der Klausur sind mindestens die Hälfte aller möglichen Übungspunkte zu erreichen. Der genaue Termin wird noch bekannt gegeben.

Eine empfehlenswerte Demonstrationssoftware zum Thema Sortieren findet ihr unter diesem Link.
Eine empfehlenswerte Demonstrationssoftware zum Thema Single Source Shortest Path-Problem findet ihr unter diesem Link.
Die Klausur findet am Mittwoch, dem 19. 07. 2000, 15.00 - 17.00 Uhr, im Raum 1.14 (Oettingenstr. 67) statt. Es sind mit Ausnahme eines Taschenrechners keine Hilfmittel zugelassen! Nehmen Sie bitte Ihren Studentenausweis (bzw. eine Immatrikulationsbescheinigung) und einen Lichtbildausweis mit. Zur Teilnahme an der Klausur sind folgende Studentinnen und Studenten berechtigt. Wer seinen Namen in dieser Liste nicht findet, aber die notwendige Punktezahl (65.5) erreicht zu haben glaubt, meldet sich bitte bei einem der beiden Übungsleitern bis spätenstens Montag, den 17. Juli 2000.
Die Klausurnachbesprechung findet am Mittwoch, den 26.07. in der Vorlesung statt.
Es finden nach der Klausur keine Uebungen mehr statt.
Klausurergebnis

Veranstaltung	Zeit (Übungskennzeichen)	Ort	Beginn
Vorlesung	Mo, 13.00 - 15.00 Uhr Mi, 15.00 - 17.00 Uhr	Raum 1.14 (Oettingenstr. 67)	03.05.2000
Übungen in Gruppen	Mi, 9.00 - 11.00 Uhr (A)	Raum 15 (Oettingenstr. 67)	10.05.2000
	Mi, 11.00 - 13.00 Uhr (B)	Raum 0.37 (Oettingenstr. 67)	10.05.2000
	Do, 13.00 - 15.00 Uhr (C)	Raum 17 (Oettingenstr. 67)	11.05.2000
	Do, 15.00 - 17.00 Uhr (D)	Raum 17 (Oettingenstr. 67)	11.05.2000

Termin	Vorlesung	Übung
Woche 18 (1 Vorlesung)	1. Einführung Algorithmen und ihre Analyse	Übungsblatt 1 Lösungsidee (1.3-b)
Woche 19 (2 Vorlesungen)	1. Einführung Datenstrukturen und abstrakte Datentypen 2. Suchverfahren Binäre Suchbäume	Übungsblatt 2 Lösungsidee (2.1)
Woche 20 (2 Vorlesungen)	2. Suchverfahren Binäre Suchbäume (Forts.), B-Bäume	Übungsblatt 3
Woche 21 (2 Vorlesungen)	2. Suchverfahren optimale Suchbäume, Hashverfahren	Übungsblatt 4
Woche 22 (2 Vorlesungen)	2. Suchverfahren Hashverfahren (Forts.)	Übungsblatt 5
Woche 23 (2 Vorlesungen)	3. Sortierverfahren einfache Sortieralgorithmen, Divide-and-Conquer Methoden	Übungsblatt 6
Woche 24 (1 Vorlesung)	3. Sortierverfahren Sortieren mit Bäumen	Übungsblatt 7
Woche 25 (2 Vorlesungen)	3. Sortierverfahren externe Sortierverfahren 4. Graphen und Graphalgorithmen Speicherdarstellung, Graphdurchläufe	Übungsblatt 8
Woche 26 (2 Vorlesungen)	4. Graphen und Graphalgorithmen Bestimmung kürzester Wege, transitive Hülle, minimaler Spannbaum	Letztes Übungsblatt! Übungsblatt 9
Woche 27 (2 Vorlesungen)	5. Algorithmische Methoden und Techniken erschöpfende Suche, greedy algorithms, Backtracking und "Branch-and-bound" Verfahren
Woche 28 (2 Vorlesungen)	5. Algorithmische Methoden und Techniken "Divide-and-conquer" Verfahren, Dynamische Programmierung	Klausurvorbereitung
Woche 29 (2 Vorlesungen)	6. Ausgewählte Themen Suchen in Texten
Woche 30 (1 Vorlesung)	6. Ausgewählte Themen Suchen in Texten * Klausur *

Bei Problemen oder Vorschlägen schicken Sie bitte eine eMail an:
wwwmaster@dbs.informatik.uni-muenchen.de