empty
Lehre empty
empty
empty

Lehrveranstaltungen Wintersemester 2016/2017

 
Platzeffiziente Algorithmen  






Platzeffiziente Algorithmen (2 SWS) mit Übungen (2 SWS)
für den Masterstudiengang (ab 1. Semester)


Dozent:  Dr. Frank Kammer
Vorlesung: Mi. 15.45-17.15 Raum 1054N
Übung: Do. 14.00-15.30 Raum 1055N

Manchmal hat ein Algorithmus eine große Eingabe, aber nur wenig frei beschreibbaren Arbeitsspeicher. Zum Beispiel könnte die Eingabe im Internet für Anfragen zur Verfügung stehen, aber in ihrer Gesamtheit so riesig sein, dass es unmöglich oder unpraktisch ist, sie auf den lokalen Rechner herunterzuladen.

Die Vorlesung beschäftigt sich aus theoretischer Sicht mit Algorithmen, die mit weniger Arbeitsspeicher als klassische Algorithmen für dieselben Probleme auskommen. Der Fokus liegt auf Graphenprobleme wie die Durchführung einer Tiefensuche oder die Berechnung kürzester Wege, aber auch Sortieren und platzeffiziente Datenstrukturen kommen zur Sprache. Ein Großteil der in der Vorlesung vorgestellten Ergebnisse wurde seit 2014 am Lehrstuhl für Theoretische Informatik erzielt. Die Vorlesung behandelt somit ein sehr aktives und aktuelles Forschungsgebiet.



     Unterrichtsmaterialien:

19.10.16
Skript
PDF
PDF 1/2 Größe
26.10.16
Animation der DFS
PDF

08.12.16
Cutvertices und Außenplanar
PDF

01.02.17
Euler Partition
PDF


     Übungsblätter:

Ausgabe
Abgabe
PDF
19.10.16
24.10.16
Übungsblatt 1

19.10.16
26.10.16
Übungsblatt 2

26.10.16
04.11.16
Übungsblatt 3

02.11.16
11.11.16
Übungsblatt 4

09.11.16
18.11.16
Übungsblatt 5

16.11.16
25.11.16
Übungsblatt 6

23.11.16
02.12.16
Übungsblatt 7

30.11.16
09.12.16
Übungsblatt 8

07.12.16
16.12.16
Übungsblatt 9

14.12.16
22.12.16
Übungsblatt 10

21.12.16
13.01.17
Übungsblatt 11

11.01.17
20.01.17
Übungsblatt 12

18.01.17
27.01.17
Übungsblatt 13

25.01.17
03.02.17
Übungsblatt 14



     Pensum:


Ausgabe

PDF
13.02.17

Pensum



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.