Algorithmen und Datenstrukturen II

Veranstaltungsart: Vorlesung
Semester: Sommersemester
Stunden: 3+1
Dozent:
Übungsleiter:
Hörerkreis: Studenten der Informatik, Wirtschaftsinformatik, Informationssystemtechnik und Medienwissenschaften
Ort und Zeit: Vorlesung:
Dienstag 8:45 - 11:15 Uhr in SN 19.1

Daneben werden wieder kleine Übungsgruppen angeboten:
Sechs parallele Übungsgruppen, 14-tägig, jeweils 1,5 Stunden. Die ersten Übungen finden in der zweiten Vorlesungswoche statt (ab 15.04.). Das erste Übungsblatt gibt es am 14.04 (Abgabe am 22.04.)

Beginn: Dienstag, 8. April 2003
Inhalt: "Algorithmen und Datenstrukturen" (AuD) wird zu den wichtigsten Grundlagen des Faches Informatik gezählt. In dieser zweisemstrigen Veranstaltung werden die Teilnehmer mit Begriffen wie Algorithmus, Programmierung, abstrakter Datentyp, Objektorientierung, Komplexität etc. vertraut gemacht. Die Vorlesung wird wie folgt aufgebaut sein:
  • AuD I (vergangenes Semester)
  1. Grundbegriffe
  2. Algorithmus-Begriff
  3. Imperative Programmierung
  4. Abstrakte Datentypen und Objektorientierung
  5. Algorithmenkonstruktion I
  • AuD II (dieses Semester)
  1. Bäume
  2. Mengen und Verzeichnisse
  3. Graphen
  4. Sortieralgorithmen
  5. Algorithmenkostruktion II
  6. Andere Programmierstile
Empfohlene Voraussetzungen: AuD I
Scheinerwerb:

Sie haben die Möglichkeit, einen Schein für AuD-I, AuD-II oder AuD-I+II zu erwerben. Hierzu müssen Sie in den jeweiligen Übungsblättern mindestens 50% der Gesamtpunktzahl erreichen und eine kurze mündliche Prüfung (Kolloquium) erfolgreich absolvieren. Bitte melden Sie sich direkt im IBR-Sekretariat für einen Kolloquiums-Termin an.

Weiterhin konnten Sie an einer Vordiplomsklausur "Informatik 1" teilnehmen, die am 03. September 2003 (13:30 Uhr bis 18:00 Uhr) stattgefunden hat.

Diese Klausur ist wie folgt ausgefallen:

  • Teilnehmer: 287
  • zur Klausur erschienen: 200
  • Note 5,0: 179 (<50 Punkte)
  • Note 4,0: 24 (<55 Punkte)
  • Note 3,7: 17 (<60 Punkte)
  • Note 3,3: 21 (<65 Punkte)
  • Note 3,0: 13 (<70 Punkte)
  • Note 2,7: 10 (<75 Punkte)
  • Note 2,3: 6 (<80 Punkte)
  • Note 2,0: 12 (<85 Punkte)
  • Note 2,7: 4 (<90 Punkte)
  • Note 1,3: 1 (<95 Punkte)
  • Note 1,0: 0 (<=100 Punkte)

Hier können Sie Ihr persönliches Ergebnis abfragen (Geben Sie als Benutzernamen Ihre Matrikel-Nr. und als Kennwort Ihren 6-stelligen Zahlencode an).

Klausureinsicht: Sie haben an folgenden Terminen die Möglichkeit, Ihre bewertete Klausur einzusehen:

  • Mittwoch, der 22.10.2003, 9:00 Uhr bis 11:00 Uhr, Raum IZ105
  • Montag, der 27.10.2003, 9:00 Uhr bis 11:00 Uhr, Raum IZ105

Materialien zur Klausurvorbereitung: In erster Linie sollten Sie sich mit den Vorlesungsfolien, Folienvideos, Übungsunterlagen und der genannten Literatur auf die Klausur vorbereiten.
Zur Kontrolle Ihres Wissensstands können Sie sich aber auch zusätzlich die Klausuren und Musterlösungen der vergangenen Jahre anschauen. Bitte berücksichtigen Sie aber, dass in unserer AuD-Veranstaltung die Schwerpunkte z.T. etwas anders gewählt wurden als in den vergangenen Jahren. Erschrecken Sie also nicht, wenn Sie manche der in der Vegangenheit gestellten Klausuraufgaben nicht lösen können.

Evaluation: Eine anonyme, aber nicht öffentliche Online-Umfrage der Vorlesung mittels Popollog unter den Studenten ergab folgendes Evaluationsergebnis.
Literatur:
  • G. Goos: Vorlesungen über Informatik, Band 1-3, versch. Auflagen, Springer-Verlag.
  • T. Cormen et al.: Introduction to Algorithms, The MIT Press, 2001.
  • G. Saake, K. Sattler: Algorithmen & Datenstrukturen - Eine Einführung in Java, dpunkt.verlag, 2002.
  • R. Sedgewick: Algorithmen, 2. Auflage, Addison-Wesley, 2002.
  • T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, 4. Auflage, Spektrum Akademischer verlag GmbH, 2002.
  • W. Küchlin, A. Weber: Einführung in die Informatik, Springer Verlag, 2000.
  • M. Waite, R. Lafore: Data Structures & Algorithms in Java, Waite Group Press, 1998.
  • S. Baase, A. van Gelder: Computer Algorithms - Introduction to Design and Analysis, 3. Auflage, Addison Wesley, 2000.
Links: Java-Tutorial
Applet zur Visualisierung von Red-Black-Bäumen
Applet zur Visualisierung von Suchbäumen (unterstützt auch AVL- und Red-Black-Bäume)
Applet zur Visualisierung von Algorithmen zur Textsuche (u.a. Knuth-Morris-Pratt)
Bemerkungen:

Gewinner des Hash-Funktionen-Wettbewerbs (Aufgabe 3.3.b) ist die Übungsgruppe "Timo Steinwender, Lars Schönpflug, Hannes Rusch". Ihr Gütemaß G beträgt 0,7842 (Quelltext).

Alle Studierenden sind herzlich eingeladen, an Diskussionen in der AuD-Newsgroup teilzunehmen.

  • Newsserver (NNTP): inn.ibr.cs.tu-bs.de
  • Newsgroup: ibr.lehre.aud
Unterlagen:

Das Material zu dieser Vorlesung steht einerseits in Form von PDF-Dateien zur Verfügung. Zudem werden sämtliche Sitzungen der Vorlesung als Video der Vorlesungsfolien mitgeschnitten und hier ebenfalls zur Verfügung gestellt. Damit sollte eine optimale Vor- und Nachbereitung des Stoffes möglich sein.

Als Videocodec haben wir uns für den Open-Source-MPEG4-XviD-Codec entschieden. Zur Verwendung unter Windows müssen Sie zuerst den Codec hier downloaden und installieren. Sollten Sie mit Linux arbeiten, verwenden Sie bitte den mplayer (dort sollte der passende Codec bereits enthalten sein).

Achtung: An den folgenden Terminen besteht für Sie die Möglichkeit eigene DVD-R bzw. DVD-RW (keine +R bzw. +RW) Rohlinge (4.7 GB) im Raum 119, 1.OG, Mühlenpfordstrasse 23, abzugeben. Diese werden dann gebrannt und können an den darauffolgenden Tagen im Raum 119 abgeholt werden. Die DVD beinhaltet alle Files, die Sie auch auf dieser Seite unter Unterlagen finden.
Bitte kennzeichnen Sie Ihre DVD mit ´Ihrem Namen´ und ´AuD II´! Falls Sie auch die Unterlagen von AuD I gebrannt haben möchten, kennzeichnen Sie bitte eine zweite DVD mit ´Ihrem Namen´ und ´AuD I´ und geben diese ebenfalls ab. Leider passen die Unterlagen der beiden AuD-Veranstaltungen nicht auf einen DVD-Rohling!

Termine: Freitag, der 15. August 2003 und Mittwoch, der 20. August 2003 (jeweils 9-12 Uhr).

Kap. Thema Unterlagen
6 Bäume Folien Download (PDF) -- eine Folie pro SeiteFolien Download (PDF) -- drei Folien pro SeiteFolien Download (PDF) -- drei Folien pro Seite (Farbe)Folien Download (PDF) -- vier Folien pro SeiteQuelltexte und ergänzende LiteraturQuelltexte und ergänzende LiteraturQuelltexte und ergänzende Literatur Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4) Übungsblatt Download (PDF)Lösungsblatt Download (PDF)Übungsblatt Download (PDF)Lösungsblatt Download (PDF)
7 Mengen und Verzeichnisse Folien Download (PDF) -- eine Folie pro SeiteFolien Download (PDF) -- drei Folien pro SeiteFolien Download (PDF) -- drei Folien pro Seite (Farbe)Folien Download (PDF) -- vier Folien pro Seite Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4) Übungsblatt Download (PDF)Lösungsblatt Download (PDF)
8 Graphen Folien Download (PDF) -- eine Folie pro SeiteFolien Download (PDF) -- drei Folien pro SeiteFolien Download (PDF) -- drei Folien pro Seite (Farbe)Folien Download (PDF) -- vier Folien pro Seite Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4) Übungsblatt Download (PDF)Lösungsblatt Download (PDF)
9 Sortieralgorithmen Folien Download (PDF) -- eine Folie pro SeiteFolien Download (PDF) -- drei Folien pro SeiteFolien Download (PDF) -- drei Folien pro Seite (Farbe)Folien Download (PDF) -- vier Folien pro Seite Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4) Übungsblatt Download (PDF)Lösungsblatt Download (PDF)
10 Algorithmenkonstruktion II Folien Download (PDF) -- eine Folie pro SeiteFolien Download (PDF) -- drei Folien pro SeiteFolien Download (PDF) -- drei Folien pro Seite (Farbe)Folien Download (PDF) -- vier Folien pro Seite Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4)Slideshow Download (XviD MPEG4) Übungsblatt Download (PDF)Lösungsblatt Download (PDF)
11 Andere Programmierstile Folien Download (PDF) -- eine Folie pro SeiteFolien Download (PDF) -- drei Folien pro SeiteFolien Download (PDF) -- drei Folien pro Seite (Farbe)Folien Download (PDF) -- vier Folien pro Seite Slideshow Download (XviD MPEG4)
12 Deduktive Algorithmen Folien Download (PDF) -- eine Folie pro SeiteFolien Download (PDF) -- drei Folien pro SeiteFolien Download (PDF) -- drei Folien pro Seite (Farbe)Folien Download (PDF) -- vier Folien pro Seite Slideshow Download (XviD MPEG4)