42 
Datenstrukturen und Algorithmen (SS 2004)
Inhalt
- Rechnermodelle und Komplexitätsmaße
- Sortieralgorithmen
- Laufzeitanalyse rekursiver Algorithmen
- Elementare Datenstrukturen:
- Dynamische Suchbäume
- Hashingverfahren
- Skip-Listen
- Elementare Graphalgorithmen
- Entwurfsmethoden für Algorithmen
Klausur
1. Klausur: (20.08.2004)
2. Klausur: (08.10.2004)
3. Klausur: (09.03.2005)
Es gelten die folgenden Spielregeln:
Bringen Sie einen Studienausweis und einen Lichtbildausweis zu der Klausur mit, damit wir ihre Identität überprüfen können.
Das einzige zugelassenes Hilfsmittel, welches Sie neben Stiften zum Schreiben mitbringen dürfen, ist ein beidseitig handschriftlich beschriebenes DIN A4 Blatt.
Ergebnisse aus der Vorlesung dürfen zitiert werden.
Ergebnisse aus den Übungen oder anderen Quellen dürfen nicht zitiert werden und müssen ausgeführt werden; d.h., es genügt nicht zu sagen, "Das geht nach Aufgabe XY der Übungen" oder "Wir haben aber in der Präsenzübung gezeigt ...".
Studierende, welche sich nicht über ihr Prüfungssekretariat anmelden müssen (z.B. Bachelor/Diplom Informatik nach DPO4), müssen sich über das Web-Anmeldeskript anmelden.
Sollte eine Online-Anmeldung aus irgendeinem Grund nicht möglich sein, so kann sich auch persönlich bei Alexander May im Büro F2.126 an- bzw. abgemeldet werden.
Newsgroup
Die Informatik-Rechnerbetreuung (IRB) stellt zu der Vorlesung die Newsgroup pbinfo.info_dua für die Studierenden zur Diskussion zur Verfügung. Die Organisatoren haben keinen Einfluss auf Inhalt und Gestaltung dieser Newsgroup. Bei technischen Problemen können wir Ihnen nicht helfen, wenden sie sich bitte an postmaster@upb.de.
Wichtig: Von unserer Seite aus werden niemals offizielle Ankündigungen in dieser Newsgroup veröffentlicht. Alle offiziellen Informationen befinden sich auf dieser Webseite.
Termine
-
Vorlesung:
Tag Zeit Raum Dozent Di 09:00-11:00 AM Blömer Do 09:00-11:00 AM Blömer -
Zentralübung:
Gruppe Tag Zeit Raum Tutor ZÜ Di 11:00-12:00 C1 Blömer Achtung: Es wird eine zusätzliche Zentralübung und Fragestunde mit Prof. Blömer am Mittwoch, den 11.08.2004 um 13 Uhr c.t. im C1 geben. Thema dieser ZÜ soll vor allem die Probeklausur (siehe Aufgaben) sein.
-
Übungsgruppen:
Gruppe Tag Zeit Raum Tutor Ü1 Mo 11:00-13:00 D 1.312 Dominic Dumrauf Ü2 Mo 11:00-13:00 P1 4.18 Michael Köster Ü3 Mo 11:00-13:00 P1 6.11 Christian Viergutz Ü4 Mo 14:00-16:00 D 1.312 Marcel R. Ackermann Ü5 Mo 14:00-16:00 D 1.303 Karsten Tiemann Ü6 Mo 16:00-18:00 D 1.303 Karsten Tiemann Ü7 Mo 16:00-18:00 P1 4.18 Michael Köster Ü8 Mi 09:00-11:00 D 1.312 Dominik Niehus Ü9 Mi 09:00-11:00 D 1.303 Matthias Ernst Ü10 Mi 11:00-13:00 P1 6.11 Dominik Niehus Ü11 Mi 11:00-13:00 D 1.303 Matthias Ernst Ü12 Mi 16:00-18:00 P1 6.11 Christian Soltenborn Ü13 Do 11:00-13:00 D 1.312 Annie Yi Ü14 Do 11:00-13:00 E 2.310 Stefan Schamberger Ü15 Do 15:00-17:00 P1 4.18 Sascha Effert Ü16 Do 15:00-17:00 D 1.312 Stefan Schamberger Ü17 Fr 09:00-11:00 D 1.312 Christoph Spanke Ü18 Fr 09:00-11:00 N 3.206 Christoph Ackermann Ü19 Fr 14:00-16:00 P1 4.18 Sascha Effert Ü20 Fr 14:00-16:00 P1 5.08.2 Christoph Spanke Ü21 Di 16:00-18:00 P6 2.03 Dominic Dumrauf Ü22 Di 16:00-18:00 B1 Alexander May
Skript
Die Vorlesung orientiert sich in Notation und Aufbau an dem Grundlagenbuch "Introduction to Algorithms" von Cormen, Leiserson, Rivest und Stein (2. Auflage). Es wird kein gesondertes Skript zu dieser Vorlesung geben.
Zur Nacharbeit und Vertiefung wird die unten angegebene Literatur empfohlen.
Folien
Hier erscheint im Laufe des Semesters die Folien-Präsentation der einzelnen Vorlesungen. Bitte beachten Sie, dass diese nur zur Unterstützung der Vorlesung gedacht sind und keinen selbsterklärenden Charakter besitzen. Ein alleiniges Lernen an Hand dieser Folien kann den Besuch der Vorlesung und die Lektüre der angegebenen Literatur nicht ersetzen und wird im Allgemeinen zum Bestehen der Prüfung nicht ausreichen. Die Literaturangaben beziehen sich immer auf Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein (2. Auflage).
Aufgaben
Hier erscheinen im Laufe des Semesters die Übungen und die Musterlösungen.
Wir fordern Sie ausdrücklich auf, in kleinen Gruppen (2-4 Personen) gemeinsam die Vorlesung nachzuarbeiten und die Übungen zu bearbeiten. Für den Lernerfolg (und den Spaß am Studieren) ist das sehr förderlich. Sie dürfen Ihre Übungen auch in solchen Gruppen abgeben. Übungszettel, bei welchen jedoch mehr als 4 Personen angegeben sind, werden für die Bonuspunkte mit 0 Punkten gewertet.
Bonuspunkte
Durch aktive Mitarbeit in den Übungen haben Sie die Möglichkeit, ihre in der abschliessenden Prüfung erreichte Note wie folgt zu verbessern:
- Erreichen Sie mindestens 50% der Punkte der Übungsaufgaben, so verbessert sich die Note der Prüfung um 1/3 (ein Notenschritt).
- Erreichen Sie mindestens 75% der Punkte der Übungsaufgaben, so verbessert sich die Note der Prüfung um 2/3 (zwei Notenschritte).
- Eine Verbesserung über die Note 1,0 (sehr gut) hinaus ist nicht möglich.
- WICHTIG: Eine Verbesserung der Prüfungsnote 5,0 (nicht bestanden) ist nicht möglich.
Literatur
- Cormen, Leiserson, Rivest: "Introduction to Algorithms",
MIT Press / McGraw-Hill, 1st ed., ISBN: 0-262-53091-0 - Cormen, Leiserson, Rivest, Stein: "Introduction to Algorithms",
MIT Press / McGraw-Hill, 2nd ed., ISBN: 0-262-53196-8 - Ottman, Widmayer: "Algorithmen und Datenstrukturen",
Spektrum Adakemischer Verlag, ISBN: 3-827-41029-0 - Sedgewick: "Algorithms in Java (parts 1-4)",
Addison-Wesley, ISBN: 0-201-36120-5 - Baase, Van Gelder: "Computer Algorithms: Introduction to Design and Analysis",
Addison-Wesley, ISBN: 0-201-61244-5