|
|
||||||||||
English
Deutsch
Theory of Computing
Theoretical Computer Science deals with the development of fundamental methods and concepts, sometimes of a speculative nature, for the science of processes and information (examples are computability, complexity, randomization, on-line computation, zero knowledge proofs, quantum computing, etc.). Theory is interdisciplinary in the sense that it bridges different disciplines in computer science, mathematics, operations research, physics, economics, etc.
These issues are dealt with in a formal manner that allows absolute statements (often relative to some hypothesis) of what cannot be done. On the other hand, very surprising positive results show up (e.g. probabilistically checkable proofs). Many of the question considered are motivated by applications, and it is part of the field to carry the insights back to applications via experimental and implementation work.
The program at ETH focuses on
- combinatorial and geometric algorithms,
- randomized algorithms and probabilistic methods,
- security and cryptography, and
- mathematical foundations of these topics.
Prerequisites (applicable to ETH Bachelor students in Computer Science only)
Passed:
|
Core Course |
Semester |
|
252-0209-00 Algorithms, Probability, and Computing* |
Autumn |
(* formerly 252-0200-00 Theory of Computing in Summer)
All other students should have a solid knowledge of the material from this course.
Focus
26 credits to be achieved as follows:
| 1) 3 out of the following courses: | |
| 252-0407-00 Cryptography | Autumn |
| 252-0417-00 Randomized Algorithms and Probabilistic Methods | Autumn |
|
252-1407-00 Algorithmic Game Theory |
Autumn |
|
252-0535-00 Machine Learning |
Autumn |
| 252-4125-00 Computational Geometry | Autumn |
| 252-0491-00 Satisfiability of Boolean Formulas - Combinatorics and Algorithms | Autumn |
|
252-1408-00 Graphs and Algorithms |
Spring |
| 227-0558-00 Principles of Distributed Systems | Spring |
ETH Bachelor Students in Computer Science who already passed courses from this list during their Bachelor studies can substitute each such course by any course listed under 3).
| 2) 2 out of the following seminars: | |
|
252-4700-00 Research Topics in Cryptography |
Autumn |
| 252-4202-00 Seminar Theoretical Computer Science |
Autumn / Spring |
|
263-4203-00 Geometric Graphs and Graph Drawing |
Autumn |
| 252-4102-00 Seminar on Randomized Algorithms and Probabilistic Methods | Spring |
|
252-3002-00 Algorithms for Database Systems |
Spring |
| 263-4200-00 Seminar SAT | Spring |
| 252-4201-00 Seminar Approximate Methods in Geometry |
Spring |
|
252-4800-00 Quantum Information and Cryptograhy |
Spring |
|
252-4302-00 Seminar Algorithmic Game Theory |
Spring |
| 3) Remaining Focus Credit to be acquired out of the following courses | |
|
252-1403-00 Einführung in die Quanteninformatik |
Autumn |
|
252-1409-00 Graphs and Algorithms: Advanced Topics |
Autumn |
|
252-4050-00 Complexity Theory |
Autumn |
| 252-0408-00 Cryptographic Protocols | Spring |
|
252-4206-00 Graph Drawing |
Spring |
|
252-4103-00 Topics in Random Graphs |
Spring |
|
252-0447-00 Topological Methods in Combinatorics and Geometry |
Spring |
|
263-4051-00 Complexity Theoretic Cryptography |
Spring |
|
252-4210-00 Discrete Geometry |
Spring |
|
252-1403-00 Einführung in die Quanteninformatik |
Spring |
All courses are given in English on demand, unless indicated otherwise.
Elective Courses
20 - 24 credits to be achieved.
Multidiscipline Courses
8 credits to be achieved.
HuSS Courses
2 credits to be achieved.
Master Thesis
The topic of the Master thesis has to be within the area of Theoretical Computer Science and must be accepted by the Mentor.
Professors involved
Angelika Steger, Emo Welzl, Peter Widmayer, Ueli Maurer, Stefan Wolf, Thomas Holenstein
Associated Professor
Juraj Hromkovic
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information
