Johannes Lengler: Katalogdaten im Herbstsemester 2024 |
| Name | Herr Prof. Dr. Johannes Lengler |
| Adresse | Informatik (Theoretische Inform.) ETH Zürich, OAT Z 14.1 Andreasstrasse 5 8092 Zürich SWITZERLAND |
| johannes.lengler@inf.ethz.ch | |
| Departement | Informatik |
| Beziehung | Titularprofessor |
| Nummer | Titel | ECTS | Umfang | Dozierende | |||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 252-0026-00L | Algorithmen und Datenstrukturen | 7 KP | 3V + 2U + 1A | J. Lengler, 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 auf Deutsch ist in der Entwicklung. | ||||||||||||||||||||||||||||||||||||||
| 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 | ||||||||||||||||||||||||||||||||||||||
Kompetenzen |
| ||||||||||||||||||||||||||||||||||||||
| 252-4202-00L | Seminar in Theoretical Computer Science  | 2 KP | 2S | A. Steger, B. Gärtner, M. Hoffmann, J. Lengler, D. Steurer | |||||||||||||||||||||||||||||||||||
| 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. | ||||||||||||||||||||||||||||||||||||||
| 263-4500-00L | Advanced Algorithms | 9 KP | 3V + 2U + 3A | J. Lengler, B. Häupler, M. Probst | |||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | This is a graduate-level course on algorithm design (and analysis). It covers a range of topics and techniques in approximation algorithms, sketching and streaming algorithms, and online algorithms. | ||||||||||||||||||||||||||||||||||||||
| Lernziel | This course familiarizes the students with some of the main tools and techniques in modern subareas of algorithm design. | ||||||||||||||||||||||||||||||||||||||
| Inhalt | The lectures will cover modern topics in algorithm design and analysis, including the following: graph sparsifications while preserving cuts or distances, various approximation algorithms techniques and concepts, metric embeddings and probabilistic tree embeddings, online algorithms, multiplicative weight updates, streaming algorithms, sketching algorithms. | ||||||||||||||||||||||||||||||||||||||
| Skript | https://people.inf.ethz.ch/~aroeyskoe/AA24 | ||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | This course is designed for masters and doctoral students and it especially targets those interested in theoretical computer science, but it should also be accessible to last-year bachelor students. Sufficient comfort with both (A) Algorithm Design & Analysis and (B) Probability & Concentrations. E.g., having passed the course Algorithms, Probability, and Computing (APC) is recommended, though not required formally. If you are not sure whether you're ready for this class or not, please consult the instructor. | ||||||||||||||||||||||||||||||||||||||
| Kompetenzen |
| ||||||||||||||||||||||||||||||||||||||