Uni-Logo
Algorithms and Complexity
 

Vorlesung
"Ausgewählte Kapitel aus Effiziente Algorithmen"
Wintersemester 2007/08
Prof. Dr. Susanne Albers
Dr. Alexander Souza
Fabian Schiller


Vorlesung

Die folgenden Formalitäten bilden den Rahmen der Veranstaltung: 3 + 1 SWS

Vorlesung

  • Zeit: Dienstags 11:00-13:00 und Donnerstags 11:00-13:00 Uhr
  • Ort: SR 01-009/13 Geb. 101

Übung

  • Zeit: Donnerstags 11:00-13:00
  • Ort: SR 01-009/13 Geb. 101

Vorlesung und Übung wechseln sich Donnerstags im wöchentlichen Rhythmus ab.

Leistungsnachweis

Wird noch bekannt gegeben.

Kreditpunkte

In dieser Veranstaltung können 6 ECTS-Punkte erworben werden.
Bei Anregungen und Fragen wenden Sie sich bitte an Alexander Souza oder Fabian Schiller.

Aktuelles / News

Deutsch English
12. November:
Die erste Übung findet am Donnerstag, den 15. November statt. The first assignment will be discussed on Thursday, November 15th, 2007.
15. November:
Aufgabe 2 vom ersten Übungsblatt kann auf mit dem zweiten Übungsblatt nochmals eingereicht werden. Exercise 2 of the first assignment may still be returned together with the second assignment.
19. November:
Nächster Übungstermin ist der 29. November 2007. Die Übung beginnt um 11:00 c.t. The current assignment will be discussed on November 29th, 2007. Discussion starts at 11:00 c.t.
8. January:
Das fünfte Übungsblatt ist selbstverständlich in der Vorlesung am 15. Januar 2008 abzugeben. The fifth assignment is to be returned in the lectures on January 15th 2008 of course.
28. January:
Am 7. Februar 2008 wird anstelle der Übung eine Vorlesung stattfinden. Die Übung wird am 12. Februar 2008 anstelle der Vorlesung stattfinden. On February 7th 2008 a lecture will be given instead of the exercises. The exercises will be made up on February 12th 2008 instead of the lectures.

Inhalt der Veranstaltung

Die Vorlesung wird je nach Auditorium auf Deutsch oder Englisch gehalten. Es wird weiterführender Stoff zu Algorithmentheorie behandelt. Dieser eignet sich sehr gut als Vorbereitung für eine Diplom- bzw Semesterarbeit in dem Bereich.

The lecture will be given in german or english depending on the audience. Advanced material of algorithm theory will be treated. The lecture is an excellent preparation for a thesis in this area.

Preliminary Table of Contents:

  1. Introduction
  2. Online Algorithms
    • List Update
    • Paging
  3. Algorithmic Graph Theory
    • Eulerian Tours
    • Strong Connectivity
    • Matching in Bipartite Graphs
    • Max-Flow Min-Cut
  4. Combinatorial Optimization
    • Linear Programming
    • Simplex-Algorithm
    • Duality
    • Applications
  5. Approximation Algorithms
    • Knapsack
    • Travelling Salesman
    • Scheduling

Für eine erfolgreiche Teilnahme an der Vorlesung sind grundlegende Kenntnisse in den Bereichen Algorithmen, Optimierung und Wahrscheinlichkeitsrechnung hilfreich aber nicht Voraussetzung.

Übungsblätter / Assignments

Abgabe der Übungsblätter in der Vorlesung. Rückgabe in der Übung.

Assignments have to be returned in the lectures. You will get the corrected assignments back in the exercises.

AssignmentReturn Date
First AssignmentNovember 6th, 2007
Second AssignmentNovember 20th, 2007
Third AssignmentDecember 4th, 2007
Fourth AssignmentDecember 18th, 2007
Fifth AssignmentJanuary 15th, 2008
Sixth AssignmentJanuary 29th, 2008
Seventh AssignmentFebruary 12th, 2008

Weiterführendes Material

Hier finden Sie Links zu Materialien, die in der sonstigen Literatur nicht oder nicht ausführlich genug behandelt werden.
  • Wird begleitend bekannt gegeben.

Literatur

Die folgenden Literaturangaben dienen als Grundlage für die Vorlesung.