David Steurer: Katalogdaten im Herbstsemester 2020

NameHerr Prof. Dr. David Steurer
LehrgebietTheoretische Informatik
Adresse
Professur Theoretische Informatik
ETH Zürich, OAT Z 22.2
Andreasstrasse 5
8092 Zürich
SWITZERLAND
E-Maildavid.steurer@inf.ethz.ch
URLhttps://www.dsteurer.org
DepartementInformatik
BeziehungAusserordentlicher Professor

NummerTitelECTSUmfangDozierende
252-0026-00LAlgorithmen und Datenstrukturen Information Belegung eingeschränkt - Details anzeigen 7 KP3V + 2U + 1AM. Püschel, D. Steurer
KurzbeschreibungThe 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.
LernzielVerständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen. Verständnis der Grundlagen der Graphentheorie und einiger ihrere grundlegenden Algorithmen,
InhaltDer 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.
SkriptEin vollständiges Skript in Deutsch ist in der Entwicklung und bereits als vollständiger Entwurf auf der Vorlesungswebseite verfügbar.
LiteraturAbgesehen 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-00LAlgorithms, Probability, and Computing Information 8 KP4V + 2U + 1AB. Gärtner, M. Ghaffari, R. Kyng, D. Steurer
KurzbeschreibungAdvanced 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).
LernzielStudying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory.
SkriptWill be handed out.
LiteraturIntroduction 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-00LSeminar in Theoretical Computer Science Information Belegung eingeschränkt - Details anzeigen 2 KP2SE. Welzl, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, D. Steurer, B. Sudakov
KurzbeschreibungPräsentation wichtiger und aktueller Arbeiten aus der theoretischen Informatik, sowie eigener Ergebnisse von Diplomanden und Doktoranden.
LernzielDas 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 / BesonderesThis 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.