Algorithmen und Datenstrukturen II (ADS II)

Modul-Nr.: 10-201-2001-1

Vorlesung:Mittwochs 09:15-10:45 Uhr, Audimax, Augustusplatz
Beginn:11.04.2018
Ende:11.07.2018
Klausur:19.07.2018 13:00 - 14:30 Uhr, Audimax, HS9, HS3, Augustusplatz

Vorlesung: 2 SWS = 30h Präsenzzeit + 55h Selbststudium
Übung: 1 SWS = 15h Präsenzzeit + 65h Selbststudium

Modulbeschreibung

Das Modul vermittelt die wichtigen Basisalgorithmen der Informatik. Das Grundwissen über effiziente Algorithmen und Datenstrukturen fördert die Problemlösungsfähigkeiten der Studierenden. Sie sollen in der Lage sein, einfache Probleme von der Auswahl der Verfahren bis zur effizienten Implementierung zu lösen. Für Lehramtsstudierende vermittelt das Modul somit Kenntnisse über grundlegende Problemstellungen der Informatik und dazugehörige Lösungsmöglichkeiten.

Kontakt: adshelp@informatik.uni-leipzig.de
(nutzen sie diese Addresse bei Fragen, schreiben sie nicht direkt an die Lehrenden)
Die Kontaktaddresse ist auschließlich für organisatorische Fragen gedacht. Bitte schicken Sie - auch aus Rücksicht gegenüber Studenten mit teils dringlichen organisatorischen Problemen und Fragen - keine inhaltichen Fragen zu den Übungsserien an diese Addresse.

News & Frequently asked Answers

25.04.2018

Die Zuordnung der ÜbungsleiterInnen (Mittwoch 13:15) im Almaweb ist nicht ganz korrekt. Die Zuordnung auf der Veranstaltungsseite gilt.

09.04.2018

Die Seminare starten am Mittwoch, den 02.05.2018.

Vorlesungen

Die Folien werden nach der entsprechenden Vorlesung zum Download angeboten.

Die Vorlesungsfolien können im Laufe des Semesters aktualisiert werden. Das Erstellungsdatum ist auf der Startfolie notiert. Zur Klausurvorbereitung sollten die aktuellsten Folien verwendet werden.

VorlesungDatumFolien zum DownloadThema
0111.04.2018 Vorlesung Organisation, Arten von Algorithmen, Übersicht, Kompression I (Lauflängenkodierung, Huffman, Überblick LZ-Algorithmen)
0218.04.2018 Vorlesung
Shannon: Entropy
Kompression II, Entropie I
0325.04.2018 Vorlesung Randomisierte Algorithmen
0402.05.2018 Graphen, Spannbäume
0509.05.2018 Graphtraversierung, Zusammenhangskomponenten, Zentralität
0616.05.2018 Greedy, Matroide, noch mal Huffmann, Kruskal
0723.05.2018 Flüsse: Ford-Fulkerson, Push & Relabel
0830.05.2018 Matching, kürzeste Wege – Dijkstra, Bellmann-Ford
0906.06.2018 Rucksackproblem, TSP, Greedy und Relaxation, Branch-and-Bound, Grundlagen Dynamische Programmierung
1013.06.2018 Dynamische Programmierung (DP), Alignment, Rucksack, TSP, Parsing
1120.06.2018 [tba]
1227.06.2018 [tba]
1304.07.2018 [tba]
1411.07.2018 Hörsaalübung
1519.07.2018
13:00 - 14:30 Uhr
Klausur

Übungen

Der Übungsbetrieb findet wöchentlich statt, wobei in den mit 'A' gekennzeichneten Wochen die Ausgabe der korrigierten Übungsblätter erfolgt.
Für die Teilnahme an den Übungen ist die Anmeldung zu einer der folgenden Übungsgruppen unbedingt erforderlich. Die Übungsanmeldung findet über Almaweb statt.

* = Ab 20.06 Härtelstraße 16-18 Raum 015.1 (Wird im Seminar erläutert)

GruppeUhrzeit TagRaumSeminarleiter
a09:15 - 10:45DiSG 3-13Sven Findeiß
b11:15 - 12:45DiSG 3-11Martin Reckziegel
c11:15 - 12:45DiSG 3-13Sven Findeiß
d11:15 - 12:45MiSG 3-13Thomas Efer
e11:15 - 12:45MiHärtelstraße 16-18, S 109*Manuela Geiß
f13:15 - 14:45MiSG 3-13Thomas Efer
g13:15 - 14:45MiHärtelstraße 16-18, S 109*Manuela Geiß
h15:15 - 16:45MiHärtelstraße 16-18, S 109*Manuela Geiß
i17:15 - 18:45MiHärtelstraße 16-18, S 109*Manuela Geiß
k13:15 - 14:45DoSG 3-11Martin Reckziegel
l13:15 - 14:45DoSG 3-13Christian Kahmann

(Vorläufige) Termine der Übungsgruppen:

SeminarZeitraum
A102.05 - 08.05
B109.05 - 15.05
A216.05 - 22.05
B223.05 - 29.05
A330.05 - 05.06
B306.06 - 12.06
A413.06 - 19.06
B420.06 - 26.06
A527.05 - 03.07
B604.07 - 10.07

Informationen zur Übungsabgabe

Übungsaufgaben

Gesamtpunkte:
SerieAusgabeAbgabeDownload
118.04.201825.04.2018 Aufgabenblatt 1
202.05.201809.05.2018
316.05.201823.05.2018
430.05.201806.06.2018
513.06.201820.06.2018

Literatur

Robert Sedgewick
Algorithmen in C
Addison-Wesley

Uwe Schöning
Algorithmen - kurz gefasst
Spektrum Akademischer Verlag

Thomas Ottmann, Peter Widmeyer
Algorithmen und Datenstrukturen
Spektrum Akademischer Verlag

Jon Kleinberg, Eva Tardos
Algorithm Design
Pearson