Suchergebnis: Katalogdaten im Frühjahrssemester 2022
Informatik DZ  Detaillierte Informationen zum Ausbildungsgang auf: www.didaktischeausbildung.ethz.ch | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 Fachwissenschaftliche Vertiefung mit pädagogischem Fokus | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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 | 5 KP | 2V + 1U + 1A | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 272-0302-00L | Approximations- und Online-Algorithmen | W | 5 KP | 2V + 1U + 1A | 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-0400-00L | Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik A  | W+ | 2 KP | 4A | J. Hromkovic, G. Serafini | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | In der mentorierten Arbeit in FV verknüpfen die Studierenden gymnasiale und universitäre Aspekte des Fachs mit dem Ziel, ihre Lehrkompetenz im Hinblick auf curriculare Entscheidungen und auf die zukünftige Entwicklung des Unterrichts zu stärken. Angeleitet erstellen sie Texte, welche die anvisierte Leserschaft, in der Regel gymnasiale Fachlehrpersonen, unmittelbar verstehen. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lernziel | Das Ziel ist, dass die Studierenden - sich in ein neues Thema einarbeiten, indem sie Materialien beschaffen und die Quellen studieren und so ihre Fachkompetenz gezielt erweitern können. - selbständig einen Text über den Gegenstandentwickeln und dabei einen speziellen Fokus auf die mathematische Verständlichkeit in Bezug auf den Kenntnisstand der anvisierten Leser/Leserinnen legen können. - Möglichkeiten berufsbezogener fachlicher Weiterbildung ausprobieren. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Inhalt | Thematische Schwerpunkte: Die mentorierte Arbeit in FV besteht in der Regel in einer Literaturarbeit über ein Thema, das einen Bezug zum gymnasialem Unterricht oder seiner Weiterentwicklung hat. Die Studierenden setzen darin Erkenntnisse aus den Vorlesungen in FV praktisch um. Lernformen: Alle Studierenden erhalten ein individuelles Thema und erstellen dazu eine eigenständige Arbeit. Sie werden dabei von ihrer Betreuungsperson begleitet. Gegebenenfalls stellen sie ihre Arbeit oder Aspekte daraus in einem Kurzvortrag vor. Die mentorierte Arbeit ist Teil des Portfolios der Studierenden. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Skript | Eine Anleitung zur mentorierten Arbeit in FV wird zur Verfügung gestellt. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Literatur | Die Literatur ist themenspezifisch. Sie muss je nach Situation selber beschafft werden oder wird zur Verfügung gestellt. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | Die Arbeit sollte vor Beginn des Praktikums abgeschlossen werden. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 252-0408-00L | Cryptographic Protocols | W | 6 KP | 2V + 2U + 1A | M. Hirt | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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 | We provide short lecture notes and handouts of the slides. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 252-0341-01L | Information Retrieval | W | 4 KP | 2V + 1U | G. Fourny | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | This course gives an introduction to information retrieval with a focus on text documents and unstructured data. Main topics comprise document modelling, various retrieval techniques, indexing techniques, query frameworks, optimization, evaluation and feedback. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lernziel | We keep accumulating data at an unprecedented pace, much faster than we can process it. While Big Data techniques contribute solutions accounting for structured or semi-structured shapes such as tables, trees, graphs and cubes, the study of unstructured data is a field of its own: Information Retrieval. After this course, you will have in-depth understanding of broadly established techniques in order to model, index and query unstructured data (aka, text), including the vector space model, boolean queries, terms, posting lists, dealing with errors and imprecision. You will know how to make queries faster and how to make queries work on very large datasets. You will be capable of evaluating the quality of an information retrieval engine. Finally, you will also have knowledge about alternate models (structured data, probabilistic retrieval, language models) as well as basic search algorithms on the web such as Google's PageRank. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Inhalt | 1. Introduction 2. Boolean retrieval: the basics of how to index and query unstructured data. 3. Term vocabulary: pre-processing the data prior to indexing: building the term vocabulary, posting lists. 4. Tolerant retrieval: dealing with spelling errors: tolerant retrieval. 5. Index construction: scaling up to large datasets. 6. Index compression: how to improve performance by compressing the index in various ways. 7. Ranked retrieval: how to ranking results with scores and the vector space model 8. Scoring in a bigger picture: taking ranked retrieval to the next level with various improvements, including inexact retrieval 9. Probabilistic information retrieval: how to leverage Bayesian techniques to build an alternate, probabilistic model for information retrieval 10. Language models: another alternate model based on languages, automata and document generation 11. Evaluation: precision, recall and various other measurements of quality 12. Web search: PageRank 13. Wrap-up. The lecture structure will follow the pedagogical approach of the book (see material). The field of information retrieval also encompasses machine learning aspects. However, we will make a conscious effort to limit overlaps, and be complementary with, the Introduction to Machine Learning lecture. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Literatur | C. D. Manning, P. Raghavan, H. Schütze, Introduction to Information Retrieval, Cambridge University Press. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | Prior knowledge in elementary set theory, logics, linear algebra, data structures, abstract data types, algorithms, and probability theory (at the Bachelor's level) is required, as well as programming skills (we will use Python). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kompetenzen |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 263-0007-00L | Advanced Systems Lab Only for master students, otherwise a special permission by the study administration of D-INFK is required. | W | 8 KP | 3V + 2U + 2A | M. Püschel, C. Zhang | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | This course introduces the student to the foundations and state-of-the-art techniques in developing high performance software for mathematical functionality occurring in various fields in computer science. The focus is on optimizing for a single core and includes optimizing for the memory hierarchy, for special instruction sets, and the possible use of automatic performance tuning. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lernziel | Software performance (i.e., runtime) arises through the complex interaction of algorithm, its implementation, the compiler used, and the microarchitecture the program is run on. The first goal of the course is to provide the student with an understanding of this "vertical" interaction, and hence software performance, for mathematical functionality. The second goal is to teach a systematic strategy how to use this knowledge to write fast software for numerical problems. This strategy will be trained in several homeworks and a semester-long group project. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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 mathematical software development using important functionality such as matrix operations, transforms, filters, and others as examples. The course will explain how to optimize for the memory hierarchy, take advantage of special instruction sets, and other details of current processors that require optimization. The concept of automatic performance tuning is introduced. The focus is on optimization for a single core; thus, the course complements others on parallel and distributed computing. Finally a general strategy for performance analysis and optimization is introduced that the students will apply in group projects that accompany the course. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | Solid knowledge of the C programming language and matrix algebra. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Seite
1
von
1
