 |
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 |
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.,
- zwischen 9.00 Uhr und 11.00 Uhr, Raum 1.56 (Besprechungszimmer, Eingang über das Sekretariat, Raum 1.54), und
- zwischen 13.00 Uhr und 14.00 Uhr, Raum E1.04,
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
- Die Scheine zur Vorlesung können ab sofort abgeholt werden (Sekretariat, 1.54, Oettingenstraße 67).
- Die Ergebnisse der Klausur finden Sie im Abschnitt "Klausur".
- Mit der Klausur endet der Übungsbetrieb. Die Vorlesung findet weiterhin statt. Am 5.7 wird in der Vorlesung die Klausur besprochen.
- Es steht nun fest, wer an der Klausur teilnehmen darf. Sie finden die Zulassungsliste und weitere Hinweise zur Klausur im Abschnitt "Klausur".
- Die Vorlesung am Dienstag, 28.6., dient der Wiederholung und Klausurvorbereitung sowie der Beantwortung Ihrer Fragen zum Stoff von Vorlesung und Übungen.
- Zur Klarstellung: Falls Sie bei abgeschriebenen Hausaufgaben den Vermerk "Aufgabe X abgeschrieben, ohne Wertung" auf Ihrer Hausaufgabe finden, erhalten Sie keine Punkte auf diese Aufgabe. In Aufgabe X erreichte Punkte werden nicht gewertet.
- Bitte beachten Sie den Hinweis zum Übungsblatt 8 im Abschnitt "Übungsblätter".
- Die Übung am Dienstag 16.00-18.00 und Donnerstag 16.00-18.00 werden wegen Teilnehmermangels nicht mehr angeboten. Alle anderen Übungen finden weiterhin wie gewohnt statt.
- Bitte beachten Sie den Hinweis zum "Entfernen aus B-Bäumen" im Abschnitt "Übungsblätter" dieser Seite!
- Bei Fragen zur Bewertung Ihrer Hausaufgaben wenden Sie sich bitte während der Sprechstunden an einen der Mitarbeiter. Bitte kommen Sie für diesen Zweck in die Sprechstunde, da wir dort Zugriff auf die Bewertungsergebnisse haben.
- Lösungen zu Programmieraufgaben in den Hausaufgaben werden jeweils 14 Tage lang ins Netz gestellt.
- Bitte geben Sie Ihre Hausaufgaben mit Deckblatt und getackert ab!
Ü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).
- Merkblatt zum Übungsbetrieb
- Deckblatt für Abgabe (Abgabe nur mit Deckblatt!) Bitte geben Sie auf dem Deckblatt Ihren Übungstag an, da Sie nur dann Ihre korrigierten Hausaufgaben zurückerhalten können.
- Merkblatt zur Klausur.
- Wer korrigierte Übungsblätter nicht in den Übungen abgeholt hat, kann sie bei Arthur Zimek abholen.
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
- am darauffolgenden Freitag (Tag 5 der Bearbeitungszeit) vor der Freitagsübung (nur von 13.00 Uhr bis 13.15 Uhr) beim Übungsgruppenleiter in der Theresienstr. 39 (Raum 133) abgeben oder
- am darauffolgenden Montag (Tag 8 der Bearbeitungszeit) vor der ersten Montagsübung (nur von 12.00 Uhr bis 12.15 Uhr) beim Übungsgruppenleiter im Hauptgebäude (Raum 109) abgeben oder
- am darauffolgenden Montag (Tag 8 der Bearbeitungszeit) durch Einwurf in den Übungsbriefkasten vor 12.15 Uhr in der Oettingenstr. 67 abgeben.
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.
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