Algorithmen und Datenstrukturen (SS 2007)

Teilnehmerliste Alle angegebenen Zeiten sind minutengenau (nicht c.t.).
Die Teilnehmerlisten können nur innerhalb der Universität Passau eingesehen werden.

Aktuelles

• Die Wiederholungsklausur findet in der ersten Vorlesungswoche am Donnerstag den 18.10.2007 um 10-12 Uhr im Raum 147 b des Juridicums statt. Die Anmeldefrist dafür endet am 30.09.2007. Zur Einschreibung sind nur diejenigen berechtigt, die bei der Klausur vom 25.07.2007 zugelassen waren.
• Die Ergebnisse der Klausur sind online; An der Pinnwand neben Raum 128 IM ist ein entsprechender Aushang zu finden. Schüler können ihre Note in Raum 128 IM erfragen.
• Folgende Studierende sind zugelassen zur Klausur: Zulassungen.pdf.
• Die Abschlussklausur findet am Mittwoch, dem 25.07.2007, um 10:00-12:00 Uhr in den Räumen HS 13 IM und HS 09 AM statt. Studierende des Studiengangs Internet Computing schreiben ihre Klausur in Raum HS 09 AM. Studierende aller sonstigen Studiengänge (BA INF, LY INF, LR INF) schreiben ihre Klausur in Raum HS 13 IM. Studenten, die beide Studiengänge belegen, fallen unter die Kategorie, unter der sie sich im His-qis System angemeldet haben. Wichtig ist, dass alle Teilnehmer einen Lichtbildausweis mitbringen, zur Kontrolle der Anwesenheit. Es sind keine Hilfsmittel erlaubt, ausgenommen nicht-programmierbare Taschenrechner und Schreibutensilien. Es brauchen keine Blätter mitgebracht zu werden; diese werden gestellt.

Informationen zur Klausur

Literatur

• Uwe Schöning: Algorithmik, oder Algorithmen - kurz gefasst, Spektrum, ST 134 S365
• Uwe Schöning: Theoretische Informatik - kurz gefaßt, Spektrum, ST 130 S365
• R. Sedgewick: Algorithmen in Java, Pearson, oder Algorithms in Java, Addison-Wesley, ST 250 J35
• M. Goodrich, R. Tamassia: Data Structures and Algorithms in Java, Wiley, ST 265 G655
• V. Heun, Grundlegende Algorithmen, Vieweg, ST 134 H593
• H. Gumm, M. Sommer: Einführung in die Informatik, Oldenbourg, ST 110 G974
• W. Küchlin, A. Weber: Einführung in die Informatik, Springer-Verlag, ST 110 K95
• T.H. Cormen, C.E. Leiseron, R.R. Rivest, C. Stein: Introduction to Algorithms, 2nd ed., The MIT Press / McGraw-Hill, ST 134 C811 (2)
• J. Kleinberg, E. Tardos: Algorithm Design, Addison-Wesley, ST 134 K64

Supplemente

• Stoffübersicht und Vorlesungsplan
• Java-Dokumentation
• Programme (nur innerhalb der Uni zugreifbar)
• Vorlesungsfolien (nur innerhalb der Uni zugreifbar):
  • Kapitel 1 "Grundlagen": Folien 1-59 (in Endform)
  • Kapitel 2 "Listen": Folien 1-97 (in Endform)
  • Kapitel 3 "Bäume": Folien 1-93 (in Endform)
  • Kapitel 4 "Graphen": Folien 1-75 (in Endform)
  • Kapitel 5 "Harte Probleme": Folien 1-40
• Komplexitätsklassen und Problembeispiele
• Größenverhalten einiger Funktionen (Beispiele aus der Vorlesung)
• Cantorsche Diagonalverfahren:
  • Beweis der Abzählbarkeit der rationalen Zahlen (.ps, .pdf)
  • Beweis der Überabzählbarkeit der unendlichen Folgen natürlicher Zahlen (.ps, .pdf)
• Übersicht verschiedener Sortierverfahren (Bitte Wikipedia grundsätzlich mit Vorsicht genießen!)
• Visualisierung verschiedener Sortierverfahren
• Ein induktiver Beweis zur Heapsort-Komplexität (.ps, .pdf)

Übungen

Schein

Übungsblätter

Die Menschen hinter der Informatik:

• Der englische Informatiker Alan Turing hat die Turing-Machine konzipiert. Nach ihm ist auch die höchste Auszeichnung in der Informatik benannt: der Turing Award der ACM (Association for Computing Machinery).
• Der ungarische Mathematiker John von Neumann, hat das von-Neumann-Rechnermodell konzipiert.
• Der englische Mathematiker und Erfinder Charles Babbage, der den ersten mechanischen Computer entworfen hat.
• Die erste "Programmiererin" Ada Lovelace, nach der die Sprache Ada benannt ist.
• Über den Mathematiker Georg Cantor, von dem zwei in der Vorlesung präsentierte Diagonalverfahren stammen.
• Über den Mathematiker Leonardo Pisano Fibonacci, nach dem die Fibonacci-Zahlen benannt sind.
• Über den Mathematiker Kasimierz Kuratowski, nach dem die vollständigen Graphen K(n) mit in Knoten benannt wurden.
• Über den Logiker Kurt Gödel, der die Unvollständigkeit logischer Systeme bewiesen hat.