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.

Basiert auf Ihre Rückmeldungen haben wir an die Uni-Verwaltung den Klausurtermin 20.8.2020 gemeldet, und hoffen dass dieser Termin bald genehmigt wird. Die letzte Woche mit Vorlesung ist 13.-17.7. aber wir versuchen die letzte Vorlesung früh(er) online stellen. Wenn möglich, eine letzte Übung und eine Fragestunde findet noch am 23.7. statt.

Vorlesung

Für alle Studierende, auch für Bachelor PO 2011 besteht die Möglichkeit, die 5 CP Variante oder die 10 CP Variante zu belegen, jedoch entfällt die 9 CP Variante.

Die Vorlesungen und Übungen werden in elektronischer Form stattfinden.

  • Die Vorlesungen werden von StudiumDigitale aufgezeichnet und online gestellt (sie werden nicht “live gestreamt”).
  • Eine Fragerunde (30-60 Min.) zu der Vorlesung findet jeden Donnerstag um 13:00 Uhr in Form eines Video-Meetings statt. Bitte beachten Sie, dass manche kleine Fragen aus dem Stoff erst während der Fragerunde im Detail diskutiert werden. Die Fragerunde wird aufgezeichnet.
  • Anschließend, um 14:15, findet ebenfalls dort die Übung statt.
    Den Zugang zu diesen Meetings finden Sie unter Moodle.
  • Unsere nächsten online Treffen sind: am Mittwoch 10.6. die Fragerunde zur Vorlesung um 16:00 Uhr
  • Die Frage bezüglich ‘bestmögliche Wettbewerbsfaktor’ aus der Fragestunde gilt weiterhin (bestmöglich unter den vier angegebenen Möglichkeiten, den man für beliebigen Paging Algorithmus zeigen kann)
  • Bitte melden Sie sich für die Teilnahme an den Übungen per E-Mail bei Mahyar Behdju an. Geben Sie dabei Ihren (vollständigen) Namen und Ihre Matrikelnummer an. Geben Sie auch Ihre Studenten-E-Mail-Adresse an, falls Sie für die Anmeldung eine andere E-Mail-Adresse verwenden.
    Nur wer zu den Übungen angemeldet ist, wird seine/ihre Übungsblätter abgeben können. Mit Vorrechnen in den Übungen können Übungspunkte erworben werden, s. unten. Die Teilnahme an den Übungen wird sehr empfohlen! Eine Plusnote zur Klausur kann erworben werden (s. unten).
  • Derzeit gehen wir von einer traditionellen Klausur (Ende Juli/Anfang August), und Nachklausur (September) aus (Terminwahl s. oben), die Universitäten befinden sich in Diskussion mit der Landesregierung bzgl. der Möglichkeiten.
  • 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 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

Je nach Teilnehmerzahl findet eine mündliche Prüfung oder eine 180-minütige Klausur 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

Übungen

Effiziente Algorithmen 1

Effiziente Algorithmen 2

LaTeX

Nützliches

LaTeX-Code zu den Übungsblättern

Klausuren und Prüfungsmaterial

  • Altklausuren finden Sie hier.

Skript und zusätzliche Literatur

  • Skript der Vorlesung vom Sommersemester 2010 von Prof. Schnitger.