Johannes Lengler: Katalogdaten im Herbstsemester 2021

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 Wird zum letzten Mal angeboten.	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; Kryptographie und Zero-Knowledge-Protokolle.
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.
252-4202-00L	Seminar in Theoretical Computer Science	2 KP	2S	E. Welzl, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, A. Steger, 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 restriction is: prior successful participation in a master level seminar in theoretical computer science.