Algorithmen und Datenstrukturen 2 (WS 2020/2021)

Die Vorlesungen und Übungen werden in elektronischer Form stattfinden.

Große Teile der Vorlesung werden dieses Semester auf Videos und Dokumente ausgelagert.
Es wird unregelmäßig Online-Fragestunden über Zoom geben. Diese werden nicht aufgezeichnet.
Für manche Inhalte dieser Seite benötigen Sie Zugangsdaten. Diese erhalten Sie über Moodle. Sollten Sie noch keinen HRZ-Account haben, melden Sie sich bitte bei bei Alex Schickedanz.

Dieses Semester findet die Kommunikation mehr denn je über diese Webseite und E-Mails statt. Bitte schauen Sie regelmäßig hier vorbei und verwenden Sie Ihre Uni-Mailadresse (@stud.uni-frankfurt.de), wenn Sie uns schreiben. Wir haben immer wieder Probleme, dass unsere Antworten in Spamfiltern landen. Verwenden Sie nach Möglichkeit auch keine Weiterleitung auf eine andere Mailadresse.

Prüdungsanmeldung

Denken Sie an die Anmeldung zur Klausur am 23.2.

Sollten Sie bei der Anmeldung einen “Voraussetzungsfehler” angezeigt bekommen, verwenden Sie bitte das Formular “Anmeldung schriftliche Modulabschlussprüfung” und schicken Sie dieses digital ausgefüllt oder als Scan an das Prüfungsamt Informatik.

Am 21.1. findet die Evaluation der Vorlesung statt. Den Link und weitere Informationen finden Sie im Moodle.

Die Übungsgruppen wurden zugeteilt. Inzwischen sollten Sie an Ihre Uni-Mailadresse (@stud.uni-frankfurt.de) eine E-Mail mit einem Abgabelink bekommen haben, über den Sie das ganze Semester die Übungen abgeben und die Korrektur runterladen können. Schauen Sie auch im Spam-Ordner nach. Melden Sie sich frühzeitig, sollten Sie keinen Link bekommen haben, da wir nicht garantieren können kurz vor der Abgabe neue Links verschicken zu können.

Die Übungen beginnen ab Donnerstag dem 12.11. mit der Besprechung von Blatt 0. Nutzen Sie die ersten Termine auch um evtl. vorhandene technische Probleme mit den Onlinediensten in den den Griff zu bekommen.

Die Links zu den Tutorien finden Sie im Moodle.

Am Do. 14.01. um 8:30 findet über Zoom die nächste Fragestunde statt.
Die Veranstaltung wird nicht aufgezeichnet, allerdings werden die Folien hier auf der Webseite veröffentlicht.

Wenn Sie Fragen haben die in der Fragestunde besprochen werden sollen, schicken Sie diese bitte bis 24 Stunden vorher an algo220-fragestunde@ae.cs.uni-frankfurt.de

Den Link und die Zugangsdaten für das Zoom-Meeting finden Sie im Moodle.

Übungsblatt 6 ist online.
Vorlesungsvideo V12 ist jetzt online.
Das Lösungsvideo zu Blatt 5 ist online.
Neue Selbsttests: 2.2 und 2.3

Vorlesung

Prof. Dr. Ulrich Meyer

Dienstag 08:00 - 10:00 Donnerstag 08:00 - 10:00

Alle anderen Termine werden rechtzeitig hier angekündigt.

LSF

Übungsbetrieb

Elizaveta Kovalevskaya
Alex Schickedanz

Fragen rund um die Vorlesung bitte an algo220@ae.cs.uni-frankfurt.de.

Hinweis: In der Vergangenheit kam es immer wieder zu Zustellungsproblemen bei externen E-Mail Providern. Wenn Sie eine Antwort auf Ihre E-Mail erwarten, verwenden Sie bitte Ihre Uni-Mailadresse.

Fragen zu Vorlesungsinhalten oder Übungsaufgaben stellen Sie bitte in den Tutorien oder beim Lernzentrum.

Das Lösen von Übungsaufgaben geschieht auf freiwilliger Basis. Dennoch ist die Teilnahme am Übungsbetrieb unbedingt zu empfehlen. Es werden weiterführende Inhalte vermittelt und es gibt die Möglichkeit Bonuspunkte zu sammeln. Eine Beobachtung unsererseits ist: Je höher die Bonuspunkte, desto höher die Wahrscheinlichkeit, eine gute Note zu erhalten. Weiterhin gilt aber, dass leider in der Vergangenheit immer wieder Betrugsversuche bei Übungsabgaben vorkamen. Deshalb bitten wir Sie darum, von solchen Täuschungsversuchen Abstand zu nehmen. Es lohnt sich nicht! Eine Zuwiderhandlung kann dazu führen, dass wir Ihnen alle Bonuspunkte aberkennen (genaue Regelung: siehe “Hinweise zu den Übungsabgaben”).

Es gibt wöchentlich Übungsblätter. Die Abgabe der Lösungen erfolgt dieses Semester ausschließlich über unseren Online-Briefkasten. Den genauen Ablauf erfahren Sie rechtzeitig hier auf der Webseite.

Sie können durch die Teilnahme an den Übungen bis zu 10% Bonuspunkte in der Klausur erhalten. Diese werden auf die Note einer bestanden Klausur angerechnet.

Termine der Übungsgruppen

Gruppe 01	Mo	10 - 12
Gruppe 02	Mo	12 - 14
Gruppe 03	Mo	16 - 18
Gruppe 04	Di	10 - 12
Gruppe 05	Di	16 - 18
Gruppe 06	Mi	10 - 12
Gruppe 07	Mi	14 - 16
Gruppe 08	Mi	16 - 18
Gruppe 09	Do	10 - 12
Gruppe 10	Do	10 - 12
Gruppe 11	Do	14 - 16
Gruppe 12	Fr	10 - 12
Gruppe 13	Fr	14 - 16

Aus gegebenem Anlass sehen wir uns verpflichtet auf folgendes hinzuweisen:

Ein Wechsel der zugeteilten Übungsgruppe für die Abgabe ist NICHT möglich!

Hinweise zu den Übungsabgaben

Wie immer gilt: Was unsere Tutoren nicht lesen können, müssen sie auch nicht korrigieren und gibt dementsprechend auch keine Punkte.
Da es eine online Abgabe gibt, ist eine Abgabe per E-Mail dieses Semester nicht vorgesehen.
Wir stellen eine LaTeX Vorlage zur Verfügung.

Onlineabgabe:

Die Abgabe wird Ihnen automatisch zugeordnet. Es schadet jedoch nicht Matrikelnummer und Namen darauf zu vermerken.
Laden Sie Ihre Lösung nicht in der letzten Minute hoch. Wir können den reibungslosen Ablauf nicht garantieren, wenn alle 5 Minuten vor Schluss abgeben wollen.
Wir nehmen Lösungen nur als eine PDF-Datei entgegen. Bitte stellen Sie sich darauf ein und testen Sie vorher.
- Am besten ist es, wenn Sie gleich LaTeX verwenden. Das ist gut lesbar und erzeugt kleine Dateien. Wir bieten auch eine LaTeX Vorlage an.
- Zur Not können Sie Scans oder Bilder zu einer PDF zusammenfügen. Wenn Sie dafür ein Smartphone verwenden, nutzen Sie eine Scannerapp Ihres Vertrauens. Damit lassen sich Ränder wegschneiden und Seiten gerade ziehen.

Plagiate und Betrugsversuche:

Wenn festgestellt wird, dass eine Aufgabe abgeschrieben wurde, dann…
- … gibt es beim ersten Mal für alle Beteiligten 0 Punkte auf das Blatt.
- … wird beim zweiten Mal allen Beteiligten die Bonifikation sowohl für die Erst- als auch die Zweitklausur aberkannt. Außerdem werden keine weiteren Abgaben der Beteiligten mehr korrigiert.
Wichtig: Wer bereits in einer unseren anderen Veranstaltung erwischt wurde, bekommt keine Verwarnung. In dem Fall wird die Bonifikation sofort aberkannt. Leider sehen wir uns zu diesem Schritt gezwungen nachdem die Zahlen der abgeschriebenen Lösungen in den letzten Semestern massiv angestiegen sind.
Sie dürfen in Gruppen über die Aufgaben diskutieren und zusammen Lösungswege erarbeiten (es ist sogar empfohlen). Jedoch muss jeder Student in der Abgabe die Lösung selbst schreiben und somit erkennbar machen, dass der Lösungsweg verstanden wurde. Im Zweifelsfall kann der Tutor verlangen, dass Sie eine Lösung vorrechnen. Sind Sie im Tutorium gar nicht anwesend, so kann der Tutor die Punkte vom Übungsblatt aberkennen.

Hinweise zu den Korrekturen

Sie sollen anhand der Übungsaufgaben den Stoff der Vorlesung besser verstehen. Ein wichtiger Teil davon sind die Kommentare der Tutoren auf den korrigierten Abgaben. Hier finden Sie die Gründe, wenn nicht die vollen Übungspunkte erreicht wurden.

GL-1 aus der alten Prüfungsordnung

Das Modul GL-1 wird nicht mehr angeboten. Studenten die noch GL-1 benötigen müssen Algo1b und Algo2 belegen.

Inhalte

Die Vorlesung behandelt fundamentale Algorithmen, und allgemeine Methoden für den Entwurf und die Analyse von Algorithmen, sowie die NP-Vollständigkeit und die Grenzen der Berechenbarkeit. Algorithmen für Ordnungsprobleme wie Sortieren und Mischen werden beschrieben und analysiert. Algorithmentypen bzw. Entwurfsmethoden wie Greedy-Algorithmen, Teile-und-Beherrsche und dynamisches Programmieren werden eingeführt und angewandt. Das Konzept der NP-Vollständigkeit erlaubt die Untersuchung der algorithmischen Komplexität von Problemen. Die NP-Vollständigkeit des Erfüllbarkeitsproblems und weiterer Berechnungsprobleme wird gezeigt. Abschließend wird ein Ausblick auf die Behandlung komplexer algorithmischer Probleme unter Betonung der Approximationsalgorithmen gegeben. Der Begriff der Berechenbarkeit wird eingeführt und ausführlich diskutiert. Es werden Beispiele für nicht entscheidbare Sprachen angeführt, und mit dem Satz von Rice wird nachgewiesen, dass fast alle interessanten Fragen über das Verhalten eines Programms unentscheidbar sind.

Lernergebnisse / Kompetenzziele

Wissen und Verstehen: Die Kenntnis fundamentaler Algorithmen; die Fähigkeit, den Prozess des Entwurfs und der Analyse von Algorithmen eigenständig durchführen zu können; sowie das Wissen um die Grenzen der (effizienten) Berechenbarkeit.

Können: Neben der Wissensaneignung lernen die Studierenden, die nichteffiziente Lösbarkeit algorithmischer Probleme einzuschätzen. Dafür werden die Konzepte der NP-Vollständigkeit und der Entscheidbarkeit eingeübt (instrumentale Kompetenz). Die Kraft, aber auch die prinzipiellen Grenzen algorithmischer Lösungsansätze werden ausgelotet: ähnliche Fragestellungen im Berufsleben werden dadurch jenseits kurzlebiger Trends beantwortbar. Kommunikative Kompetenzen werden durch Arbeiten in Gruppenübungen und die dortige Vorstellung und Diskussion von Übungsaufgaben erworben.

Literatur

J. Kleinberg und E. Tardos, Algorithm Design, Pearson Education Limited 2013, ISBN 1292023945
T. H. Cormen, C. E. Leiserson, R. L. Rivest und C. Stein, Introduction to Algorithms, Third Edition, The Mit Press 2009, ISBN 0262533057 (4. deutsche Auflage: 3486748610)

Klausur

Hauptklausur: 23.02.2021, 09:00 - 12:00
Nachklausur: 30.03.2021, 14:00 - 17:00

Die Anmeldung über QIS ist ab sofort möglich.

Details zum genauen Ablauf werden rechtzeitig bekannt gegeben.

Die Klausur ist bestanden, wenn mindestens 50% aller erreichbaren Punkte erzielt wurden. Zur Benotung werden neben dem Klausurergebnis Bonuspunkte aus den Übungen mit einem Maximalgewicht von 10% eingehen.

Freiversuchsregelung

Hier finden Sie die aktuellen Freiversuchsregelungen der Informatik.

Auch für das Wintersemester 2020/21 gilt eine universitätsweite Freiversuchsregelung für nichtbestandene Prüfungsleistungen (Abschlussarbeiten ausgenommen). Diese Regelung gilt nur einmalig pro Prüfung und nur für Prüfungsleistungen, für welche nicht bereits im Sommersemester 2020 ein Freiversuch in Anspruch genommen wurde.

Dazu wird klargestellt: Es gibt nur einen “Corona-Freiversuch” pro Modul inkl. äquivalenten Modulen.

D.h. für Algo2: Wenn Ihnen bereits ein universitärer Freiversuch für die GL-1 Nachklausur im Sommersemester 2020 gegeben wurde, können Sie keinen Freiversuch mehr für die ALGO-2-Klausuren erhalten.

Materialien

Folien

Videoaufzeichnungen

Videos zur Vorlesung stehen hier zur Verfügung.

Hinweis: Das erste Video wird am 5.11. veröffentlicht.

Es handelt sich dabei um Aufzeichnungen der Vorlesungen Theoretische Informatik 1 aus den vergangen Semestern. Teilweise werden die Videos neu geschnitten oder durch neue Videos ergänzt um den Inhalt der aktuellen Vorlesung gerecht zu werden.

Hinweis: Die Videos werden von studiumdigitale gehostet. Sie benötigen dafür evtl. einen HRZ-Account.

Folien zu den Videos

Video V01: Einführung, Bubble- und Selection Sort
Video V02: Selection-, Insertion-, Heap- und Quicksort
Video V03: Laufzeit Quicksort und Mergesort
Video V04: Joulesort-Challenge, Externspeichersortieren und vergleichsorientierte Sortierverfahren
Video V05: Distribution Counting, Radixsort, Sample Sort, MPI, Parralleles Sortieren
Video V06.1: Sample Sort, Graphen und Datenstrukturen
Video V06.2: NP-Vollständigkeit und schwierige Probleme
Video V07: Turingmaschinen, Klasse P, Klasse NP und polynomielle Reduktion
Video V08: polynomielle Reduktion, NP-Vollständigkeit, KNF-SAT, 3-SAT, 2-SAT und Clique
Video V09: Independent Set-, Set Cover-, Vertex Cover ist NP-vollständig, Schwierige Wegeprobleme in Graphen
Video V10: Satz von Cook, Optimierungsprobleme, Approximationsprobleme und Last-Verteilung
Video V11: Last-Verteilung, On-line und Off-line Heuristik, Rucksackproblem
Video V12: ungewichtetes Vertex Cover Problem, Matching Heuristik, gewichtetes Vertex Cover Problem

Altklausuren

Altklausuren finden Sie hier.

Übungsblätter

Die Bearbeitung der Übungsblätter in Gruppen ist erlaubt, jedoch müssen Sie Ihre Lösungen eigenständig aufschreiben.

Die Übungsblätter werden so entworfen, dass ihre Bearbeitung mit den Kenntnissen aus der Vorlesung und aus vorangegangenen Übungsblättern möglich ist. Sollten Sie in Ihrer Lösung dennoch andere Quellen (Bücher, Skripte, Internetforen, soziale Netzwerke, Lösungen anderer Studenten, etc.) verwenden, so müssen Sie die entsprechenden Stellen als direkte oder indirekte Zitate kennzeichnen. Orientieren Sie sich hierfür einfach an den Hinweisen zum Zitieren in schriftlichen Arbeiten am Institut für Informatik. Darüber hinaus muss Ihre persönliche Leistung stets deutlich erkennbar sein. Bei direkten Zitaten oder fast unverändert übernommenen Passagen liegt keine persönliche Leistung vor.

Beachten Sie auch die Hinweise zu Plagiaten und Betrugsversuchen.

Download	Ausgabe	Abgabe
Übung 0	03.11.	keine
Übung 1	17.11.	24.11. 08:00 (morgens)
Übung 2	24.11.	01.12. 08:00 (morgens)
Übung 3	01.12.	08.12. 08:00 (morgens)
Übung 4	08.12.	15.12. 08:00 (morgens)
Übung 5	15.12.	12.01. 08:00 (morgens)
Übung 6	12.01.	19.01. 08:00 (morgens)

Update: In Aufgabe 1.4 wurde der Begriff “Wartezeit” klargestellt.

Lösungsvideos

Dieses Semester bieten wir Videos an, in denen die Übungsaufgaben vorgerechnet werden. Die gezeigten Lösungen sind nicht als Musterlösung zu verstehen, sondern als einer von evtl. mehreren Lösungswegen.

Die Videos finden Sie hier.