Peter Widmayer: Katalogdaten im Frühjahrssemester 2014

Auszeichnung: Die Goldene Eule
NameHerr Prof. em. Dr. Peter Widmayer
LehrgebietInformatik
Adresse
Inst. f. Theoretische Informatik
ETH Zürich, CAB H 39.2
Universitätstrasse 6
8092 Zürich
SWITZERLAND
E-Mailwidmayer@inf.ethz.ch
DepartementInformatik
BeziehungProfessor emeritus

NummerTitelECTSUmfangDozierende
252-0002-AALData Structures and Algorithms Belegung eingeschränkt - Details anzeigen
Die Lerneinheit kann nur von MSc Studierenden mit Zulassungsauflagen belegt werden.
7 KP15RP. Widmayer
KurzbeschreibungThis course is about fundamental algorithm design paradigms (such as induction, divide-and-conquer, backtracking, dynamic programming), classic algorithmic problems (such as sorting and searching), and data structures (such as lists, hashing, search trees). The connection between algorithms and data structures is explained for geometric and graph problems.
LernzielAn understanding of the design and analysis of fundamental algorithms and data structures.
Voraussetzungen / BesonderesThis is a self-study course. The relevant topics are those of the underlying course taught in the previous spring semester. A course summary with literature in English is provided at:

http://www.cadmo.ethz.ch/education/lectures/FS12/DA/
252-0002-00LDatenstrukturen & Algorithmen Information 7 KP4V + 2UP. Widmayer
KurzbeschreibungEs werden grundlegende Entwurfsmuster für Algorithmen (wie z.B. Induktion, divide-and-conquer, backtracking, dynamische Programmierung), klassische algorithmische Probleme (wie z.B. Suchen, Sortieren) und Datenstrukturen (wie z.B. Listen, Hashverfahren, Suchbäume) behandelt. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert.
LernzielVerständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen.
InhaltEs werden grundlegende Algorithmen und Datenstrukturen vorgestellt und analysiert. Dazu gehören auf der einen Seite Entwurfsmuster für Algorithmen, wie Induktion, divide-and-conquer, backtracking und dynamische Optimierung, ebenso wie klassische algorithmische Probleme, wie Suchen und Sortieren. Auf der anderen Seite werden Datenstrukturen für verschiedene Zwecke behandelt, darunter verkettete Listen, Hashtabellen, balancierte Suchbäume, verschiedene heaps und union-find-Strukturen. Weiterhin wird Adaptivität bei Datenstrukturen (wie etwa Splay-Bäume) und bei Algorithmen (wie etwa online-Algorithmen) beleuchtet. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert.
LiteraturTh. Ottmann, P.Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011
Voraussetzungen / BesonderesVoraussetzung:
252-0021-00L Einführung in die Programmierung
252-0934-00LAlgorithms and Complexity (FS) Information 1 KP1SP. Widmayer, J. Hromkovic
KurzbeschreibungThis seminar treats selected problems of current interest in the area of algorithms and complexity.
LernzielDevelop an understanding of selected problems of current interest in the area of algorithms and complexity.
InhaltThis seminar treats selected problems of current interest in the area of algorithms and complexity.
SkriptNone.
LiteraturResearch papers, to be chosen in the seminar.
Voraussetzungen / BesonderesPrerequisites: Basic understanding of algorithms and complexity.
252-3002-00LAlgorithms for Database Systems Information 2 KP2SP. Widmayer, D. Kossmann
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-4220-00LWie funktioniert Forschung? Algorithmen und Kombinatorik Information 2 KP2SB. Gärtner, J. Matousek, A. Steger, E. Welzl, P. Widmayer
KurzbeschreibungStudierende arbeiten gemeinsam mit Dozenten an offenen Fragen zu Themen aus Algorithmik und Kombinatorik.
LernzielZiel ist das Erlernen und Einüben wichtiger Forschungstechniken: Literaturrecherche, Verstehen und Präsentieren von Originalarbeiten, Ideenentwicklung in der Gruppe, Testen von Vermutungen mit Computerhilfe, Aufschreiben von Ergebnissen.
InhaltStudieren von Originalarbeiten und Bearbeiten offener Probleme aus den Bereichen Algorithmik und Kombinatorik.
SkriptNicht verfügbar.
LiteraturWird im Seminar und auf der zugehörigen Webseite angekündigt.
Voraussetzungen / BesonderesBestandene Basisprüfung.
252-4302-00LSeminar Algorithmic Game Theory Information 2 KP2SP. Widmayer, M. Mihalak
KurzbeschreibungIn the seminar we will get familiar with the current original research in the area of algorithmic game theory by reading and presenting selected research papers in that area.
LernzielDevelop an understanding of selected problems of current interest in the area of algorithmic game theory, and a practice of a scientific presentation.
InhaltStudy and understanding of selected topics of current interest in algorithmic game theory such as: Complexity Results (class PPAD, PLS, NP), Sponsored Search, Approximation Algorithms via Algorithmic Game Theory, Price of Anarchy, New paradigms of computation (e.g., envy-fee, truthful), Mechanism Design.
LiteraturSelected research articles.
Voraussetzungen / BesonderesYou must have passed our "Algorithmic Game Theory" class (or have acquired equivalent knowledge, in exceptional cases).