Effiziente Algorithmen (SS 2010)

Peter Rossmanith

Bereich

3+2 SWS Vorlesung im Bereich Theoretische Informatik
und im Vertiefungsgebiet Effiziente Algorithmen

2. Klausur

Die zweite Klausur fand am Donnerstag, den 16.09., von 09:00 Uhr bis 11:30 Uhr im AH I statt.
Die vorläufigen Ergebnisse der zweiten Klausur finden sich hier: Vorläufige Punkteliste (jpg). Der Notenspiegel lautet wie folgt:
38-40: 1.0
36-37: 1.3
34-35: 1.7
31-33: 2.0
29-30: 2.3
27-28: 2.7
24-26: 3.0
22-23: 3.3
20-21: 3.7
17-19: 4.0
0-16: 5.0


Die Einsicht findet am 29.9. zwischen 10:00 Uhr und 11:00 Uhr in Raum 6103, 1. Etage, E2, Hörn, statt.

1. Klausur

Die erste Klausur fand am Montag, den 26.7., von 8:30 Uhr bis 10:30 Uhr im AH VI statt.

Die vorläufigen Ergebnisse der ersten Klausur finden sich hier: Vorläufige Punkteliste (jpg) (Notenspiegel siehe oben).
  • Aufgabenblatt PS PDF
  • Lösungsvorschlag und typische Fehler PS PDF. Da beide Klausuren identisch waren (bis auf andere Bezeichnungen), enthält der Lösungsvorschlag nur die Aufgaben aus Gruppe A.

    Zeit und Ort

    Vorlesung: Dienstags 08:15-09:45 Uhr im AH VI und freitags 10:00-10:45 Uhr im AH III
    Fragestunde: Freitags 10:45-11:30 Uhr im AH III

    Übung: Mittwochs 11:45-13:15 Uhr im AH V

    Übungsblätter

    Zur weiteren Übung: Im Sommersemester 2006 konnten Diplomstudenten im Hauptstudium einen Schein in dieser Vorlesung erwerben. Notwendig war dazu unter anderem die erfolgreiche Teilnahme an dieser Klausur (PDF). Wir übernehmen natürlich keine Garantie, daß die diesjährige Klausur ähnlich ausfallen wird.

    Voraussetzungen

    Stoff der ersten Semester des Informatikstudiums und der zugehörigen Mathematikvorlesungen.

    Inhalt

    Die Vorlesung gibt einen Überblick über verschiedene Gebiete der Algorithmik. Im Zentrum der Vorlesung steht die theoretische Analyse der vorgestellten Algorithmen bezüglich ihrer Korrektheit, Laufzeit und Güte. Die Themenauswahl berücksichtigt insbesondere die praktische Relevanz der vorgestellten algorithmischen Konzepte. Im Einzelnen widmen wir uns den folgenden Themen.
    • Flüsse und Matchings
    • Lineare Programmierung
    • Algorithmische Geometrie
    • Randomisierte Algorithmen
    • Approximationsalgorithmen
    • Online-Algorithmen

    Folien (als pdf-Dateien)

    Literatur

    Buch Introduction to Algorithms.
    Will man, aus welch merkwürdigen Gründen auch immer, nur ein Buch über Algorithmen lesen, dann sollte es dieses sein.
    Buch The Art of Computer Programming.
    Hier ist besonders der dritte Band interessant. Diese Bücher sind in der Fachbereichsbibliothek und in der Lehrbuchsammlung in ausreichender Menge vorhanden.

    Peter Rossmanith