Suchergebnis: Katalogdaten im Frühjahrssemester 2018

Nummer	Titel	Typ	ECTS	Umfang	Dozierende
Rechnergestützte Wissenschaften DZ Detaillierte Informationen zum Ausbildungsgang auf: www.didaktischeausbildung.ethz.ch
Weitere Fachdidaktik
272-0300-00L	Algorithmik für schwere Probleme Findet dieses Semester nicht statt. Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik A n i c h t !	W	4 KP	2V + 1U	J. Hromkovic
Kurzbeschreibung	Diese Lerneinheit beschäftigt sich mit algorithmischen Ansätzen zur Lösung schwerer Probleme. 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.
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.
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, D. Kratsch: Exact Exponential Algorithms, 2010.
272-0302-00L	Approximations- und Online-Algorithmen	W	4 KP	2V + 1U	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
272-0301-00L	Methoden zum Entwurf von zufallsgesteuerten Algorithmen Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik B n i c h t !	W	4 KP	2V + 1U	H.‑J. Böckenhauer, D. Komm, R. Kralovic
Kurzbeschreibung	Die Studierenden sollen die Entwicklung unserer Vorstellung über Zufall und dessen Rolle verfolgen. Mit Grundkenntnissen der Wahrscheinlichkeitstheorie und grundlegender Arithmetik sollen sie entdecken, dass Zufallssteuerung ein Mittel zur Erreichung unglaublicher Effizienz von Prozessen werden kann. Das Ziel ist, die Methodik des Entwurfs von zufallsgesteuerten Algorithmen zu vermitteln.
Lernziel	Thematische Schwerpunkte - Modellierung und Klassifizierung von randomisierten Algorithmen - Die Methode der Überlistung des Gegners: Hashing und randomisierte Online-Algorithmen - Die Methode der Fingerabdrücke: Kommunikationsprotokolle - Die Methode der häufigen Zeugen: randomisierter Primzahltest von Solovay und Strassen - Wahrscheinlichkeitsverstärkung durch Wiederholung - Randomisierte Algorithmen für Optimierungsprobleme
Skript	J. Hromkovic: Randomisierte Algorithmen, Teubner 2004. J.Hromkovic: Design and Analysis of Randomized Algorithms. Springer 2006. J.Hromkovic: Algorithmics for Hard Problems, Springer 2004.
Literatur	J. Hromkovic: Randomisierte Algorithmen, Teubner 2004. J.Hromkovic: Design and Analysis of Randomized Algorithms. Springer 2006. J.Hromkovic: Algorithmics for Hard Problems, Springer 2004.
252-0408-00L	Cryptographic Protocols	W	5 KP	2V + 2U	M. Hirt, U. Maurer
Kurzbeschreibung	The course presents a selection of hot research topics in cryptography. The choice of topics varies and may include provable security, interactive proofs, zero-knowledge protocols, secret sharing, secure multi-party computation, e-voting, etc.
Lernziel	Indroduction to a very active research area with many gems and paradoxical results. Spark interest in fundamental problems.
Inhalt	The course presents a selection of hot research topics in cryptography. The choice of topics varies and may include provable security, interactive proofs, zero-knowledge protocols, secret sharing, secure multi-party computation, e-voting, etc.
Skript	the lecture notes are in German, but they are not required as the entire course material is documented also in other course material (in english).
Voraussetzungen / Besonderes	A basic understanding of fundamental cryptographic concepts (as taught for example in the course Information Security or in the course Cryptography Foundations) is useful, but not required.
263-2300-00L	How To Write Fast Numerical Code Findet dieses Semester nicht statt. Number of participants limited to 84. Prerequisite: Master student, solid C programming skills.	W	6 KP	3V + 2U	M. Püschel
Kurzbeschreibung	This course introduces the student to the foundations and state-of-the-art techniques in developing high performance software for numerical functionality such as linear algebra and others. The focus is on optimizing for the memory hierarchy and for special instruction sets. Finally, the course will introduce the recent field of automatic performance tuning.
Lernziel	Software performance (i.e., runtime) arises through the interaction of algorithm, its implementation, and the microarchitecture the program is run on. The first goal of the course is to provide the student with an understanding of this interaction, and hence software performance, focusing on numerical or mathematical functionality. The second goal is to teach a general systematic strategy how to use this knowledge to write fast software for numerical problems. This strategy will be trained in a few homeworks and semester-long group projects.
Inhalt	The fast evolution and increasing complexity of computing platforms pose a major challenge for developers of high performance software for engineering, science, and consumer applications: it becomes increasingly harder to harness the available computing power. Straightforward implementations may lose as much as one or two orders of magnitude in performance. On the other hand, creating optimal implementations requires the developer to have an understanding of algorithms, capabilities and limitations of compilers, and the target platform's architecture and microarchitecture. This interdisciplinary course introduces the student to the foundations and state-of-the-art techniques in high performance software development using important functionality such as linear algebra functionality, transforms, filters, and others as examples. The course will explain how to optimize for the memory hierarchy, take advantage of special instruction sets, and, if time permits, how to write multithreaded code for multicore platforms. Much of the material is based on state-of-the-art research. Further, a general strategy for performance analysis and optimization is introduced that the students will apply in group projects that accompany the course. Finally, the course will introduce the students to the recent field of automatic performance tuning.

Seite 1 von 1