Das Herbstsemester 2020 findet in einer gemischten Form aus Online- und Präsenzunterricht statt.
Bitte lesen Sie die publizierten Informationen zu den einzelnen Lehrveranstaltungen genau.

Dennis Komm: Katalogdaten im Frühjahrssemester 2019

NameHerr Dr. Dennis Komm
Adresse
Inform.technologie und Ausbildung
ETH Zürich, CAB F 13.1
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
BeziehungDozent

NummerTitelECTSUmfangDozierende
252-0842-00LProgrammieren und Problemlösen Information Belegung eingeschränkt - Details anzeigen
Maximale Teilnehmerzahl: 40
3 KP2V + 0.5UD. Komm
KurzbeschreibungEinführung in die Programmierung in Java und in das Problemlösen mittels Standard-Algorithmen und -Datenstrukturen.
LernzielDie Ziele der Lehrveranstaltung sind einerseits mit der Programmiersprache Java vertraut zu sein und andererseits gegebene Probleme des eigenen Fachbereichs (z.Bsp. Datenverarbeitung) mittels eigener Programme lösen zu können.

Die Studierenden sollen bestehende Algorithmen und Datenstrukturen kennen, diese benutzen können und deren Eigenschaften kennen. Das Ziel ist es, für ein gegebenes Problem eine geeignete Datenstruktur und einen geeigneten Algorithmus auswählen zu können und das eigene Programm, basierend auf dieser Wahl, programmieren zu können.

Während der Lehrveranstaltung arbeiten die Studierenden an einem eigenen Projekt, das sie während der letzten Vorlesungsstunde präsentieren müssen.
InhaltFolgende Themen werden behandelt:
- Programmierkonzepte vs. Programmiersprachen
- Einführung in Java
- Arrays
- Methoden und Methodenparameter
- Klassen, Typen und Objekte
- I/O: Tastatureingaben, Bildschrimausgaben, Dateien lesen und schreiben
- Exceptions
- Lambda Ausdrücke und das Stream API
- Datenstrukturen
- Einführung in GUI-Programmierung
SkriptVorlesungswebseite: http://lec.inf.ethz.ch/ppl
Voraussetzungen / BesonderesAchtung: Dies ist ein Blockkurs, der nur während der ersten sieben Wochen des Semesters stattfindet. Diese sieben Wochen sind sehr intensiv, da gleichzeitig das bewertete Projekt umgesetzt wird.

Empfehlung:
- Einsatz von Informatikmitteln (252-0839-00)
- Anwendungsnahes Programmieren mit Python (252-0840-01)
272-0302-00LApproximations- und Online-Algorithmen Information 4 KP2V + 1UH.‑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