David Steurer: Katalogdaten im Herbstsemester 2019

Name	Herr Prof. Dr. David Steurer
Lehrgebiet	Theoretische Informatik
Adresse	Professur Theoretische Informatik ETH Zürich, OAT Z 22.2 Andreasstrasse 5 8092 Zürich SWITZERLAND
E-Mail	david.steurer@inf.ethz.ch
URL	https://www.dsteurer.org
Departement	Informatik
Beziehung	Ausserordentlicher Professor

Nummer	Titel	ECTS	Umfang	Dozierende
252-0026-00L	Algorithmen und Datenstrukturen	7 KP	3V + 2U + 1A	M. Püschel, D. Steurer
Kurzbeschreibung	Es werden grundlegende Entwurfsmuster für Algorithmen sowie klassische algorithmische Probleme und Datenstrukturen behandelt. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. In die Graphentheorie wird kurz eingeführt.
Lernziel	Verständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen.
Inhalt	Es werden grundlegende Algorithmen und Datenstrukturen vorgestellt und analysiert. Dazu gehören auf der einen Seite Entwurfsmuster für Algorithmen, wie Induktion, divide-and-conquer, backtracking und dynamische Optimierung, ebenso wie klassische algorithmische Probleme, wie Suchen und Sortieren. Auf der anderen Seite werden Datenstrukturen für verschiedene Zwecke behandelt, darunter verkettete Listen, Hashtabellen, balancierte Suchbäume, verschiedene heaps und union-find-Strukturen. Weiterhin wird Adaptivität bei Datenstrukturen (wie etwa Splay-Bäume) und bei Algorithmen (wie etwa online-Algorithmen) beleuchtet. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. Hierfür werden grundlegende Konzepte der Graphentheorie eingeführt.
Literatur	Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011
252-0209-00L	Algorithms, Probability, and Computing	8 KP	4V + 2U + 1A	A. Steger, B. Gärtner, M. Ghaffari, D. Steurer
Kurzbeschreibung	Advanced design and analysis methods for algorithms and data structures: Random(ized) Search Trees, Point Location, Minimum Cut, Linear Programming, Randomized Algebraic Algorithms (matchings), Probabilistically Checkable Proofs (introduction).
Lernziel	Studying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory.
Skript	Will be handed out.
Literatur	Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest; Randomized Algorithms by R. Motwani und P. Raghavan; Computational Geometry - Algorithms and Applications by M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf.
252-4202-00L	Seminar in Theoretical Computer Science	2 KP	2S	A. Steger, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, D. Steurer, B. Sudakov
Kurzbeschreibung	Präsentation wichtiger und aktueller Arbeiten aus der theoretischen Informatik, sowie eigener Ergebnisse von Diplomanden und Doktoranden.
Lernziel	Das Lernziel ist, Studierende an die aktuelle Forschung heranzuführen und sie in die Lage zu versetzen, wissenschaftliche Arbeiten zu lesen, zu verstehen, und zu präsentieren.
Voraussetzungen / Besonderes	This seminar takes place as part of the joint research seminar of several theory groups. Intended participation is for students with excellent performance only. Formal minimal requirement is passing of one of the courses Algorithms, Probability, and Computing, Randomized Algorithms and Probabilistic Methods, Geometry: Combinatorics and Algorithms, Advanced Algorithms. (If you cannot fulfill this restriction, because this is your first term at ETH, but you believe that you satisfy equivalent criteria, please send an email with a detailed description of your reasoning to the organizers of the seminar.)