Lehr- und Forschungseinheit für Datenbanksysteme 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 2005

Vorhergehende Jahre:
[ SS 04 | SS 01 | SS 00 ]


Inhalt

In der Vorlesung wird der Entwurf effizienter Algorithmen für die Bereiche Suchen, Sortieren, Graphmethoden sowie geometrische Verfahren behandelt. Besonderer Schwerpunkt liegt hierbei auf allgemeinen algorithmischen Techniken, wie etwa divide-and-conquer, lokal-optimierender Berechnung ("greedy methods"), backtracking, branch-and-bound sowie dynamischer Programmierung.

Organisation


Zeit und Ort

Veranstaltung Zeit Ort Beginn
Vorlesung Di, 10.00 s.t. - 11.30 Uhr Raum 147 (Hauptgebäude) 12.04.2005
Vorlesung Do, 10.00 s.t. - 11.30 Uhr Raum 209 (Hauptgebäude) 14.04.2005
Übung Mo, 12.00 - 14.00 Uhr Raum 109 (Hauptgebäude) 18.04.2005
Übung Mo, 16.00 - 18.00 Uhr Raum 1.05 (Oettingenstr. 67) 18.04.2005
Übung Di, 14.00 - 16.00 Uhr Raum 0.43 (Oettingenstr. 67) 19.04.2005
Übung Fr, 13.00 - 15.00 Uhr Raum 133 (Theresienstr. 39) 22.04.2005

Klausur

Sie finden das Ergebnis Ihrer Klausur unter Ihrer Matrikelnummer in Klausur-Ergebnisse, wenn Sie der Veröffentlichung zugestimmt haben.

Um Ihr Ergebnis einzuordnen, können Sie auch die Statistik einsehen.

In Ihre korrigierte Klausur können Sie am Montag, 11.7.,

Oettingenstraße 67, Einsicht nehmen.

Bitte beachten Sie: Die Klausur-Einsicht endet um 11.00 Uhr bzw. um 14.00 Uhr. Erfahrungsgemäß kommen viele Studenten lieber gegen Ende der gegebenen Zeit. Wir können aber nur drei Personen gleichzeitig einlassen. Daher empfehlen wir, auch die erste Hälfte der Zeit zu nutzen.


Aktuelles


Übungsbetrieb

Zur Vorlesung werden 2-stündige Übungen angeboten, in denen der Stoff vertieft und eingeübt wird. Zum Scheinerwerb ist eine Anmeldung zum Übungsbetrieb notwendig (bis 20.04.2005, Frist nun abgelaufen).

Abgabe von Hausaufgaben

Die Abgabe von Hausaufgaben wird folgendermaßen geregelt: Sie können Hausaufgaben entweder in der Oettingenstrasse, dem Hauptgebäude oder der Theresienstrasse abgeben.
Wichtig: Je nachdem wo Sie abgeben, gelten unterschiedliche Abgabetermine und -regeln! Die Abgabetermine sind auf jedem Übungsblatt genau angegeben.


Im Normalfall gilt folgende Regelung: Das neue Übungsblatt wird montags (Tag 1 der Bearbeitungszeit) ins Netz gestellt.
Sie können dann Ihre Hausaufgaben Mehrfachabgaben und abgeschriebene Lösungen sind nicht erlaubt und werden nicht bewertet.

Übungsblätter

Bitte beachten Sie:

Sie können nur noch mit Übungsblatt 8 Punkte sammeln. Auf Übungsblatt 9 gibt es keine Punkte mehr, aber die Aufgaben sind noch klausurrelevant und werden in der letzten Übung vor der Klausur besprochen. Außerdem können in der letzten Übung Ihre Fragen besprochen werden.

Ausgabedatum Übungsblatt
18.04.2005 Übungsblatt 1
25.04.2005 Übungsblatt 2
02.05.2005 Übungsblatt 3
09.05.2005 Übungsblatt 4
23.05.2005 Übungsblatt 5
30.05.2005 Übungsblatt 6
06.06.2005 Übungsblatt 7
13.06.2005 Übungsblatt 8
20.06.2005 Übungsblatt 9
Zu Übungsblatt 8:
Übungsblatt 8 steht nun in einer neuen Version zur Verfügung. Geändert hat sich nur ein Wort in Aufgabe 8.1: Ursprünglich hieß es da: "Bestimmen". Gemeint war (wie es jetzt dasteht): "Sortieren".
Zu Übungsblatt 4:
Zum Entfernen in B-Bäumen: Ausgleichen und Verschmelzen sind sowohl mit dem linken als auch dem rechten Bruder erlaubt, falls die im Skript angegeben Bedingungen gelten.
Bitte gehen Sie also beim Entfernen aus B-Bäumen bei Underflows folgendermassen vor:
1.a) Ausgleichen mit dem rechten Bruder möglich? Falls ja: Durchführen und Stop; falls nein: gehe zu Punkt 1.b)
1.b) Ausgleichen mit dem linken Bruder möglich? Falls ja: Durchführen und Stop; falls nein: gehe zu Punkt 2.a)
2.a) Verschmelzen mit dem rechten Bruder möglich? Falls ja: Durchführen und ggf. Underflow im Vaterknoten untersuchen; falls nein: gehe zu Punkt 2.b)
2.b) Verschmelzen mit dem linken Bruder möglich? Falls ja: Durchführen und ggf. Underflow im Vaterknoten untersuchen.

Bei Problemen oder Vorschlägen wenden Sie sich bitte an: wwwmaster@dbs.informatik.uni-muenchen.de
Last Modified: , validate