Informatik II - FS 2020

Vorlesungsverzeichnis: 252-0846-00L
Dozenten: Felix Friedrich, Hermann Lehner

Neuigkeiten

Datum Mitteilung
25.11.2020 Prüfung vom August ist inklusive Lösung verfügbar (siehe Vergangene Prüfungen / Lösungen)

Online Vorlesungen und Übungen

Alle Vorlesungen und Uebungsgruppen werden online stattfinden. Sie finden die Informationen unter folgendem Link. Verwenden Sie Ihr ETH-Login, wenn Sie nach einem Passwort gefragt werden. .

Link zu den Online-Vorlesungen und Übungen

Termine

Vorlesung Montag 12:45-14:30 HIL E 6
Übungen Donnerstag 12:45-14:30, 14:45-16:30 Verschiedene Räume

Die Vorlesung wird aufgezeichnet. Login und Passwort wurden per Email kommuniziert.

Lernziel und Überblick

Zusammen mit der Veranstaltung Informatik I bietet diese Veranstaltung eine Einführung in die Grundlagen der Programmierung. Die Vorlesung II vermittelt insbesondere die gebräuchlichsten Algorithmen und Datenstrukturen. Verwendete Programmiersprachen der Vorlesung sind Java und Python.

Studenten beherrschen nach erfolgreichem Abschluss der Vorlesung die Mechanismen zur Erstellung eines Programmes im objektorientierten Kontext. Sie kennen die gängigen Datenstrukturen und Algorithmen. Sie können korrekte und ausreichend effiziente Programme entwickeln, um eine klar formulierte Problemstellung zu lösen.

Es wird generell das formale Denken und Notwendigkeit zur Abstraktion, sowie die Bedeutung geeigneter Modellbildungen für die Informatik motiviert. Der Schwerpunkt der Vorlesung liegt auf der praktischen Informatik. Konkrete Themen sind u.a.: Komplexität von Algorithmen, Divide and Conquer-Prinzip, Rekursion, Sortieralgorithmen, Datenstrukturen (Listen, Stacks, Warteschlangen, binäre Bäume) und Algorithmen auf Graphen.

Die Konzepte der Vorlesung werden jeweils durch Algorithmen und Anwendungen motiviert und illustriert. Verwendete Programmiersprachen der Vorlesung und der praktischen Übungen sind Java und Python.

Für das effiziente Praktizieren der vorgestellten Inhalte wird in den Übungen ein Online-Compiler mit Abgabesystem verwendet.

Code Expert IDE Sandbox

Um eigene Programme auszuprobieren, empfehlen wir folgende Sandbox Projekte:

Java Python

Material

Die Vorlesungsunterlagen bestehen aus Vorlesungsfolien und Übungsunterlagen. Die Vorlesungsfolien sind auf Deutsch verfasst und stellen zusammen mit den Übungsblättern den Prüfungsstoff dar.

Übungsserien und Vorlesungsfolien

Die erste Übungsserie und die Folien zur Vorlesung werden in der ersten Vorlesungswoche aufgeschaltet.

Zeitplan, Folien und Übungen

Dies ist ein Plan und als solcher unterliegt er Änderungen -- auch und insbesondere nach Semesterbeginn.

Woche Datum Thema Vorlesung Übung PPrerequisites to unlock bonus exercises BBonus exercises
1 17.02. Python I (Einführung) Organisatorisches (en) Folien 1 (en)
Handout 1 (en)
Beispiele als Jupyter Notebook 		Einschreibung Uebungen Ant Algorithm
2 24.02. Python II (Data Processing ) Folien 2 (en)
Handout 2 (en)
Jupyter Notebook [PDF] 		Dynamic Data Structures (Queue) and Data Analysis with Python.
Slides (en)
3 02.03. Komplexität und Effizienz von Algorithmen Beispiel Sortieren durch Auswahl, Random Access Machine Model, Effizienz von Algorithmen, Asymptotik: O-Notation, Omega, Theta
 Folien 3 (en)
Handout 3 (en)
Jupyter Notebook (Sorting) [PDF] 		Asymptotics (Theory). Artificial Words
Slides (en) 		Ant algorithm
4 09.03. Suchen und Sortieren. Lineare Suche, Binäre Suche, Divide and Conquer, Mergesort, Quicksort Folien 4 (en)
Handout 4 (en)
Jupyter Notebook (Searching and Sorting) [PDF] 		Recursive Function Analysis, Compare Sort Algorithms, Throwing Eggs Merge Sort
Slides (en) 		Heaps
5 16.03. Bäume Suchbäume, Heaps Folien 5 (en)
Handout 5 (en)
Jupyter Notebook (Trees) [PDF] 		Search trees and Heaps
Slides (en)
6 23.03. Bäume ctd. Augmentierung und balancierte (AVL) Bäume Folien 6 (en)
Handout 6 (en) 		Augmented Trees and AVL Trees
Slides (en) 		Heaps
7 30.03. Wörterbücher: Hashtabellen, Hashfunktionen (Pre-Hashing und Hashing), Kollisionsauflösung durch Verkettung, Tabellenvergrösserung, offene Addressierung. Folien 7 (en)
Handout 7 (en)
Jupyter Notebook (Hashing) [PDF] 		Hashing
Slides (en) 		Shortest Paths
8 06.04. Graphen Notation und Repräsentation, Traversieren (DFS, BFS), Topologisches Sortieren Folien 8 (en)
Handout 8 (en)
Handgeschriebene Notizen 		DFS, BFS and Topological Sorting.
Slides (en)
-- 13.04. -- --Osterferien--
-- 20.04. -- --Sechseläuten-- (Productive Failure Exercise 2)
9 27.04. Kürzeste Wege Motivation, Dreiecksungleichung, Optimale Substruktur, Dijkstras Algorithmus auf Distanzgraphen, Algorithmus von Bellman-Ford Folien 9 (en)
Handout 9 (en)
Handgeschriebene Notizen 		Shortest Paths.
Slides (en) 		Shortest Paths Graph
10 04.05. Minimale Spannbäume Motivation, Greedy, Algorithmus von Kruskal, Allgemeine Regeln, Union-Find Struktur, Algorithmus von Jarnik, Prim, Dijkstra Folien 10 (en)
Handout 10 (en)
Handgeschriebene Notizen Folien zu Pruefungen / Semesterfeedback 		Minimum Spanning Trees
Slides (en)
11 11.05. Maximaler Fluss Flussnetzwerk, Maximaler Fluss, Schnitt, Restnetzwerk, Max-flow Min-cut Theorem, Ford-Fulkerson Methode, Edmonds-Karp Algorithmus, Maximales Bipartites Matching Folien 11 (en)
Handout 11 (en)
Handgeschriebene Notizen 		Max Flow
Slides (en)
12 18.05. Dynamische Programmierung Memoisieren, Optimale Substruktur, Überlappende Teilprobleme, Abhängigkeiten, Allgemeines Vorgehen. Beispiele: Schneiden von Eisenstäben, Kaninchen Folien 12 (en)
Handout 12 (en)
handwritten
Jupyter Notebook (DP) (pdf) 		(kein Übungsbetrieb: Auffahrt) Dynamic Programming
13 25.05. Dynamische Programmierung Editierdistanz, Bellman-Ford Algorithmus Folien 13 (en)
Handout 13 (en)

handwritten
Jupyter Notebook (DP) (pdf)

Alle Folien (en)
Alle Handout (en)
 Slides (en)

Übungen

Einschreibung für die Übungen

Die Einschreibung zum Übungssystem erfolgt online. Weitere Informationen während der ersten Vorlesung.

Orte und Zeiten

Die Übungsgruppen sind derzeit wie folgt zugeteilt:
Zeit Assistent Ort Sprache
Donnerstag 13-15 Sverrir Thorgeirsson, Prashanth Chandran HCI J 8 englisch
Donnerstag 13-15 Vu Nguyen HIT H 51 deutsch
Donnerstag 13-15 Michael Seeber HIT K 52deutsch
Donnerstag 15-17 Jan Osusky HCI D 6deutsch

Literatur

Wir versuchen, den Kurs grundsätzlich selbsterklärend zu gestalten. Trotzdem lohnt sich es sich natürlich immer, auch andere Quellen heranzuziehen.
  • Hanspeter Mössenböck, Sprechen Sie Java?, dpunkt Verlag, 5. Auflage 2014.
  • Thomas Ottmann, Peter Widmayer, Algorithmen und Datenstrukturen, Springer, auch online
  • T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algorithmen - Eine Einführung, Oldenbourg, 2010
  • Aditya Y. Bhargava, Algorithmen Kapieren, mitp 2019
Folgende Links könnten Ihnen beim Erlernen der verwendeten Programmiersprache Java und als Nachschlagequellen hilfreich sein

Zur Prüfung

Modus

Prüfungsstoff für die Endprüfung, welche in der Prüfungssession Sommer 2019 stattfinden wird, schliesst Vorlesungsinhalt und Übungsinhalte ein.

Die Prüfung ist schriftlich. Teile finden am Computer statt. Erlaubte Hilfsmittel: Acht A4 Seiten (vier A4 Blätter). Keine inhaltlichen oder formalen Einschränkungen.

Vergangene Prüfungen

Online-Prüfungsteile sind hier direkt abrufbar.

Kontakt

Felix Friedrich (Lecturer)

Für inhaltliche Fragen: bitte auch das Forum auf Moodle verwenden