Neuigkeiten
- 2017-10-16 (fof): Probeprüfung 07.2017 und Prüfung 08.2017 online
- 2018-01-08 (fof): Lösung Aufgabe 6b im Mock-Exam 2017 verbessert.
Übungsserien und Vorlesungsfolien
Die erste Übungsserie und die Folien zur Vorlesung werden in der ersten Vorlesungswoche aufgeschaltet.
Termine
| Vorlesung | Montag 10:15 - 12:00 | ML F 36 |
|---|---|---|
| Donnerstag 08:15 - 10:00 | ML E 12 | |
| Übungen | Freitag 10:15 - 12:00 | Verschiedene Räume (s.u.) |
Überblick
Es werden grundlegende Entwurfsmuster für Algorithmen (z.B. Induktion, divide-and-conquer, backtracking, dynamische Programmierung), klassische algorithmische Probleme (Suchen, Sortieren) und Datenstrukturen (Listen, Hashverfahren, Suchbäume) behandelt. Ausserdem enthält der Kurs eine Einführung in das parallele Programmieren. Das Programmiermodell von C++ wird vertieft behandelt.
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 Programmiersprache C++(14).
Vorrausetzung: Vorlesung Informatik I (D-ITET) oder gleichwertige Kenntnisse. Folien und Skript zur Vorlesung Informatik I finden Sie hier
Zeitplan, Folien und Übungen
Dies ist ein Plan und als solcher unterliegt er Änderungen -- auch und insbesondere nach Semesterbeginn.
| Woche | Datum | Thema | Folien und Handouts | Übungen, Lösungsskizzen |
|---|---|---|---|---|
| 1 | MO 20.02. | Begriff des Algorithmus, drei Beispiele: Altägyptische Multiplikation, Schnelle Multiplikation grosser Zahlen, Finde den Star |
Folien 1 handout 2x2 english 2x2 |
|
| 1 | DO 23.02. | Effizienz von Algorithmen, Random Access Machine Modell, Asymptotik: O-Notation, Omega, Theta, Entwurf von Algorithmen: Maximum Subarray (naiv, Präfixsummen, Divide and Conquer, linear) |
Folien 2 handout 2x2 english 2x2 |
Exercise 1 Solution 1 Folien |
| 2 | MO 27.02. | Suchen und Auswählen Lineare Suche, Binäre Suche, Interpolationssuche, Exponentielle Suche, untere Schranken, Das Auswahlproblem, Randomisierte Berechnung des Medians, Auswahl in linearer Zeit |
Folien 3 handout 2x2 english 2x2 |
|
| 2 | DO 02.03. |
C++ Vertieft (I) Kurzwiederholung (Vektoren, Zeiger und Iteratoren), Bereichsbasiertes for, Schlüsselwort auto, eine Klasse für Vektoren, Subskript-Operator, Move-Konstruktion, Iteration. Sortieren I: Insertion-Sort, Selection-Sort, Bubble-Sort, Shell-Sort |
Folien 4 handout 2x2 english 2x2 |
Exercise 2 Solution 2 Folien Slides |
| 3 | MO 06.03. | Sortieren II: Heapsort: implizite Repräsentation vom Heap im Array, Heapbilden in Linearzeit, Mergesort, Quicksort: Schlüsselvergleiche im besten/schlechtesten Fall. |
Folien 5 handout 2x2 english 2x2 |
|
| 3 | DO 09.03. |
Fortsetzung Sortieren II C++ II: Templates. |
Folien 6 handout 2x2 english 2x2 |
Exercise 3 Solution 3 Folien Slides |
| 4 | MO 13.03. |
Sortieren III: Schlüsselbewegungen und Speicherbedarf beim Quicksort, Quicksort randomisiert, Untere Schranken, Radixsort. Elementare Datenstrukturen Stapel, Warteschlange, Implementationsvarianten der verkettete Liste, Amortisierte Analyse beim Multistack |
Folien 7 handout 2x2 english 2x2 |
|
| 4 | DO 16.03. |
Wörterbücher II : Array, verkettete Liste, Amortisierte Analyse Move-To-Front, Skipliste C++ III Funktoren und Lambda. |
Folien 8 handout 2x2 english 2x2 |
Exercise 4 Solution 4 Folien Slides |
| 5 | MO 20.03. |
C++ III ctd. Wörterbücher III Prinzip des Hashing, Hashfunktionen, Kollisionsauflösung durch Verkettung, offene Hashverfahren |
Folien 9 handout 2x2 english 2x2 |
|
| 5 | DO 23.03. |
Wörterbücker III ctd. C++ IV: Ausnahmen |
Folien 10 handout 2x2 english 2x2 |
Exercise 5 Solution 5 Folien Slides |
| 6 | MO 27.03. |
Wörterbücher IV Natürliche Suchbäume, AVL Bäume |
Folien 11 handout 2x2 english 2x2 Clickerfrage Exceptions |
|
| 6 | DO 30.03. | AVL Tress ctd. Quadtrees Bildsegmentierung, Funktionalminimierung, Reduktionsprinzip |
Folien 12 handout 2x2 english 2x2 |
Exercise 6 Solution 6 AVL Baum Implementation ohne ** Folien Slides |
| 7 | MO 03.04. | Dynamische Programmierung I Fibonacci, Längste aufsteigende Teilfolge, längste gemeinsame Teilfolge, Editierdistanz, Matrixkettenmultiplikation, Matrixmultiplikation nach Strassen |
Folien 13 handout 2x2 english 2x2 |
|
| 7 | DO 06.04. | Dynamische Programmierung II Subset Sum Problem, Rucksackproblem, Greedy Algorithmus, Lösungen mit dynamischer Programmierung, FPTAS, Optimaler Suchbaum |
Folien 14 handout 2x2 english 2x2 |
Exercise 7 Solution 7 Folien Slides |
| 8 | MO 10.04. | Dynamic Programming II ctd. Greedy Algorithmen Dynamic Programming vs. Greedy. Aktivitätenzuteilung, Huffman Coding |
Folien 15 handout 2x2 english 2x2 |
|
| 8 | DO 13.04. | Graphenalgorithmen I Notation, Repräsentationsarten, Graphen und Relationen, Reflexive transitive Hülle, Traversieren (DFS, BFS), Zusammenhangskomponenten, Topologisches Sortieren |
Folien 16 handout 2x2 english 2x2 |
keine Übung |
| - | MO 17.04. | OSTERN | ||
| - | DO 20.04. | OSTERFERIEN | ||
| 9 | MO 24.04. | Graphenalgorithmen II: Kürzeste Wege Dijkstras Algorithmus auf Distanzgraphen, Algorithmus von Bellman-Ford, Algorithmus von Floyd-Warshall, Algorithmus von Johnson |
Folien 17 handout 2x2 english 2x2 |
|
| 9 | DO 27.04. | Graphenalgorithmen III: Minimale Spannbäume Greedy, Algorithmus von Kruskal, Allgemeine Regeln, Union-Find Struktur, Algorithmus von Jarnik,Prim,Dijkstra, Fibonacci Heaps |
Folien 18 handout 2x2 english 2x2 |
Exercise 8 Solution 8 Folien Slides |
| 10 | MO 01.05. | TAG DER ARBEIT | ||
| 10 | DO 04.05. | Graphenalgorithmen III: Minimale Spannbäume Fortsetzung | --- | Exercise 9 Solution 9 Folien Slides |
| 11 | MO 08.05. | Graphenalgorithmen IV: Flüsse in Graphen Flussnetzwerk, Maximaler Fluss, Schnitt, Restnetzwerk, Max-flow Min-cut Theorem, Ford-Fulkerson Methode, Edmonds-Karp Algorithmus, Maximales Bipartites Matching |
Folien 19 handout 2x2 english 2x2 |
|
| 11 | DO 11.05. | Geometrische Algorithmen Lage von Strecken, Schnitt vieler Strecken, Konvexe Hülle, Dichtestes Punktepaar |
Folien 20 handout 2x2 english 2x2 |
Exercise 10 Solution 10 Folien Slides |
| 12 | MO 15.05. |
Parallele Programmierung I Moore's Law und The Free Lunch, Parallele Ausführung, Hardware Architekturen, Parallele Ausführung, Klassifikation nach Flynn, Multi-Threading, Parallelität und Nebenläufigkeit
|
Folien 21 handout 2x2 english 2x2 |
|
| 12 | DO 18.05. |
(Parallele Programmierung I ctd.)
Skalierbarkeit: Amdahl und Gustafson, Daten- und Taskparallelität, Scheduling
Parallele Programmierung II Threads in C++. |
Folien 22 handout 2x2 english 2x2 |
Exercise 11 Solution 11 Folien Slides |
| 13 | MO 22.05. |
(Parallele Programmierung II ctd.) Nebenläufige Programmierung. Data-Race, Interleavings, Memory-Reordering, Mutexes in C++11 |
(Counter)Examples from the lectures: Bank_Account_Sequential Thread_Unsafe_Counter |
Exercise 12 Solution 12 Folien Slides |
| 13 | DO 25.05. | AUFFAHRT | ||
| 14 | MO 29.05. | Parallele Programmierung III Deadlocks, Deadlock Erkennung und Vermeidung, Producer / Consumer, Monitore und Condition Variablen, Condition Variablen in C++, Promises und Futures in C++ |
Folien 23 handout 2x2 english 2x2 (Counter)Examples from the lectures: Bank_Account_Concurrent Producer_Consumer |
|
| 14 | DO 01.06. | Parallele Programmierung IV C++ Futures, Atomare Register und RMW Operationen, Idee vom Lock-Free Programming |
Folien 24 handout 2x2 english 2x2 Examples from the lectures: Self-made Future Using C++11 Futures Lock-Free Stack |
Folien Slides |
|
Alle Folien handout 2x2 english 2x2 |
Ü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 wie folgt zugeteilt:
| Zeit | Ort | Assistent | Sprache |
|---|---|---|---|
| Fr, 08:15 - 10:00 | CAB G 57 | Alexander Pilz | english |
| Fr, 10:15 - 12:00 | HG D 5.1 | Daniel Hupp | deutsch |
| Fr, 10:15 - 12:00 | RZ F 21 | Lukas Humbel | deutsch |
Kontakt
Zur Prüfung
Prüfungsstoff für die Endprüfung, welche in der Prüfungssession Sommer 2017 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.
Alte Prüfungen
- 2017
Exam 08.2017 Solution
Mock-Exam 07.2017 Solution
- Datenstrukturen und Algorithmen
- Parallel Programming (nur sehr eingeschränkt anwendbar, zumal mit Java, am ehesten die Theorieteile):
BP_2017_Winter (Solution)
BP_2016_Summer (Solution)
BP_2015_Winter (Solution)
BP_2015_Summer (Solution)
BP_2014_Winter (English) BP_2014_Winter (German) (Solution)
BP_2014_Summer (English) BP_2014_Summer (German) (Solution)
Literatur
- Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011, auch online / download.
- Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein: Algorithmen - Eine Einführung, Oldenbourg, 2010
- Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009. ISBN 978-0-262-03384-8 (recommended english text book)
- Maurice Herlihy, Nir Shavit, The Art of Multiprocessor Programming, Elsevier, 2012.
- Anthony Willians, C++ Concurrency in Action, Manning, 2012
- B. Stroustrup, The C++ Programming Language (4th Edition) Addison-Wesley, 2013.
- Genaue Behandlung der zugrundeliegenden Mathematik im Buch Concrete Mathematics von Graham, Knuth und Patashnik. [Geht weit über die benötigten Mittel der Vorlesung hinaus].