Johannes Lengler: Katalogdaten im Herbstsemester 2019

Name	Herr Prof. Dr. Johannes Lengler
Adresse	Informatik (Theoretische Inform.) ETH Zürich, OAT Z 14.1 Andreasstrasse 5 8092 Zürich SWITZERLAND
E-Mail	johannes.lengler@inf.ethz.ch
Departement	Informatik
Beziehung	Titularprofessor

Nummer	Titel	ECTS	Umfang	Dozierende
252-0851-00L	Algorithmen und Komplexität	4 KP	2V + 1U	J. Lengler, A. Steger
Kurzbeschreibung	Einfü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.
Lernziel	Nach 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.
Inhalt	Die 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.
Skript	Ja. Wird zu Beginn des Semesters verteilt.
252-4202-00L	Seminar in Theoretical Computer Science	2 KP	2S	A. Steger, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, D. Steurer, B. Sudakov
Kurzbeschreibung	Präsentation wichtiger und aktueller Arbeiten aus der theoretischen Informatik, sowie eigener Ergebnisse von Diplomanden und Doktoranden.
Lernziel	Das 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.
Voraussetzungen / Besonderes	This 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.)