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 des Blattes erfolgt normalerweise eine Wochen später vor Beginn der Vorlesung. Die genaue Abgabefrist steht auf der Webseite und dem Übungsblatt. Außerdem besteht dieses Semester die Möglichkeit die Lösungen online als PDF abzugeben. 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

Die Termine der Übungsgruppen sowie der Link zur Anmeldung werden hier rechtzeitig bekannt gegeben.

Hinweise zu den Übungsabgaben

• Die Abgabe der Übungen hat stets bis zu Beginn der Vorlesung zu erfolgen.
• 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.

Zu 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, Entwurfsmethoden wie Divide and Conquer, dynamische Programmierung und Greedy Algorithmen auf verschiedenste algorithmische Fragestellungen anzuwenden. Um die nichteffiziente Lösbarkeit algorithmischer Probleme einschätzen zu können, 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

Termine und Räume werden hier noch rechtzeitig bekannt gegeben.