---

Vorlesung Informatik II

Klausurtermine

Die Klausur zur Vorlesung Informatik II findet amDienstag, den 25.07.2006, 10-12 Uhr, HS 3.28, R 5.09 und 5.10 statt.
Die Nachklausur zur Vorlesung Informatik II findet am Mittwoch, den 27.09.2006, 10-12 Uhr, HS 3.31, 3.04, R 5.09 und 5.10 statt.

Ort, Zeit

Vorlesung: Di 14-16 Uhr und Do 14-16 Uhr, jeweils HS 3.28
Übungen: Di 12-14 Uhr, SR 1.03
               Di 16-18 Uhr, SR 1.27
              Mi 16.18 Uhr, SR 1.27

Vorlesungsinhalt

Die Vorlesung wendet sich an die Studierenden der Fachrichtungen Informatik und Bioinformatik und stehtunter dem Motto "Vom Programm zum schnellen Programm". Hauptthema ist der Entwurf und die Analyse effizienter Datenstrukturen und Algorithmen.

  1. Aufwandsanalyse: Zeitaufwand funktionaler Programme, Analyse des Zeitaufwands funktionaler Programme durch Rekurrenzen, Loesen von Rekurrenzen
  2. Algorithmenentwurf 1: Gierige Algorithmen, Teile-und-Herrsche-Algorithmen (jeweils funktional), O-Kalkuel, Master-Theorem
  3. Sortieren: Aufwand imperativer Programme, Herleitung diverser Sortierverfahren durch schrittweise Verfeinerung
  4. Suchen: Objekt-orientierte Implementierungen des Datentyps Menge, lineare Suche, binaere Suchbaeume, AVL-Baeume, Hashverfahren
  5. Algorithmenentwurf 2: Dynamisches Programmieren, Vorberechnung, amortisierte Analyse
  6. Algorithmen auf Graphen: Objekt-orientierte Implementierung von Graphen, Durchlaufen von Graphen (Tiefensuche, Breitensuche) mit Anwendungen (z.B. Zusammenhangskomponenten, spannende Baeume), topologisches Sortieren, schwierige Probleme

Folien

Allgemeines
slides-4.pdf (externe Datei)

Kapitel 1: Autwandsanalyse funktionaler Programme
funktional-4.pdf (externe Datei)

Kapitel 2: Algorithmenentwurf 1
algo-1-4.pdf (externe Datei)

Kapitel 3: Imperativer Algorithmenentwurf
imperativ-4.pdf (externe Datei)

Kapitel 4: Suchen in Mengen
mengen-4.pdf (externe Datei)

Kapitel 5: Algorithmenentwurf 2 (endgültig korrigierte und vollständige Folien)
algo-2-4.pdf (externe Datei)

Kapitel 6: Algorithmen auf Graphen
graphen-4.pdf (externe Datei)

Übungen

Übungsserie 1
uebung01_1.pdf (externe Datei)

Übungsserie 2
uebung02_1.pdf (externe Datei)

Übungsserie 3
uebung03.pdf (externe Datei)

Übungsserie 4
uebung04.pdf (externe Datei)

Übungsserie 5
uebung05.pdf (externe Datei)

Übunksblatt 6
uebung06.pdf (externe Datei)

Übungsblatt 7
uebung07.pdf (externe Datei)

Übungsblatt 8
uebung08.pdf (externe Datei)

Übungsblatt 9
uebung09.pdf (externe Datei)

Übungsserie 10
uebung10.pdf (externe Datei)

Übungsblatt 11
uebung11.pdf (externe Datei)

Übungsblatt 12
uebung12.pdf (externe Datei)

Übungsblatt 13 (mit Zusatztheorieaufgaben)
uebung13.pdf (externe Datei)

Übungsblatt 14 (Zusatzprogrammieraufgaben)
uebung14.pdf (externe Datei)

Sonstige Materialien

Beweis von Satz 2.11
beweis.pdf (externe Datei)

Zum Seitenanfang