Angelika Steger: Katalogdaten im Herbstsemester 2018

Auszeichnung: Die Goldene Eule
NameFrau Prof. Dr. Angelika Steger
LehrgebietInformatik (Theoretische Informatik)
Adresse
Inst. f. Theoretische Informatik
ETH Zürich, OAT Z 27
Andreasstrasse 5
8092 Zürich
SWITZERLAND
E-Mailsteger@inf.ethz.ch
URLhttp://www.cadmo.ethz.ch/as/people/professor/asteger/index
DepartementInformatik
BeziehungOrdentliche Professorin

NummerTitelECTSUmfangDozierende
252-0209-00LAlgorithms, Probability, and Computing Information 8 KP4V + 2U + 1AE. Welzl, M. Ghaffari, A. Steger, D. Steurer, P. Widmayer
KurzbeschreibungAdvanced design and analysis methods for algorithms and data structures: Random(ized) Search Trees, Point Location, Minimum Cut, Linear Programming, Randomized Algebraic Algorithms (matchings), Probabilistically Checkable Proofs (introduction).
LernzielStudying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory.
SkriptWill be handed out.
LiteraturIntroduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest;
Randomized Algorithms by R. Motwani und P. Raghavan;
Computational Geometry - Algorithms and Applications by M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf.
252-0417-00LRandomized Algorithms and Probabilistic Methods8 KP3V + 2U + 2AA. Steger
KurzbeschreibungLas 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
LernzielAfter 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.
InhaltRandomized 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.
SkriptYes.
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-0851-00LAlgorithmen und Komplexität4 KP2V + 1UJ. Lengler, A. Steger
KurzbeschreibungEinführung: RAM-Maschine, Datenstrukturen; Algorithmen: Sortieren, Medianbest., Matrixmultiplikation, kürzeste Pfade, min. spann. Bäume; Paradigmen: Divide&Conquer, dynam. Programmierung, Greedy; Datenstrukturen: Suchbäume, Wörterbücher, Priority Queues; Komplexitätstheorie: Klassen P und NP, NP-vollständig, Satz von Cook, Beispiele für Reduktionen.
LernzielNach dieser Vorlesung kennen die Studierenden einige Algorithmen und übliche Werkzeuge. Sie kennen die Grundlagen der Komplexitätstheorie und können diese verwenden um Probleme zu klassifizieren.
InhaltDie Vorlesung behandelt den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Die zentralen Themengebiete sind: Sortieralgorithmen, Effiziente Datenstrukturen, Algorithmen für Graphen und Netzwerke, Paradigmen des Algorithmenentwurfs, Klassen P und NP, NP-Vollständigkeit, Approximationsalgorithmen.
SkriptJa. Wird zu Beginn des Semesters verteilt.
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.
2 KP2SE. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, B. Sudakov
KurzbeschreibungPräsentation wichtiger und aktueller Arbeiten aus der theoretischen Informatik, sowie eigener Ergebnisse von Diplomanden und Doktoranden.
LernzielDas Lernziel ist, Studierende an die aktuelle Forschung heranzuführen und sie in die Lage zu versetzen, wissenschaftliche Arbeiten zu lesen, zu verstehen, und zu präsentieren.
263-0006-00LAlgorithms Lab
Only for master students, otherwise a special permission by the student administration of D-INFK is required.
8 KP4P + 3AA. Steger, E. Welzl, P. Widmayer
KurzbeschreibungStudents learn how to solve algorithmic problems given by a textual description (understanding problem setting, finding appropriate modeling, choosing suitable algorithms, and implementing them). Knowledge of basic algorithms and data structures is assumed; more advanced material and usage of standard libraries for combinatorial algorithms are introduced in tutorials.
LernzielThe objective of this course is to learn how to solve algorithmic problems given by a textual description. This includes appropriate problem modeling, choice of suitable (combinatorial) algorithms, and implementing them (using C/C++, STL, CGAL, and BGL).
LiteraturT. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1990.
J. Hromkovic, Teubner: Theoretische Informatik, Springer, 2004 (English: Theoretical Computer Science, Springer 2003).
J. Kleinberg, É. Tardos: Algorithm Design, Addison Wesley, 2006.
H. R. Lewis, C. H. Papadimitriou: Elements of the Theory of Computation, Prentice Hall, 1998.
T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum, 2012.
R. Sedgewick: Algorithms in C++: Graph Algorithms, Addison-Wesley, 2001.
263-4110-00LInterdisciplinary Algorithms Lab Information Belegung eingeschränkt - Details anzeigen
Maximale Teilnehmerzahl: 12

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.
5 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.