Johannes Lengler: Katalogdaten im Herbstsemester 2021

NameHerr Prof. Dr. Johannes Lengler
Adresse
Informatik (Theoretische Inform.)
ETH Zürich, OAT Z 14.1
Andreasstrasse 5
8092 Zürich
SWITZERLAND
E-Mailjohannes.lengler@inf.ethz.ch
DepartementInformatik
BeziehungTitularprofessor

NummerTitelECTSUmfangDozierende
252-0851-00LAlgorithmen und Komplexität Information Belegung eingeschränkt - Details anzeigen
Wird zum letzten Mal angeboten.
4 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; Kryptographie und Zero-Knowledge-Protokolle.
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.
252-4202-00LSeminar in Theoretical Computer Science Information Belegung eingeschränkt - Details anzeigen 2 KP2SE. Welzl, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, A. Steger, D. Steurer, 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.
Voraussetzungen / BesonderesThis 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.