Hans-Joachim Böckenhauer: Katalogdaten im Frühjahrssemester 2023 |
| Name | Herr Dr. Hans-Joachim Böckenhauer |
| Sprechstunde | Nach Vereinbarung |
| Adresse | Professur Algorithmen und Didaktik ETH Zürich, CAB F 11 Universitätstrasse 6 8092 Zürich SWITZERLAND |
| Telefon | +41 44 632 81 83 |
| Fax | +41 44 632 13 90 |
| hjb@inf.ethz.ch | |
| URL | http://www.ite.ethz.ch/people/hjb/ |
| Departement | Informatik |
| Beziehung | Dozent |
| Nummer | Titel | ECTS | Umfang | Dozierende | ||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 252-4910-00L | Approximation Algorithms   The deadline for deregistering expires at the end of the second week of the semester. Students who are still registered after that date, but do not attend the seminar, will officially fail the seminar. | 2 KP | 2S | H.‑J. Böckenhauer, R. Kralovic | ||||||||||||||||||||||||||||||||
| Kurzbeschreibung | We look into approximation algorithms for computationally hard discrete optimization problems. Their quality is measured by the approximation ratio, i.e., the worst-case ratio between the quality of the computed solution and an optimal one, depending on the input size. We explore different techniques for the design and analysis of approximation algorithms and the limits of this approach. | |||||||||||||||||||||||||||||||||||
| Lernziel | To systematically acquire an overview of the methods for the design and analysis of approxmation algorithms. To get deeper knowledge of the classification of optimization problems according to their approximability. To learn how to analyze the approximation ratio of approximation algorithms.To learn about the limits of the approximation approach. | |||||||||||||||||||||||||||||||||||
| Inhalt | In this seminar, we discuss how approximation can help to compute satisfactory solutions for computationally hard optimization problems. In the kick-off meeting, we will give a brief overview of modeling and classifying approximation algorithms. Then, each participant will study one aspect of this topic, following a specific scientific publication, and will give a presentation about this topic. The topics will include design methods for approximation algorithms like greedy strategies, dynamic programming, or LP-based techniques as well as the classification of optimization problems according to their approximability. The considered problems will be well-known optimization tasks like satisfiability problems, routing problems, packing problems, etc. | |||||||||||||||||||||||||||||||||||
| Literatur | The literature will consist of textbook chapters and original research papers and will be provided during the kick-off meeting. | |||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | The participants should be familiar with the content of the lectures "Algorithmen und Datenstrukturen" (252-0026-00) and "Theoretische Informatik" (252-0057-00). The presentations will be given in the form of a block course in June 2023, preferrably shortly after the end of the normal lectures. The language can be mixed in German and English in the following sense: The teaching material will be in English, but it will be possible for at least half of the participants to give their presentations and hand in their written summaries in German. | |||||||||||||||||||||||||||||||||||
| Kompetenzen |
| |||||||||||||||||||||||||||||||||||
| 272-0300-00L | Algorithmik für schwere Probleme Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik A n i c h t ! | 5 KP | 2V + 1U + 1A | H.‑J. Böckenhauer, D. Komm | ||||||||||||||||||||||||||||||||
| Kurzbeschreibung | Diese Lerneinheit beschäftigt sich mit algorithmischen Ansätzen zur Lösung schwerer Probleme, insbesondere mit exakten Algorithmen mit moderat exponentieller Laufzeit und parametrisierten Algorithmen. Eine umfassende Reflexion über die Bedeutung der vorgestellten Ansätze für den Informatikunterricht an Gymnasien begleitet den Kurs. | |||||||||||||||||||||||||||||||||||
| Lernziel | Auf systematische Weise eine Übersicht über die Methoden zur Lösung schwerer Probleme kennen lernen. Vertiefte Kenntnisse im Bereich exakter und parameterisierter Algorithmen erwerben. | |||||||||||||||||||||||||||||||||||
| Inhalt | Zuerst wird der Begriff der Berechnungsschwere erläutert (für die Informatikstudierenden wiederholt). Dann werden die Methoden zur Lösung schwerer Probleme systematisch dargestellt. Bei jeder Algorithmenentwurfsmethode wird vermittelt, was sie uns garantiert und was sie nicht sichern kann und womit wir für die gewonnene Effizienz bezahlen. Ein Schwerpunkt liegt auf exakten Algorithmen mit moderat exponentieller Laufzeit und auf parametrisierten Algorithmen. | |||||||||||||||||||||||||||||||||||
| Skript | Unterlagen und Folien werden zur Verfügung gestellt. | |||||||||||||||||||||||||||||||||||
| Literatur | J. Hromkovic: Algorithmics for Hard Problems, Springer 2004. R. Niedermeier: Invitation to Fixed-Parameter Algorithms, 2006. M. Cygan et al.: Parameterized Algorithms, 2015. F. Fomin et al.: Kernelization, 2019. F. Fomin, D. Kratsch: Exact Exponential Algorithms, 2010. | |||||||||||||||||||||||||||||||||||
| Kompetenzen |
| |||||||||||||||||||||||||||||||||||