Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
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.
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:
Die Programmierprüfung findet am Fr, 11. August, 9:00-11:00 in den Computerräumen des HG statt:
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:
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
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.
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.
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 { ... }".
You can find a sample main class here.
You can find a sample of the flow algorithm here.
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.
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.
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.
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). |