empty
Lehre empty
empty
empty

Lehrveranstaltungen Sommersemester 2011

 
Datenstrukturen, IO-effiziente Algorithmen,
Graphenalgorithmen für ..., Praktikum: NP-harte Graphprobleme



Datenstrukturen (4 SWS) mit Übungen (2 SWS)
für Diplom- und Masterstudiengang


Vorlesung Di. und Do. 12.15-13.45 jeweils im Raum 1057N
Übung Mi. 14.00-15.30 im Raum 1058N

Datenstrukturen realisieren abstrakte Datentypen so, dass die Operationen der Datentypen besonders effizient ausgeführt werden können. Beispiele von Datenstrukturen sind balancierte Bäume und Hashtabellen. Datenstrukturen können mit objektorientierten Programmiersprachen als Klassen zur Verfügung gestellt werden. In der Vorlesung sollen verschiedene Datenstrukturen behandelt werden, die über die in Informatik III behandelten Datenstrukturen hinausgehen, unter anderem die sogenannten dynamischen Bäume von Sleator und Tarjan, Range-Query-Strukturen und Suffix-Bäume.


     Skript:

Ausgabe

Postscript
PDF

03.05.11

Skript
Skript


     Übungen:

Ausgabe
Abgabe
Postscript
PDF
Zusätzliches Material
03.05.11
06.05.11
Wochenzettel 1
Wochenzettel 1

05.05.11
11.05.11
Wochenzettel 2
Wochenzettel 2

12.05.11
18.05.11
Wochenzettel 3
Wochenzettel 3

19.05.11
25.05.11
Wochenzettel 4
Wochenzettel 4

26.05.11
02.06.11
Wochenzettel 5
Wochenzettel 5

31.05.11
08.06.11
Wochenzettel 6
Wochenzettel 6

09.06.11
15.06.11
Wochenzettel 7
Wochenzettel 7

16.06.11
22.06.11
Wochenzettel 8
Wochenzettel 8

22.06.11
29.06.11
Wochenzettel 9
Wochenzettel 9

30.06.11
06.07.11
Wochenzettel 10
Wochenzettel 10

07.07.11
13.07.11
Wochenzettel 11
Wochenzettel 11

14.07.11
29.07.11
Wochenzettel 12
Wochenzettel 12







I/O-effiziente Algorithmen (2 SWS) mit Übungen (2 SWS)
für Diplom- und Masterstudiengang


Vorlesung Mo. 14.00-15.30 im Raum 1057N
Übung Mi. 10.00-11.30 im Raum 1058N

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

15.06.11

Skript Kapitel 1-8
Skript Kapitel 1-8


     Übungen:

Ausgabe
Abgabe
Postscript
PDF
Zusätzliches Material
02.05.11
06.05.11
Wochenzettel 1
Wochenzettel 1
permdif.c
09.05.11
13.05.11
Wochenzettel 2
Wochenzettel 2

16.05.11
20.05.11
Wochenzettel 3
Wochenzettel 3

23.05.11
27.05.11
Wochenzettel 4
Wochenzettel 4

30.05.11
03.06.11
Wochenzettel 5
Wochenzettel 5

06.06.11
10.06.11
Wochenzettel 6
Wochenzettel 6

14.06.11
17.06.11
Wochenzettel 7
Wochenzettel 7

20.06.11
24.06.11
Wochenzettel 8
Wochenzettel 8

27.06.11
01.07.11
Wochenzettel 9
Wochenzettel 9

04.07.11
08.07.11
Wochenzettel 10
Wochenzettel 10

11.07.11
15.07.11
Wochenzettel 11
Wochenzettel 11

18.07.11
22.07.11
Wochenzettel 12
Wochenzettel 12







Graphenalgorithmen für Pfad- und Zusammenhangsprobleme (2 SWS)
mit Übungen (2 SWS) für Diplom- und Bachelorstudiengang


Vorlesung Di. 10.00-11.30 Raum 1054N (Neue Uni)
Übung Di. 14.00-15.30 Raum 1054N

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 kann als Ergänzung zur Vorlesung vom WS10/11 besucht werden, setzt diese aber nicht voraus. Der Schwerpunkt dieser Vorlesung liegt bei Pfad- und Zusammenhangsproblemen auf Graphen, die relativ große Teilgebiete innerhalb der Graphentheorie darstellen.

     Skript:

Ausgabe

Postscript PDF
02.05.11

Kapitel 1-5
Kapitel 1-5




    
Folien:

Ausgabe

Postscript (4:1)
PDF (4:1)
Postscript (1:1)
PDF (1:1)
02.05.11

Foliensatz 1
Foliensatz 1


10.05.11

Foliensatz 2
Foliensatz 2
Foliensatz 1+2
Foliensatz 1+2
17.05.11

Foliensatz 3
Foliensatz 3
Foliensatz 3
Foliensatz 3
01.06.11

Foliensatz 4
Foliensatz 4
Foliensatz 4
Foliensatz 4
01.06.11

Ersatzfolie
Ersatzfolie
Ersatzfolie
Ersatzfolie
21.06.11

Foliensatz 5
Foliensatz 5
Foliensatz 5
Foliensatz 5
27.06.11

Foliensatz 6
Foliensatz 6
Foliensatz 6
Foliensatz 6
12.07.11

Foliensatz 7
Foliensatz 7
Foliensatz 7
Foliensatz 7
21.07.11

Foliensatz 8
Foliensatz 8
Foliensatz 8
Foliensatz 8
21.07.11

Foliensatz 9
Foliensatz 9
Foliensatz 9
Foliensatz 9
26.07.11

Ersatzfolie 2
Ersatzfolie 2
Ersatzfolie 2
Ersatzfolie 2


     Übungen:

Ausgabe
Abgabe
Postscript
PDF
Postscript
PDF
03.05.11
10.05.11
Wochenzettel 1
Wochenzettel 1


10.05.11
17.05.11
Wochenzettel 2
Wochenzettel 2


17.05.11
24.05.11
Wochenzettel 3
Wochenzettel 3


24.05.11
31.05.11
Wochenzettel 4
Wochenzettel 4
Homework 4
Homework 4
31.05.11
07.06.11
Wochenzettel 5
Wochenzettel 5
Homework 5
Homework 5
8.06.11
21.06.11
Wochenzettel 6
Wochenzettel 6
Homework 6
Homework 6
21.06.11
28.06.11
Wochenzettel 7
Wochenzettel 7
Homework 7
Homework 7
28.06.11
05.07.11
Wochenzettel 8
Wochenzettel 8
Homework 8
Homework 8
05.07.11
12.07.11
Wochenzettel 9
Wochenzettel 9
Homework 9
Homework 9
12.07.11
19.07.11
Wochenzettel 10
Wochenzettel 10
Homework 10
Homework 10



empty



Praktikum: NP-harte Graphprobleme (6 SWS)
für Diplom- und Masterstudiengang


Di. 14.00-18.30 im Raum 3079N


In der Informatik III wurden einige Probleme als NP-hart klassifiziert. Es wird allgemein erwartet, dass diese Probleme nicht in voller Allgemeinheit in Polynomialzeit gelöst werden können. Ungeachtet dessen sind NP-harte Probleme in der Praxis von großer Bedeutung.
Das Praktikum soll einen einfachen Einblick geben, unter welchen Bedingungen man Lösungen für so schwierige Probleme finden kann. Insbesondere wird sich das Praktikum mit sogenannten Fixed-Parameter Algorithmen und dem Finden von Problemkernen beschäftigen.
Ziel des Praktikums ist praktische Programmiererfahrung zu erlangen und einige in der Informatik III vorgestellten Graphalgorithmen zu implementieren und so zu erweitern, dass komplexere Probleme gelöst werden können. Zudem soll der Umgang mit wissenschaftlichen Texten erlernt werden.

Als Programmiersprache wird C++ mit der Erweiterung LEDA verwendet werden.


     Übungen und Projekte:

Beginn der Bearbeitung
Abgabe
Postscript
PDF
Literatur, C++ - Sourcen, etc.
03.05.11
14.06.11
Übung 1
Übung 1
bspl1, bspl2, M.
10.05.11
14.06.11
Übung 2
Übung 2

17.05.11
14.06.11
Übung 3
Übung 3

24.05.11
14.06.11
Übung 4
Übung 4

31.05.11
14.06.11
Übung 5
Übung 5





21.06.11
25.07.11
Projekt 1
Projekt 1
Multifluss


     Weitere Informationen:

Ausgabe
HTML
Postscript
PDF
Sourcen
03.05.11
LEDA



03.05.11


LEDA Graphwin

03.05.11
graphwin.h



03.05.11

AGD
AGD

03.05.11
Makefile Tutorial



03.05.11


Latex Handbuch

03.05.11


Latexklasse Beamer

03.05.11


PDF Anim
1, 2
03.05.11


Asymptote




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.