Bernd Gärtner: Katalogdaten im Herbstsemester 2016

NameHerr Prof. Dr. Bernd Gärtner
Adresse
Inst. f. Theoretische Informatik
ETH Zürich, CAB G 31.1
Universitätstrasse 6
8092 Zürich
SWITZERLAND
Telefon+41 44 632 70 26
Fax+41 44 632 10 63
E-Mailgaertner@inf.ethz.ch
URLhttp://people.inf.ethz.ch/gaertner/
DepartementInformatik
BeziehungTitularprofessor

NummerTitelECTSUmfangDozierende
252-0847-00LInformatik Information 5 KP2V + 2UB. Gärtner
KurzbeschreibungDie Vorlesung gibt eine Einführung in das Programmieren anhand der Sprache C++. Wir behandeln fundamentale Typen, Kontrollanweisungen, Funktionen, Felder und Klassen. Die Konzepte werden dabei jeweils durch Algorithmen und Anwendungen motiviert und illustriert.
LernzielDas Ziel der Vorlesung ist eine algorithmisch orientierte Einführung ins Programmieren.
InhaltDie Vorlesung gibt eine Einführung in das Programmieren anhand der Sprache C++. Wir behandeln fundamentale Typen, Kontrollanweisungen, Funktionen, Felder und Klassen. Die Konzepte werden dabei jeweils durch Algorithmen und Anwendungen motiviert und illustriert.
SkriptEin Skript in englischer Sprache sowie Handouts in deutscher Sprache werden semesterbegleitend elektronisch herausgegeben.
LiteraturAndrew Koenig and Barbara E. Moo: Accelerated C++, Addison-Wesley, 2000.

Stanley B. Lippman: C++ Primer, 3. Auflage, Addison-Wesley, 1998.

Bjarne Stroustrup: The C++ Programming Language, 3. Auflage, Addison-Wesley, 1997.

Doina Logofatu: Algorithmen und Problemlösungen mit C++, Vieweg, 2006.

Walter Savitch: Problem Solving with C++, Eighth Edition, Pearson, 2012
252-1425-00LGeometry: Combinatorics and Algorithms Information 6 KP2V + 2U + 1AB. Gärtner, E. Welzl, M. Hoffmann, A. Pilz
KurzbeschreibungGeometric 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?)
LernzielThe 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.
InhaltPlanar 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.
Skriptyes
LiteraturMark 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 / BesonderesPrerequisites: 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-00LSeminar in Theoretical Computer Science Information 2 KP2SE. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, 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.