Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Algorithmen und Wahrscheinlichkeit

Frühjahrssemester 2017, ETH Zürich

Dozenten: Prof. Angelika Steger
Prof. Emo Welzl
Vorlesung: Dienstag, 13:15 - 15:00 Uhr, HG F1 und Donnerstag, 10:15 - 12:00 Uhr, HG E7
Übungen: Donnerstag, 15:15 - 17:00 Uhr (die Anmeldung erfolgt während der ersten Vorlesungswoche auf echo.ethz.ch (inzwischen geschlossen))

Weitere Informationen zur Vorlesung und verbindliche Informationen zur Prüfung finden Sie im Vorlesungsverzeichnis. Für Fragen und Kommentare haben wir ein Moodle-Forum eingerichtet.

Letzte Änderungen/News:

  • 08.08.: Testprüfung (Computeraufgabe) online gestellt in Abschnitt "Programmieraufgaben".
  • 31.07.: Prüfungsinformationen aktualisiert.
  • 25.07.: allgemeine Prüfungsinformationen hinzugefügt.
  • 24.07.: Fehler im Skript korrigiert: In Satz 1.48 benötigt man einen bipartiten Graphen.
  • 24.07.: Das Skript ist vollständig, mit Ausnahme des Stoffes der letzten anderthalb Vorlesungen. Dieser Stoff (Testen von geometrischen Prädikaten, konvexe Hülle, numerische Aspekte von geometrischen Berechnungen) ist daher nicht prüfungsrelevant.
  • 24.07.: Die Testprüfung wird in einem einzigen Durchgang stattfinden, am Mo, 07.08. um 13:00 in HG G1.
  • 24.07.: Ihr Kommilitone Pascal Wacker hat ein Javascript-Tool zur Berechnung der Note aus den Einzelpunktzahlen gebaut. Wir übernehmen keine Garantie für die Richtigkeit des Tools.
  • 20.07.: Fehler in Formelsammlung korrigiert: Schranke an N für Target-Shooting.

Prüfungsinformationen:

Die schriftliche Prüfung findet am Di, 08. August, 9:00-11:00 in HIL F15 und HIL F41 (Hönggerberg !) statt. Seien Sie bitten schon 10 Minuten vor Klausurbeginn da.
Die Einteilung erfolgt nach Nachnamen:

  • A - Lo : HIL F 15
  • Lu - Z : HIL F 41
Dabei sind Nachnamen, die mit de ... oder von ... beginnen, unter d bzw. v einsortiert.
Bei der schriftlichen Klausur herrscht freie Platzwahl. Wenn Sie den Raum betreten, dann suchen Sie sich bitte einen Tisch mit Klausur, aber schlagen Sie die Klausur noch nicht auf, bis Sie dazu aufgefordert werden. Sie dürfen Ihre Tasche/Jacke mit an den Tisch nehmen (aber natürlich während der Klausur nicht verwenden).

Die Programmierprüfung findet am Fr, 11. August, 9:00-11:00 in den Computerräumen des HG statt:

  • A - Me : HG G1
  • Mo - Ruh : HG E19
  • Rus - Se : HG E26.1
  • Sh - Tob : HG E26.3
  • Toc - Z : HG E27
Bei der Computerprüfung (und der Probeprüfung) ist der Sitzplatz vorgegeben. Für den Raum HG G1 wird ein beschrifteter Plan vor der Tür hängen, damit Sie Ihren Platz leichter finden. Sie müssen Ihre Tasche/Jacke am Eingang ablegen. Wie bei der schriftlichen Klausur: Schlagen Sie ihre Klausur noch nicht auf, bis Sie dazu aufgefordert werden.

Für alle, die sich angemeldet haben, findet am Mo, 07. August, 13:00-14:00 Uhr eine Probeprüfung für den Programmierteil in HG G1 statt. Die Aufgaben der Probeprüfung werden ausserdem im Laufe des 07. August auf der Homepage veröffentlicht.

Hilfsmittel sind keine erlaubt, mit folgenden Ausnahmen:

  • Sie dürfen Ihr eigenes Schreibzeug und eine einfache Uhr (keine Smartphones oder Smartwatches) benutzen. Papier wird gestellt. Während der schriftlichen Klausur werden wir ausserdem die Formelsammlung zur Verfügung stellen. Während der Programmierprüfung wird eine Template-Datei (im Wesentlichen das Main.java-template auf dieser Homepage) vorhanden sein. Ausserdem werden Sie Zugriff auf diese Java-Dokumentation haben (Zugriff nur aus dem ethz-Netzwerk bzw. über vpn). Zum reibungslosen Starten werden Sie ausserdem die folgende Anleitung erhalten.
  • Essen und Trinken sind in vernünftigem Umfang erlaubt (insbesondere darf keine Geruchs- oder Geräuschbelästigung davon ausgehen). Flüssigkeiten sind nur in fest verschliessbaren Behältern erlaubt (keine Tassen, Becher etc).
  • Ohropax und vergleichbare Produkte sind erlaubt, jedoch keine Kopfhörer und kein Kapselgehörschutz.
  • Sie müssen während der Klausur Ihren Studierendenausweis (Legi) dabei haben und (für die Programmierprüfung) Ihr nethz-Passwort auswendig kennen. Wir werden tolerieren, wenn jemand das Passwort auf einem kleinen Zettel mitführt, sofern der Zettel unmittelbar nach Login weggesteckt wird. USB-Sticks sind nicht als Hilfsmittel zum Einloggen erlaubt!
  • Wer weitere Hilfsmittel benötigt (zum Beispiel ein Wörterbuch), möge diese bis spätestens 30. Juli per E-Mail bei Johannes Lengler anmelden. Das gleiche gilt, wenn Sie die Klausur auf Englisch bekommen möchten. (Lösungen dürfen prinzipiell auch auf Englisch abgegeben werden, hierzu ist keine Anmeldung nötig).

Vorbereitungsmaterial:

Bonuspunkte

Ihre Bonuspunkte können Sie hier einsehen.

Sowohl für das Lösen eines Übungsblattes als auch für die Korrektur während der Übungsstunde können Bonuspunkte erarbeitet werden. Sie bekommen Bonuspunkte für

  • das gemeinsame Lösen und Abgeben des Übungsblattes;
  • die gemeinsame Korrektur eines abgegebenen Übungsblattes in der Übungsstunde (nur wenn Sie selber ein Blatt abgegeben haben!);
  • die Mini-Tests;
  • das individuelle (!) Lösen der Programmieraufgaben.
Sie bekommen nur dann Bonuspunkte für abgegebene Übungsblätter und gelöste Programmieraufgaben, wenn Sie persönlich in der darauf folgenden Übungsstunde anwesend sind.

Am Ende des Semesters wird für alle vier Typen von Bonuspunkten (Lösen, Korrektur, Minitests, Programmieren) jeweils eine (nicht gerundete) Note berechnet, und diese vier Noten werden gemittelt. Die so errechnete (nicht gerundete) Note ("Bonusnote") fliesst in die Endnote ein, sofern deren Berücksichtigung vorteilhaft ist. Die Endnote ist das Maximum aus der Note der Sessionsprüfung und dem gewichteten Mittel der Bonusnote (30%) und der Note der Sessionsprüfung (70%).

Ihr Kommilitone Pascal Wacker hat ein Javascript-Tool zur Berechnung der Note aus den Einzelpunktzahlen gebaut. Wir übernehmen keine Garantie für die Richtigkeit des Tools.

Übungen

An dieser Stelle werden jeden Donnerstag (in Ausnahmefällen Dienstags) abwechselnd Programmieraufgaben bzw. theoretische Aufgaben online gestellt. Sie haben jeweils eine Woche Zeit zur Bearbeitung der Aufgaben. Programmieraufgaben können Sie direkt an einen online-judge schicken. Theoretische Aufgaben werden in den Übungen abgegeben. Wir werden ausserdem Beispiellösungen für alle Übungsblätter vorbereiten und auf dieser Webseite veröffentlichen. Das erste Übungsblatt erscheint am Dienstag, den 21. Februar.

Erster Übungstermin ist Donnerstag, der 23. Februar.

Programmieraufgaben:

Die Programmierübung 0 gibt keine Bonuspunkte und dient Ihnen als Wiederholung.

Ihre Datei sollte Main.java heissen und die Klasse Main enthalten. Diese Klasse sollte nicht public sein, benutzen Sie also "class Main { ... }" statt "public class Main { ... }".

Scoreboard

You can find a sample main class here.

You can find a sample of the flow algorithm here.

Woche Datum Übung Submission link Input Output Solutions
1 Di,
21.02.17
Programmierübung 0 Sum It - Submission

Distances - Submission
Input

Input
Output

Output
Solution

Solution
2 Do,
02.03.17
Programmierübung 1 MST - Submission

Important stops - Submission
Input

Input
Output

Output
Solution

Solution
3 Do,
16.03.17
Programmierübung 2 Password - Submission

Dining table - Submission
Input

Input
Output

Output
Solution

Solution
4 Do,
30.03.17
Programmierübung 3 Island tribes - Submission

Roulette - Submission
Input

Input
Output

Output
Solution

Solution
5 Do,
27.04.17
Programmierübung 4 Primality testing - Submission Input Output Solution
6 Do,
04.05.17
Programmierübung 5 Volume estimation - Submission Input Output Solution
7 Do,
18.05.17
Programmierübung 6 Santa claus - Submission

Dominoes - Submission
Input

Input
Output

Output
Solution

Solution
Test Exam Mo,
07.08.17
Test Exam Jackpot - Submission Input Output Solution
Exam Do,
17.08.17
Exam Unequal wedding - Submission

Shrinking array - Submission
Input

Input
Output

Output
Solution

Solution

Theoretische Aufgaben:

Theoretische Übung 1 Lösung 1
Minitest 1 Lösung MT1
Theoretische Übung 2 Lösung 2
Minitest 2 Lösung MT2
Theoretische Übung 3 Lösung 3
Minitest 3 Lösung MT3
Theoretische Übung 4 Lösung 4
Minitest 4 Lösung MT4
Theoretische Übung 5 Lösung 5
Minitest 5 Lösung MT5
Theoretische Übung 6 Lösung 6
Theoretische Übung 7 Lösung 7

Einschreibung in die Übungsstunden

Sie können sich selbstständig auf echo.ethz.ch für eine Übungsstunde anmelden. Ein späterer Wechsel ist in der Regel nicht möglich.
Wichtig: Melden Sie sich bis spätestens Mittwoch, 22. Februar, für eine Übungsgruppe an. Die Anmeldung zu einer Übungsstunde funktioniert nur, wenn Sie die Vorlesung in myStudies belegt haben.

Melden Sie sich bei Problemen mit der Anmeldung bitte umgehend an Johannes Lengler.

Ablauf der Übungen

In der ersten Übungsstunde werden Sie einer Arbeitsgruppe von zwei bis drei Personen zugeteilt. Die Arbeitsgruppen werden im Laufe des Semesters mehrmals neu eingeteilt. Sie bearbeiten die theoretischen Übungen (nicht die Programmieraufgaben!) gemeinsam in Ihrer Arbeitsgruppe und geben eine gemeinsame Lösung ab. Sie dürfen sich bei der Lösung der Aufgaben Inspiration aus anderen Quellen besorgen (Literatur, Kommilitonen, Forum). Allerdings empfehlen wir stark, dass Sie vorher ernsthaft versuchen, die Aufgaben selbständig zu lösen. In jedem Fall erwarten wir, dass Sie nur eigenständig formulierte Lösungen einreichen, selbst wenn Sie Ideen aus anderen Quellen bezogen haben. Ausserdem müssen alle Mitglieder der Arbeitsgruppe die Lösungen verstanden haben. Wir werden bei Verdacht während der Übungsstunde überprüfen, ob Sie die abgegebene Lösung verstanden haben.

In den Wochen, in denen Sie theoretische Aufgaben abgeben, wird die eingereichte Lösung einer Arbeitsgruppe von einer anderen Arbeitsgruppe korrigiert und anschliessend beim Assistenten abgegeben. Der Assistent wird die Korrektur bis zur darauf folgenden Übungsstunde bewerten. In den anderen Wochen wird es zu Beginn der Übungen Mini-Tests geben. Anschliessend werden die aktuellen Übungsaufgaben bzw. die Mini-Tests besprochen und allfällige Fragen zur Vorlesung geklärt.

Die Programmierabgaben werden einzeln (nicht in Arbeitsgruppen!) gelöst und innerhalb einer Woche an einen Judge geschickt, der den Code testet. Beachten Sie, dass Sie nur selbständig geschriebenen Code einschicken dürfen! Sie haben beliebig viele Versuche, einen korrekten Code abzuliefern. Auch bei den Programmieraufgabe kann von Ihnen während der Übungsstunde verlangt werden, dass Sie die Ideen Ihres Codes erklären.

Fragen und Kommentare

Sie können Kommentare und organisatorische Fragen von allgemeinem Interesse im Forum auf Moodle stellen. Wir werden Ihre Beiträge lesen und die Fragen direkt im Forum beantworten, damit auch andere Studierende von den Antworten profitieren können. Ausserdem gibt Ihnen das Forum auch die Möglichkeit, sich untereinander über die Übungen und die Vorlesung auszutauschen. Lesen Sie dazu bitte die Verhaltensregeln im Forum. Beachten Sie, dass wir von offizieller Seite in der Regel keine Hilfen und Tipps zu Übungsaufgaben geben werden.

Skript

Das Skript ist nun vollständig, bis auf den Stoff der letzten anderthalb Vorlesungen (Testen von geometrischen Prädikaten, konvexe Hülle, numerische Aspekte). Diese letzten Teile sind nicht prüfungsrelevant.
- Kapitel I: Graphentheorie (komplett)
- Kapitel II: Wahrscheinlichkeitstheorie (komplett)
- Kapitel III: Algorithmen (bis einschl. Abschnitt 3.2.1 (kleinster umschliessender Kreis))
- Gesamtskript: Skript Algorithmen und Wahrscheinlichkeit

Voraussetzungen: Graphen und Bäume
Vorlesung 1:
- Minimale Spannbäume (MST)
- Blaue/Rote Regel
Slides: lang kurz
Vorlesung 2:
- Algorithmen von Prim und Kruskal, Union-Find-Datenstruktur
- Shannons Switching Game
Slides: lang kurz
Vorlesung 3:
- k-zusammenhängend, k-kantenzusammenhängend
- Satz von Menger
- Artikulationspunkte und Brücken
Slides: lang kurz
Vorlesung 4:
- Eulertouren
- Hamiltonkreise und das Problem des Handlungsreisenden (travelling salesman problem, TSP)
- P und NP
Slides: lang kurz
Vorlesung 5:
- DP zur Berechnung von Hamiltonkreisen
- metrisches TSP (2-Aprooximation)
- Matchings, Satz von Hall
Slides: lang kurz
Vorlesung 6:
- Beweis der Sätze von Hall und Frobenius
- metrisches TSP (1.5-Aproximation)
- Färbungen (Einführung)
Slides: lang kurz
Vorlesung 7:
- Färbungen: Greedy Algorithmus
- Satz von Brooks
Slides: kurz (keine Animationen)
Vorlesung 8:
- Einführung in die Wahrscheinlichkeitstheorie
- Siebformel (Inklusion/Exklusion)
- Bedingte Wahrscheinlichkeit
Slides Teil 1: lang kurz
Slides Teil 2: lang kurz
Vorlesung 9:
- Ziegenproblem, Zwei-Kinder-Problem, Geburtstagsproblem
- Satz von der totalen Wahrscheinlichkeit
- Multiplikationssatz
- Satz von Bayes
- Unabhängigkeit von Zufallsvariablen
Slides: lang kurz
Vorlesung 10:
- Zufallsvariablen
- Erwartungswert
- Ungleichung von Markov (Spezialfall)
Slides: lang kurz
Vorlesung 11:
- Wiederholung und Beispiele: Erwartungswert
- bedingte Zufallsvariablen
- Varianz
Vorlesung 12:
- Dichte und Verteilungsfunktion
- Bernoulli-Verteilung, Binomialverteilung, geometrische Verteilung
- Balls-into-Bins
- Coupon Collector Problem
Vorlesung 13:
- Gedächtnislosigkeit der geometrischen Verteilung
- Poisson-Verteilung
- mehrere Zufallsvariablen: gemeinsame Dichte, Randdichte
- Unabhängigkeit von Zufallsvariablen
Slides: lang kurz
Vorlesung 14:
- zweistufiger Zufallsprozess
- Dichte von X+Y (Faltung)
- Summe von Poisson-Variablen ist Poison-verteilt
- E[XY] = E[X]E[Y], Var[X+Y]=Var[X]+Var[Y] für unabhängige X,Y
- Wald'sche Identität
Slides: lang kurz
Vorlesung 15:
- randomisierte Algorithmen
- Mehrfachläufe von randomisierten Algorithmen
- Ungleichung von Markov
- Ungleichung von Chebyshev
Slides: lang kurz
Vorlesung 16:
- Ungleichung von Markov: Auswirkungen auf Algorithmen
- Ungleichung von Chebyshev: Varianz des Coupon Collector Prozess
- Chernoff-Schranke
Slides: lang kurz
Vorlesung 17:
- Las Vegas-Algorithmen/Monte-Carlo-Algorithmen
- Randomized Quicksort
- Quickselect
- Target Shooting
Slides: lang kurz
Vorlesung 18:
- Las Vegas-Algorithmen/Monte-Carlo-Algorithmen (Fortsetzung)
- Target Shooting (Fortsetzung)
- Primzahltest
- Balls into Bins (maximales Bin)
Slides: lang kurz
Vorlesung 19:
- Balls into Bins (Fortsetzung)
- Bloom-Filter
Slides: lang kurz
Vorlesung 20:
- Lange Pfade
Keine Folien, siehe Skript (Kap. III, Algorithmen).
Vorlesung 21:
- Maximale Flüsse/Minimale Schnitte
Keine Folien, siehe Skript (Kap. III, Algorithmen).
Vorlesung 22:
- Maximale Flüsse/Minimale Schnitte (Fortsetzung)
- Algorithmus von Ford-Fulkerson
- Matching maximaler Grösse
Keine Folien, siehe Skript (Kap. III, Algorithmen).
Vorlesung 23:
- Maximale Flüsse/Minimale Schnitte (Fortsetzung)
- Bildsegmentierung durch minimale Schnitte
- Flüsse als konvexe Mengen
Keine Folien, siehe Skript (Kap. III, Algorithmen).
Vorlesung 24:
- Minimale Schnitte (in Multigraphen)
- Randomisierter Algorithmus mit Kantenkontraktion
- Bootstrapping
Keine Folien, siehe Skript (Kap. III, Algorithmen).
Vorlesung 25:
- Sampling mit vorgegebenen Wahrscheinlichkeiten
- Kleinster umschliessender Kreis
Slides: lang kurz
Vorlesung 26:
- Sampling Lemma für kleinsten umschliessenden Kreis
- Testen von geometrischen Prädikaten:
auf welcher Seite liegt ein Punkt von einer Gerade, einer Ebene, einem Kreis?
Keine Folien, siehe Skript (Kap. III, Algorithmen).
Vorlesung 27:
- konvexe Hülle
- numerische Aspekte von geometrischen Berechnungen
Keine Folien, siehe Skript (Kap. III, Algorithmen).

Literatur

Es gibt kein Buch, das den Vorlesungsstoff komplett abdeckt. Die folgenden Bücher können jedoch als Sekundärliteratur hilfreich sein.
  • T. Schickinger, A. Steger: Diskrete Strukturen 2: Wahrscheinlichkeitstheorie und Statistik, Springer, 2013
  • T. Ottmann , P. Widmayer: Algorithmen und Datenstrukturen, Spektrum, 2002
  • T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1990
  • H.J. Prömel, A. Steger: The Steiner Tree Problem: A Tour Through Graphs, Algorithms and Complexity, Vieweg, 2002
  • R. Sedgewick: Algorithmen in C++, Pearson, 2003
  • S Baase, A. van Gelder: Computer Algorithms, Addison Wesley, 2000
  • G. Brassard, P. Bratley: Fundamentals of Algorithms, Prentice Hall, 1996
  • J. Kleinberg, E. Tardos: Algorithm Design, Addison Wesley, 2005

Kontakt

Die Übungen werden von Johannes Lengler organisiert, die Programmieraufgaben (Anfragen falls möglich bitte auf Englisch) von Nemanja Skoric und Milos Trujic.