Algorithmen und Komplexität (D-MATH)

Dozenten

Prof. Dr. Angelika Steger, Prof. Dr. Thomas Holenstein

Übungsleitung

Ralph Keusch

Zeit und Ort

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

Die Vorlesung beginnt am 15. September 2015. Die ersten Übungsstunden finden während der zweiten Semesterwoche statt.

Übungsgruppen

Die Einteilung in die Übungsgruppen wird während der ersten Vorlesung vorgenommen.

• Gruppe 1 (Stephan Ammann): Donnerstag 15:45 - 16:30, HCI D 4
• Gruppe 2 (Ralph Keusch): Donnerstag 16:15 - 17:00, CAB G 52
• Gruppe 3 (Florian Meier): Donnerstag 16:15 - 17:00, CAB G 56
• Gruppe 4 (Pascal Pfister): Donnerstag 16:15 - 17:00, ML H 34.3
• Gruppe 5 (Cyril Jonas Frei): Freitag 12:15 - 13:00, CAB G 57

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, Beispiele für Reduktionen, NP-Vollständigkeit
• Ausblick: Optimierungsprobleme, Approximationsalgorithmen

Unterlagen

• Übungen: Übungsserien und Musterlösungen
• Weitere Unterlagen: Vorlesungsslides und Beispielklausuren

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.

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