empty
Lehre empty
empty
empty

Lehrveranstaltungen Wintersemester 2007/2008

 
Informatik III   Einführung in die alg. Geometrie   Graphenalgorithmen für ...   Praktikum Zeichnen von Graphen  




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

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:
15.10.07
Postscript
PDF
PS 1/2 Größe
PDF 1/2 Größe
29.10.07
Errata.ps
Errata.pdf


     Wochenzettel:

Ausgabe
Abgabe
Postscript
PDF
15.10.07
18.10.07
Wochenzettel 1
Wochenzettel 1

17.10.07
23.10.07
Wochenzettel 2
Wochenzettel 2

24.10.07
30.10.07
Wochenzettel 3
Wochenzettel 3

31.10.07
06.11.07
Wochenzettel 4
Wochenzettel 4

07.11.07
13.11.07
Wochenzettel 5
Wochenzettel 5

14.11.07
20.11.07
Wochenzettel 6
Wochenzettel 6

21.11.07
27.11.07
Wochenzettel 7
Wochenzettel 7

28.11.07
05.12.07
Wochenzettel 8
Wochenzettel 8

05.12.07
11.12.07
Wochenzettel 9
Wochenzettel 9

12.12.07
18.12.07
Wochenzettel 10
Wochenzettel 10

19.12.07
08.01.08
Wochenzettel 11
Wochenzettel 11

09.01.08
15.01.08
Wochenzettel 12
Wochenzettel 12

14.01.08
22.01.08
Wochenzettel 13
Wochenzettel 13

24.01.08
29.01.08
Wochenzettel 14
Wochenzettel 14



     Informationen:

Ausgabe

Postscript
PDF
22.11.07

Klausur
Klausur





Eine Klausureinsicht der Zweitklausur fand am Donnerstag, den
10. April 2008, in Raum 511 (alte Uni) statt.





Einführung in die algorithmische Geometrie (2 SWS) mit Übungen (1 SWS)
ab 5. Semester (5 LP für V + Ü)


Vorlesung Do. 08.15-09.45 Raum 104F
Übung Do. 10.00-11.30 Raum 202F


Es werden grundlegende Konzepte, Algorithmen und Datenstrukturen der algorithmischen Geometrie der zweidimensionalen Ebene behandelt. Beispiele:
- konvexe Hüllen
- Schnitt von Geradensegmenten
- planare Unterteilungen
- Triangulierung.


     Literatur:
Computational Geometry. Algorithms and Applications
von de Berg, van Kreveld, Overmars und Schwarzkopf.


     Wochenzettel:

Ausgabe
Abgabe
Postscript
PDF
18.10.07
30.10.07
Wochenzettel 1
Wochenzettel 1

08.11.07
15.11.07
Wochenzettel 2
Wochenzettel 2

22.11.07
29.11.07
Wochenzettel 3
Wochenzettel 3

06.12.07
13.12.07
Wochenzettel 4
Wochenzettel 4

20.12.07
17.01.08
Wochenzettel 5
Wochenzettel 5

24.12.07
31.01.08
Wochenzettel 6
Wochenzettel 6









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





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 azyklisch gerichteten 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 Graphen- algorithmen für Pfad- und Zusammenhangsprobleme vom SS07 einen Überblick über die wichtigsten algorithmischen Probleme der Graphentheorie geben. Insofern ist der Besuch der Vorlesung vom SS07 hilfreich, jedoch nicht Voraussetzung für die Vorlesung im WS07/08.


     Skript:

Ausgabe

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

Kapitel 1-2
Kapitel 1-2
Kapitel 1-2
Kapitel 1-2
30.10.07

Kapitel 3
Kapitel 3
Kapitel 3
Kapitel 3
06.02.08

Kapitel 4
Kapitel 4
Kapitel 4
Kapitel 4
06.02.08

Stichwortv.
Stichwortv.
Stichwortv.
Stichwortv.


     Folien:

Ausgabe

Postscript
PDF

16.10.07

Foliensatz 1
Foliensatz 1

24.10.07

Foliensatz 2
Foliensatz 2

30.10.07

Foliensatz 3
Foliensatz 3

05.11.07

Foliensatz 4
Foliensatz 4

13.11.07

Foliensatz 5
Foliensatz 5

13.11.07

Foliensatz 6
Foliensatz 6

03.12.07

Foliensatz 7
Foliensatz 7

03.12.07

Foliensatz 8
Foliensatz 8

11.12.07

Foliensatz 9
Foliensatz 9

18.12.07

Foliensatz 10
Foliensatz 10

08.01.08

Foliensatz 11
Foliensatz 11

01.02.08

Foliensatz 12
Foliensatz 12

01.02.08

Foliensatz 13
Foliensatz 13



     
Übungen:

Ausgabe
Abgabe
Postscript
PDF

16.10.07
23.10.07
Wochenzettel 1
Wochenzettel 1

22.10.07
30.10.07
Wochenzettel 2
Wochenzettel 2

29.10.07
06.11.07
Wochenzettel 3
Wochenzettel 3

05.11.07
13.11.07
Wochenzettel 4
Wochenzettel 4

12.11.07
20.11.07
Wochenzettel 5
Wochenzettel 5

20.11.07
27.11.07
Wochenzettel 6
Wochenzettel 6

26.11.07
04.12.07
Wochenzettel 7
Wochenzettel 7

03.12.07
11.12.07
Wochenzettel 8
Wochenzettel 8

10.12.07
18.12.07
Wochenzettel 9
Wochenzettel 9

17.12.07
08.01.08
Wochenzettel 10
Wochenzettel 10

07.01.08
15.01.08
Wochenzettel 11
Wochenzettel 11

14.01.08
22.01.08
Wochenzettel 12
Wochenzettel 12

21.01.08
29.01.08
Wochenzettel 13
Wochenzettel 13



     Informationen:

Ausgabe

Postscript
PDF
11.01.08

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 21.02.08, zwischen 11 und 12 Uhr im Raum 511 (Alte Uni) statt.








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


Praktikum Do. 12.45-17.15 im 1. Stock, Eichl. (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.
12.07.07
19.09.07
Zulassungstest
Zulassungstest

18.10.07
13.12.07
Übung 1
Übung 1
bspl1, bspl2, M.
25.10.07
13.12.07
Übung 2
Übung 2

08.11.07
13.12.07
Übung 3
Übung 3
Cluster
15.11.07
13.12.07
Übung 4
Übung 4
Heuristik
22.11.07
13.12.07
Übung 5
Übung 5
29.11.07
13.12.07
Übung 6
Übung 6
Ballon, TD
06.12.07
13.12.07
Übung 7
Übung 7
OP-SL




13.12.07

Projekt 1
Projekt 1
I-Graph
13.12.07

Projekt 2
Projekt 2
st-Ori., Decr.


     Manuals:

Ausgabe
HTML
Postscript
PDF
27.09.07
LEDA



27.09.07


LEDA Graphwin

27.09.07
graphwin.h



27.09.07

AGD
AGD

27.09.07
Makefile Tutorial



27.09.07


Latex Handbuch

27.09.07


Latexklasse Beamer

27.09.07


PDF Animationen




Die Präsentation des Praktikums findet am 11.02.08 ab 14.15 in Raum 207F statt. Auch nicht in das Praktikum involvierte Personen sind 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