empty
Lehre empty
empty
empty

Lehrveranstaltungen Wintersemester 2015/2016

 
Informatik III,   Platzeffiziente Algorithmen  




Informatik III (4 SWS) mit Übungen (2 SWS)
für den Bachelorstudiengang (ab 3. Semester)


Vorlesung: Mo. und Do. 15.45-17.15 Raum 1001T
Offener Inforaum: Mi 14.00-15.30 Raum 1055N (bis einschließlich 10.02.2016)
Übungen: Terminvergabe erfolgte über VV

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:

07.10.15

PDF
PDF 1/2 Größe

     Wochenzettel:

Ausgabe
Abgabe
PDF
Zusätzliches Material
15.10.15
15.10.15
Wochenzettel 1

15.10.15
22.10.15
Wochenzettel 2
W2_1.java
22.10.15
29.10.15
Wochenzettel 3

29.10.15
05.11.15
Wochenzettel 4

05.11.15
12.11.15
Wochenzettel 5

12.11.15
19.11.15
Wochenzettel 6

19.11.15
26.11.15
Wochenzettel 7

26.11.15
03.12.15
Wochenzettel 8

03.12.15
10.12.15
Wochenzettel 9

10.12.15
17.12.15
Wochenzettel 10

17.12.15
07.01.16
Wochenzettel 11

08.01.16
14.01.16
Wochenzettel 12
SortedBinTree.java, TestSortedBinTree.java
14.01.16
21.01.16
Wochenzettel 13

21.01.16
28.01.16
Wochenzettel 14



     Zusätzliches Material:
Übung   3.11
(Impl. von Karatsuba/Ofman) ko.zip
Übung   3.13
(exp. Vergleich von Sortierverfahren) compare.zip
Übung   4.9
(Test von bitonischen Sortierern) bitonic.zip
Übung 10.5
(Kantenklassifizierung durch Tiefensuche) dfs.zip


     Vorrechenpunkte (bis einschließlich vierzehntem Wochenzettel):
Platz
Punkte
Tutorium
1. 1068 Montag
2. 910 Mittwoch
3. 804 Freitag
4. 778 Donnerstag
(Bild konnte nicht angezeigt werden.)
     Informationen:


Ausgabe

PDF

16.11.15

Informationen zur Klausur


25.01.16

Informationen zum Notenabruf über das Internet


10.02.16

Klausurpensum

Die Klausureinsicht der Nachholklausur wird am Donnerstag, den 14.04.2016, von 17.30 bis 18.00 Uhr in 3076N stattfinden. Die Ergebnisse der Nachholklausur hängen vor dem Raum 3076N aus. Studenten, die sowohl fristgerecht in VV eine Geheimzahl abgefragt haben als auch auf Ihrer Klausur dem Notenabruf über das Internet zugestimmt haben, können Ihre Klausurnote auch in VV abfragen.

 




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


Vorlesung: Mi. 10.00-11.30 Raum 1054N
Übung: Di. 15.45-17.15 Raum 2013N

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.



     Skript:
22.12.15
Kapitel 1-9
PDF
PDF 1/2 Größe

     Wochenzettel:
Ausgabe
Abgabe
PDF
14.10.15
16.10.15
Wochenzettel 1

16.10.15
21.10.15
Wochenzettel 2

21.10.15
28.10.15
Wochenzettel 3

28.10.15
04.11.15
Wochenzettel 4

04.11.15
11.11.15
Wochenzettel 5

11.11.15
18.11.15
Wochenzettel 6

18.11.15
25.11.15
Wochenzettel 7

25.11.15
02.12.15
Wochenzettel 8

02.12.15
09.12.15
Wochenzettel 9

09.12.15
16.12.15
Wochenzettel 10

16.12.15
04.01.16
Wochenzettel 11

23.12.15
13.01.16
Wochenzettel 12

13.01.16
20.01.16
Wochenzettel 13

20.01.16
27.01.16
Wochenzettel 14



     Pensum:
Ausgabe

PDF
08.02.16

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.