Dennis Komm: Katalogdaten im Frühjahrssemester 2020

NameHerr Prof. Dr. Dennis Komm
LehrgebietAlgorithmen und Didaktik
Adresse
Professur Algorithmen und Didaktik
ETH Zürich, CAB F 13.2
Universitätstrasse 6
8092 Zürich
SWITZERLAND
Telefon+41 44 632 82 23
E-Maildennis.komm@inf.ethz.ch
URLhttps://people.inf.ethz.ch/dkomm/
DepartementInformatik
BeziehungAusserordentlicher Professor

NummerTitelECTSUmfangDozierende
252-0842-00LProgrammieren und Problemlösen Information Belegung eingeschränkt - Details anzeigen
Maximale Teilnehmerzahl: 80
3 KP2V + 1UD. Komm
KurzbeschreibungInformatikkonzepte und deren Umsetzung in Python.
LernzielDie 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
SkriptVorlesungswebseite: http://lec.inf.ethz.ch/ppl
Voraussetzungen / BesonderesEmpfehlung:
- Grundlagen der Informatik (252-0852-00)
- Anwendungsnahes Programmieren mit Python (252-0840-01)
272-0302-00LApproximations- und Online-Algorithmen Information 5 KP2V + 1U + 1AH.‑J. Böckenhauer, D. Komm
KurzbeschreibungDiese Lerneinheit behandelt approximative Verfahren für schwere Optimierungsprobleme und algorithmische Ansätze zur Lösung von Online-Problemen sowie die Grenzen dieser Ansätze.
LernzielAuf 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.
InhaltApproximationsalgorithmen 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.
LiteraturDie 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