Algorithmen und Komplexität (D-MATH)

Dozierende

Prof. Dr. Angelika Steger

Übungsleitung

Ralph Keusch, Florian Meier

Zeit und Ort

Dienstag 8:15 - 10:00, HG D 1.2

Die Vorlesung beginnt am 19. September 2017. Die ersten Übungsstunden finden am 28. September statt.

Übungsgruppen

Die Übungen finden jeweils am Donnerstag von 16:15 bis 17:00 im Zentrum statt. Melden Sie sich bis spätestens Montag, 25. September, auf echo.ethz.ch für eine Übungsgruppe an. Ein späterer Wechsel ist in der Regel nicht möglich. Die Anmeldung zu einer Übungsstunde funktioniert nur, wenn Sie die Vorlesung in myStudies belegt haben.

• Gruppe 1: Ralph Keusch, CAB G 52
• Gruppe 2: Florian Meier, CAB G 56
• Gruppe 3: Daniel Bertschinger, IFW C 35
• Gruppe 4: Florian Rossmannek, LEE C 114
• Gruppe 5: Pascal Su, ML H 34.3

Inhalt

Die Vorlesung behandelt den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Themengebiete sind:

• Einführung: RAM-Maschine, Landau-Notation, Datenstrukturen, Graphen
• Algorithmen: Binäre Suche, Sortieren, Medianbestimmung, Matrixmultiplikation, kürzeste Pfade, minimale Spannbäume
• Paradigmen des Algorithmenentwurfs: Divide&Conquer, dynamische Programmierung, Greedy-Algorithmen
• Effiziente Datenstrukturen: Suchbäume, Union-Find-Strukturen, Wörterbücher, Priority Queues
• Berechenbarkeit und Komplexität: berechenbare Sprachen, Klassen P und NP, Formeln und Schaltkreise, NP-Vollständigkeit, Beispiele für Reduktionen
• Ausblick: Optimierungsprobleme, Approximationsalgorithmen

Übungsblätter

Die Bearbeitung der Serien ist nicht verpflichtend. Wir empfehlen Ihnen trotzdem dringend, die Übungen schon während des Semesters zu lösen. Beachten Sie, dass dies die einzige Möglichkeit ist, direktes Feedback zu erhalten. Pro Serie werden von der Übungsleitung jeweils zwei Aufgaben ausgewählt, die bei allen Abgaben korrigiert werden. Diese beiden Aufgaben werden auf der Serie jeweils angegeben. Für die anderen Aufgaben steht jeweils die Musterlösung zur Selbstkorrektur zur Verfügung. Die Übungsaufgaben werden jeweils am Dienstag in der Vorlesung verteilt und in der anschliessenden Übungsstunde vorbesprochen. (Die erste Serie wird nicht vorbesprochen.) Die Serien können dann jeweils in der nächsten Vorlesung abgegeben werden.

Challenge-Aufgaben

Die erste korrekte Lösung gewinnt einen Bücherpreis! Die nächsten 5 korrekten Lösungen werden mit einer feinen Tafel Schokolade belohnt. Zudem verdient sich jeder, der eine korrekte Lösung findet, einen Platz in der Liste der gewieften Challenge-Aufgaben Bezwinger.

Slides

Die Slides der Vorlesung werden jeweils dienstags nach der Vorlesung online gestellt.

Zusätzliche Animationen von Algorithmen können auf vielen Webseiten im Internet gefunden werden. z.B. auf http://visualgo.net/.

Vorlesungsunterlagen

• Das Skript zur Vorlesung ist gegen einen Druckkostenbeitrag von 10 Fr. erhältlich.

Prüfung

Die Prüfung ist schriftlich und dauert 120 Minuten. Sie findet während der Prüfungssession im Winter statt. Als Hilfsmittel dürfen 10 (beidseitig) handgeschriebene DIN A4 Blätter verwendet werden. Für die Prüfungsvorbereitung stellen wir die folgenden Testklausuren zur Verfügung:

Die folgenden Abschnitte aus dem Skript gehören nicht zum Prüfungsstoff:

• Kapitel 1.1.1
• Kapitel 5.2.3, 5.2.4
• polynomieller Algorithmus für 2-SAT
• alle Beweise aus Kapitel 5.3.2
• Kapitel 5.8 (Beweise mit beschränkter Länge)

Literatur

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

T. Ottmann , P. Widmayer:

Algorithmen und Datenstrukturen, Spektrum, 2002

S. Arora, B. Barak:

Computational Complexity, Cambridge University Press, 2009