Dennis Komm: Katalogdaten im Frühjahrssemester 2023 |
| 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 |
| 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 | 3 KP | 2V + 1U | D. Komm, M. Dahinden, M. Fischer | |||||||||||||||||||||||||||||||||||
| 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: https://moodle-app2.let.ethz.ch/course/view.php?id=19344 | ||||||||||||||||||||||||||||||||||||||
| Literatur | Die ausführlichen Folien werden auf der Vorlesungshomepage zum Herunterladen bereitgestellt. | ||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | Empfehlung: - Grundlagen der Informatik (252-0852-00) - Anwendungsnahes Programmieren mit Python (252-0840-01) | ||||||||||||||||||||||||||||||||||||||
Kompetenzen |
| ||||||||||||||||||||||||||||||||||||||
| 252-4225-00L | Presenting Theoretical Computer Science  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 | B. Gärtner, D. Komm, R. Kyng, A. Steger, D. Steurer, E. Welzl | |||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | Students present current or classical results from theoretical computer science. | ||||||||||||||||||||||||||||||||||||||
| Lernziel | Students learn to read, understand and present results from theoretical computer science. The main focus and deliverable is a good presentation of 45 minutes that can easily be followed and understood by the audience. | ||||||||||||||||||||||||||||||||||||||
| Inhalt | Students present current or classical results from theoretical computer science. | ||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | The seminar takes place as a block seminar on two Saturdays in April and/or May. Each presentation is jointly prepared and given by two students (procedure according to the seminar's Moodle page). All students must attend all presentations. Participation requires successful completion of the first year, or instructor approval. | ||||||||||||||||||||||||||||||||||||||
| 272-0102-00L | Fachdidaktik Informatik II Voraussetzung: Fachdidaktik Informatik I | 4 KP | 3G | J. Hromkovic, D. Komm, G. Serafini | |||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | Die Fachdidaktik Informatik II behandelt primär die Beiträge der Informatik zur allgemeinen Bildung, welche einerseits die Entwicklung der Denkweise der Jugendlichen auf einzigartige Art und Weise fördern und andererseits zum Verständnis unserer Welt und zur Hochschulreife beitragen. | ||||||||||||||||||||||||||||||||||||||
| Lernziel | Die Fachdidaktik Informatik II behandelt primär die Beiträge der Informatik zur allgemeinen Bildung, welche einerseits die Entwicklung der Denkweise der Jugendlichen auf einzigartige Art und Weise fördern und andererseits zum Verständnis unserer Welt und zur Hochschulreife beitragen. Die Fachdidaktik Informatik II befasst sich mit der adäquaten Auswahl von Unterrichtsinhalten für den Informatikunterricht, ihrer Zugänglichkeit im entsprechenden Alter sowie mit geeigneten didaktischen Methoden für einen erfolgreichen Wissenstransfer. Im Rahmen einer semesterbegleitenden Übung entwickeln und dokumentieren die Studierenden eine adaptive Unterrichtseinheit für den Informatikunterricht. Dabei vertiefen sie den Umgang mit den in der Fachdidaktik Informatik I eingeführten Unterrichtsmethoden und -techniken. Das Ziel der Lerneinheit besteht darin, die Verbindung von mathematischer und algorithmischer Denkweise mit der ingenieurwissenschaftlichen Denkweise zu vermitteln. Die Studierenden verstehen die grundlegenden Konzepte der Informatik im breiten und tiefen Kontext. Aus diesem Verständnis heraus sind sie befähigt, Unterrichtsunterlagen zum erfolgreichen Wissenstransfer zu erarbeiten und ihre Begeisterung für das Fach an die Schülerinnen und Schüler weiterzugeben. Die Studierenden kennen unterschiedliche Unterrichtsmethoden, ihre Vor- und Nachteile. Sie können mit den oft stark unterschiedlichen Vorkenntnissen der Lernenden umgehen. Neben dem Klassenunterricht legen die Studierenden Wert auf die Einzelbetreuung. Sie fördern die Selbständigkeit der Lernenden. Sie schaffen es, mit verschiedenartigen Zielgruppen zu arbeiten und ein gutes Lernklima aufzubauen. Die Studierenden sind in der Lage, sich in einer verständlichen und gepflegten Fachsprache mündlich und schriftlich auszudrücken und beherrschen die grundlegenden Begriffe der Informatik. Neben den englischen Fachausdrücken sind ihnen auch die deutschen Benennungen geläufig. Die Studierenden sind fähig, ausführliche, ausgereifte, sprachlich einwandfreie und ansprechend gestaltete Unterrichtsunterlagen anzufertigen. | ||||||||||||||||||||||||||||||||||||||
| Inhalt | Die Hauptthemen der Fachdidaktik Informatik II sind Kryptologie und Berechenbarkeit. Im Mittelpunkt der Lerneinheit stehen Informatikinhalte, die allgemeine Bildungswerte vermitteln. Es geht um das Verständnis für Grundbegriffe der Wissenschaft wie - Algorithmus - Komplexität - Determinismus - Nichtdeterminismus - Zufall - Berechnung | ||||||||||||||||||||||||||||||||||||||
| Skript | Unterlagen und Folien werden zur Verfügung gestellt. | ||||||||||||||||||||||||||||||||||||||
| Literatur | J. Hromkovic: Sieben Wunder der Informatik: Eine Reise an die Grenze des Machbaren, mit Aufgaben und Lösungen. Vieweg+Teubner; Auflage: 2 (2008). K. Freiermuth, J. Hromkovic, L. Keller und B. Steffen: Einfuehrung in die Kryptologie: Lehrbuch für Unterricht und Selbststudium. Springer Vieweg; Auflage: 2 (2014). J. Hromkovic: Berechenbarkeit: Logik, Argumentation, Rechner und Assembler, Unendlichkeit, Grenzen der Automatisierbarkeit. Vieweg+Teubner; Auflage: 1 (2011). H.-J. Böckenhauer, J. Hromkovic: Formale Sprachen: Endliche Automaten, Grammatiken, lexikalische und syntaktische Analyse. Springer Vieweg; Auflage: 1 (Januar 2013). | ||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | Bewilligung der Dozierenden für alle Studierenden notwendig | ||||||||||||||||||||||||||||||||||||||
| 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 |
| ||||||||||||||||||||||||||||||||||||||
| 272-0302-00L | Approximations- und Online-Algorithmen Findet dieses Semester nicht statt. | 5 KP | 2V + 1U + 1A | 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 | ||||||||||||||||||||||||||||||||||||||
| Kompetenzen |
| ||||||||||||||||||||||||||||||||||||||