Manuela Fischer: Katalogdaten im Frühjahrssemester 2023 |
| Name | Frau Dr. Manuela Fischer |
| Adresse | Lehre D-INFK ETH Zürich, CAB H 33.1 Universitätstrasse 6 8092 Zürich SWITZERLAND |
| Telefon | +41 44 632 74 61 |
| manuela.fischer@inf.ethz.ch | |
| URL | http://people.inf.ethz.ch/fiscmanu/ |
| Departement | Informatik |
| Beziehung | Dozentin |
| Nummer | Titel | ECTS | Umfang | Dozierende | |||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 252-0002-AAL | Data Structures and Algorithms  Belegung ist NUR erlaubt für MSc Studierende, die diese Lerneinheit als Auflagenfach verfügt haben. Alle anderen Studierenden (u.a. auch Mobilitätsstudierende, Doktorierende) können diese Lerneinheit NICHT belegen. | 8 KP | 15R | M. Fischer, F. Friedrich Wicker | |||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | The course provides the foundations for the design and analysis of algorithms. Classic problems ranging from sorting up to problems on graphs are used to discuss common data structures, algorithms and algorithm design paradigms. The course also comprises an introduction to parallel and concurrent programming and the programming model of C++ is discussed in some depth. | ||||||||||||||||||||||||||||||||||||||
| Lernziel | An understanding of the analysis and design of fundamental and common algorithms and data structures. Deeper insight into a modern programming model by means of the programming language C++. Knowledge regarding chances, problems and limits of parallel and concurrent programming. | ||||||||||||||||||||||||||||||||||||||
| Inhalt | Data structures and algorithms: mathematical tools for the analysis of algorithms (asymptotic function growth, recurrence equations, recurrence trees), informal proofs of algorithm correctness (invariants and code transformation), design paradigms for the development of algorithms (induction, divide-and-conquer, sweep-line method, backtracking and dynamic programming), classical algorithmic problems (searching, selection and sorting), data structures for different purposes (linked lists, hash tables, balanced search trees, quad trees, heaps, union-find), further tools for runtime analysis (e.g. amortized analysis). The relationship and tight coupling between algorithms and data structures is illustrated with geometric problems (convex hull, line intersections, closest point pairs) graph algorithms (traversals, topological sort, transitive closure, shortest paths, minimum spanning trees, max flow). Programming model of C++: correct and efficient memory handling, generic programming with templates, functional approaches with functors and lambda expressions. Parallel programming: concepts of parallel programming (Amdahl's and Gustavson's laws, task/data parallelism, scheduling), problems of concurrency (data races, bad interleavings, memory reordering), process synchronisation and communication in a shared memory system (mutual exclusion, semaphores, monitors, condition variables), progress conditions (freedom from deadlock, starvation). The concepts provided in the course are motivated and illustrated with practically relevant algorithms and applications. Exercises are carried out in Code-Expert, an online IDE and exercise management system. All required mathematical tools above high school level are covered, including a basic introduction to graph theory. | ||||||||||||||||||||||||||||||||||||||
| Literatur | (available on the course website) | ||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | Prerequisites: Lecture Series 252-0856-00L Computer Science or equivalent knowledge in programming with C++. Please note that this is a self study (virtual) course, which implies that (in the autumn semester) there are no physical lectures or exercise sessions offered. If you want to attend the real course, please go to 252-0002-00L in the spring semester. | ||||||||||||||||||||||||||||||||||||||
| Kompetenzen |
| ||||||||||||||||||||||||||||||||||||||
| 252-0002-00L | Datenstrukturen & Algorithmen | 8 KP | 4V + 2U | M. Fischer, F. Friedrich Wicker | |||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | Der Kurs vermittelt die Grundlagen für den Entwurf und die Analyse von Algorithmen. Anhand klassischer Probleme werden gängige Datenstrukturen, Algorithmen und Paradigmen für den Algorithmenentwurf diskutiert. Der Kurs umfasst auch eine Einführung in die parallele und nebenläufige Programmierung und das Programmiermodell von C++ wird eingehend diskutiert. | ||||||||||||||||||||||||||||||||||||||
| Lernziel | Verständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen. Wissen um die Chancen, Probleme und Grenzen der parallelen und nebenläufigen Programmierung. Vertiefter Einblick in ein modernes Programmiermodell anhand der Prorgammiersprache C++. | ||||||||||||||||||||||||||||||||||||||
| Inhalt | Datenstrukturen und Algorithmen: Mathematische Tools für die Analyse von Algorithmen (asymptotisches Funktionenwachstum, Rekursionsgleichungen, Rekursionsbäume), informelle Beweise für die Korrektheit von Algorithmen (Invarianten und Codetransformation), Entwurfsparadigmen für die Entwicklung von Algorithmen (Induktion, Divide-and-Conquer, Sweep-Line-Methode, Backtracking und dynamische Programmierung), klassische algorithmische Probleme (Suche, Auswahl und Sortierung), Datenstrukturen für verschiedene Zwecke (verkettete Listen, Hash-Tabellen, balancierte Suchbäume, Quad-Trees, Heaps, Union-Find), weitere Tools für die Laufzeitanalyse (z.B. amortisierte Analyse). Die Beziehung und enge Kopplung zwischen Algorithmen und Datenstrukturen wird anhand von geometrischen Problemen (konvexe Hülle, Linienschnitte, dichteste Punktepaare) und Graphenalgorithmen (Traversierungen, topologische Sortierung, transitive Hülle, kürzeste Pfade, minimale Spannbäume, maximaler Fluss) illustriert. Programmiermodell von C++: korrekte und effiziente Speicherbehandlung, generische Programmierung mit Templates, funktionale Ansätze mit Funktoren und Lambda-Ausdrücken. Parallele Programmierung: Konzepte der parallelen Programmierung (Amdahl/Gustavson, Task/Daten-Parallelität, Scheduling), Probleme der Nebenläufigkeit (data races, bad interleavings, memory reordering), Prozess-Synchronisation und Kommunikation in einem Shared-Memory-System (Mutual Exclusion, Semaphoren, Monitore, Condition-Variablen), Fortschrittsbedingungen (Deadlock-Freiheit, Starvation). Die im Kurs vermittelten Konzepte werden mit praktisch relevanten Algorithmen und Anwendungen motiviert und illustriert. Die Übungen werden in Code-Expert, einer Online-IDE und einem Übungsmanagementsystem, durchgeführt. Alle benötigten mathematischen Tools ausserhalb des Schulwissens werden im Kurs behandelt, einschliesslich einer Einführung zur Graphentheorie. | ||||||||||||||||||||||||||||||||||||||
| Literatur | (auf der Kurshomepage angegeben) | ||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | Voraussetzung: Vorlesung 252-0835-00L Informatik I 252-0835-00L oder äquivalente Kenntnisse in der Programmierung mit C++. | ||||||||||||||||||||||||||||||||||||||
| Kompetenzen |
| ||||||||||||||||||||||||||||||||||||||
| 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-0846-AAL | Computer Science II Belegung ist NUR erlaubt für MSc Studierende, die diese Lerneinheit als Auflagenfach verfügt haben. Alle anderen Studierenden (u.a. auch Mobilitätsstudierende, Doktorierende) können diese Lerneinheit NICHT belegen. | 4 KP | 9R | C. Cotrini Jimenez, M. Fischer | |||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | This course provides the foundations of programming and working with data. Computer Science II particularly stresses code efficiency and provides the basis for understanding, design, and analysis of algorithms and data structures. In terms of working with data, foundations required for understanding experimental data and notation and basic concepts for machine learning are covered. | ||||||||||||||||||||||||||||||||||||||
| Lernziel | Based on the knowledge covered by the lecture Computer Science I, the primary educational objective of this course is the constructive knowledge of data structures and algorithms. After successfully attending the course, students have a good command of the mechanisms to construct a program in Python and to work with multidimensional data using Python libraries. Students particularly understand how an algorithmic problem can be solved with a sufficiently efficient computer program. Secondary educational objectives are formal thinking, the power of abstraction, and appropriate modeling capabilities. | ||||||||||||||||||||||||||||||||||||||
| Inhalt | Introduction of Python: from Java to Python, advanced concepts and built-in data structures in Python; parsing data, operating on data using Numpy and visualization using Matplotlib; linear regression, classification and (k-means) clustering, mathematical tools for the analysis of algorithms (asymptotic function growth, recurrence equations, recurrence trees), classical algorithmic problems (searching, selection and sorting), design paradigms for the development of algorithms (divide-and-conquer and dynamic programming), data structures for different purposes (linked lists, trees, heaps, hash-tables). The relationship and tight coupling between algorithms and data structures is illustrated with graph algorithms (traversals, topological sort, closure, shortest paths). In general, the concepts provided in the course are motivated and illustrated with practically relevant algorithms and applications. Exercises are carried out in Code-Expert, an online IDE and exercise management system. Programming language used in this course is Python. | ||||||||||||||||||||||||||||||||||||||
| Skript | The slides will be available for download on the course home page. | ||||||||||||||||||||||||||||||||||||||
| Literatur | T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms , 3rd ed., MIT Press, 2009 | ||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | Preliminaries: course 252-0845 Computer Science or equivalent knowledge in programming. | ||||||||||||||||||||||||||||||||||||||
| 252-0846-00L | Informatik II | 4 KP | 2V + 2U | M. Fischer, C. Cotrini Jimenez | |||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | Dieser Kurs behandelt Grundlagen für das Programmieren und Arbeiten mit Daten. Informatik II legt die Grundlage für das Verständnis, den Entwurf und die Analyse von Algorithmen und Datenstrukturen. | ||||||||||||||||||||||||||||||||||||||
| Lernziel | Basierend auf Kenntnissen aus der Vorlesung Informatik I ist das primäre Ziel dieses Kurses das konstruktive Wissen über Datenstrukturen und Algorithmen. Nach erfolgreichem Besuch des Kurses beherrschen die Teilnehmer die Mechanismen zum Erstellen eines Programms in Python und zum Arbeiten mit mehrdimensionalen Daten mithilfe von Python-Bibliotheken. Die Studierenden verstehen insbesondere, wie ein algorithmisches Problem mit einem ausreichend effizienten Computerprogramm gelöst werden kann. Sekundäre Bildungsziele sind formales Denken, die Macht der Abstraktion und Modellierungsfähigkeiten. In dem Fach "Informatik II" wird die Kompetenz Modellierung, Programmieren und Datenanalyse & Interpretation gelehrt, angewandt und geprüft. | ||||||||||||||||||||||||||||||||||||||
| Inhalt | Einführung von Python: von Java zu Python, erweiterte Konzepte und integrierte Datenstrukturen in Python; Analysieren von Daten, Bearbeiten von Daten mit Numpy und Visualisieren mit Matplotlib; mathematische Werkzeuge zur Analyse von Algorithmen (asymptotisches Funktionswachstum, Rekurrenzgleichungen, Rekurrenzbäume); klassische algorithmische Probleme (Suchen, Auswahl und Sortieren), Entwurfsparadigmen für die Entwicklung von Algorithmen (Divide and Conquer und dynamische Programmierung), Datenstrukturen für verschiedene Zwecke (verknüpfte Listen, Bäume, Heaps, Hash-Tabellen). Die Beziehung und enge Kopplung zwischen Algorithmen und Datenstrukturen wird mit Graph-Algorithmen (Traversieren, Topologische Sortierung, Kürzeste Wege, Minimaler Spannbaum, Maximaler Fluss) und geometrischen Algorithmen (Scanline) veranschaulicht. Die im Kurs bereitgestellten Konzepte werden mit praktisch relevanten Algorithmen und Anwendungen motiviert und veranschaulicht. Die in diesem Kurs verwendete Programmiersprache ist Python. Die Übungen werden in Code Expert, einem Online-IDE- und Übungsmanagementsystem, durchgeführt. | ||||||||||||||||||||||||||||||||||||||
| Skript | Die Folien werden auf der Vorlesungswebseite zum Herunterladen bereitgestellt. | ||||||||||||||||||||||||||||||||||||||
| Literatur | Thomas Ottmann, Peter Widmayer, Algorithmen und Datenstrukturen, Springer 2012 T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algorithmen - Eine Einführung, Oldenbourg, 2010 Aditya Y. Bhargava, Algorithmen Kapieren, mitp 2019 | ||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | Voraussetzungen: Kurs 252-0845 Informatik I oder äquivalente Programmierkenntnisse. Alle erforderlichen mathematischen Werkzeuge über Schulniveau werden behandelt, einschließlich einer grundlegenden Einführung in die Graphentheorie. | ||||||||||||||||||||||||||||||||||||||