Vorlesung
Prof. Dr. Ulrich Meyer
Dienstag 08:00 - 10:00
Donnerstag 08:00 - 10:00
Hörsaal H V (Jügelhaus/Hörsaalgebäude)
Alle anderen Termine werden rechtzeitig hier angekündigt.
LSF
Übungsbetrieb
Alex Schickedanz
Hung Tran
Fragen rund um die Vorlesung bitte an gl118@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.
Die Übungsgruppen beginnen ab Dienstag, den 23.10.2018, mit Blatt 0.
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”).
Der Übungsbetrieb ist im wöchentlichen Rhythmus organisiert. Die Abgabe des Blattes erfolgt am Dienstag in der Folgewoche vor Beginn der Vorlesung. Für eine frühere Abgabe benutzen Sie bitte den Briefkasten neben Raum 312.
Termine der Übungsgruppen
| Gruppe 01 | Mo | 10 - 12 | NM 123 |
| Gruppe 02 | Mo | 12 - 14 | NM 123 |
| Gruppe 03 | Mo | 14 - 16 | NM 123 |
| Gruppe 04 | Di | 10 - 12 | NM 103 |
| Gruppe 05 | Di | 10 - 12 | NM 126 |
| Gruppe 06 | Di | 10 - 12 | NM 130 |
| Gruppe 07 | Di | 14 - 16 | NM 126 |
| Gruppe 08 | Mi | 10 - 12 | NM 103 |
| Gruppe 09 | Mi | 12 - 14 | NM 126 |
| Gruppe 10 | Do | 10 - 12 | NM 103 |
| Gruppe 11 | Do | 10 - 12 | NM 130 |
| Gruppe 12 | Do | 12 - 14 | NM 130 |
| Gruppe 13 | Do | 14 - 16 | NM 130 |
| Gruppe 14 | Fr | 12 - 14 | NM 130 |
| Gruppe 15 | Fr | 14 - 16 | NM 130 |
Aus gegebenem Anlass sehen wir uns verpflichtet auf folgendes hinzuweisen:
- Ein Wechsel der zugeteilten Übungsgruppe für die Abgabe ist NICHT möglich!
- Wenn Abgaben mit der falschen Gruppennummer abgegeben werden, wird die Abgabe ab Blatt 2 mit 0 Punkten gewertet.
Hinweise zu den Übungsabgaben
- Die Abgabe der Übungen hat stets bis zu Beginn der Vorlesung zu erfolgen.
- Jedes(!) Blatt ist mit dem vollständigen Namen, Matrikelnummer und Gruppennummer zu versehen.
- Bei Abgabe im Briefkasten muss auch die Veranstaltung auf das Blatt geschrieben werden.
- Wer eine falsche Gruppennummer auf dem Blatt angibt und deshalb nicht bei seinem Tutor landet, bekommt auf die Abgabe keine Punkte.
- Eine Abgabe via E-Mail ist nur in Ausnahmefällen (z.B. Krankheit) und nur als PDF Datei möglich.
- Nur an gl118@ae.cs.uni-frankfurt.de. Nicht an Prof. Meyer oder die Mitarbeiter.
- Bitte keine Fotos! Verwenden Sie am besten LaTeX oder zur Not ein anderes Textsatzprogramm.
- Nur im äußersten Notfall werden Fotos akzeptiert. Achten Sie darauf: keine dunklen/schwarzen Ränder oder Hintergrund, richtig gedreht, gut lesbar und als eine PDF Datei.
- Abgaben, die nicht als PDF eingereicht werden, werden ohne Antwort ignoriert.
- Die Tutoren müssen grundsätzlich keine Abgaben per Mail akzeptieren.
- Die Tutoren sind auch nicht verpflichtet schwer lesbare Abgaben zu korrigieren.
- Wenn eine Aufgabe nicht lesbar ist, dann gibt es auf die Aufgabe keine Punkte.
- Wir stellen eine LaTeX Vorlage zur Verfügung.
- Abgaben ohne vollständigen Namen, Matrikelnummer und Gruppennummer werden nicht korrigiert.
- Mehrseitige Übungsabgaben sind zu tackern.
- 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.
- 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.
- Sie bekommen Punkte auf Ihre abgegeben Lösungen. Um Übertragungsfehler zu vermeiden finden Sie auf der ersten Seite Ihrer Abgabe eine Zusammenfassung der erreichten Punkte. Bitte prüfen Sie noch im Tutorium, ob die Punkte neben der Aufgabe den Punkten in der Zusammenfassung entspricht und sprechen Sie Ihren Tutor an, sollte einmal etwas übersehen worden sein. Wir können fehlende Punkte nicht mehr nachtragen, wenn Sie ihre Abgabe bereits zurückerhalten haben.
Die Themen “Dynamische Programmierung”, “Lineare Programmierung” und “Entscheidbarkeit und Berechenbarkeit” sind nicht Bestandteil des Moduls TIWI.
Auf Übungszetteln wird dies entsprechend berücksichtigt werden, so dass Aufgaben zu diesen Themengebieten entfallen.
Inhalt
Die Vorlesung behandelt fundamentale Algorithmen und allgemeine Methoden für den Entwurf und die Analyse von Algorithmen sowie die NP-Vollständigkeit. Algorithmen für Ordnungsprobleme wie Sortieren und Mischen wie auch Algorithmen für Graphprobleme wie die Berechnung kürzester Wege und minimaler Spannbäume 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. Dazu werden Branch & Bound und Backtracking Verfahren wie auch verschiedene Varianten der lokalen Suche für den Entwurf vorgestellt.
Lernziele
Die Kenntnis fundamentaler Algorithmen sowie die Fähigkeit, den Prozess des Entwurfs und der Analyse von Algorithmen eigenständig durchführen zu können.
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: 26.02.2019, 09:00 - 12:00, Hörsaal V (römisch 5) und Hörsaal VI (römisch 6)
Nachklausur: 02.04.2019, 09:00 - 12:00
Die Klausur ist bestanden, wenn mindestens 50% aller in ihrem Klausurteil erreichbaren Punkte erzielt wurden.
Zur Benotung werden neben dem Klausurergebnis Bonuspunkte aus den Übungen mit einem Maximalgewicht von 10% eingehen.
Materialien
Evaluierungsmöglichkeit
- Am Di. 15.01. zwischen 8 und 10 Uhr hier.
Folien
Klickerfolien und weitere Materialien
Links zu in der Vorlesung gezeigten Animationen
Videoaufzeichnungen
Die Videoaufzeichnungen der Vorlesung stehen hier zur Verfügung.
Hinweis: Die Videos werden von studium Digitale gehostet.
Übungsblätter
- Wenn keine Übungsblätter besprochen werden, finden in den Tutorien Wiederholungsstunden statt. Änderungen an den Ausgabeterminen vorbehalten.
- Übungsblatt 0, Ausgabe: 16.10.2018, Abgabe: keine
- Übungsblatt 1, Ausgabe: 23.10.2018, Abgabe: 30.10.2018 8:10
Hinweis zu Aufgabe 1.4: Ein Kellner kann seinen Tisch nicht mehrmals abräumen.
- Übungsblatt 2, Ausgabe: 30.10.2018, Abgabe: 06.11.2018 8:10
Die Formulierung der Aufgabe 2.2a wurde verbessert.
- Übungsblatt 3, Ausgabe: 06.11.2018, Abgabe: 13.11.2018 8:10
Bei Aufgabe 3.4b ist nicht nach trivialen Lösungen gefragt.
- Übungsblatt 4, Ausgabe: 13.11.2018, Abgabe: 20.11.2018 8:10
- Übungsblatt 5, Ausgabe: 27.11.2018, Abgabe: 04.12.2018 8:10
- Übungsblatt 6, Ausgabe: 04.12.2018, Abgabe: 11.12.2018 8:10
- Übungsblatt 7, Ausgabe: 11.12.2018, Abgabe: 18.12.2018 8:10
Hinweis: Das Blatt hat insgesamt 112 Punkte und ist auch etwas voller geraten. Das nächste Blatt wird weniger voll sein.
- Übungsblatt 8, Ausgabe: 18.01.2018, Abgabe:15.01.2019 8:10
Hinweis: Natürlich will die Oberelfin Transportelfen und keine anderen Oberelfen los schicken.
- Übungsblatt 9, Ausgabe: 15.01.2019, Abgabe: 22.01.2019 8:10
Hinweis: Die Aufgabenstellung von Aufgabe 9.3 wurde minimal ergänzt, um die Collatz-Vermutung verständlicher zu machen.
- Übungsblatt 10, Ausgabe: 22.01.2019, Abgabe: 05.02.2019 8:10
Dies ist das letzte Übungsblatt.
Weitere Materialien
- [Es steht das Skript von Herrn Prof. Dr. G. Schnitger zum download bereit, an dem sich diese Veranstaltung orientiert.
