Emo Welzl: Katalogdaten im Herbstsemester 2014

Auszeichnung: Die Goldene Eule
NameHerr Prof. em. Dr. Emo Welzl
NamensvariantenEmo Welzl
LehrgebietInformatik
Adresse
Inst. f. Theoretische Informatik
ETH Zürich, OAT Z 13.2
Andreasstrasse 5
8092 Zürich
SWITZERLAND
Telefon+41 44 632 73 70
Fax+41 44 632 10 63
E-Mailemo@inf.ethz.ch
URLhttp://www.inf.ethz.ch/personal/emo/
DepartementInformatik
BeziehungProfessor emeritus

NummerTitelECTSUmfangDozierende
252-0057-00LTheoretische Informatik Information 8 KP4V + 2U + 1AJ. Hromkovic, E. Welzl
KurzbeschreibungKonzepte zur Beantwortung grundlegender Fragen wie: a) Was ist völlig automatisiert machbar (algorithmisch lösbar) b) Wie kann man die Schwierigkeit von Aufgaben (Problemen) messen? c) Was ist Zufall und wie kann er nützlich sein? d) Was ist Nichtdeterminisus und welche Rolle spielt er in der Informatik? e) Wie kann man unendliche Objekte durch Automaten und Grammatiken endlich darstellen?
LernzielVermittlung der grundlegenden Konzepte der Informatik in ihrer geschichtlichen Entwicklung
InhaltDie Veranstaltung ist eine Einführung in die Theoretische Informatik, die die grundlegenden Konzepte und Methoden der Informatik in ihrem geschichtlichen Zusammenhang vorstellt. Wir präsentieren Informatik als eine interdisziplinäre Wissenschaft, die auf einer Seite die Grenzen zwischen Möglichem und Unmöglichem und die quantitativen Gesetze der Informationsverarbeitung erforscht und auf der anderen Seite Systeme entwirft, analysiert, verifiziert und implementiert.

Die Hauptthemen der Vorlesung sind:

- Alphabete, Wörter, Sprachen, Messung der Informationsgehalte von Wörtern, Darstellung von algorithmischen Aufgaben
- endliche Automaten, reguläre und kontextfreie Grammatiken
- Turingmaschinen und Berechenbarkeit
- Komplexitätstheorie und NP-Vollständigkeit
- Algorithmenentwurf für schwere Probleme
SkriptDie Vorlesung ist detailliert durch das Lehrbuch "Theoretische Informatik" bedeckt.
LiteraturBasisliteratur:
1. J. Hromkovic: Theoretische Informatik. 5. Auflage, Teubner 2014.

2. J. Hromkovic: Theoretical Computer Science. Springer 2004.

Weiterführende Literatur:
3. M. Sipser: Introduction to the Theory of Computation, PWS Publ. Comp.1997
4. J.E. Hopcroft, R. Motwani, J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie.
Pearson 2002.
5. I. Wegener: Theoretische Informatik. Teubner
Weitere Übungen und Beispiele:
6. A. Asteroth, Ch. Baier: Theoretische Informatik
Voraussetzungen / BesonderesWährend des Semesters werden zwei freiwillige Probeklausuren gestellt.
252-0209-00LAlgorithms, Probability, and Computing Information 8 KP4V + 2U + 1AE. Welzl, T.  Holenstein, P. Widmayer
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-0860-00LDiskrete Mathematik4 KP2V + 1UE. Welzl, J. Lengler
KurzbeschreibungGrundlagen der Diskreten Mathematik: Kombinatorik (elementare Zählprobleme), Graphentheorie (Pfade, Wege, Eulerkreise, Matchings, Bäume, planare Graphen), Algebra (modulare Arithmetik, Gruppen, Körper), Anwendungen (Netzwerkflüsse, Kryptographie, Codierungstheorie).
Lernzielsiehe oben
252-1425-00LGeometry: Combinatorics and Algorithms Information 6 KP2V + 2U + 1AB. Gärtner, M. Hoffmann, E. Welzl
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
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.
263-0006-00LAlgorithms Lab Information 6 KP4P + 1AA. Steger, E. Welzl, P. Widmayer
KurzbeschreibungStudents learn how to solve algorithmic problems given by a textual description (understanding problem setting, finding appropriate modeling, choosing suitable algorithms, and implementing them). Knowledge of basic algorithms and data structures is assumed; more advanced material and usage of standard libraries for combinatorial algorithms are introduced in tutorials.
LernzielThe objective of this course is to learn how to solve algorithmic problems given by a textual description. This includes appropriate problem modeling, choice of suitable (combinatorial) algorithms, and implementing them (using C/C++, STL, CGAL, and BGL).
LiteraturT. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1990.
J. Hromkovic, Teubner: Theoretische Informatik, Springer, 2004 (English: Theoretical Computer Science, Springer 2003).
J. Kleinberg, É. Tardos: Algorithm Design, Addison Wesley, 2006.
H. R. Lewis, C. H. Papadimitriou: Elements of the Theory of Computation, Prentice Hall, 1998.
T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum, 2012.
R. Sedgewick: Algorithms in C++: Graph Algorithms, Addison-Wesley, 2001.
263-4200-00LSeminar SAT Information 2 KP2SE. Welzl
KurzbeschreibungStudy and presentation of research papers from the literature on "Boolean Satisfiability-Combinatorics and Algorithms".
LernzielGoal of this seminar is to study and present, in continuation of the course "Boolean Satisfiability-Combinatorics and Algorithms", research papers from the literature.
LiteraturA list of papers for presentations will be distributed at the beginning of the seminar.
Voraussetzungen / BesonderesThe seminar builds heavily on the material covered in the course "Boolean Satisfiability-Combinatorics and Algorithms." Successful completion of that course is a prerequisite for participation in the seminar.
263-4203-00LGeometry: Combinatorics and Algorithms Information
Findet dieses Semester nicht statt.
2 KP2SB. Gärtner, E. Welzl
KurzbeschreibungThis seminar is held once a year and complements the courses Computational Geometry and Geometric Graphs: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area.
LernzielEach student is expected to read, understand, and elaborate on a selected research paper. To this end, (s)he should give a 45-min. presentation about the paper. The process includes

* getting an overview of the related literature;
* understanding and working out the background/motivation:
why and where are the questions addressed relevant?
* understanding the contents of the paper in all details;
* selecting parts suitable for the presentation;
* presenting the selected parts in such a way that an audience
with some basic background in geometry and graph theory can easily understand and appreciate it.
Voraussetzungen / BesonderesTo attend the seminar, some basic knowledge in (discrete and computational) geometry and graphs and algorithms is required. Thus, previous participation in some of the courses "Graphs and Algorithms", "Computational Geometry", "Geometric Graphs: Combinatorics & Algorithms", or similar courses is strongly encouraged. It is also possible to take this seminar in parallel to the lecture "Computational Geometry".