Suchergebnis: Katalogdaten im Frühjahrssemester 2019
Informatik Master | ||||||
Vertiefungsfächer | ||||||
Vertiefung in Theoretical Computer Science | ||||||
Kernfächer der Vertiefung in Theoretical Computer Science | ||||||
Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |
---|---|---|---|---|---|---|
252-0407-00L | Cryptography Foundations Takes place the last time in this form. | W | 7 KP | 3V + 2U + 1A | U. Maurer | |
Kurzbeschreibung | Fundamentals and applications of cryptography. Cryptography as a mathematical discipline: reductions, constructive cryptography paradigm, security proofs. The discussed primitives include cryptographic functions, pseudo-randomness, symmetric encryption and authentication, public-key encryption, key agreement, and digital signature schemes. Selected cryptanalytic techniques. | |||||
Lernziel | The goals are: (1) understand the basic theoretical concepts and scientific thinking in cryptography; (2) understand and apply some core cryptographic techniques and security proof methods; (3) be prepared and motivated to access the scientific literature and attend specialized courses in cryptography. | |||||
Inhalt | See course description. | |||||
Skript | yes. | |||||
Voraussetzungen / Besonderes | Familiarity with the basic cryptographic concepts as treated for example in the course "Information Security" is required but can in principle also be acquired in parallel to attending the course. | |||||
261-5110-00L | Optimization for Data Science | W | 8 KP | 3V + 2U + 2A | B. Gärtner, D. Steurer | |
Kurzbeschreibung | This course teaches an overview of modern optimization methods, with applications in particular for machine learning and data science. | |||||
Lernziel | Understanding the theoretical and practical aspects of relevant optimization methods used in data science. Learning general paradigms to deal with optimization problems arising in data science. | |||||
Inhalt | This course teaches an overview of modern optimization methods, with applications in particular for machine learning and data science. In the first part of the course, we will discuss how classical first and second order methods such as gradient descent and Newton's method can be adapated to scale to large datasets, in theory and in practice. We also cover some new algorithms and paradigms that have been developed specifically in the context of data science. The emphasis is not so much on the application of these methods (many of which are covered in other courses), but on understanding and analyzing the methods themselves. In the second part, we discuss convex programming relaxations as a powerful and versatile paradigm for designing efficient algorithms to solve computational problems arising in data science. We will learn about this paradigm and develop a unified perspective on it through the lens of the sum-of-squares semidefinite programming hierarchy. As applications, we are discussing non-negative matrix factorization, compressed sensing and sparse linear regression, matrix completion and phase retrieval, as well as robust estimation. | |||||
Voraussetzungen / Besonderes | As background, we require material taught in the course "252-0209-00L Algorithms, Probability, and Computing". It is not necessary that participants have actually taken the course, but they should be prepared to catch up if necessary. | |||||
Wahlfächer der Vertiefung in Theoretical Computer Science | ||||||
Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |
252-0408-00L | Cryptographic Protocols | W | 5 KP | 2V + 2U | M. Hirt, U. Maurer | |
Kurzbeschreibung | The course presents a selection of hot research topics in cryptography. The choice of topics varies and may include provable security, interactive proofs, zero-knowledge protocols, secret sharing, secure multi-party computation, e-voting, etc. | |||||
Lernziel | Indroduction to a very active research area with many gems and paradoxical results. Spark interest in fundamental problems. | |||||
Inhalt | The course presents a selection of hot research topics in cryptography. The choice of topics varies and may include provable security, interactive proofs, zero-knowledge protocols, secret sharing, secure multi-party computation, e-voting, etc. | |||||
Skript | the lecture notes are in German, but they are not required as the entire course material is documented also in other course material (in english). | |||||
Voraussetzungen / Besonderes | A basic understanding of fundamental cryptographic concepts (as taught for example in the course Information Security or in the course Cryptography Foundations) is useful, but not required. | |||||
252-1403-00L | Invitation to Quantum Informatics | W | 3 KP | 2V | S. Wolf | |
Kurzbeschreibung | Nach einer Einführung wichtiger Grundbegriffe der Quantenphysik, wie etwa Überlagerung, Interferenz und Verschränkung, werden verschiedene Themen behandelt: Quantenalgorithmen, Teleportation, Quanten-Kommunikationskomplexität und "Pseudo-Telepathie", Quantenkryptographie sowie die Grundzüge der Quanten-Informationstheorie. | |||||
Lernziel | Das Ziel dieser Vorlesung ist es, mit den wichtigsten Begriffen vetraut zu werden, welche fuer die Verbindung zwischen Information und Physik wichtig sind. Der Grundformalismus des Quantenphysik soll erarbeitet, und der Einsatz der entsprechenden Gesetze fuer die Informationsverarbeitung verstanden werden. Insbesondere sollen wichtige Algorithmen dargelegt und analysiert werden, wie der Grover- sowie der Shor-Algorithmus. | |||||
Inhalt | Gemäss Landauer kann Information und ihre Verarbeitung nicht völlig losgelöst von der physikalischen Repräsentation betrachtet werden. Die Quanteninformatik befasst sich mit den Konsequenzen und Möglichkeiten der quantenphysikalischen Gesetze für die Informationsverarbeitung. Nach einer Einführung wichtiger Grundbegriffe der Quantenphysik, wie etwa Überlagerung, Interferenz und Verschränkung, werden verschiedene Themen behandelt: Quantenalgorithmen, Teleportation, Quanten-Kommunikationskomplexität und "Pseudo-Telepathie", Quantenkryptographie sowie die Grundzüge der Quanten-Informationstheorie. | |||||
252-1424-00L | Models of Computation | W | 6 KP | 2V + 2U + 1A | M. Cook | |
Kurzbeschreibung | This course surveys many different models of computation: Turing Machines, Cellular Automata, Finite State Machines, Graph Automata, Circuits, Tilings, Lambda Calculus, Fractran, Chemical Reaction Networks, Hopfield Networks, String Rewriting Systems, Tag Systems, Diophantine Equations, Register Machines, Primitive Recursive Functions, and more. | |||||
Lernziel | The goal of this course is to become acquainted with a wide variety of models of computation, to understand how models help us to understand the modeled systems, and to be able to develop and analyze models appropriate for new systems. | |||||
Inhalt | This course surveys many different models of computation: Turing Machines, Cellular Automata, Finite State Machines, Graph Automata, Circuits, Tilings, Lambda Calculus, Fractran, Chemical Reaction Networks, Hopfield Networks, String Rewriting Systems, Tag Systems, Diophantine Equations, Register Machines, Primitive Recursive Functions, and more. | |||||
263-4506-00L | Massively Parallel Algorithms | W | 6 KP | 2V + 1U + 2A | M. Ghaffari | |
Kurzbeschreibung | Data sizes are growing faster than the capacities of single processors. This makes it almost a certainty that the future of computation will rely on parallelism. In this new graduate-level course, we discuss the expanding body of work on the theoretical foundations of modern parallel computation, with an emphasis on the algorithmic tools and techniques for large-scale processing. | |||||
Lernziel | This course will familiarize the students with the algorithmic tools and techniques in modern parallel computation. In particular, we will discuss the growing body of algorithmic results in the Massively Parallel Computation (MPC) model. This model is a mathematical abstraction of some of the popular large-scale processing settings such as MapReduce, Hadoop, Spark, etc. By the end of the semester, the students will know all the standard tools of this area, as well as the state of the art on a number of the central problems. Our hope is that the course prepares the students for independent research at the frontier of this area, and we will attempt to move in that direction with the course projects. The course assumes no particular familiarity with parallel computation and should be accesible to any student with sufficient theoretical/algorithmic background. In particular, we expect that all students are comfortable with the basics of algorithmics designs and analysis, as well as probability theory. | |||||
Inhalt | The course will cover a sampling of the recent developments (and open questions) at the frontier of research in massively/modern parallel computation. the material will be based on compilation of recent papers on this area, which will be provided throughout the semester. | |||||
Voraussetzungen / Besonderes | The class does not expect any prior knowledge in parallel algorithms/computing. Our only prerequisite is the undergraduate class Algorithms, Probability, and Computing (APC) or any other course that can be seen as the equivalent. In particular, much of waht we will discuss uses randomized algorithms and therefore, we will assume that the students are familiar with the tools and techniques in randomized algorithms and analysis (to the extent covered in the APC class). | |||||
272-0300-00L | Algorithmik für schwere Probleme Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik A n i c h t ! | W | 4 KP | 2V + 1U | H.‑J. Böckenhauer, R. Kralovic | |
Kurzbeschreibung | Diese Lerneinheit beschäftigt sich mit algorithmischen Ansätzen zur Lösung schwerer Probleme, insbesondere mit exakten Algorithmen mit moderat exponentieller Laufzeit und parametrisierten Algorithmen. Eine umfassende Reflexion über die Bedeutung der vorgestellten Ansätze für den Informatikunterricht an Gymnasien begleitet den Kurs. | |||||
Lernziel | Auf systematische Weise eine Übersicht über die Methoden zur Lösung schwerer Probleme kennen lernen. Vertiefte Kenntnisse im Bereich exakter und parameterisierter Algorithmen erwerben. | |||||
Inhalt | Zuerst wird der Begriff der Berechnungsschwere erläutert (für die Informatikstudierenden wiederholt). Dann werden die Methoden zur Lösung schwerer Probleme systematisch dargestellt. Bei jeder Algorithmenentwurfsmethode wird vermittelt, was sie uns garantiert und was sie nicht sichern kann und womit wir für die gewonnene Effizienz bezahlen. Ein Schwerpunkt liegt auf exakten Algorithmen mit moderat exponentieller Laufzeit und auf parametrisierten Algorithmen. | |||||
Skript | Unterlagen und Folien werden zur Verfügung gestellt. | |||||
Literatur | J. Hromkovic: Algorithmics for Hard Problems, Springer 2004. R. Niedermeier: Invitation to Fixed-Parameter Algorithms, 2006. M. Cygan et al.: Parameterized Algorithms, 2015. F. Fomin, D. Kratsch: Exact Exponential Algorithms, 2010. | |||||
272-0302-00L | Approximations- und Online-Algorithmen | W | 4 KP | 2V + 1U | H.‑J. Böckenhauer, D. Komm | |
Kurzbeschreibung | Diese Lerneinheit behandelt approximative Verfahren für schwere Optimierungsprobleme und algorithmische Ansätze zur Lösung von Online-Problemen sowie die Grenzen dieser Ansätze. | |||||
Lernziel | Auf systematische Weise einen Überblick über die verschiedenen Entwurfsmethoden von approximativen Verfahren für schwere Optimierungsprobleme und Online-Probleme zu gewinnen. Methoden kennenlernen, die Grenzen dieser Ansätze aufweisen. | |||||
Inhalt | Approximationsalgorithmen sind einer der erfolgreichsten Ansätze zur Behandlung schwerer Optimierungsprobleme. Dabei untersucht man die sogenannte Approximationsgüte, also das Verhältnis der Kosten einer berechneten Näherungslösung und der Kosten einer (nicht effizient berechenbaren) optimalen Lösung. Bei einem Online-Problem ist nicht die gesamte Eingabe von Anfang an bekannt, sondern sie erscheint stückweise und für jeden Teil der Eingabe muss sofort ein entsprechender Teil der endgültigen Ausgabe produziert werden. Die Güte eines Algorithmus für ein Online-Problem misst man mit der competitive ratio, also dem Verhältnis der Kosten der berechneten Lösung und der Kosten einer optimalen Lösung, wie man sie berechnen könnte, wenn die gesamte Eingabe bekannt wäre. Inhalt dieser Lerneinheit sind - die Klassifizierung von Optimierungsproblemen nach der erreichbaren Approximationsgüte, - systematische Methoden zum Entwurf von Approximationsalgorithmen (z. B. Greedy-Strategien, dynamische Programmierung, LP-Relaxierung), - Methoden zum Nachweis der Nichtapproximierbarkeit, - klassische Online-Probleme wie Paging oder Scheduling-Probleme und Algorithmen zu ihrer Lösung, - randomisierte Online-Algorithmen, - Entwurfs- und Analyseverfahren für Online-Algorithmen, - Grenzen des "competitive ratio"- Modells und Advice-Komplexität als eine Möglichkeit, die Komplexität von Online-Problemen genauer zu messen. | |||||
Literatur | Die Vorlesung orientiert sich teilweise an folgenden Büchern: J. Hromkovic: Algorithmics for Hard Problems, Springer, 2004 D. Komm: An Introduction to Online Computation: Determinism, Randomization, Advice, Springer, 2016 Zusätzliche Literatur: A. Borodin, R. El-Yaniv: Online Computation and Competitive Analysis, Cambridge University Press, 1998 | |||||
401-3052-05L | Graph Theory | W | 5 KP | 2V + 1U | B. Sudakov | |
Kurzbeschreibung | Basic notions, trees, spanning trees, Caley's formula, vertex and edge connectivity, blocks, 2-connectivity, Mader's theorem, Menger's theorem, Eulerian graphs, Hamilton cycles, Dirac's theorem, matchings, theorems of Hall, König and Tutte, planar graphs, Euler's formula, basic non-planar graphs, graph colorings, greedy colorings, Brooks' theorem, 5-colorings of planar graphs | |||||
Lernziel | The students will get an overview over the most fundamental questions concerning graph theory. We expect them to understand the proof techniques and to use them autonomously on related problems. | |||||
Skript | Lecture will be only at the blackboard. | |||||
Literatur | West, D.: "Introduction to Graph Theory" Diestel, R.: "Graph Theory" Further literature links will be provided in the lecture. | |||||
Voraussetzungen / Besonderes | Students are expected to have a mathematical background and should be able to write rigorous proofs. NOTICE: This course unit was previously offered as 252-1408-00L Graphs and Algorithms. | |||||
401-3903-11L | Geometric Integer Programming | W | 6 KP | 2V + 1U | R. Weismantel, J. Paat, M. Schlöter | |
Kurzbeschreibung | Integer programming is the task of minimizing a linear function over all the integer points in a polyhedron. This lecture introduces the key concepts of an algorithmic theory for solving such problems. | |||||
Lernziel | The purpose of the lecture is to provide a geometric treatment of the theory of integer optimization. | |||||
Inhalt | Key topics are: - lattice theory and the polynomial time solvability of integer optimization problems in fixed dimension, - the theory of integral generating sets and its connection to totally dual integral systems, - finite cutting plane algorithms based on lattices and integral generating sets. | |||||
Skript | not available, blackboard presentation | |||||
Literatur | Bertsimas, Weismantel: Optimization over Integers, Dynamic Ideas 2005. Schrijver: Theory of linear and integer programming, Wiley, 1986. | |||||
Voraussetzungen / Besonderes | "Mathematical Optimization" (401-3901-00L) | |||||
401-4904-00L | Combinatorial Optimization | W | 6 KP | 2V + 1U | R. Zenklusen | |
Kurzbeschreibung | Combinatorial Optimization deals with efficiently finding a provably strong solution among a finite set of options. This course discusses key combinatorial structures and techniques to design efficient algorithms for combinatorial optimization problems. We put a strong emphasis on polyhedral methods, which proved to be a powerful and unifying tool throughout combinatorial optimization. | |||||
Lernziel | The goal of this lecture is to get a thorough understanding of various modern combinatorial optimization techniques with an emphasis on polyhedral approaches. Students will learn a general toolbox to tackle a wide range of combinatorial optimization problems. | |||||
Inhalt | Key topics include: - Polyhedral descriptions; - Combinatorial uncrossing; - Ellipsoid method; - Equivalence between separation and optimization; - Design of efficient approximation algorithms for hard problems. | |||||
Skript | Lecture notes will be available online. | |||||
Literatur | - Bernhard Korte, Jens Vygen: Combinatorial Optimization. 5th edition, Springer, 2012. - Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003. This work has 3 volumes. | |||||
Voraussetzungen / Besonderes | Prior exposure to Linear Programming can greatly help the understanding of the material. We therefore recommend that students interested in Combinatorial Optimization get familiarized with Linear Programming before taking this lecture. | |||||
263-4110-00L | Interdisciplinary Algorithms Lab Findet dieses Semester nicht statt. Im Masterstudium können zusätzlich zu den Vertiefungsübergreifenden Fächern nur max. 10 KP mit Laboratorien erarbeitet werden. Weitere Labs werden auf dem Beiblatt aufgeführt. | W | 5 KP | 2P | A. Steger, D. Steurer | |
Kurzbeschreibung | In this course students will develop solutions for algorithmic problems posed by researchers from other fields. | |||||
Lernziel | Students will learn that in order to tackle algorithmic problems from an interdisciplinary or applied context one needs to combine a solid understanding of algorithmic methodology with insights into the problem at hand to judge which side constraints are essential and which can be loosened. | |||||
Voraussetzungen / Besonderes | Students will work in teams. Ideally, skills of team members complement each other. Interested Bachelor students can apply for participation by sending an email to Link explaining motivation and transcripts. | |||||
272-0301-00L | Methoden zum Entwurf von zufallsgesteuerten Algorithmen Findet dieses Semester nicht statt. Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik B n i c h t ! | W | 4 KP | 2V + 1U | ||
Kurzbeschreibung | Die Studierenden sollen die Entwicklung unserer Vorstellung über Zufall und dessen Rolle verfolgen. Mit Grundkenntnissen der Wahrscheinlichkeitstheorie und grundlegender Arithmetik sollen sie entdecken, dass Zufallssteuerung ein Mittel zur Erreichung unglaublicher Effizienz von Prozessen werden kann. Das Ziel ist, die Methodik des Entwurfs von zufallsgesteuerten Algorithmen zu vermitteln. | |||||
Lernziel | Thematische Schwerpunkte - Modellierung und Klassifizierung von randomisierten Algorithmen - Die Methode der Überlistung des Gegners: Hashing und randomisierte Online-Algorithmen - Die Methode der Fingerabdrücke: Kommunikationsprotokolle - Die Methode der häufigen Zeugen: randomisierter Primzahltest von Solovay und Strassen - Wahrscheinlichkeitsverstärkung durch Wiederholung - Randomisierte Algorithmen für Optimierungsprobleme | |||||
Skript | J. Hromkovic: Randomisierte Algorithmen, Teubner 2004. J.Hromkovic: Design and Analysis of Randomized Algorithms. Springer 2006. J.Hromkovic: Algorithmics for Hard Problems, Springer 2004. | |||||
Literatur | J. Hromkovic: Randomisierte Algorithmen, Teubner 2004. J.Hromkovic: Design and Analysis of Randomized Algorithms. Springer 2006. J.Hromkovic: Algorithmics for Hard Problems, Springer 2004. | |||||
Seminar in Theoretical Computer Science | ||||||
Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |
252-3002-00L | Algorithms for Database Systems Limited number of participants. The deadline for deregistering expires at the end of the second week of the semester. Students who are still registered after that date, but do not attend the seminar, will officially fail the seminar. | W | 2 KP | 2S | P. Penna | |
Kurzbeschreibung | Query processing, optimization, stream-based systems, distributed and parallel databases, non-standard databases. | |||||
Lernziel | Develop an understanding of selected problems of current interest in the area of algorithms for database systems. | |||||
252-4102-00L | Seminar on Randomized Algorithms and Probabilistic Methods The deadline for deregistering expires at the end of the second week of the semester. Students who are still registered after that date, but do not attend the seminar, will officially fail the seminar. | W | 2 KP | 2S | A. Steger | |
Kurzbeschreibung | The aim of the seminar is to study papers which bring the students to the forefront of today's research topics. This semester we will study selected papers of the conference Symposium on Discrete Algorithms (SODA18). | |||||
Lernziel | Read papers from the forefront of today's research; learn how to give a scientific talk. | |||||
Voraussetzungen / Besonderes | The seminar is open for both students from mathematics and students from computer science. As prerequisite we require that you passed the course Randomized Algorithms and Probabilistic Methods (or equivalent, if you come from abroad). | |||||
252-4202-00L | Seminar in Theoretical Computer Science The deadline for deregistering expires at the end of the second week of the semester. Students who are still registered after that date, but do not attend the seminar, will officially fail the seminar. | W | 2 KP | 2S | A. Steger, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, D. Steurer, B. Sudakov | |
Kurzbeschreibung | Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates. | |||||
Lernziel | To get an overview of current research in the areas covered by the involved research groups. To present results from the literature. | |||||
Voraussetzungen / Besonderes | This seminar takes place as part of the joint research seminar of several theory groups. Intended participation is for students with excellent performance only. Formal minimal requirement is passing of one of the courses Algorithms, Probability, and Computing, Randomized Algorithms and Probabilistic Methods, Geometry: Combinatorics and Algorithms, Advanced Algorithms. (If you cannot fulfill this restriction, because this is your first term at ETH, but you believe that you satisfy equivalent criteria, please send an email with a detailed description of your reasoning to the organizers of the seminar.) | |||||
263-4203-00L | Geometry: Combinatorics and Algorithms The deadline for deregistering expires at the end of the second week of the semester. Students who are still registered after that date, but do not attend the seminar, will officially fail the seminar. | W | 2 KP | 2S | B. Gärtner, M. Hoffmann, C.‑H. Liu, M. Wettstein | |
Kurzbeschreibung | This seminar complements the course Geometry: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent. | |||||
Lernziel | Each 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. | |||||
Inhalt | This 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. | |||||
Voraussetzungen / Besonderes | Prerequisite: Successful participation in the course "Geometry: Combinatorics & Algorithms" (takes place every HS) is required. |
- Seite 1 von 1