Suchergebnis: Katalogdaten im Herbstsemester 2020

Informatik Master Information
Master-Studium (Studienreglement 2020)
Vertiefungen
Vertiefung in Theoretical Computer Science
Kernfächer
NummerTitelTypECTSUmfangDozierende
252-0417-00LRandomized Algorithms and Probabilistic Methods
Findet dieses Semester nicht statt.
W10 KP3V + 2U + 4AA. Steger
KurzbeschreibungLas Vegas & Monte Carlo algorithms; inequalities of Markov, Chebyshev, Chernoff; negative correlation; Markov chains: convergence, rapidly mixing; generating functions; Examples include: min cut, median, balls and bins, routing in hypercubes, 3SAT, card shuffling, random walks
LernzielAfter this course students will know fundamental techniques from probabilistic combinatorics for designing randomized algorithms and will be able to apply them to solve typical problems in these areas.
InhaltRandomized Algorithms are algorithms that "flip coins" to take certain decisions. This concept extends the classical model of deterministic algorithms and has become very popular and useful within the last twenty years. In many cases, randomized algorithms are faster, simpler or just more elegant than deterministic ones. In the course, we will discuss basic principles and techniques and derive from them a number of randomized methods for problems in different areas.
SkriptYes.
Literatur- Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (1995)
- Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)
252-0535-00LAdvanced Machine Learning Information W10 KP3V + 2U + 4AJ. M. Buhmann, C. Cotrini Jimenez
KurzbeschreibungMachine learning algorithms provide analytical methods to search data sets for characteristic patterns. Typical tasks include the classification of data, function fitting and clustering, with applications in image and speech analysis, bioinformatics and exploratory data analysis. This course is accompanied by practical machine learning projects.
LernzielStudents will be familiarized with advanced concepts and algorithms for supervised and unsupervised learning; reinforce the statistics knowledge which is indispensible to solve modeling problems under uncertainty. Key concepts are the generalization ability of algorithms and systematic approaches to modeling and regularization. Machine learning projects will provide an opportunity to test the machine learning algorithms on real world data.
InhaltThe theory of fundamental machine learning concepts is presented in the lecture, and illustrated with relevant applications. Students can deepen their understanding by solving both pen-and-paper and programming exercises, where they implement and apply famous algorithms to real-world data.

Topics covered in the lecture include:

Fundamentals:
What is data?
Bayesian Learning
Computational learning theory

Supervised learning:
Ensembles: Bagging and Boosting
Max Margin methods
Neural networks

Unsupservised learning:
Dimensionality reduction techniques
Clustering
Mixture Models
Non-parametric density estimation
Learning Dynamical Systems
SkriptNo lecture notes, but slides will be made available on the course webpage.
LiteraturC. Bishop. Pattern Recognition and Machine Learning. Springer 2007.

R. Duda, P. Hart, and D. Stork. Pattern Classification. John Wiley &
Sons, second edition, 2001.

T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical
Learning: Data Mining, Inference and Prediction. Springer, 2001.

L. Wasserman. All of Statistics: A Concise Course in Statistical
Inference. Springer, 2004.
Voraussetzungen / BesonderesThe course requires solid basic knowledge in analysis, statistics and numerical methods for CSE as well as practical programming experience for solving assignments.
Students should have followed at least "Introduction to Machine Learning" or an equivalent course offered by another institution.

PhD students are required to obtain a passing grade in the course (4.0 or higher based on project and exam) to gain credit points.
252-1425-00LGeometry: Combinatorics and Algorithms Information W8 KP3V + 2U + 2AB. Gärtner, E. Welzl, M. Hoffmann, M. Wettstein
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.
263-4500-00LAdvanced Algorithms Information W9 KP3V + 2U + 3AM. Ghaffari
KurzbeschreibungThis 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.
LernzielThis course familiarizes the students with some of the main tools and techniques in modern subareas of algorithm design.
InhaltThe lectures will cover a range of topics, tentatively 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, and derandomization.
SkriptLink
Voraussetzungen / BesonderesThis 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 highly recommended, though not required formally. If you are not sure whether you're ready for this class or not, please consult the instructor.
Wahlfächer
NummerTitelTypECTSUmfangDozierende
252-1407-00LAlgorithmic Game Theory Information W7 KP3V + 2U + 1AP. Penna
KurzbeschreibungGame theory provides a formal model to study the behavior and interaction of self-interested users and programs in large-scale distributed computer systems without central control. The course discusses algorithmic aspects of game theory.
LernzielLearning the basic concepts of game theory and mechanism design, acquiring the computational paradigm of self-interested agents, and using these concepts in the computational and algorithmic setting.
InhaltThe Internet is a typical example of a large-scale distributed computer system without central control, with users that are typically only interested in their own good. For instance, they are interested in getting high bandwidth for themselves, but don't care about others, and the same is true for computational load or download rates. Game theory provides a mathematical model for the behavior and interaction of such selfish users and programs. Classic game theory dates back to the 1930s and typically does not consider algorithmic aspects at all. Only a few years back, algorithms and game theory have been considered together, in an attempt to reconcile selfish behavior of independent agents with the common good.

This course discusses algorithmic aspects of game-theoretic models, with a focus on recent algorithmic and mathematical developments. Rather than giving an overview of such developments, the course aims to study selected important topics in depth.

Outline:
- Introduction to classic game-theoretic concepts.
- Existence of stable solutions (equilibria), algorithms for computing equilibria, computational complexity.
- Speed of convergence of natural game playing dynamics such as best-response dynamics or regret minimization.
- Techniques for bounding the quality-loss due to selfish behavior versus optimal outcomes under central control (a.k.a. the 'Price of Anarchy').
- Design and analysis of mechanisms that induce truthful behavior or near-optimal outcomes at equilibrium.
- Selected current research topics, such as Google's Sponsored Search Auction, the U.S. FCC Spectrum Auction, Kidney Exchange.
SkriptLecture notes will be usually posted on the website shortly after each lecture.
Literatur"Algorithmic Game Theory", edited by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge University Press, 2008;

"Game Theory and Strategy", Philip D. Straffin, The Mathematical Association of America, 5th printing, 2004

Several copies of both books are available in the Computer Science library.
Voraussetzungen / BesonderesAudience: Although this is a Computer Science course, we encourage the participation from all students who are interested in this topic.

Requirements: You should enjoy precise mathematical reasoning. You need to have passed a course on algorithms and complexity. No knowledge of game theory is required.
401-3054-14LProbabilistic Methods in Combinatorics Information W6 KP2V + 1UB. Sudakov
KurzbeschreibungThis course provides a gentle introduction to the Probabilistic Method, with an emphasis on methodology. We will try to illustrate the main ideas by showing the application of probabilistic reasoning to various combinatorial problems.
Lernziel
InhaltThe topics covered in the class will include (but are not limited to): linearity of expectation, the second moment method, the local lemma, correlation inequalities, martingales, large deviation inequalities, Janson and Talagrand inequalities and pseudo-randomness.
Literatur- The Probabilistic Method, by N. Alon and J. H. Spencer, 3rd Edition, Wiley, 2008.
- Random Graphs, by B. Bollobás, 2nd Edition, Cambridge University Press, 2001.
- Random Graphs, by S. Janson, T. Luczak and A. Rucinski, Wiley, 2000.
- Graph Coloring and the Probabilistic Method, by M. Molloy and B. Reed, Springer, 2002.
401-3901-00LMathematical OptimizationW11 KP4V + 2UR. Zenklusen
KurzbeschreibungMathematical treatment of diverse optimization techniques.
LernzielThe goal of this course is to get a thorough understanding of various classical mathematical optimization techniques with an emphasis on polyhedral approaches. In particular, we want students to develop a good understanding of some important problem classes in the field, of structural mathematical results linked to these problems, and of solution approaches based on this structural understanding.
InhaltKey topics include:
- Linear programming and polyhedra;
- Flows and cuts;
- Combinatorial optimization problems and techniques;
- Equivalence between optimization and separation;
- Brief introduction to Integer Programming.
Literatur- Bernhard Korte, Jens Vygen: Combinatorial Optimization. 6th edition, Springer, 2018.
- Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. This work has 3 volumes.
- Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
- Alexander Schrijver: Theory of Linear and Integer Programming. John Wiley, 1986.
Voraussetzungen / BesonderesSolid background in linear algebra.
401-4521-70LGeometric Tomography - Uniqueness, Statistical Reconstruction and Algorithms Information Belegung eingeschränkt - Details anzeigen W4 KP2VJ. Hörrmann
KurzbeschreibungSelf-contained course on the theoretical aspects of the reconstruction of geometric objects from tomographic projection and section data.
LernzielIntroduction to geometric tomography and understanding of various theoretical aspects of reconstruction problems.
InhaltThe problem of reconstruction of an object from geometric information like X-ray data is a classical inverse problem on the overlap between applied mathematics, statistics, computer science and electrical engineering. We focus on various aspects of the problem in the case of prior shape information on the reconstruction object. We will answer questions on uniqueness of the reconstruction and also cover statistical and algorithmic aspects.
LiteraturR. Gardner: Geometric Tomography
F. Natterer: The Mathematics of Computerized Tomography
A. Rieder: Keine Probleme mit inversen Problemen
Voraussetzungen / BesonderesA sound mathematical background in geometry, analysis and probability is required though a repetition of relevant material will be included. The ability to understand and write mathematical proofs is mandatory.
  •  Seite  1  von  1