empty
Lehre empty
empty
empty

Lehrveranstaltungen Sommersemester 2009

 
Flüsse in Netzwerken   Online Algorithmen   Multikriteria-Optimierung   Praktikum: Zeichnen von Graphen  




Flüsse in Netzwerken (4 SWS) mit Übungen (2 SWS)
ab 6. Semester

Vorlesung Mo. und Do. 10.00-11.30 jeweils im Raum 202 (alte Uni)
Übungen Di. 14.00-15.30 im Raum 004 (alte Uni)


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
20.04.09

Kapitel 1-6
Kapitel 1-6

27.05.09

Kapitel 1-7
Kapitel 1-7

04.06.09

Kapitel 1-8
Kapitel 1-8

17.06.09

Kapitel 1-10
Kapitel 1-10

08.07.09

Kapitel 1-11
Kapitel 1-11

23.07.09

Korrigierter Beweis von Lemma 11.28
Korrigierter Beweis von Lemma 11.28





     Wochenzettel:

Ausgabe
Abgabe
Postscript
PDF
20.04.09
23.04.09
Wochenzettel 1
Wochenzettel 1

23.04.09
30.04.09
Wochenzettel 2
Wochenzettel 2

30.04.09
07.05.09
Wochenzettel 3
Wochenzettel 3

07.05.09
14.05.09
Wochenzettel 4
Wochenzettel 4

17.05.09
22.05.09
Wochenzettel 5
Wochenzettel 5

21.05.09
28.05.09
Wochenzettel 6
Wochenzettel 6

28.05.09
10.06.09
Wochenzettel 7
Wochenzettel 7

09.06.09
18.06.09
Wochenzettel 8
Wochenzettel 8

18.06.09
26.06.09
Wochenzettel 9
Wochenzettel 9

22.06.09
02.07.09
Wochenzettel 10
Wochenzettel 10

02.07.09
09.07.09
Wochenzettel 11
Wochenzettel 11

10.07.09
16.07.09
Wochenzettel 12
Wochenzettel 12








Online Algorithmen (2 SWS) mit Übungen (2 SWS)
ab 6. Semester

Vorlesung Mo. 14.00-15.30 im Raum 202 (alte Uni)
Übungen Mo. 15.45-17.15 im Raum 004 (alte Uni)


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
20.04.09

Kapitel 1-5
Kapitel 1-5

16.06.09

Kapitel 1-7
Kapitel 1-7





     Wochenzettel:

Ausgabe
Abgabe
Postscript
PDF
20.04.09
23.04.09
Wochenzettel 1
Wochenzettel 1

20.04.09
29.04.09
Wochenzettel 2
Wochenzettel 2

28.04.09
06.05.09
Wochenzettel 3
Wochenzettel 3

05.05.09
13.05.09
Wochenzettel 4
Wochenzettel 4

11.05.09
20.05.09
Wochenzettel 5
Wochenzettel 5

19.05.09
03.06.09
Wochenzettel 6
Wochenzettel 6

28.05.09
10.06.09
Wochenzettel 7
Wochenzettel 7

08.06.09
17.06.09
Wochenzettel 8
Wochenzettel 8

15.06.09
24.06.09
Wochenzettel 9
Wochenzettel 9

22.06.09
01.07.09
Wochenzettel 10
Wochenzettel 10

29.06.09
08.07.09
Wochenzettel 11
Wochenzettel 11

06.07.09
15.07.09
Wochenzettel 12
Wochenzettel 12








Multikriteria-Optimierung (2 SWS) mit Übungen (2 SWS)
ab 6. Semester


Vorlesung Di. 10.00-11.30 in Raum 2002 T (neue Uni)
Übungen Do. 15.45-17.15 in Raum 1009 H (Jura neue Uni)

Für viele Probleme der kombinatorischen Optimierung existieren effiziente Algorithmen, wenn bezüglich eines Optimalitätskriteriums optimiert wird. In vielen praktischen Anwendungen besteht jedoch der Wunsch, gleichzeitig bezüglich mehrerer Kriterien zu optimieren. So möchte man beim Kauf eines Computers häufig nicht nur den Preis minimieren, sondern auch den Speicherplatz der Festplatte oder des Arbeitsspeichers sowie die Geschwindigkeit des Prozessors maximieren. Da die Optimierung bezüglich eines Kriteriums häufig die Optimierung bezüglich eines anderen Kriteriums verhindert, ist es Ziel der Mulitkriterien-Optimierung, zu untersuchen, wie sich die Optimierung bezüglich mehrerer Kriterien am ehesten algorithmisch umsetzten lässt. Ein weiteres Ziel ist es, besonders effiziente Algorithmen für Multikriterien-Probleme zu finden. Die Vorlesung gibt einen ersten Überblick über die Multikriterien-Optimierung.




     Folien:

Ausgabe

Postscript
PDF

23.04.09

Foliensatz 1
Foliensatz 1

23.04.09

Foliensatz 2
Foliensatz 2

23.04.09

Foliensatz 3
Foliensatz 3

13.05.09

Foliensatz 4
Foliensatz 4

28.05.09

Foliensatz 5
Foliensatz 5

11.06.09

Foliensatz 6
Foliensatz 6

26.06.09

Foliensatz 7
Foliensatz 7

03.07.09

Foliensatz 8
Foliensatz 8

10.07.09

Foliensatz 9
Foliensatz 9

16.07.09

Foliensatz 10
Foliensatz 10

23.07.09

Foliensatz 10
Foliensatz 10

23.07.09

alle Folien
alle Folien



     
Übungen:

Ausgabe
Abgabe
Postscript
PDF

23.04.09
30.04.09
Wochenzettel 1
Wochenzettel 1

29.04.09
07.05.09
Wochenzettel 2
Wochenzettel 2

06.05.09
14.05.09
Wochenzettel 3
Wochenzettel 3

13.05.09
28.05.09
Wochenzettel 4
Wochenzettel 4

28.05.09
04.06.09
Wochenzettel 5
Wochenzettel 5

04.06.09
12.06.09
Wochenzettel 6
Wochenzettel 6

11.06.09
18.06.09
Wochenzettel 7
Wochenzettel 7

18.06.09
25.06.09
Wochenzettel 8
Wochenzettel 8

22.06.09
02.07.09
Wochenzettel 9
Wochenzettel 9

02.07.09
09.07.09
Wochenzettel 10
Wochenzettel 10

10.07.09
16.07.09
Wochenzettel 11
Wochenzettel 11



     Informationen:

Ausgabe

Postscript
PDF
13.07.09

Klausur
Klausur


Eine Liste mit den Klausurergebnissen hängt im 5. Stock an der alten Uni aus. Hier können Sie außerdem in verschlüsselter Form Ihre Note nachsehen, sofern Sie das bei der Klausuranmeldung gewünscht hatten.

Eine Klausureinsicht findet am Donnerstag, den 06.08.09, zwischen 15 und 16 Uhr im Raum 511 (Alte Uni) statt.










Praktikum: Zeichnen von Graphen (6 SWS)
ab 6. Semester

Di. 14.00-18.30 im Raum 111 (alte Uni)


Das Praktikum behandelt Algorithmen zum Zeichnen von Graphen in der Ebene. Ein solcher Algorithmus nimmt als Eingabe einen Graphen und berechnet ein zweidimensionales Layout. Im Praktikum sollen verschiedene Algorithmen aus der Literatur in C++ implementiert werden, die versuchen, anhand von bestimmten Kriterien ästhetisch schöne und leicht zu verstehende Zeichnungen von Graphen zu generieren. Ziel des Praktikums ist neben praktischer Programmiererfahrung das Erlernen sinnvoller Darstellungen der in vielerlei Anwendungen auftretenden Graphen.


     Informationen, Übungen und Projekte:

Beginn der Bearbeitung
Abgabe
Postscript
PDF
Literatur, C++ - Sourcen, etc.
05.02.09
05.04.09
Zulassungstest
Zulassungstest

21.04.09
08.06.09
Übung 1
Übung 1
bspl1, bspl2, M.
28.04.09
08.06.09
Übung 2
Übung 2
05.05.09
08.06.09
Übung 3
Übung 3
12.05.09
08.06.09
Übung 4
Übung 4
19.05.09
08.06.09
Übung 5
Übung 5
26.05.09
08.06.09
Übung 6
Übung 6




09.06.09
12.07.09
Projekt 1
Projekt 1
09.06.09
12.07.09
Projekt 2
Projekt 2


     Weitere Informationen:

Ausgabe
HTML
Postscript
PDF
Sourcen
21.04.09
LEDA



21.04.09


LEDA Graphwin

21.04.09
graphwin.h



21.04.09

AGD
AGD

21.04.09
Makefile Tutorial



21.04.09


Latex Handbuch

21.04.09


Latexklasse Beamer

21.04.09


PDF Anim
1, 2
21.04.09


Asymptote


Die Abschlusspräsentation findet am 06.08.09 ab 10.15 Uhr in Raum 207F (alte Uni) statt. Interessierte können gerne kommen.





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