David Steurer: Katalogdaten im Herbstsemester 2022 |
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 |
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 | The Kurs behandelt die Grundlagen des Entwurfs und der Analyse von Algorithmen und Datenstrukturen. Diese werden anhand von klassischen algorithmischen Problemen einschliesslich Graphenproblemen studiert. Die dazu nötige Einführung in die Graphentheorie ist ebenfalls Teil dieses Kurses. | ||||
Lernziel | Verständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen. Verständnis der Grundlagen der Graphentheorie und einiger ihrere grundlegenden Algorithmen, | ||||
Inhalt | Der Kurs ist eine Einführung in die Grundlagen des Designs and der Analyse von Algorithmen. Dazu gehören zum einen klassische Entwurfsmuster für Algorithmen wie Induktion, Divide-and-Conquer und dynamische Programmierung. Diese werden anhand von klassischen Problemen wie zum Beispiel Suchen und Sortieren studiert. Zum anderen geht es um das Zusammenspiel von Algorithmen und Datenstrukturen wie verkettete Listen, Suchbäumen, Heaps und Union-Find Strukturen. Ein besondere Fokus sind Graphenalgorithmen für Probleme wie kürzeste Wege und minimale Spannbäume. Die dazu notwendige erste Einführung in die Graphentheorie ist ebenfalls Teil der Vorlesung. | ||||
Skript | Ein vollständiges Skript in Deutsch ist in der Entwicklung und bereits als vollständiger Entwurf auf der Vorlesungswebseite verfügbar. | ||||
Literatur | Abgesehen vom Skript und Vorlesungsunterlagen empfehlen wir die folgenden Bücher als zusätzliches Nachschlagewerk. Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: An Introduction to Algorithms, 3rd edition, MIT Press, 2009 | ||||
252-0209-00L | Algorithms, Probability, and Computing ![]() | 8 KP | 4V + 2U + 1A | B. Gärtner, R. Kyng, A. Steger, D. Steurer, E. Welzl | |
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 | E. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, 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 restriction is: prior successful participation in a master level seminar in theoretical computer science. |