Suchergebnis: Katalogdaten im Frühjahrssemester 2019

Informatik Master Information
Vertiefungsfächer
Vertiefung in Theoretical Computer Science
Kernfächer der Vertiefung in Theoretical Computer Science
NummerTitelTypECTSUmfangDozierende
252-0407-00LCryptography Foundations Information
Takes place the last time in this form.
W7 KP3V + 2U + 1AU. Maurer
KurzbeschreibungFundamentals 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.
LernzielThe 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.
InhaltSee course description.
Skriptyes.
Voraussetzungen / BesonderesFamiliarity 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-00LOptimization for Data Science Information W8 KP3V + 2U + 2AB. Gärtner, D. Steurer
KurzbeschreibungThis course teaches an overview of modern optimization methods, with applications in particular for machine learning and data science.
LernzielUnderstanding 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.
InhaltThis 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 / BesonderesAs 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
NummerTitelTypECTSUmfangDozierende
252-0408-00LCryptographic Protocols Information W5 KP2V + 2UM. Hirt, U. Maurer
KurzbeschreibungThe 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.
LernzielIndroduction to a very active research area with many gems and paradoxical
results. Spark interest in fundamental problems.
InhaltThe 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.
Skriptthe 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 / BesonderesA 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-00LInvitation to Quantum Informatics Information W3 KP2VS. Wolf
KurzbeschreibungNach 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.
LernzielDas 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.
InhaltGemä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-00LModels of ComputationW6 KP2V + 2U + 1AM. Cook
KurzbeschreibungThis 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.
LernzielThe 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.
InhaltThis 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-00LMassively Parallel Algorithms Information W6 KP2V + 1U + 2AM. Ghaffari
KurzbeschreibungData 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.
LernzielThis 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.
InhaltThe 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 / BesonderesThe 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-00LAlgorithmik für schwere Probleme Information
Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik A n i c h t !
W4 KP2V + 1UH.‑J. Böckenhauer, R. Kralovic
KurzbeschreibungDiese 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.
LernzielAuf systematische Weise eine Übersicht über die Methoden zur Lösung schwerer Probleme kennen lernen. Vertiefte Kenntnisse im Bereich exakter und parameterisierter Algorithmen erwerben.
InhaltZuerst 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.
SkriptUnterlagen und Folien werden zur Verfügung gestellt.
LiteraturJ. 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-00LApproximations- und Online-Algorithmen Information W4 KP2V + 1UH.‑J. Böckenhauer, D. Komm
KurzbeschreibungDiese Lerneinheit behandelt approximative Verfahren für schwere Optimierungsprobleme und algorithmische Ansätze zur Lösung von Online-Problemen sowie die Grenzen dieser Ansätze.
LernzielAuf 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.
InhaltApproximationsalgorithmen 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.
LiteraturDie 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-05LGraph Theory Information W5 KP2V + 1UB. Sudakov
KurzbeschreibungBasic 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
LernzielThe 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.
SkriptLecture will be only at the blackboard.
LiteraturWest, D.: "Introduction to Graph Theory"
Diestel, R.: "Graph Theory"

Further literature links will be provided in the lecture.
Voraussetzungen / BesonderesStudents 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-11LGeometric Integer ProgrammingW6 KP2V + 1UR. Weismantel, J. Paat, M. Schlöter
KurzbeschreibungInteger 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.
LernzielThe purpose of the lecture is to provide a geometric treatment of the theory of integer optimization.
InhaltKey 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.
Skriptnot available, blackboard presentation
LiteraturBertsimas, 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-00LCombinatorial Optimization Information W6 KP2V + 1UR. Zenklusen
KurzbeschreibungCombinatorial 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.
LernzielThe 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.
InhaltKey topics include:
- Polyhedral descriptions;
- Combinatorial uncrossing;
- Ellipsoid method;
- Equivalence between separation and optimization;
- Design of efficient approximation algorithms for hard problems.
SkriptLecture 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 / BesonderesPrior 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-00LInterdisciplinary Algorithms Lab Belegung eingeschränkt - Details anzeigen
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.
W5 KP2PA. Steger, D. Steurer
KurzbeschreibungIn this course students will develop solutions for algorithmic problems posed by researchers from other fields.
LernzielStudents 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 / BesonderesStudents 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-00LMethoden zum Entwurf von zufallsgesteuerten Algorithmen Information
Findet dieses Semester nicht statt.
Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik B n i c h t !
W4 KP2V + 1U
KurzbeschreibungDie 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.
LernzielThematische 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
SkriptJ. Hromkovic: Randomisierte Algorithmen, Teubner 2004.

J.Hromkovic: Design and Analysis of Randomized Algorithms. Springer 2006.

J.Hromkovic: Algorithmics for Hard Problems, Springer 2004.
LiteraturJ. 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
NummerTitelTypECTSUmfangDozierende
252-3002-00LAlgorithms for Database Systems Information
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.
W2 KP2SP. Penna
KurzbeschreibungQuery processing, optimization, stream-based systems, distributed and parallel databases, non-standard databases.
LernzielDevelop an understanding of selected problems of current interest in the area of algorithms for database systems.
252-4102-00LSeminar 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.
W2 KP2SA. Steger
KurzbeschreibungThe 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).
LernzielRead papers from the forefront of today's research; learn how to give a scientific talk.
Voraussetzungen / BesonderesThe 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-00LSeminar in Theoretical Computer Science Information
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.
W2 KP2SA. Steger, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, D. Steurer, 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.
Voraussetzungen / BesonderesThis 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-00LGeometry: Combinatorics and Algorithms Information
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.
W2 KP2SB. Gärtner, M. Hoffmann, C.‑H. Liu, M. Wettstein
KurzbeschreibungThis seminar complements the course Geometry: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent.
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.
InhaltThis 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 / BesonderesPrerequisite: Successful participation in the course "Geometry: Combinatorics & Algorithms" (takes place every HS) is required.
  •  Seite  1  von  1