Dennis Komm: Katalogdaten im Frühjahrssemester 2020

Name	Herr Prof. Dr. Dennis Komm
Lehrgebiet	Algorithmen und Didaktik
Adresse	Professur Algorithmen und Didaktik ETH Zürich, CAB F 10.1 Universitätstrasse 6 8092 Zürich SWITZERLAND
Telefon	+41 44 632 82 23
E-Mail	dennis.komm@inf.ethz.ch
URL	https://people.inf.ethz.ch/dkomm/
Departement	Informatik
Beziehung	Ausserordentlicher Professor

Nummer	Titel	ECTS	Umfang	Dozierende
252-0842-00L	Programmieren und Problemlösen Maximale Teilnehmerzahl: 80	3 KP	2V + 1U	D. Komm
Kurzbeschreibung	Informatikkonzepte und deren Umsetzung in Python.
Lernziel	Die Ziele der Lehrveranstaltung sind einerseits das Programmieren in Python zu vertiefen und andererseits Informatikkonzepte kennenzulernen, die im Algorithmendesign Anwendung finden. Hierbei liegt der Fokus auf dem algorithmischen Denken, also der Fähigkeit, Probleme systematisch mit Hilfe von entwickelten Algorithmen zu lösen. Es werden verschiedene Strategien für das Problemlösen vorgestellt, theoretisch analysiert und praktisch in Python umgesetzt. Die Verknüpfung von Theorie und Praxis ist in dieser Lehrveranstaltung zentral.
Inhalt	- Repetition von grundlegenden Programmierkonzepten wie Variablen, Listen, Kontrollstrukturen und Schleifen - Einlesen und darstellen von Daten - Komplexitätstheorie - Sortieren und Suchen - Dynamische Programmierung - Rekursion - Graph-Algorithmen
Skript	Vorlesungswebseite: http://lec.inf.ethz.ch/ppl
Voraussetzungen / Besonderes	Empfehlung: - Grundlagen der Informatik (252-0852-00) - Anwendungsnahes Programmieren mit Python (252-0840-01)
272-0302-00L	Approximations- und Online-Algorithmen	5 KP	2V + 1U + 1A	H.‑J. Böckenhauer, D. Komm
Kurzbeschreibung	Diese Lerneinheit behandelt approximative Verfahren für schwere Optimierungsprobleme und algorithmische Ansätze zur Lösung von Online-Problemen sowie die Grenzen dieser Ansätze.
Lernziel	Auf systematische Weise einen Überblick über die verschiedenen Entwurfsmethoden von approximativen Verfahren für schwere Optimierungsprobleme und Online-Probleme zu gewinnen. Methoden kennenlernen, die Grenzen dieser Ansätze aufweisen.
Inhalt	Approximationsalgorithmen sind einer der erfolgreichsten Ansätze zur Behandlung schwerer Optimierungsprobleme. Dabei untersucht man die sogenannte Approximationsgüte, also das Verhältnis der Kosten einer berechneten Näherungslösung und der Kosten einer (nicht effizient berechenbaren) optimalen Lösung. Bei einem Online-Problem ist nicht die gesamte Eingabe von Anfang an bekannt, sondern sie erscheint stückweise und für jeden Teil der Eingabe muss sofort ein entsprechender Teil der endgültigen Ausgabe produziert werden. Die Güte eines Algorithmus für ein Online-Problem misst man mit der competitive ratio, also dem Verhältnis der Kosten der berechneten Lösung und der Kosten einer optimalen Lösung, wie man sie berechnen könnte, wenn die gesamte Eingabe bekannt wäre. Inhalt dieser Lerneinheit sind - die Klassifizierung von Optimierungsproblemen nach der erreichbaren Approximationsgüte, - systematische Methoden zum Entwurf von Approximationsalgorithmen (z. B. Greedy-Strategien, dynamische Programmierung, LP-Relaxierung), - Methoden zum Nachweis der Nichtapproximierbarkeit, - klassische Online-Probleme wie Paging oder Scheduling-Probleme und Algorithmen zu ihrer Lösung, - randomisierte Online-Algorithmen, - Entwurfs- und Analyseverfahren für Online-Algorithmen, - Grenzen des "competitive ratio"- Modells und Advice-Komplexität als eine Möglichkeit, die Komplexität von Online-Problemen genauer zu messen.
Literatur	Die Vorlesung orientiert sich teilweise an folgenden Büchern: J. Hromkovic: Algorithmics for Hard Problems, Springer, 2004 D. Komm: An Introduction to Online Computation: Determinism, Randomization, Advice, Springer, 2016 Zusätzliche Literatur: A. Borodin, R. El-Yaniv: Online Computation and Competitive Analysis, Cambridge University Press, 1998