Effiziente Algorithmen (SS 2020)
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 studentische E-Mail-Adresse (…@stud.uni-frankfurt.de),
wenn Sie uns E-Mails schreiben. Wir haben immer wieder Probleme, dass unsere Antworten in Spamfiltern landen.
Zweitklausur
Erstklausur
Vorlesung
Die Vorlesungen und Übungen werden in elektronischer Form stattfinden.
- 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 Mahyar Behdju.
Teilnahmevoraussetzungen:
Im Master: keine.
Im Bachelor PO-2011: Modellierung (B-MOD) UND Datenstrukturen (B-DS).
Im Bachelor PO-2019: 25 CP in den Basismodulen.
Den Zugangslink zum virtuellen Ingo-Wegener-Lernzentrum finden Sie auf OLAT.
Dr. Annamaria Kovacs
Mittwoch 12:00 - 14:00 in SR 11 (R-M-S 11–15)
Donnerstag 12:00 - 14:00 in SR 11 (R-M-S 11–15)
Übungsbetrieb
Mahyar Behdju, Elias Pitschmann, Conrad Schecker
Donnerstag 14:00 - 16:00, SR 307 (R-M-S 11–15)
Die Teilnahme am Übungsbetrieb wird dringend empfohlen, ist jedoch nicht verpflichtend.
Durch die Aufgaben wird Bekanntes vertieft und weiterführende Inhalte vermittelt.
Des Weiteren kann durch das Lösen der Aufgaben eine Bonifikation von bis zu einem Notenschritt für die Prüfung erworben werden.
Die Bonifikation wird erst angerechnet, wenn die Klausur selbstständig bestanden wurde.
Es besteht die Möglichkeit, durch Vorrechnen in den Tutorien Bonuspunkte zu erwerben, welche zu den erworbenen Übungspunkten hinzuaddiert werden.
Dabei gelten die folgenden Regeln:
- Pro Übungsblatt wird der Bonus höchstens einmal pro Person vergeben.
- Beim ersten Vorrechnen gibt es 5 Bonuspunkte.
- Beim zweiten Vorrechnen gibt es 4 Bonuspunkte.
- Beim dritten Vorrechnen gibt es 3 Bonuspunkte.
- Beim vierten Vorrechnen gibt es 2 Bonuspunkte.
- Jedes weitere Vorrechnen gibt 1 Bonuspunkt.
Die Bearbeitung der Aufgaben in Gruppen wird begrüßt, jedoch muss von jedem Teilnehmer eine individuelle Ausarbeitung eingereicht werden.
Blätter, auf denen plagiierte oder kopierte Lösungen gefunden werden, werden für jeden Betroffenen nicht bewertet.
Im Wiederholungsfall kann es zur Aberkennung sämtlicher Bonifikation kommen.
Hinweise zu den Übungsabgaben
- Übungsblätter werden in der Regel wöchentlich freitags ausgegeben.
- Die Abgabefrist für ein Blatt endet am Samstag in der darauffolgenden Woche.
- Da es eine Online-Abgabe gibt, ist eine Abgabe per E-Mail dieses Semester nicht vorgesehen.
Zu Online-Abgabe:
- Die Abgabe wird Ihnen automatisch zugeordnet; bitte vermerken Sie trotzdem Ihren Namen und Ihre Matrikelnummer darauf.
- 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.
Inhalt
Entwurf und Analyse effizienter sequentieller Algorithmen und Datenstrukturen:
- Entwurfsmethoden
- Random Walks
- Pseudo-Random Generatoren
- Online-Algorithmen
- Randomisierte Algorithmen
- Selbst-organisierende Datenstrukturen
Literatur
- J. Hromkovic, “Design and Analysis of Randomized Algorithms”, Springer, 2005 Online-Version über Bibliothek.
- C. Moore und S. Mertens, “The Nature of Computation”, Chapter 10. Oxford Univ. Press, 2013
- M. Mitzenmacher und E. Upfal, Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.
- R. Motwani und P. Raghavan, “Randomized Algorithms”, Cambridge University Press, 1995 Online-Version über Bibliothek.
- A. Borodin und R. El-Yaniv, “Online Computation and Competitive Analysis”, Cambridge University Press, 1995
Leistungsnachweis
Die Erstklausur findet am Donnerstag, den 20.08.2020, um 13:30 Uhr am Campus Westend im Hörsaalzentrum HZ 1 statt.
Die Zweitklausur findet am Dienstag, den 20.10.2020, statt.
Materialien
Videoaufzeichnungen
- Videos zur Vorlesung stehen hier zur Verfügung.
Hinweis: Die Videos werden von Studiumdigitale gehostet.
Handschriftliches Skript
Effiziente Algorithmen 1
Effiziente Algorithmen 2
Folien
Randomisierte Algorithmen I
Übungen
Effiziente Algorithmen 1
Effiziente Algorithmen 2
LaTeX
Nützliches
LaTeX-Code zu den Übungsblättern
Klausuren und Prüfungsmaterial
Skript und zusätzliche Literatur
- Skript der Vorlesung vom Sommersemester 2010 von Prof. Schnitger.
