Suchergebnis: Katalogdaten im Frühjahrssemester 2018

Informatik Master Information
Vertiefungsfächer
Vertiefung in Theoretical Computer Science
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-4110-00LInterdisciplinary Algorithms Lab Information Belegung eingeschränkt - Details anzeigen
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, J. Lengler
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 steger@inf.ethz.ch explaining motivation and transcripts.
263-4310-00LLinear Algebra Methods in Combinatorics Information W5 KP2V + 2UP. Penna
KurzbeschreibungThis course describes the linear algebra bound technique also called dimension argument. To learn the technique we discuss several examples in combinatorics, geometry, and computer science. Besides this technique, the course aims at showing the mathematical elegance of certain proofs and the simplicity of the statements.
LernzielBecoming familiar with the method and being able to apply it to problems similar to those encountered during the course.
InhaltThis course is (essentially) about one single technique called the "linear algebra bound" (also known as "dimension argument"). We shall see several examples in combinatorics, geometry, and computer science and learn the technique throughout these examples. Towards the end of the course, we shall see the power of this method in proving rather amazing results (e.g., a circuit complexity lower bound, explicit constructions of Ramsey graphs, and a famous conjecture in geometry disproved). The course also aims at illustrating the main ideas behind the proofs and how the various problems are in fact connected to each other.
SkriptLecture notes of each single lecture will be made available (shortly after the lecture itself).
LiteraturMost of the material of the course is covered by the following book:

1. Linear algebra methods in combinatorics, by L. Babai and P. Frankl, Department of Computer Science, University of Chicago, preliminary version, 1992.

Some parts are also taken from

2. Extremal Combinatorics (with Applications in Computer Science), by Stasys Jukna, Springer-Verlag 2001.
263-4312-00LAdvanced Data Structures Information W5 KP2V + 2UP. Uznanski
KurzbeschreibungData structures play a central role in modern computer science and are essential building blocks in obtaining efficient algorithms. The course covers major results and research directions in data structures, that (mostly) have not yet made it into standard computer science curriculum.
LernzielLearning modern models of computation. Applying new algorithmic techniques to the construction of efficient data structures. Understanding techniques used in both lower- and upper- bound proofs on said data structures.
InhaltThis course will survey important developments in data structures that have not (yet) worked their way into the standard computer science curriculum.
Though we will cover state of the art techniques, the presentation is relatively self-contained, and only assumes a basic undergraduate data structures course (e.g., knowledge of binary search trees).

The course material includes (but is not exhausted by):
- computation models and memory models
- string indexing (suffix trees, suffix arrays)
- search trees
- static tree processing (Lowest Common Ancestor queries, Level Ancestry queries)
- range queries on arrays (queries for minimal element in a given range)
- integers-only data structures: how to sort integers in linear time, faster predecessor structures (van Emde Boas trees)
- hashing
- dynamic graphs connectivity
Voraussetzungen / BesonderesThis is a highly theoretical course. You should be comfortable with:
- algorithms and data structures
- probability

Completing Algorithms, Probability, and Computing course (252-0209-00L) is a good indicator.
272-0301-00LMethoden zum Entwurf von zufallsgesteuerten Algorithmen Information
Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik B n i c h t !
W4 KP2V + 1UH.‑J. Böckenhauer, D. Komm, R. Kralovic
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.
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 / BesonderesNOTICE: This course unit was previously offered as 252-1408-00L Graphs and Algorithms.
401-3903-11LGeometric Integer ProgrammingW6 KP2V + 1UR. Weismantel
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.
272-0300-00LAlgorithmik für schwere Probleme Information
Findet dieses Semester nicht statt.
Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik A n i c h t !
W4 KP2V + 1UJ. Hromkovic
KurzbeschreibungDiese Lerneinheit beschäftigt sich mit algorithmischen Ansätzen zur Lösung schwerer Probleme.
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.
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.
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.
  •  Seite  1  von  1