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:Donnerstag 19.07.2018 13:00 - 14:00 Uhr, Audimax, HS9, HS3
Bitte erscheinen Sie spätestens 15 Minuten vor der Klausur.
Nachklausur: 04.10.2018, 10-11 Uhr (60 min). HS 3.
Klausurergebnisse
Klausurstatistiken
Die Klausurergebnisse sind final. Sollten Sie Ungereimtheiten feststellen, melden Sie sich bitte über die Kontaktaddresse.
Wiederholungsklausurergebnisse
Wiederholungsklausurstatistiken


Die Klausureinsicht findet zu folgenden Terminen statt. Bitte melden Sie sich bei der Kontaktaddresse mit Wunschtermin (Betreff/Subject) , Name und Matrikelnummer. Ohne Anmeldung wird die Klausur nicht bereit liegen!
Es ist sinnvoll, weniger besuchte Termine zu bevorzugen.
Die Anmeldungen werden nicht bestätigt. Der Ort wird am Tag vorher mit weiteren Informationen per Email genannt.
17.09.2018 11-12 Uhr (*Anmeldung geschlossen*)
18.09.2018 13-14 Uhr (*Anmeldung geschlossen*)
19.09.2018 13-14 Uhr (*Anmeldung geschlossen*)
20.09.2018 14-15 Uhr (*Anmeldung geschlossen*)
24.09.2018 11-12 Uhr (*Anmeldung geschlossen*)

Folgende Studierende sind aufgrund der Übungspunkte bei der Klausur eingeplant:
Übung ohne Wiederholende
Für die Zweit- oder Drittklausur angemeldete Studierende können die Zulassung im Almaweb prüfen. Sollten Sie Ungereimtheiten feststellen, prüfen Sie die Anmeldung im Almaweb und die Punkte. Sollten Sie immernoch Ungereihmtheiten feststellen, melden Sie sich bei der Kontaktaddresse.

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

27.06.2018

Wir werden bei der Hörsaalübung versuchen, eine Klausur zu simulieren. Es werden für je x Minuten klausurähnliche Fragen an die Wand projeziert, jeder beantwortet die für sich und nach der Veranstaltung werden die Lösungen zum Abgleichen veröffentlicht.

Es gibt keine Punkte und nichts zu gewinnen. Ziel ist es, allen einen Eindruck dafür zu vermitteln, was bei der Prüfung zu erwarten ist und durch eine ähnliche Übungssitutation "Prüfungsschock" vorzubeugen.

Das macht natürlich substantiell mehr Sinn, wenn man die Fragen auch (grob) beantworten kann, also hier nochmal ein Motivationsaufruf, sich vorher mit dem Stoff auseinanderzusetzen und nicht unvorbereitet zur Hörsaalübung zu erscheinen.

Und Schreibzeug nicht vergessen!

18.06.2018

Das B Seminar 13:15 im Raum SG 3-13 fällt am 20.06. aus bzw. wird mit dem Termin 11:15 SG 3-13 zusammengelegt. Es kann auch der Termin 13:15 von Manuela Geiss besucht werden.

13.06.2018

Bei der Korrektur der Aufgabe wurde versehentlich die Musterlösung hochgeladen. Deshalb wird Serie 5 nicht für die für die Klausurzulassung nötigen Punkte berücksichtigt. Damit dadurch kein Nachteil entsteht, wird die Klausurzulassung nach Fertigkorrektur von Serie 4 berechnet, wobei pauschal 25 Punkte für Serie 5 addiert werden.

Es macht also keinen Sinn, Kopien der Musterlösung für die Korrektur einzureichen!

Abgesehen davon wird die Serie wie üblich eingesammelt, korrigiert und im Seminar besprochen und zurückgegeben. Es ist stark empfehlenswert, die Aufgaben trotzdem wie üblich zu bearbeiten um sich angemessen auf die Klausur vorzubereiten, es geht ja wesentlich um den Lerneffekt und nicht (nur) darum, Punkte zu sammeln. Da dadurch die Punktegrenze effektiv herabgesetzt wurde, wird es kein Extraseminar geben, wie es letztes Semester für ADS 1 angeboten wurde.

05.06.2018

Der Übungstermin h (Mi,15.15-16.45) wird nicht länger angeboten. Die Übungsaufgaben sollten weiter in Mappe h abgegeben werden. Studierende können sich selbstständig auf andere Termine von Manuela Geiß verteilen oder nach Absprache auch andere Termine wahrnehmen.

22.05.2018

Das 2B Seminar 13:15 im Raum SG 3-13 fällt am 23.05. aus bzw. wird mit dem Termin 11:15 SG 3-13 zusammengelegt. Es kann auch der Termin 13:15 in der Härtelstraße 16-18, S 109 besucht werden.

16.05.2018

Bei Aufgabe 10 gab es einen Typo, der möglicherweise irreführend war. Die korrekte Knotenmenge V ist {1,2,3,4,5}. Das Aufgabenblatt wurde korrigiert.

15.05.2018

Es gab in den Folien 04 & 05 Inkonsistenzen darüber, ob Spannbäume nur für ungerichtete oder auch für gerichtete Graphen existieren. Folien 15 in VO 5 wurde entsprechend angepasst. Der von uns festgelegte Lehrkonsens ist jetzt, dass wir Spannbäume nur für ungerichtete Graphen definieren. Bei Übungsaufgabe 8d) werden beide Argumentationen als richtig bewertet.

30.04.2018

Die Gruppennummer ist diesmal ein Buchstabe und entspricht der Almaweb-Gruppen-ID.

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 DownloadThemaChangelog
(ohne Gewähr auf Vollständigkeit)
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 (LZ Algorithmen, BTW, MTF) , Entropie I Änderungen
0325.04.2018 Vorlesung Randomisierte Algorithmen, Fitness, Walks, Genetische Algorithmen Änderungen
0402.05.2018 Vorlesung Graphen, Spannbäume, Kruskal Änderungen
0509.05.2018 Vorlesung DAG, Topologische Sortierung, Transitive Hülle, Warshall, Graphtraversierung, Zusammenhangskomponenten, Tarjan, Zentralität Änderungen
0616.05.2018 Vorlesung Greedy, Matroide, Huffmann Codebaum (Greedy), Kruskal (Greedy)
0723.05.2018 Vorlesung Flüsse: Ford-Fulkerson, Push & Relabel, Matching Änderungen
0830.05.2018 Vorlesung
Page et.al: Pagerank
kürzeste Wege – Dijkstra, Bellmann-Ford, Shortest Path Betweenness, Pagerank Änderungen
0906.06.2018 Vorlesung Rucksackproblem, TSP, Greedy und Relaxation, Branch-and-Bound, Grundlagen Dynamische Programmierung Änderungen
1013.06.2018 Vorlesung Dynamische Programmierung (DP), Alignment, TSP, Parsing
1120.06.2018 Vorlesung Nature-Inspired Computation, Zelluläre Automaten
1227.06.2018 Vorlesung Metaheuristiken und Optimierung nach Vorbildern der Natur
1304.07.2018 Künstliche Neuronale Netze
1411.07.2018 Almaweb Hörsaalübung (Vorlesungszeit- und Ort)
1519.07.2018
13:00 - 14:30 Uhr
Klausur

Übungen

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)

Rot hinterlegte Termine werden nicht mehr angeboten.

>
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

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.06 - 03.07
B504.07 - 10.07

Informationen zur Übungsabgabe

Übungsaufgaben

Gesamtpunkte:
Die Punktzahl orientiert sich an den tatsächlich in Serie 5 erreichten Punkten. Die Klausurzulassung mit den pauschal addierten 25 Punkten findet sich ganz oben.
Tabelle Visualisierung

Die Punktelisten der aktuellen Serie werden mit dem aktuellen Stand der Korrekturen erzeugt. Deshalb ist es möglich, dass die Punktelisten der aktuellen Serie noch unvollständig sind. Sollten nach den B-Wochen noch Punkte fehlen, wenden Sie sich bitte an oben angegebene Kontaktaddresse.
SerieAusgabeAbgabeDownload
118.04.201825.04.2018 Aufgabenblatt Punkte
202.05.201809.05.2018 Aufgabenblatt Punkte
316.05.201823.05.2018 Aufgabenblatt Punkte
430.05.201806.06.2018 Aufgabenblatt Punkte
513.06.201820.06.2018 Aufgabenblatt

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