Felix Friedrich Wicker: Katalogdaten im Frühjahrssemester 2023 |
| Name | Herr Dr. Felix Friedrich Wicker |
| Adresse | Dep. Informatik ETH Zürich, CAB H 33.3 Universitätstrasse 6 8092 Zürich SWITZERLAND |
| Telefon | +41 44 632 83 12 |
| felix.friedrich@inf.ethz.ch | |
| Departement | Informatik |
| Beziehung | Dozent |
| 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-0232-00L | Software Engineering | 6 KP | 2V + 1U | F. Friedrich Wicker, M. Schwerhoff, H. Lehner | ||||||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | This course introduces both theoretical and applied aspects of software engineering. It covers: - Software Architecture - Informal and formal Modeling - Design Patterns - Software Engineering Principles - Code Refactoring - Program Testing | |||||||||||||||||||||||||||||||||||||||||
| Lernziel | The course has two main objectives: - Obtain an end-to-end (both, theoretical and practical) understanding of the core techniques used for building quality software. - Be able to apply these techniques in practice. | |||||||||||||||||||||||||||||||||||||||||
| Inhalt | While the lecture will provide the theoretical foundations for the various aspects of software engineering, the students will apply those techniques in project work that will span over the whole semester - involving all aspects of software engineering, from understanding requirements over design and implementation to deployment and change requests. | |||||||||||||||||||||||||||||||||||||||||
| Skript | no lecture notes | |||||||||||||||||||||||||||||||||||||||||
| Literatur | Will be announced in the lecture | |||||||||||||||||||||||||||||||||||||||||
| Kompetenzen |
| |||||||||||||||||||||||||||||||||||||||||
| 252-0856-AAL | Computer Science Belegung ist NUR erlaubt für MSc Studierende, die diese Lerneinheit als Auflagenfach verfügt haben. Alle andere Studierenden (u.a. auch Mobilitätsstudierende, Doktorierende) können diese Lerneinheit NICHT belegen. | 4 KP | 9R | F. Friedrich Wicker, R. Sasse | ||||||||||||||||||||||||||||||||||||||
| Kurzbeschreibung | Die Vorlesung bietet eine Einführung in das Programmieren mit einem Fokus auf systematischem algorithmischem Problemlösen. Lehrsprache ist C++. Es wird keine Programmiererfahrung vorausgesetzt. | |||||||||||||||||||||||||||||||||||||||||
| Lernziel | Primäres Lernziel der Vorlesung ist die Befähigung zum Programmieren mit C++. Studenten beherrschen nach erfolgreichem Abschluss der Vorlesung die Mechanismen zum Erstellen eines Programms, sie kennen die fundamentalen Kontrollstrukturen, Datenstrukturen und verstehen, wie man ein algorithmisches Problem in ein Programm abbildet. Sie haben eine Vorstellung davon, was "hinter den Kulissen" passiert, wenn ein Programm übersetzt und ausgeführt wird. Sekundäre Lernziele der Vorlesung sind das Computer-basierte, algorithmische Denken, Verständnis der Möglichkeiten und der Grenzen der Programmierung und die Vermittlung der Denkart eines Computerwissenschaftlers. | |||||||||||||||||||||||||||||||||||||||||
| Inhalt | Wir behandeln fundamentale Datentypen, Ausdrücke und Anweisungen, (Grenzen der) Computerarithmetik, Kontrollanweisungen, Funktionen, Felder, zusammengesetze Strukturen und Zeiger. Im Teil zur Objektorientierung werden Klassen, Vererbung und Polymorhpie behandelt, es werden exemplarisch einfache dynamische Datentypen eingeführt. Die Konzepte der Vorlesung werden jeweils durch Algorithmen und Anwendungen motiviert und illustriert. | |||||||||||||||||||||||||||||||||||||||||
| Skript | Ein Skript in englischer Sprache wird semesterbegleitend herausgegeben. Das Skript und die Folien werden auf der Vorlesungshomepage zum Herunterladen bereitgestellt. | |||||||||||||||||||||||||||||||||||||||||
| Literatur | Bjarne Stroustrup: Einführung in die Programmierung mit C++, Pearson Studium, 2010 Stephen Prata: C++ Primer Plus, Sixth Edition, Addison Wesley, 2012 Andrew Koenig and Barbara E. Moo: Accelerated C++, Addison-Wesley, 2000. | |||||||||||||||||||||||||||||||||||||||||
| Voraussetzungen / Besonderes | Dieser virtuelle Kurs zum Selbststudium wird im Herbstsemester auch als physikalischer Kurs angeboten. Studenten ist empfohlen die Vorlesung und Übungen des physikalischen Kurses 252-0856-00L zu besuchen. | |||||||||||||||||||||||||||||||||||||||||