max planck institut
informatik
informatik
| Datum | Dozent | Thema | Referenzen | Übungen |
|---|---|---|---|---|
| 20. Oktober | BD |
Anmeldung zur Vorlesung und zu den Übungsgruppen; Einführung und Überblick; Binärsuche |
Skript, Kap. 1.1 | Übung 1 MuLö 1 |
| 27. Oktober | BD | O-Notation, Laufzeitanalyse | Skript, Kap. 1.2 – 1.4 | Übung 2 MuLö 2 |
| 03. November | RS | Sortieralgorithmen: Selectionsort und Mergesort | Skript, Kap. 2 | Übung 3 MuLö 3 |
| 10. November | RS | Sortieralgorithmen: Heapsort und Quicksort | Skript, Kap. 3 | Übung 4 MuLö 4 |
| 17. November | BD | Selektion und Mediansuche in Linearzeit | Skript, Kap. 4 | Übung 5 MuLö 5 Vorbereitung Test 2 |
| 24. November | RS | Master-Theorem; Strassen-Matrix-Multiplikation | Skript, Kap. 10; Strassen-Multiplikation auf Wikipedia: de, en | Übung 6 MuLö 6 |
| 01. Dezember | RS | Stacks und Queues; amortisierte Analyse | Skript, Kap. 5.1 – 5.2 und 9.1 | Übung 7 MuLö 7 Vorbereitung Test 3 |
| 08. Dezember | BD | Binäre Suchbäume | Skript, Kap. 6 | Übung 8 MuLö 8 |
| 15. Dezember | RS | AVL-Bäume | Skript, Kap. 7 | Übung 9 MuLö 9 Vorbereitung Test 4 |
| 22. Dezember | BD | Binomial-Heaps | Skript, Kap. 8 | Übung 10 MuLö 10 |
| 29. Dezember | keine Vorlesung (Weihnachtsferien) | |||
| 05. Januar | keine Vorlesung (Weihnachtsferien) | |||
| 12. Januar | RS | Graph-Algorithmen: Grundbegriffe, Breiten- und Tiefensuche | Skript, Kap. 12 | Übung 11 MuLö 11 |
| 19. Januar | BD | Minimale Spannbäume; Greedy-Algorithmen | Skript, Kap. 11.2 und 13 | Übung 12 MuLö 12 |
| 26. Januar | RS | Kürzeste Pfade; Dynamische Programmierung | Skript, Kap. 11.1 und 14; Floyd-Warshall-Algorithmus auf Wikipedia: de, en | Übung 13 MuLö 13 |
| 02. Februar | RS | Besprechung von Übungsblatt 13 | ||
| 03. Februar | 14:30 bis 16:30 Uhr; Gebäude E2 2, Hörsaal 001 (Günter-Hotz-Hörsaal, vormals AudiMO), Gebäude E1 3, Hörsaal 002 und Gebäude E2 5, Hörsaal I: Klausur | |||
| 09. Februar | RS | Polynomielle Approximations-Schemen für NP-schwere geometrische Probleme | Slides [PPTX, PDF]; Journalartikel (Preprint) | |
| 20. April | 16:30 bis 18:30 Uhr; Gebäude E2 2, Hörsaal 001 (Günter-Hotz-Hörsaal, vormals AudiMO) und Gebäude E2 5, Hörsaal I: Nachklausur | |||
Wir diskutieren grundlegende Methoden zum Aufbau von Algorithmen, ihre Analyse sowie gebräuchliche Datenstrukturen anhand klassischer Beispiele:
Die Vorlesung richtet sich nach dem Skript Introduction to Algorithms and Data Structures von Markus Bläser (Errata dazu, Stand 02.02.12, 15:02 Uhr).
Grundzüge von Algorithmen und Datenstrukturen ist eine verpflichtende Grundvorlesung für Studenten in den Bachelor- und Lehramts-Studiengängen Informatik.
Sie sollte nach den Empfehlungen von Fachschaft und Universität im dritten Fachsemester gehört werden.
Für eine erfolgreiche Teilnahme (nämlich das Lösen der wöchentlichen Übungen sowie Bestehen einer Klausur) werden 6 benotete ECTS-Leistungspunkte gutgeschrieben.
Vorlesung und Tutorien werden auf Deutsch gehalten.
Der vorgesehene Arbeitsaufwand beträgt 180 Stunden, verteilt auf 60 Stunden Präsenzzeit (zwei Stunden Vorlesung + zwei Stunden Tutorium pro Woche) und 120 Stunden Nachbereitung.
Programmierung 1 und 2 sowie Mathematik für Informatiker 1 und 2 (bzw. Analysis 1 und 2) sind hilfreich, aber keine unbedingte Voraussetzung.
Zumindest paralleles Hören von Programmierung 1 und Mathematik für Informatiker 1 ist jedoch empfehlenswert.
In jeder Vorlesung wird ein Übungsblatt ausgeteilt, das innerhalb einer Woche zu bearbeiten ist.
Die Übungsblätter werden außerdem auch auf dieser Website veröffentlicht.
Die Abgabefrist der Übungsblätter ist jeweils am auf die Ausgabe folgenden Mittwoch Abend um 17:00 Uhr, in dem entsprechend gekennzeichneten Briefkasten (ganz unten rechts) im Erdgeschoss des Gebäudes E1 3 (neben Hörsaal 001).
Die Abgaben sind zu heften (keine Büroklammern oder nur falten!) und deutlich auf der ersten Seite mit Ihrem Namen und der Nummer Ihrer Übungsgruppe zu versehen.
Die Übungsblätter dürfen alleine oder in Zweierteams innerhalb der gleichen Übungsgruppe bearbeitet werden.
Auf jedem Übungsblatt können Sie 16 Punkte erreichen. Außerdem schreiben Sie in jeder zweiten Übung bis zum 20. Dezember, beginnend ab dem 7. oder 8. November, einen Mini-Test mit jeweils 8 erreichbaren Punkten. Um zu den Klausuren zugelassen zu werden, müssen Sie nach verschiedenen Abschnitten der Vorlesung eine Quote von jeweils 50 Prozent der erreichbaren Punkte aus Übungen und Tests erzielen, abzüglich eines konstanten Bonus von 8 (Übungen) und 4 (Tests) Punkten.
| Übungen | Mini-Tests | |||||
|---|---|---|---|---|---|---|
| Zeitpunkt | max. erreichbar | benötigt | Zeitpunkt | max. erreichbar | benötigt | |
| nach 3 Übungen | 48 | 16 (= 0.5⋅48 − 8) | nach 2 Mini-Tests | 16 | 4 (= 0.5⋅16 − 4) | |
| nach 6 Übungen | 96 | 40 (= 0.5⋅96 − 8) | nach 4 Mini-Tests | 32 | 12 (= 0.5⋅32 − 4) | |
| nach 9 Übungen | 144 | 64 (= 0.5⋅144 − 8) | ||||
| nach 12 Übungen | 192 | 88 (= 0.5⋅192 − 8) | ||||
Über das gesamte Semester finden Tutorien begleitend zur Vorlesung statt, in denen die Übungsaufgaben und der aktuelle Vorlesungsstoff besprochen und vertieft werden. Die Teilnahme an den Tutorien ist ab dem neuen Jahr freiwillig.
Grundzüge von Algorithmen und Datenstrukturen ist eine benotete Grundvorlesung. Die Note ergibt sich ausschließlich aus dem oder den Klausurergebnis(sen); Übungen und Mini-Tests sind lediglich Zulassungsvoraussetzungen, aber nicht relevant für die Benotung.
Wenn Sie die Zulassungskriterien erfüllen, dürfen Sie sowohl an der Hauptklausur am Freitag, dem 03.02.2012, von 14:30 bis 16:30 Uhr als auch an der Nachklausur am Freitag, dem 20.04.2012, von 16:30 bis 18:30 Uhr teilnehmen. (Bitte planen Sie für beide Klausurtermine etwas Spielraum nach vorne und hinten ein, damit wir die notwendigen Ansagen und das Einsammeln der Klausuren in Ruhe erledigen können.) Die Note ergibt sich aus dem Minimum (also dem Besten) der Klausurergebnisse – wenn das Ergebnis der Hauptklausur nicht Ihren Vorstellungen entsprochen hat, können Sie also gefahrlos an der Nachklausur teilnehmen, ohne dass sich Ihre Note verschlechtern kann.
Bitte beachten Sie, dass der Schein, den Sie nach dem Bestehen der Klausur bekommen, nur dann als erfolgreiche Prüfungsleistung anerkannt wird, wenn Sie sich rechtzeitig über das LSF-Portal der Universität (für Studenten der naturwissenschaftlich-technischen Fakultät) oder die entsprechende Registrierungsportale für Studenten anderer Fakultäten zur Vorlesung angemeldet haben.
Denken Sie daran, dass Sie zur Anmeldung im LSF eine iTAN benötigen und ggf. noch eine entsprechende Liste anfordern oder ausdrucken müssen.
Sind Sie nach Ende der Anmeldephase für die Prüfung registriert und erreichen die Zulassungskriterien nicht, gilt die Klausur als nicht bestanden und ein Fehlversuch wird gewertet.
Die rechtzeitige Anmeldung liegt allein in Ihrer Verantwortung.
Die Anmeldung zu den Tutorien reicht nicht aus!
Wir können die Anmeldung in den fakultätsinternen Systemen nicht zentral vornehmen!