empty
Lehre empty
empty
empty

Lehrveranstaltungen Sommersemester 2012

 
Flüsse in Netzwerken   Online Algorithmen   Praktikum: Graphalgorithmen  




Flüsse in Netzwerken (4 SWS) mit Übungen (2 SWS)
für den Diplom- und Bachelorstudiengang

Vorlesung Di. und Do. 10.00-11.30 jeweils im Raum 1058 N
Übungen Di. 08.15-09.45 im Raum 1058 N


Die Vorlesung behandelt Flüsse in Netzwerken, Algorithmen zu ihrer Berechnung sowie Anwendungen von Flüssen bei der Modellierung und Lösung anderer algorithmischer Probleme. Ein Netzwerk kann man sich als ein System von "Rohrleitungen" vorstellen, die eine bestimmte "Ware" transportieren können. Jedes Rohr hat eine Kapazität, die angibt, wieviel Ware pro Zeiteinheit durch das Rohr fließen kann; hierbei entstehen eventuell zusätzlich Kosten, die von dem Rohr abhängen. Bei einem vorliegenden Netzwerk kann man sich eine Fülle algorithmischer Fragen stellen. Zentral für uns wird das Problem sein, einen möglichst großen Fluss an Waren von einer ausgezeichneten Quelle zu einer ausgezeichneten Senke zu erreichen (Max-Flow-Problem). Wir werden einige der besten Algorithmen für dieses Problem kennenlernen, insbesondere den erst vor wenigen Jahren entdeckten Binary-Blocking-Flow-Algorithmus von Goldberg und Rao. Auch das Min-Cost-Max-Flow-Problem wird zur Sprache kommen.


     Skript:

Ausgabe

Postscript
PDF
17.04.12

FiN-Skript
FiN-Skript

19.04.12

Info-III Skriptauszug
Info-III Skriptauszug



     Wochenzettel:

Ausgabe
Abgabe
Postscript
PDF
17.04.12
22.04.12
Wochenzettel 1
Wochenzettel 1

19.04.12
26.04.12
Wochenzettel 2
Wochenzettel 2

27.04.12
03.05.12
Wochenzettel 3
Wochenzettel 3

03.05.12
10.05.12
Wochenzettel 4
Wochenzettel 4

10.05.12
22.05.12
Wochenzettel 5
Wochenzettel 5

24.05.12
31.05.12
Wochenzettel 6
Wochenzettel 6

31.05.12
12.06.12
Wochenzettel 7
Wochenzettel 7

14.06.12
21.06.12
Wochenzettel 8
Wochenzettel 8

21.06.12
28.06.12
Wochenzettel 9
Wochenzettel 9

28.06.12
05.07.12
Wochenzettel 10
Wochenzettel 10

05.07.12
12.07.12
Wochenzettel 11
Wochenzettel 11



     Weitere Informationen:

Ausgabe

Postscript
PDF
16.07.12

Pensum der mündl. Prüfung
Pensum der mündl. Prüfung








Online Algorithmen (2 SWS) mit Übungen (2 SWS)
für den Diplom- und Masterstudiengang

Vorlesung Do. 14.00-15.30 im Raum 1058 N
Übungen Do. 15.45-17.15 im Raum 1058 N


Manchmal muss man Entscheidungen treffen, bevor alle relevante Daten bekannt sind. Will man z.B. Aktien kaufen, so wäre es sehr hilfreich, über die künftige Entwicklung aller Aktienkurse informiert zu sein; aber es liegt in der Natur der Sache, dass man den Kauf tätigen muss, bevor diese Information vorliegt. Ein zweites Beispiel: Eine Funktaxizentrale muss nach jeder Bestellung einen der verfügbaren Wagen auswählen und zum Fahrgast schicken; mit Wissen über später eintreffende Anrufe könnten die Wagen vielleicht günstiger auf die Fahrgäste verteilt werden. Algorithmen, die Entscheidungen bei unvollständiger Information treffen, heißen Online-Algorithen. Die Vorlesung behandelt Online-Algorithmen und ihre Analyse. Konkrete betrachtete Probleme sind das sogenannte Skipass-Problem, das Listenverwaltungsproblem, Navigieren in einer unbekannten Umgebung sowie Paging.


     Skript:

Ausgabe

Postscript
PDF
19.04.12

Skript
Skript





     Wochenzettel:

Ausgabe
Abgabe
Postscript
PDF
19.04.12
23.04.12
Wochenzettel 1
Wochenzettel 1

23.04.12
27.04.12
Wochenzettel 2
Wochenzettel 2

26.04.12
03.05.12
Wochenzettel 3
Wochenzettel 3

03.05.12
10.05.12
Wochenzettel 4
Wochenzettel 4

10.05.12
21.05.12
Wochenzettel 5
Wochenzettel 5

24.05.12
31.05.12
Wochenzettel 6
Wochenzettel 6

31.05.12
11.06.12
Wochenzettel 7
Wochenzettel 7

14.06.12
21.06.12
Wochenzettel 8
Wochenzettel 8

21.06.12
28.06.12
Wochenzettel 9
Wochenzettel 9

28.06.12
05.07.12
Wochenzettel 10
Wochenzettel 10

12.07.12
16.07.12
Wochenzettel 11
Wochenzettel 11



     Weitere Informationen:

Ausgabe

Postscript
PDF
05.07.12

Informationen zur Klausur
Informationen zur Klausur

16.07.12

Pensum der Klausur
Pensum der Klausur



Die Klausurergebnisse hängen vor Raum 3076 aus. Sie können zusätzlich hier Ihre Klausurnote in verschlüsselter Form erfahren, sofern Sie bei der Klausuranmeldung dem zugestimmt haben. Eine Klausureinsicht ist am Mittwoch, den 01.08.12, zwischen 16.00 und 16.30 Uhr in Raum 3076 möglich.

Für Vorlesungsteilnehmer, die die Klausur nicht bestanden haben, wird eine Nachklausur gegen Ende des Wintersemesters 12/13 veranstaltet. Der genaue Termin steht noch nicht fest, wird aber rechtzeitig über die Internetseite des Lehrstuhls mitgeteilt. Für die Teilnahme an der Nachklausur ist eine erneute Studisanmeldung und eine erneute Anmeldung über die Internetseite des Lehrstuhls erforderlich.





Praktikum: Graphalgorithmen (6 SWS)
für den Diplom- und Bachelorstudiengang

Di. 14.00-18.30 im Raum 3079 N


Im Praktikum werden sowohl aus der Informatik III schon bekannte Algorithmen für beispielsweise das Finden eines minimalen Spannbaums oder der Bestimmung eines bipartiten Graphens als auch Algorithmen aus der Literatur für beispielsweise das Matching oder das Knotenfärbungsproblem in C++ implementiert. Hierbei werden häufig verwendete Lösungsansätze wie die Bottom-Up-Strategie oder Approximationsalgorithmen an Beispielproblemen erläutert. Ziel des Praktikums ist neben praktischer Programmiererfahrung das Vertiefen der Kenntnisse bekannter Algorithmen und das genaue Verstehen wissenschaftlicher Veröffentlichungen inklusive aller Details, die nicht weiter beschrieben sind.


     Informationen, Übungen und Projekte:

Beginn der Bearbeitung
Abgabe
PDF
Literatur, C++ - Sourcen, etc.
15.02.12
08.04.12
Zulassungstest

17.04.12
06.06.12
Übung 1
bspl1, bspl2, M.
24.04.12
06.06.12
Übung 2
Boyle Artikel, DFS, BinTree
08.05.12
06.06.12
Übung 3
Vizing Artikel
15.05.12
06.06.12
Übung 4
Flüsse Skript
22.05.12
06.06.12
Übung 5
Karp




05.06.12
15.07.12
Projekt
Paper


     Weitere Informationen:

Ausgabe
HTML
Postscript
PDF
Sourcen
17.04.12
LEDA



17.04.12


LEDA Graphwin

17.04.12
graphwin.h



17.04.12

AGD
AGD

17.04.12
Makefile Tutorial



17.04.12


Latex Handbuch

17.04.12


Latexklasse Beamer

17.04.12


PDF Anim
1, 2
17.04.12


Asymptote

17.04.12


Informatik III


Um an diesem Praktikum teilnehmen zu können, mussten Sie den obigen Zulassungstest bestehen. Der Zulassungstest lief vom 15.02.12 bis zum 08.04.12.

Alle Studenten, die den Zulassungstest bestanden hatten, sind zum Praktikum zugelassen.




Bitte beachten Sie, dass Sie sich ggf. in Studis anmelden müssen, damit Ihre Leistungen anerkannt werden können. Das Programm Studis und Anmeldungen auf unserer Homepage stehen in keinerlei Zusammenhang. Das gesamte Lehrangebot der Informatik kann im kommentierten Vorlesungsverzeichnis eingesehen werden. empty