Informatik II - FS 2019
Vorlesungsverzeichnis: 252-0845-00L
Dozenten:
Felix Friedrich,
Hermann Lehner
Vorlesungsverzeichnis: 252-0845-00L
Dozenten:
Felix Friedrich,
Hermann Lehner
| Datum | Mitteilung |
|---|---|
| 19.12.2019 | Prüfung August 2019 online (s. unten) |
| Vorlesung | Montag | 12:45-14:30 | HIL E 3 |
|---|---|---|---|
| Übungen | Donnerstag | 12:45-14:30, 14:45-16:30 | Verschiedene Räume |
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.
Um eigene Programme auszuprobieren, empfehlen wir folgendes Sandbox Projekt:
Hier können Sie Fragen an alle richten und Feedback geben:
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 | 18.02. |
Einführung.
Begriff des Algorithmus, Beispiel: Altägyptische Multiplikation Komplexität. Random Access Machine Model, Effizienz von Algorithmen, Asymptotik: O-Notation, Omega, Theta |
Organisation
(english)
Folien 1 (en) Handout 1 (en) |
Einschreibung Uebungen
Asymptotics (Theory). Artificial Words Slides (en) |
Ant Algorithm | |
| 2 | 25.02. | Suchen und Sortieren. Lineare Suche, Binäre Suche, Divide and Conquer, Selection Sort, Mergesort, Quicksort |
Folien 2
(en)
Handout 2 (en) |
Recursive Function Analysis, Hottest Path, Mergesort Slides (en) |
||
| 3 | 04.03. | Python I (Einführung) |
Folien 3
(en)
Handout 3 (en) |
Python Introduction. Transfer from Java to Python. Slides (en) |
Ant algorithm | |
| 4 | 11.03. | Python II (Data Processing ) |
Folien 4
(en)
Handout 4 (en) |
Data Analysis with Python. Slides (en) |
Heap Datastructures | |
| 5 | 18.03. | Java I/O und Exception Handling |
Folien 5
(en)
Handout 5 (en) |
Processing Earthquake Data Slides (en) |
||
| 6 | 25.03. | Wörterbücher: Hashtabellen, Hashfunktionen (Pre-Hashing und Hashing), Kollisionsauflösung durch Verkettung, Tabellenvergrösserung, offene Addressierung. |
Folien 6
(en)
Handout 6 (en) |
Hashing, Finding a Substring (Rabin-Karp) Slides (en) |
Streams and Heaps | |
| 7 | 01.04. | Bäume Suchbäume, Heaps (Wiederholung), Augmnentierung und balancierte (AVL) Bäume |
Folien 7
(en)
Handout 7 (en) |
Binary Search Trees, Heaps and AVL Trees Slides (en) |
Shortest Paths | |
| -- | 08.04. | -- | --Sechseläuten-- |
Heaps and HeapSort Slides (en) |
||
| 8 | 15.04. | Dynamische Programmierung Memoisieren, Optimale Substruktur, Überlappende Teilprobleme, Abhängigkeiten, Allgemeines Vorgehen. Beispiele: Schneiden von Eisenstäben, Kaninchen, Editierdistanz |
Folien 8
(en)
Handout 8 (en) (Handschriftliche Notizen) |
Dynamic Programming Slides (en) |
||
| -- | 22.04. | -- | --Osterferien-- | |||
| 9 | 29.04. | Graphen Notation und Repräsentation, Traversieren (DFS, BFS), Topologisches Sortieren |
Folien 9
(en)
Handout 9 (en) (Handschriftliche Notizen) |
DFS, BFS and Topological Sorting. Slides (en) |
||
| 10 | 06.05. | Kürzeste Wege Motivation, Dreiecksungleichung, Optimale Substruktur, Dijkstras Algorithmus auf Distanzgraphen, Algorithmus von Bellman-Ford |
Folien 10
(en)
Handout 10 (en) (Handschriftliche Notizen) (Clicker Frage) |
Shortest Paths. Slides (en) |
Shortest Paths Graph | |
| 11 | 13.05. | Minimale Spannbäume Motivation, Greedy, Algorithmus von Kruskal, Allgemeine Regeln, Union-Find Struktur, Algorithmus von Jarnik, Prim, Dijkstra |
Folien 11
(en)
Handout 11 (en) (Handschriftliche Notizen) |
Minimum Spanning Trees Slides (en) |
||
| 12 | 20.05. | Maximaler Fluss Flussnetzwerk, Maximaler Fluss, Schnitt, Restnetzwerk, Max-flow Min-cut Theorem, Ford-Fulkerson Methode, Edmonds-Karp Algorithmus, Maximales Bipartites Matching |
Folien 12
(en)
Handout 12 (en) (Handschriftliche Notizen) |
Max Flow Slides (en) |
||
| 13 | 27.05. | Wrap-Up, Evaluation, Prüfung |
Alle Folien
(en)
Alle Handouts (en) Alle Handouts (2x2) (en) |
(kein Übungsbetrieb: Auffahrt) |
Die Einschreibung zum Übungssystem erfolgt online. Weitere Informationen während der ersten Vorlesung.
| Zeit | Assistent | Ort | Sprache |
|---|---|---|---|
| Donnerstag 13-15 | Chris Wendler | HIT F 31.1 | deutsch |
| Donnerstag 13-15 | Patrick Gruntz | HIT H 51 | deutsch |
| Donnerstag 13-15 | Aristeidis Mastoras | HCI J8 | english |
| Donnerstag 15-17 | Manuel Winkler | HCI D4 | deutsch |
| Präsenzstunde Donnerstag 15-17 | Michael Seeber | HCI F2 | de/en |
| Präsenzstunde Donnerstag 17-19 | Michael Seeber | HCI F2 | de/en |
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. Erlaubte Hilfsmittel: Vier A4 Seiten (zwei A4 Blätter), handgeschrieben oder min. Fontgrösse 11 Pkt.
