Suchergebnis: Katalogdaten im Herbstsemester 2021
Informatik Master  | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 Master-Studium (Studienreglement 2020) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Ergänzungen | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Ergänzung in Theoretical Computer Science | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 252-0417-00L | Randomized Algorithms and Probabilistic Methods | W | 10 KP | 3V + 2U + 4A | A. Steger | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | Las 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 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lernziel | After 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Inhalt | Randomized 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Skript | Yes. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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-00L | Advanced Machine Learning | W | 10 KP | 3V + 2U + 4A | J. M. Buhmann, C. Cotrini Jimenez | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | Machine 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lernziel | Students 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Inhalt | The 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 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Skript | No lecture notes, but slides will be made available on the course webpage. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Literatur | C. 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 / Besonderes | The 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-1407-00L | Algorithmic Game Theory | W | 7 KP | 3V + 2U + 1A | P. Penna | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | Game 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lernziel | Learning 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Inhalt | The 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Skript | Lecture 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 / Besonderes | Audience: 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 252-1425-00L | Geometry: Combinatorics and Algorithms | W | 8 KP | 3V + 2U + 2A | B. Gärtner, E. Welzl, M. Hoffmann, M. Wettstein | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 263-4500-00L | Advanced Algorithms Takes place for the last time. | W | 9 KP | 3V + 2U + 3A | M. Ghaffari, G. Zuzic | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | This 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lernziel | This course familiarizes the students with some of the main tools and techniques in modern subareas of algorithm design. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Inhalt | The 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Skript | https://people.inf.ethz.ch/gmohsen/AA21/ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | This 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 401-3055-64L | Algebraic Methods in Combinatorics | W | 6 KP | 2V + 1U | B. Sudakov | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | Combinatorics is a fundamental mathematical discipline as well as an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. This course provides a gentle introduction to Algebraic methods, illustrated by examples and focusing on basic ideas and connections to other areas. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lernziel | The students will get an overview of various algebraic methods for solving combinatorial problems. We expect them to understand the proof techniques and to use them autonomously on related problems. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Inhalt | Combinatorics is a fundamental mathematical discipline as well as an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. While in the past many of the basic combinatorial results were obtained mainly by ingenuity and detailed reasoning, the modern theory has grown out of this early stage and often relies on deep, well-developed tools. One of the main general techniques that played a crucial role in the development of Combinatorics was the application of algebraic methods. The most fruitful such tool is the dimension argument. Roughly speaking, the method can be described as follows. In order to bound the cardinality of of a discrete structure A one maps its elements to vectors in a linear space, and shows that the set A is mapped to linearly independent vectors. It then follows that the cardinality of A is bounded by the dimension of the corresponding linear space. This simple idea is surprisingly powerful and has many famous applications. This course provides a gentle introduction to Algebraic methods, illustrated by examples and focusing on basic ideas and connections to other areas. The topics covered in the class will include (but are not limited to): Basic dimension arguments, Spaces of polynomials and tensor product methods, Eigenvalues of graphs and their application, the Combinatorial Nullstellensatz and the Chevalley-Warning theorem. Applications such as: Solution of Kakeya problem in finite fields, counterexample to Borsuk's conjecture, chromatic number of the unit distance graph of Euclidean space, explicit constructions of Ramsey graphs and many others. The course website can be found at https://moodle-app2.let.ethz.ch/course/view.php?id=15757 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Skript | Lectures will be on the blackboard only, but there will be a set of typeset lecture notes which follow the class closely. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | Students are expected to have a mathematical background and should be able to write rigorous proofs. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 401-3901-00L | Linear & Combinatorial Optimization | W | 11 KP | 4V + 2U | R. Zenklusen | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | Mathematical treatment of optimization techniques for linear and combinatorial optimization problems. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lernziel | The goal of this course is to get a thorough understanding of various classical mathematical optimization techniques for linear and combinatorial optimization problems, 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 such structural insights. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Inhalt | Key topics include: - Linear programming and polyhedra; - Flows and cuts; - Combinatorial optimization problems and polyhedral techniques; - Equivalence between optimization and separation. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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 / Besonderes | Solid background in linear algebra. Former course title: Mathematical Optimization. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kompetenzen |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Seite
1
von
1
