empty
Lehre empty
empty
empty

Lehrveranstaltungen Wintersemester 2008/2009

 
Informatik III   I/O-effiz. Alg.   Graphenalg. für spez. Gr.   Praktikum Impl. v. Graphenalg.  




Informatik III (4 SWS) mit Übungen (2 SWS)
ab 3. Semester (9 LP für V + Ü)


Vorlesung Mo. und Mi. 10.00-11.30 Raum 1001T (Neue Uni)

Die Vorlesung behandelt wichtige Algorithmen (z.B. Suchen, Sortieren, Mengendarstellung) und die zugehörigen Datenstrukturen (z.B. Suchbäume, Hash-Tabellen). Sie erläutert anhand von Beispielen Entwurfsmethoden wie greedy, teile und herrsche und dynamisches Programmieren. Weiter werden Grundtechniken der Komplexitätsanalyse sowie einige prinzipielle Fragen der Effizienz (z.B. NP-Vollständigkeit) besprochen.


     Skript:

13.10.08
Postscript
PDF
PS 1/2 Größe
PDF 1/2 Größe


     Wochenzettel:

Ausgabe
Abgabe
Postscript
PDF
13.10.08
16.10.08
Wochenzettel 1
Wochenzettel 1

15.10.08
21.10.08
Wochenzettel 2
Wochenzettel 2

22.10.08
28.10.08
Wochenzettel 3
Wochenzettel 3

29.10.08
04.11.08
Wochenzettel 4
Wochenzettel 4

05.11.08
11.11.08
Wochenzettel 5
Wochenzettel 5

12.11.08
18.11.08
Wochenzettel 6
Wochenzettel 6

19.11.08
25.11.08
Wochenzettel 7
Wochenzettel 7

26.11.08
02.12.08
Wochenzettel 8
Wochenzettel 8

03.12.08
09.12.08
Wochenzettel 9
Wochenzettel 9

10.12.08
16.12.08
Wochenzettel 10
Wochenzettel 10

16.12.08
23.12.08
Wochenzettel 11
Wochenzettel 11

07.01.09
13.01.09
Wochenzettel 12
Wochenzettel 12

12.01.09
20.01.09
Wochenzettel 13
Wochenzettel 13

21.01.09
27.01.09
Wochenzettel 14
Wochenzettel 14



     Zusätzliches Material:

Anleitung zur Benutzung von LEDA
leda.pdf
Übung   3.9
(Impl. von Karatsuba/Ofman) ko.zip
Übung   3.11
(exp. Vergleich von Sortierverfahren) compare.zip,
code2+3.txt
Übung   4.9
(Test von bitonischen Sortierern) bitonic.zip
Übung 10.3
(Kantenklassifizierung durch Tiefensuche) dfs.zip


     Informationen:

Ausgabe

Postscript
PDF
20.11.08

Klausur
Klausur








I/O-effiziente Algorithmen (2 SWS) mit Übungen (1 SWS)
ab 5. Semester (5 LP für V + Ü)


Vorlesung Mo. 15.45-17.15 Raum 202F (Alte Uni)

Das klassische Berechnungsmodell der Random-Access-Maschine (RAM) stößt zunehmend an seine Grenzen. Der Grund ist, dass moderne Rechner nicht über den "flachen" Speicher der RAM verfügen, bei dem alle Speicherzellen "gleichberechtigt" sind, sondern eine ausgefeilte Speicherhierarchie mit Caches, Hauptspeicher und Hintergrundspeicher(n) besitzen. Im Allgemeinen sind "näher am CPU" gelegene Speicher deutlich schneller, dafür aber kleiner, und ein effizienter Algorithmus muss versuchen, häufig benutzte Daten in Speichern mit kurzen Zugriffszeiten zu halten. In der Vorlesung werden wir uns, nach einer Einführung geeigneter Speichermodelle, aus theoretischer Sicht mit sogenannten I/O-effizienten oder "speicherbewussten" Algorithmen befassen, die die Anzahl der Datentransporte zwischen Stufen der Speicherhierarchie möglichst gering halten. Bereits für das Problem des Sortierens wird sich herausstellen, dass die "I/O-effiziente Welt" ganz anders aussieht als die "RAM-Welt".


     Skript:

Ausgabe
Postscript PDF PS 1/2 Größe PDF 1/2 Größe
13.10.08
Kapitel 1-2
Kapitel 1-2 Kapitel 1-2 Kapitel 1-2
27.10.08
Kapitel 1-3
Kapitel 1-3 Kapitel 1-3 Kapitel 1-3
07.11.08
Kapitel 1-4
Kapitel 1-4 Kapitel 1-4 Kapitel 1-4
27.11.08
Kapitel 1-5
Kapitel 1-5 Kapitel 1-5 Kapitel 1-5
12.12.08
Kapitel 1-5
Kapitel 1-5 Kapitel 1-5 Kapitel 1-5
22.12.08
Kapitel 1-6
Kapitel 1-6 Kapitel 1-6 Kapitel 1-6
26.01.09
Kapitel 1-7
Kapitel 1-7 Kapitel 1-7 Kapitel 1-7


     Zusätzliches Material:

Übung   1.3
(random permutation) permdif.cpp


     Wochenzettel:

Ausgabe
Abgabe
Postscript
PDF
13.10.08
20.10.08
Wochenzettel 1
Wochenzettel 1

27.10.08
03.11.08
Wochenzettel 2
Wochenzettel 2

10.11.08
17.11.08
Wochenzettel 3
Wochenzettel 3

24.11.08
01.12.08
Wochenzettel 4
Wochenzettel 4

08.12.08
15.12.08
Wochenzettel 5
Wochenzettel 5

22.12.08
12.01.09
Wochenzettel 6
Wochenzettel 6

20.01.09
26.01.09
Wochenzettel 7
Wochenzettel 7










Graphenalgorithmen für spezielle Graphen (2 SWS) mit Übungen (2 SWS)
ab 5. Semester (5 LP für V + Ü)


Vorlesung Di. 8.15-9.45 in Raum 2001T (Neue Uni)
Übungen Do. 15.45-17.15 in Raum 1005L (Neue Uni)

Die Graphentheorie ist ein wichtiges Teilgebiet der Informatik und Mathematik mit vielen An- wendungsgebieten auch außerhalb dieser Disziplinen wie z.B. in den Wirtschaftswissenschaften. In der Praxis müssen viele für die Graphentheorie schwierige Probleme nicht auf allgemeinen Graphen sondern auf speziellen Graphen wie planaren Graphen, bipartiten Graphen oder chordalen Graphen gelöst werden. In der Vorlesung wollen wir für viele wichtige Probleme aus der Graphentheorie wie z.B. das Matchingproblem zeigen, wie sie auf speziellen Graphen besonders effizient gelöst werden können. Die Vorlesung soll zusammen mit der Vorlesung über Graphenalgorithmen für Pfad- und Zusammenhangsprobleme vom SS08 einen Überblick über die wichtigsten algorithmischen Probleme der Graphentheorie geben. Insofern ist der Besuch der Vorlesung vom SS08 hilfreich, jedoch nicht Voraussetzung für die Vorlesung im WS08/09.


     Skript:

Ausgabe
Postscript PDF PS 1/2 Größe PDF 1/2 Größe
13.10.08
Kapitel 1-4
Kapitel 1-4
Kapitel 1-4
Kapitel 1-4
23.12.08
Kapitel 5
Kapitel 5
Kapitel 5
Kapitel 5
03.02.09
Kapitel 6.1-4
Kapitel 6.1-4
Kapitel 6.1-4
Kapitel 6.1-4
07.02.09
Kapitel 6.5-7
Kapitel 6.5-7
Kapitel 6.5-7
Kapitel 6.5-7
02.03.09
Kapitel 7-8
Kapitel 7-8
Kapitel 7-8
Kapitel 7-8


     Folien:

Ausgabe

Postscript
PDF

14.10.08

Foliensatz 1
Foliensatz 1

21.10.08

Foliensatz 2
Foliensatz 2

28.10.08

Foliensatz 3
Foliensatz 3

04.11.08

Foliensatz 4
Foliensatz 4

11.11.08

Foliensatz 5
Foliensatz 5

18.11.08

Foliensatz 6
Foliensatz 6

03.12.08

Foliensatz 7
Foliensatz 7

10.12.08

Foliensatz 8
Foliensatz 8

07.01.09

Foliensatz 8 (neu)
Foliensatz 8 (neu)

12.01.09

Foliensatz 9
Foliensatz 9

22.01.09

Foliensatz 9 (neu)
Foliensatz 9 (neu)

22.01.09

Foliensatz 10
Foliensatz 10

22.01.09

Foliensatz 11
Foliensatz 11

02.02.09

Foliensatz 12
Foliensatz 12



     
Übungen:

Ausgabe
Abgabe
Postscript
PDF

13.10.08
23.10.08
Wochenzettel 1
Wochenzettel 1

21.10.08
30.10.08
Wochenzettel 2
Wochenzettel 2

28.10.08
06.11.08
Wochenzettel 3
Wochenzettel 3

04.11.08
13.11.08
Wochenzettel 4
Wochenzettel 4

11.11.08
20.11.08
Wochenzettel 5
Wochenzettel 5

18.11.08
27.11.08
Wochenzettel 6
Wochenzettel 6

25.11.08
04.12.08
Wochenzettel 7
Wochenzettel 7

02.12.08
11.12.08
Wochenzettel 8
Wochenzettel 8

09.12.08
18.12.08
Wochenzettel 9
Wochenzettel 9

17.12.08
08.01.09
Wochenzettel 10
Wochenzettel 10

07.01.09
15.01.09
Wochenzettel 11
Wochenzettel 11

13.01.09
22.01.09
Wochenzettel 12
Wochenzettel 12

20.01.09
29.01.09
Wochenzettel 13
Wochenzettel 13



     Informationen:

Ausgabe

Postscript
PDF
08.12.08

Klausur
Klausur


Die Ergebnisse der ersten Klausur hängen jetzt im 5. Stock der alten Uni (Eichleitner Str. 30) aus. Sofern Sie einer Onlineabfrage Ihrer Klausurnote zugestimmt haben, können Sie diese hier in verschlüsselter Form erfahren.







Praktikum: Implementierung von Graphenalgorithmen (6 SWS)
ab 5. Semester (8 LP)


Praktikum Di. 13.15-17.45 Raum 111F (Alte Uni)

Im Praktikum werden sowohl theoretisch 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
Postscript
PDF
Literatur, C++ - Sourcen, etc.
23.07.08
05.10.08
Zulassungstest
Zulassungstest

14.10.08
23.11.08
Übung 1
Übung 1
bspl1, bspl2, M.
21.10.08
23.11.08
Übung 2
Übung 2
DFS, BinTree
28.10.08
23.11.08
Übung 3
Übung 3
Flüsse
04.11.08
23.11.08
Übung 4
Übung 4
SPQR
11.11.08
23.11.08
Übung 5
Übung 5




25.11.08
30.01.09
Projekt 1
Projekt 1
25.11.08
30.01.09
Projekt 2
Projekt 2


     Manuals:

Ausgabe
HTML
Postscript
PDF
14.10.08
LEDA



14.10.08


LEDA Graphwin

14.10.08
graphwin.h



14.10.08

AGD
AGD

14.10.08
Makefile Anleitung



14.10.08


Latex Handbuch

14.10.08


Latexklasse Beamer

14.10.08


PDF Animationen

14.10.08


PDF Anim
1, 2
14.10.08


Asymptote





Wer im WS 2008/2009 an diesem Praktikum teilnehmen will, mußte bis zum 05.10.08 einen Zulassungstest bestehen. Alle Studenten, die den Zulassungstest bestanden haben,
sind dieses Jahr zum Praktikum zugelassen.

Die Präsentation des Praktikums findet am 10.02.09 ab 10.15 in
Raum 207F statt. Nicht in das Praktikum involvierte Personen sind auch
zu dieser Präsentation herzlich willkommen.




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