Bernd Gärtner: Katalogdaten im Herbstsemester 2022 |
| Name | Herr Prof. Dr. Bernd Gärtner |
| Adresse | Inst. f. Theoretische Informatik ETH Zürich, OAT Z 15 Andreasstrasse 5 8092 Zürich SWITZERLAND |
| Telefon | +41 44 632 70 26 |
| Fax | +41 44 632 10 63 |
| gaertner@inf.ethz.ch | |
| URL | http://people.inf.ethz.ch/gaertner/ |
| Departement | Informatik |
| Beziehung | Titularprofessor |
| Nummer | Titel | ECTS | Umfang | Dozierende | |
|---|---|---|---|---|---|
| 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-1425-00L | Geometry: Combinatorics and Algorithms | 8 KP | 3V + 2U + 2A | B. Gärtner, E. Welzl, M. Hoffmann | |
| Kurzbeschreibung | Geometric structures are useful in many areas, and there is a need to understand their structural properties, and to work with them algorithmically. The lecture addresses theoretical foundations concerning geometric structures. Central objects of interest are triangulations. We study combinatorial (Does a certain object exist?) and algorithmic questions (Can we find a certain object efficiently?) | ||||
| Lernziel | The goal is to make students familiar with fundamental concepts, techniques and results in combinatorial and computational geometry, so as to enable them to model, analyze, and solve theoretical and practical problems in the area and in various application domains. In particular, we want to prepare students for conducting independent research, for instance, within the scope of a thesis project. | ||||
| Inhalt | Planar and geometric graphs, embeddings and their representation (Whitney's Theorem, canonical orderings, DCEL), polygon triangulations and the art gallery theorem, convexity in R^d, planar convex hull algorithms (Jarvis Wrap, Graham Scan, Chan's Algorithm), point set triangulations, Delaunay triangulations (Lawson flips, lifting map, randomized incremental construction), Voronoi diagrams, the Crossing Lemma and incidence bounds, line arrangements (duality, Zone Theorem, ham-sandwich cuts), 3-SUM hardness, counting planar triangulations. | ||||
| Skript | yes | ||||
| Literatur | Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong, Computational Geometry: Algorithms and Applications, Springer, 3rd ed., 2008. Satyan Devadoss, Joseph O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011. Stefan Felsner, Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry, Teubner, 2004. Jiri Matousek, Lectures on Discrete Geometry, Springer, 2002. Takao Nishizeki, Md. Saidur Rahman, Planar Graph Drawing, World Scientific, 2004. | ||||
| Voraussetzungen / Besonderes | Prerequisites: The course assumes basic knowledge of discrete mathematics and algorithms, as supplied in the first semesters of Bachelor Studies at ETH. Outlook: In the following spring semester there is a seminar "Geometry: Combinatorics and Algorithms" that builds on this course. There are ample possibilities for Semester-, Bachelor- and Master Thesis projects in the area. | ||||
| 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. | ||||
| 265-0101-00L | Data Science Only for CAS in Applied Information Technology and MAS in Applied Technology. | 3 KP | 3V | B. Gärtner | |
| Kurzbeschreibung | In this module, basic paradigms and techniques in working with data will be discussed, especially towards data security, managing data decentrally, and learning from data. | ||||
| Lernziel | Participants learn about some important computer science concepts necessary for data science. They understand some of these concepts in detail and see the mathematics behind them. | ||||
| Inhalt | Participants will get an introduction to key computer science concepts underlying current and upcoming technology. The module in particular covers cryptography and digital signatures, networking and distributed algorithms, distributed ledger technology, as well as machine learning (supervised and unsupervised learning). Each topic will be discussed in two different ways: (i) a hands-on and in-depth introduction that allows participants to gain a technical understanding of key ideas. This is supported by simple and concrete examples as well as programming assignments; (ii) a context part that addresses the challenges and limitations encountered in practical applications. | ||||