Uni-Logo
Algorithms and Complexity
 


Vorlesung
"Informatik II"
Sommersemester 2006
Prof. Dr. Susanne Albers



Vorlesung

Montag, 14-16 Uhr, HS 00-026, Gebäude 101 und
Donnerstag, 11-13 Uhr, HS 00-026, Gebäude 101.

Vorlesungsfolien und Aufzeichnungen sind auf unserem Webserver verfügbar.

Übungen

Übungsblätter, Vorlesungsmaterialien und organisatorische Hinweise zu den Übungen finden Sie auf der Übungsseite.

Aktuelles

21. März 2007
Die Nachklausuren können bis einschließlich 28. März 2007 bei Tobias Jacobs eingesehen werden.
21. März 2007
Die Ergebnisse der Nachklausur sind ab sofort online einsehbar.
3. Januar 2007
Die Nachklausur findet am 16. März 2007 von 10-12 Uhr in Raum 026, Geb. 101 statt.
3. August 2006
Bisher nicht abgeholte Übungsblätter der Gruppen 1, 2, 3, 4, 6 und 7 können ab sofort bei Fabian Müller abgeholt werden.

Inhalt der Veranstaltung

In dieser Vorlesung werden grundlegende Kenntnisse in den Bereichen Algorithmen und Datenstrukturen vermittelt. Dazu gehören unter anderem:
  • Hoare-Kalkül und Laufzeitbestimmung
  • Entwurfsverfahren für Algorithmen
  • Elementare Datenstrukturen: Liste, Stapel, Schlange
  • Skiplisten
  • Sortier- und Suchalgorithmen
  • Amortisierte Analyse
  • Dynamische Tabellen
Vorraussetzung für eine erfolgreiche Teilnahme an Vorlesung und Übungen sind grundlegende Kenntnisse der Programmiersprache JAVA.

Klausur

Die Klausur findet am 18.10.2006 von 14 bis 16 Uhr im Kinohörsaal in Gebäude 082 statt.

Um an der Klausur teilnehmen zu können müssen mindestens 50% der Übungsaufgaben bearbeitet und mindestens einmal eine Lösung in der Übung an der Tafel vorgestellt worden sein.

Bei Erreichen von mindestens 50% der Übungspunkte wird in der Klausur ein Bonus von einer drittel Notenstufe gegeben. Sollten mindestens 80% erreicht werden, so wird die Klausur um zwei drittel Notenstufen aufgewertet.

Kreditpunkte

In dieser Veranstaltung können 8 ECTS-Punkte erworben werden.

Weiterführendes Material

Hier finden Sie Links zu Materialien, die in der sonstigen Literatur nicht oder nicht ausführlich genug behandelt werden.
  • Ausführlichere Informationen zum Hoare-Kalkü in der Originalarbeit von C. A. R. Hoare (1969). (Der Link funktioniert nur von Rechnern mit Uni-IP)

Literatur

Die folgenden Literaturangaben dienen als Grundlage für die Vorlesung.
  • T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. Second Edition MIT Press, 2002.
  • Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen.  4. Auflage, Spektrum Akademischer Verlag, Heidelberg, 2002
  • G. Saake, K.-U. Sattler: Algorithmen und Datenstrukturen: eine Einführung mit Java. dpunkt-Verlag, Heidelberg 2002.
  • J. Kleinberg, E. Tardos: Algorithm Design. Pearson, Addison-Wesley 2006.
  • M. T. Goodrich, R. Tamassia: Data structures and algorithms in Java. John Wiley & Sons, Second Edition, 2001.
  • R. Sedgewick: Algorithmen in Java. München : Pearson Studium, 2003.
  • S. Baase, A. Van Gelder: Computer algorithms : introduction to design and analysis. Addison-Wesley, 2000.