Effiziente Algorithmen (SS 2018)

Vorlesung

Dr. Annamaria Kovacs

Mittwoch 10:00 - 12:00 in SR 11 (R-M-S 11–15)
Donnerstag 12:00 - 14:00 in Magnus Hörsaal (R-M-S 11–15)

Übungsbetrieb

Mahyar Behdju

Gruppe 1 Donnerstag 14:00 - 16:00, SR 11 (R-M-S 11–15)
Gruppe 2 Donnerstag 16:00 - 18:00, SR 11 (R-M-S 11–15)

Übungsblätter werden i.d.R. wöchentlich mittwochs ausgegeben. Die Abgabe erfolgt in der darauffolgenden Woche vor der Vorlesung. Alternativ steht der Briefkasten vor Raum 312 für eine vorzeitige Abgabe zur Verfügung. Einreichungen per E-Mail werden nur als ordentlich-formatiertes PDF Dokument (z.B. mittels Latex) akzeptiert.

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. Eine Voraussetzung dafür ist das Vorrechnen mindestens einer Übungsaufgabe im Tutorium. Die Bonifikation wird erst angerechnet, wenn die Klausur selbstständig bestanden wurde.

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.

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”, Oxford Univ. Press, 2013
  • M. Mitzenmacher und E. Upfal, Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005. Online-Version über Bibliothek.
  • 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 Modulabschlussprüfung findet in Form einer Klausur statt.
Die Erstklausur findet am 30.07.2018 um 14:00 Uhr (s.t.) in H IV (Hörsaalgebäude) statt.
Die Zweitklausur findet am 14.09.2018 um 9:00 Uhr (s.t.) in H IV (Hörsaalgebäude) statt.

Materialien

Handschriftliches Skript - EA 1

Handschriftliches Skript - EA 2

Folien

Übungen Effiziente Algorithmen 1

Effiziente Algorithmen 2

Klausuren und Prüfungsmaterial

Skript und zusätzliche Literatur

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