Effiziente Algorithmen (SS 2024)

  • Teilnahmevoraussetzungen:

    Im Master: keine.

    Im Bachelor PO-2011: Modellierung (B-MOD) UND Datenstrukturen (B-DS).

    Im Bachelor PO-2019: 25 CP in den Basismodulen.

Sie können Material herunterladen mit user: ea24 und dem Doppelten davon als Passwort.

Aktuelles

Die Bonusnoten werden bis 22.7. hier online gestellt.

Die Klausur findet am 30.7. um 9:00 Uhr im Magnus Hörsaal statt.

Die Nachklausur findet am 24.9. statt.

Hier finden Sie die Klausurthemen und dazu gehört auch das Mathe Blatt.

In der Klausur sind keine Hilfsmittel zugelassen.

Für die Bonusnote soll in den Übungen mindestens einmal vorgerechnet werden (s. unten).

Bitte beachten Sie auch die Regelung über Plagiate (s. unten).

Bitte lernen Sie auf keinen Fall (nur) aus den Vortragsfolien!! Lesen Sie das Skript von Prof. Schnitger, das handschriftliche Skript und die entsprechenden Buchkapitel.

Vorlesung

Dr. Annamaria Kovacs

Mi. 12–14 Uhr, Magnus Hörsaal (R-M. Strasse 11-15.)

Do. 12–14 Uhr, Magnus Hörsaal (R-M. Strasse 11-15.)

Übungsbetrieb

Gruppe 1 Do. 14-16 Uhr SR11 Zeno Weil

Gruppe 2 Do. 16-18 Uhr SR11 Anton Micke (anton.micke(at)stud.uni-frankfurt.de)

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, und in der Übungsstunde mindestens einmal persönlich vorgerechnet 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.
  • C. Moore und S. Mertens, “The Nature of Computation”, Chapter 10. Oxford Univ. Press, 2013 Online-Version über Bibliothek
  • 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

Weitere Informationen folgen

Materialien

Skript und zusätzliche Literatur

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

Handschriftliches Skript

Effiziente Algorithmen 1

Stochastik

Woche 1. Ergänzung, BITTE LESEN

Woche 2. Bitte lesen Sie dazu die Kapitel (1.1 und) 1.2 aus dem Hromkovic Buch

Woche 3.

Woche 4.

Woche 5.

Woche 6.

Woche 7.

Woche 8.

Effiziente Algorithmen 2

Woche 9.

Woche 10.

Woche 11.

Woche 12.

Woche 13. Ergänzung, bitte lesen!!

Woche 14. Ergänzung

Folien

Effiziente Algorithmen 1

Einführung

Stochastik

Randomisierte Algorithmen I

Markoff Ketten

Online Algorithmen I

Effiziente Algorithmen 2

Amortisierte Analyse

Randomisierte Algorithmen II

Übungen

Effiziente Algorithmen 1

Übung 1 (LaTeX Datei) Abgabe: Samstag 27.4. 12:00 Uhr

Übung 2 (LaTeX Datei) Abgabe: Samstag 4.5. 12:00 Uhr

Übung 3 (LaTeX Datei) Abgabe: Samstag 11.5. 12:00 Uhr

Übung 4 (LaTeX Datei) Abgabe: Samstag 18.5. 12:00 Uhr

Übung 5 (LaTeX Datei) Abgabe: Samstag 25.5. 12:00 Uhr

Übung 6 (LaTeX Datei) Abgabe: Samstag 1.6. 12:00 Uhr

Übung 7 (LaTeX Datei) Abgabe: Samstag 8.6. 12:00 Uhr

Effiziente Algorithmen 2

Übung 8 (LaTeX Datei) Abgabe: Samstag 15.6. 12:00 Uhr

Übung 9 (LaTeX Datei) Abgabe: Samstag 22.6. 12:00 Uhr

Übung 10 (LaTeX Datei) Abgabe: Samstag 29.6. 12:00 Uhr

Übung 11 (LaTeX Datei) Abgabe: Samstag 06.7. 12:00 Uhr

Übung 12 (LaTeX Datei) Abgabe: Samstag 13.7. 12:00 Uhr

LaTeX

Nützliches

Klausuren und Prüfungsmaterial

Den Zugangslink zum virtuellen Ingo-Wegener-Lernzentrum finden Sie auf OLAT.