Algorithmen und Datenstrukturen 2 (WS 2020/2021)

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

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

• Infoslides (Fassung vom 02.11.2020)
• Fragestunde vom 12.11.2020 mit Kommentaren
• Fragestunde vom 19.11.2020 mit Kommentaren
• Fragestunde vom 26.11.2020 mit Kommentaren
• Fragestunde vom 03.12.2020 mit Kommentaren
• Fragestunde vom 17.12.2020 mit Kommentaren
• Fragestunde vom 14.01.2021 mit Kommentaren
• Fragestunde vom 21.01.2021 mit Kommentaren aktualisiert am 27.01. !
• Fragestunde vom 28.01.2021 mit Kommentaren
• Fragestunde vom 04.02.2021 mit Kommentaren
• Fragestunde vom 18.02.2021 mit Kommentaren

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
Video V13: Entscheid- und Berechenbarkeit, Church-Turing These, PSPACE, QBF
Video V14: PSPACE, Church-Turing These, Unentscheidbarkeit, Gödelnummer, Diagonalsprache, Reduktion
Video V15: Universelle Sprache, das (spezielle) Halteproblem, Satz von Rice
Video V16: Satz von Rice, Rekursive Aufzählbarkeit, Gödelsche Unvollständigkeitssatz
Video V17: Lokale Suche, Minimum Balanced Cut, Metropolis Algorithmus
Video V18: Minimum Balanced Cut, Metropolis Algorithmus, Simulated Annealing, Evolutionäre Algorithmen, Mutationsoperatoren, Crossover Operatoren
Video V19: Exakte Algorithmen, Backtracking, Branch Operator

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.

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.

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

Aufschriebe zu den Videos

Folien Übung 8
Folien Übung 9

Selbsttests

Selbststests sind ein zusätzliches Übungsangebot. Hier finden Sie Aufgaben und Lösungen mit denen Sie Ihren Wissensstand selbst überprüfen können.

Hinweis: Die Lösungen zu den den Selbsttests 2.0 ff befinden sich am Ende des Dokuments.

Anmerkung zu Selbsttest 2.5, Aufgabe 2.1: In der Vorlesung haben wir definiert, wann eine Turingmaschine eine Eingabe „akzeptiert“ und wann sie „hält“. Den Begriff des „Verwerfens“ haben wir zwar häufig benutzt, aber nicht exakt definiert. Meistens meinten wir damit, dass die Turingmaschine in einem nicht akzeptierenden Zustand hält. Diese Sichtweise wird auch in Definition 12.2 zur rekursiven Aufzählbarkeit verwendet. Die zur Aufgabe 2.1 im Selbsttest präsentierte Lösung verwendet eine andere Sichtweise, die man ebenfalls in der Literatur findet: Verwerfen bedeutet dort, dass die Turingmaschine für die gegebene Eingabe in einem nicht akzeptierenden Zustand hält oder dass sie nicht hält.

Links und weitere Unterlagen

• Vergleichsbasierte Sortieralgorithmen
• Distribution Counting und Radixsort
• Visualisierung aller elementaren Sortierverfahren der Vorlesung (außer Externspeicher und Sample Sort)
• Sound of Sorting - schwarz-weiß oder psychedelisch

Skript

Es stehen Skripte von Herrn Prof. Dr. G. Schnitger zu Theoretische Informatik 1 (GL1) zur Verfügung.

Hinweis: Mit der Zeit soll das Skript für Algo2 neu zusammengestellt werden. Bis dahin haben wir leider erstmal nur das Skript zu GL1.