empty
Lehre empty
empty
empty

Lehrveranstaltungen Sommersemester 2007

 
Einführung in die Theoretische Informatik, Alg. für NP-harte Probleme,
Graphenalgorithmen für ..., Praktikum Visualisieren von ...  



Einführung in die Theoretische Informatik (4 SWS) mit Übungen (2 SWS)
ab 2. Semester (9 LP für V + Ü)


Vorlesung Mo. 14.00-15.30 und Do. 12.15-13.45 jeweils in Raum 1001 T (Neue Uni)
Übungen Mo. 17.30-19.00 Raum 2002T, Di 8.15-9.45 Raum 2002T, Di 14.00-15.30 Raum 2001 T und Raum 2001 (Jura), Di 15.45-17.15 Raum 2002T, Fr 10.00-11.30 Raum 2002T, Fr 12.15-13.45 Raum 2002T

Die Vorlesung behandelt für die Informatik wichtige Strukturen der diskreten Mathematik, insbesondere formale Sprachen, Automaten und Turing-Maschinen.


     Skript:

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


     Übungen:

Ausgabe
Abgabe
Postscript
PDF
Zusätzliches Material
16.04.07
19.04.07
Wochenzettel 1
Wochenzettel 1

19.04.07
25.04.07
Wochenzettel 2
Wochenzettel 2

26.04.07
02.05.06
Wochenzettel 3
Wochenzettel 3
5 Zahlen
03.05.07
09.05.07
Wochenzettel 4
Wochenzettel 4

11.05.07
16.05.07
Wochenzettel 5
Wochenzettel 5

15.05.07
23.05.07
Wochenzettel 6
Wochenzettel 6

24.05.07
30.05.07
Wochenzettel 7
Wochenzettel 7

31.05.07
06.06.07
Wochenzettel 8
Wochenzettel 8

06.06.07
13.06.07
Wochenzettel 9
Wochenzettel 9

14.06.07
20.06.07
Wochenzettel 10
Wochenzettel 10

19.06.07
27.06.07
Wochenzettel 11
Wochenzettel 11

28.06.07
05.07.07
Wochenzettel 12
Wochenzettel 12

05.07.07
13.07.07
Wochenzettel 13
Wochenzettel 13



     Informationen:

Ausgabe

Postscript
PDF
11.06.07

Klausur
Klausur





Algorithmen für NP-harte Probleme (4 SWS) mit Übungen (2 SWS)
ab 6. Semester (9 LP für V + Ü)


Vorlesung Mi. und Fr. 12.15-13.45 jeweils in Raum 004 F (alte Uni)
Übungen Di. 08.15-09.45 in Raum 202 F (alte Uni)

NP-harte Probleme können nach heutigem Wissen nicht in polynomieller Zeit auf einem üblichen Rechner gelöst werden. Ungeachtet dessen treten solche Probleme überaus häufig in der Praxis auf, z.B. bei vielen Planungsaufgaben, und es ist von großer ökonomischer Bedeutung, sie doch noch zu lösen, zumindest "so gut wie es geht". Die Vorlesung behandelt Methoden der Algorithmentheorie, die hierfür entwickelt wurden. Einige Stichpunkte: Approximationsalgorithmen, Branch-and-Bound, Parametrisierung. Es werden auch Grenzen dieser Methoden aufgezeigt.

     Skript:

16.04.07
Postscript
PDF




     Errata:

13.06.07
Lemma 9.12.ps
Lemma 9.12.pdf




     Übungen:

Ausgabe
Abgabe
Postscript
PDF

18.04.07
20.04.07
Übung 1
Übung 1
25.04.07
02.05.07
Übung 2
Übung 2
02.05.07
09.05.07
Übung 3
Übung 3
09.05.07
16.05.07
Übung 4
Übung 4
18.05.07
30.05.07
Übung 5
Übung 5
30.05.07
06.06.07
Übung 6
Übung 6
06.06.07
13.06.07
Übung 7
Übung 7
13.06.07
20.06.07
Übung 8
Übung 8
19.06.07
27.06.07
Übung 9
Übung 9
27.06.07
04.07.07
Übung 10
Übung 10
04.06.07
11.07.07
Übung 11
Übung 11




Graphenalgorithmen für Pfad- und Zusammenhangsprobleme (2 SWS)
mit Übungen (2 SWS) ab 6. Semester (5 LP für V + Ü)


Der Vorlesungsraum hat sich geändert

Vorlesung Di. 12.15-13.45 in Raum 1002 T (Neue Uni)
Übung Di. 10.00-11.30 Raum 2001 T (Neue Uni)

Die Graphentheorie ist ein wichtiges Teilgebiet der Informatik und Mathematik mit vielen Anwendungsgebieten auch außerhalb dieser beiden Fachgebiete wie z.B. in den Wirtschaftswissenschaften. Zahlreiche Probleme aus der Praxis wie z.B. Transportprobleme in Verkehrsnetzwerken, Routingprobleme, Probleme der Netzwerkzuverlässigkeit in Kommunikationsnetzwerken, Fragen des Chipdesigns, ... lassen sich als Graphenprobleme formulieren und lösen.

Die Vorlesung ist Teil einer zweisemestrigen Vorlesungsreihe (SS07+WS07/08), die insgesamt einen Überblick über die wichtigsten algorithmischen Probleme der Graphentheorie geben möchte. Der Schwerpunkt dieser Vorlesung liegt bei Pfad- und Zusammenhangsproblemen auf Graphen, die relativ große Teilgebiete innerhalb der Graphentheorie darstellen.

     Skript:

Ausgabe

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

Kapitel 1-2
Kapitel 1-2
Kapitel 1-2
Kapitel 1-2
09.05.07

Kapitel 3
Kapitel 3
Kapitel 3
Kapitel 3
20.06.07

Kapitel 4
Kapitel 4
Kapitel 4
Kapitel 4
19.07.07

Kapitel 5
Kapitel 5
Kapitel 5
Kapitel 5
26.07.07

Final 1-5
Final 1-5
Final 1-5
Final 1-5
26.07.07

Errata
Errata
Errata
Errata




     Folien:

Ausgabe

Postscript
PDF

09.05.07

Foliensatz 1
Foliensatz 1

23.05.07

Foliensatz 2
Foliensatz 2

20.06.07

Foliensatz 3
Foliensatz 3

03.07.07

Foliensatz 4
Foliensatz 4

03.07.07

Foliensatz 5
Foliensatz 5

11.07.07

Foliensatz 6
Foliensatz 6

18.07.07

Foliensatz 7
Foliensatz 7



     Übungen:





Ausgabe
Abgabe
Postscript
PDF
Zusätzliches Material
16.04.07
19.04.07
Wochenzettel 1
Wochenzettel 1

25.04.07
02.05.07
Wochenzettel 2
Wochenzettel 2

08.05.07
15.05.07
Wochenzettel 3
Wochenzettel 3

15.05.07
22.05.07
Wochenzettel 4
Wochenzettel 4

22.05.07
05.06.07
Wochenzettel 5
Wochenzettel 5

05.06.07
12.06.07
Wochenzettel 6
Wochenzettel 6

12.06.07
19.06.07
Wochenzettel 7
Wochenzettel 7

19.06.07
26.06.07
Wochenzettel 8
Wochenzettel 8

26.06.07
03.07.07
Wochenzettel 9
Wochenzettel 9

03.07.07
10.07.07
Wochenzettel 10
Wochenzettel 10







     Informationen:

Ausgabe

Postscript
PDF
19.06.07

Klausur
Klausur







Praktikum: Visualisieren von Graphalgorithmen (6 SWS)
ab 6. Semester (8 LP)


Praktikum Mi. 14.00-18.30 in Raum 111 F (Alte Uni)


Im Praktikum werden sowohl theoretisch schon bekannte Algorithmen für beispielsweise das Finden eines minimalen Spannbaums oder eines kürzesten Weges als auch Algorithmen aus der Literatur für beispielsweise das Maximal Independent Set oder das Knotenfärbungsproblem in C++ implementiert und gleichzeitig visualisiert. 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.
08.02.07
12.04.07
Zulassungstest
Zulassungstest

18.04.07
07.06.07
Übung 1
Übung 1
bspl1, bspl2, M.
25.04.07
07.06.07
Übung 2
Übung 2
DFS, Bintree
02.05.07
07.06.07
Übung 3
Übung 3
Flüsse
09.05.07
07.06.07
Übung 4
Übung 4
23.05.07
07.06.07
Übung 5
Übung 5
SPQR
30.05.07
07.06.07
Übung 6
Übung 6
Matching




06.06.07
13.07.07
Projekt 1
Projekt 1
k-outer, 2
06.06.07
13.07.07
Projekt 2
Projekt 2
Multifluss


Manuals:

Ausgabe
HTML
Postscript
PDF
17.04.07
LEDA



17.04.07


LEDA Graphwin

17.04.07
graphwin.h



17.04.07

AGD
AGD

17.04.07
Makefile Tutorial



17.04.07


Latex Handbuch

17.04.07


Latexklasse Beamer

17.04.07


PDF Animationen

Eine Vorbesprechung zum Praktikum fand am 08.02.07 um 16.15 Uhr in Raum 207 (Alte Uni) statt. Um am Praktikum teilnehmen zu können, musste ein Zulassungstest bestanden werden.

Alle Teilnehmer, die den Zulassungstest bestanden haben, sind zum Praktikum zugelassen.

Die Präsentation des Praktikums fand am Mittwoch, den 18.7 ab 14.15 Uhr in 207F statt.





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