Emo Welzl: Katalogdaten im Frühjahrssemester 2015

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-0491-00LSatisfiability of Boolean Formulas - Combinatorics and Algorithms Information 7 KP3V + 2U + 1AE. Welzl
KurzbeschreibungBasics (CNF, resolution), extremal properties (probabilistic method, derandomization, Local Lemma, partial satisfaction), 2-SAT algorithms (random walk, implication graph), NP-completeness (Cook-Levin), cube (facial structure, Kraft inequality, Hamming balls, covering codes), SAT algorithms (satisfiability coding lemma, Paturi-Pudlák-Zane, Hamming ball search, Schöning), constraint satisfaction.
LernzielStudying of advanced methods in algorithms design and analysis, and in discrete mathematics along a classical problem in theoretical computer science.
InhaltSatisfiability (SAT) is the problem of deciding whether a boolean formula in propositional logic has an assignment that evaluates to true. SAT occurs as a problem and is a tool in applications (e.g. Artificial Intelligence and circuit design) and it is considered a fundamental problem in theory, since many problems can be naturally reduced to it and it is the 'mother' of NP-complete problems. Therefore, it is widely investigated and has brought forward a rich body of methods and tools, both in theory and practice (including software packages tackling the problem).
This course concentrates on the theoretical aspects of the problem. We will treat basic combinatorial properties (employing the probabilistic method including a variant of the Lovasz Local Lemma), recall a proof of the Cook-Levin Theorem of the NP-completeness of SAT, discuss and analyze several deterministic and randomized algorithms and treat the threshold behavior of random formulas.
In order to set the methods encountered into a broader context, we will deviate to the more general set-up of constraint satisfaction and to the problem of proper k-coloring of graphs.
SkriptThere exists no book that covers the many facets of the topic. Lecture notes covering the material of the course will be distributed.
LiteraturHere is a list of books with material vaguely related to the course. They can be found in the textbook collection (Lehrbuchsammlung) of the Computer Science Library:

George Boole, An Investigation of the Laws of Thought on which are Founded the Mathematical Theories of Logic and Probabilities, Dover Publications (1854, reprinted 1973).
Peter Clote, Evangelos Kranakis, Boolean Functions and Computation Models, Texts in Theoretical Computer Science, An EATCS Series, Springer Verlag, Berlin (2002).
Nadia Creignou, Sanjeev Khanna, Madhu Sudhan, Complexity Classifications of Boolean Constrained Satisfaction Problems, SIAM Monographs on Discrete Mathematics and Applications, SIAM (2001).
Harry R. Lewis, Christos H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall (1998).
Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, (1995).
Uwe Schöning, Logik für Informatiker, BI-Wissenschaftsverlag (1992).
Uwe Schöning, Algorithmik, Spektrum Akademischer Verlag, Heidelberg, Berlin (2001).
Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, Boston (1997).
Klaus Truemper, Design of Logic-based Intelligent Systems, Wiley-Interscience, John Wiley & Sons, Inc., Hoboken (2004).
Voraussetzungen / BesonderesLanguage: The course will be given in German if nobody expresses preference for English. All accompanying material (lecture notes, web-page, etc.) is supplied in English.
Prerequisites: The course assumes basic knowledge in propositional logic, probability theory and discrete mathematics, as it is supplied in the first two years of the Bachelor Studies at ETH.
Outlook: There will be a follow-up seminar, SAT, on the topic in the subsequent semester (attendance of this course will be a prerequisite for participation in the seminar). There are ample possibilities for theses of various types (Master-, etc.).
252-4202-00LSeminar in Theoretical Computer Science Information 2 KP2SE. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, B. Sudakov
KurzbeschreibungPresentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.
LernzielTo get an overview of current research in the areas covered by the involved research groups. To present results from the literature.
252-4220-00LWie funktioniert Forschung? Algorithmen und Kombinatorik Information 2 KP2SB. Gärtner, A. Steger, E. Welzl
KurzbeschreibungStudierende arbeiten gemeinsam mit Dozenten an offenen Fragen zu Themen aus Algorithmik und Kombinatorik.
LernzielZiel ist das Erlernen und Einüben wichtiger Forschungstechniken: Literaturrecherche, Verstehen und Präsentieren von Originalarbeiten, Ideenentwicklung in der Gruppe, Testen von Vermutungen mit Computerhilfe, Aufschreiben von Ergebnissen.
InhaltStudieren von Originalarbeiten und Bearbeiten offener Probleme aus den Bereichen Algorithmik und Kombinatorik.
SkriptNicht verfügbar.
LiteraturWird im Seminar und auf der zugehörigen Webseite angekündigt.
Voraussetzungen / BesonderesBestandene Kernfach-Vorlesung Algorithms, Probability, and Computing
263-4203-00LGeometry: Combinatorics and Algorithms Information 2 KP2SB. Gärtner, M. Hoffmann, E. Welzl
KurzbeschreibungThis seminar is held once a year and complements the course Geometry: 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 knowledge in (discrete and computational) geometry and graphs and algorithms is required. Thus, previous participation in the course "Geometry: Combinatorics & Algorithms" or a comparable course is strongly encouraged.
263-4205-00LPolynomials Information
Findet dieses Semester nicht statt.
4 KP2V + 1UE. Welzl
KurzbeschreibungAlgebraic methods belong among the most powerful and succesful mathematical tools in computer science and discrete mathematics. The course covers a number of results, some of them fairly recent, whose proofs illustrate general techniques.
LernzielExtending the knowledge of mathematical methods that proved useful in recent research related to theoretical computer science. The students should understand several successful ideas of applying the properties of multivariate polynomials to various problems.
InhaltFrom the wide area of algebraic methods, we focus mainly on applications of polynomials, and we will encounter some of the elementary concepts of algebraic geometry. Here are some of the main themes: Dimension arguments using spaces of polynomials. Matchings and determinants. Randomized testing of polynomial identities. Space partitions using polynomials and geometric incidence theorems. "Contagious vanishing" arguments, geometry of lines in space.
SkriptOne part of the lecture will follow the book "Thirty-three miniatures" by J. Matousek. The rest will be based on recent research papers and on a book in preparation by Larry Guth.
LiteraturJ. Matousek: Thirty-three miniatures, Amer. Math. Soc. 2010