Dozent
Prof. Dr.
Thomas Holenstein
Übungsleitung
Ralph Keusch
Zeit und Ort
Vorlesung: Dienstag 8:15 -
10:00, HG D 1.2
Die Vorlesung beginnt am 16. September 2014. Die ersten
Übungsstunden finden während der zweiten Semesterwoche statt.
Übungsgruppen
Die Einteilung in die
Übungsgruppen wird während der ersten Vorlesung vorgenommen.
- Gruppe 1 (Pascal
Engeler): Donnerstag 15:45 - 16:30, HCI D 4
- Gruppe 2 (Stephan Ammann): Donnerstag
15:45 - 16:30, HCI D 6
- Gruppe 3 (Ralph Keusch): Donnerstag 16:15 -
17:00, CAB G 52
- Gruppe 4 (Steve Muller): Donnerstag 16:15 -
17:00, CAB G 56
- Gruppe 5 (Ralph Keusch): Freitag 13:15 - 14:00, ML H
34.3
Inhalt
Die Vorlesung
behandelt den Entwurf und die Analyse von Algorithmen und Datenstrukturen.
Themengebiete sind:
- Einführung: RAM-Maschine, Datenstrukturen, Graphen
- Algorithmen: Sortieren, Medianbestimmung, Matrixmultiplikation, kürzeste
Pfade, minimale spannende Bäume
- Paradigmen des Algorithmenentwurfs:
Divide&Conquer, dynamische Programmierung, Greedy
- Datenstrukturen:
Suchbäume, Wörterbücher, Priority Queues
- Berechenbarkeit und
Komplexität: berechenbare Sprachen, Klassen P und NP, Formeln und Schaltkreise,
Beispiele für Reduktionen, NP-Vollständigkeit
- Ausblick:
Optimierungsprobleme, Approximationsalgorithmen
Übungsblätter
Die Bearbeitung der Serien ist
nicht verpflichtend. Wir empfehlen Ihnen trotzdem dringend, die Übungen schon
während des Semesters zu lösen. Beachten Sie, dass dies die einzige Möglichkeit
ist, direktes Feedback zu erhalten. Abgabe der Serien ist jeweils dienstags in
der Vorlesung, die Serien werden von den Assistenten auf die nächste
Übungsstunde korrigiert.
Vorlesungsunterlagen
- Das Skript
zur Vorlesung ist gegen einen Druckkostenbeitrag von 10 Fr. erhältlich.
-
Errata:
S.81, Definition 5.15: Eine Sprache L ist NP-
schwer, falls für alle L' in NP gilt: L <= L' (und nicht bloss für alle L' in
P)
Prüfung
Die Prüfung ist schriftlich und dauert 120 Minuten. Als Hilfsmittel
dürfen 10 (beidseitig) handgeschriebene DIN A4 Blätter verwendet werden. Zur
Vorbereitung stehen die folgenden Beispielklausuren zur Verfügung:
Die Lösungen sind nicht so ausführlich geschrieben wie die
Musterlösungen zu den Übungen. Sie sollen demonstrieren, was in der Prüfung für
die maximale Punktzahl verlangt wird.
Literatur
- T.
Cormen, C. Leiserson, R. Rivest:
-
Introduction to Algorithms,
MIT Press, 1990
- H.J. Prömel, A. Steger:
-
The Steiner Tree
Problem: A Tour Through Graphs, Algorithms and Complexity, Vieweg 2002
- R. Sedgewick:
-
Algorithmen in C++, Pearson, 2003
- S Baase, A. van Gelder:
-
Computer Algorithms,
Addison Wesley, 2000
- G. Brassard, P. Bratley:
-
Fundamentals of Algorithms, Prentice Hall, 1996
- J.
Kleinberg, E. Tardos:
-
Algorithm Design, Addison Wesley,
2005
- T. Ottmann , P. Widmayer:
-
Algorithmen und
Datenstrukturen, Spektrum, 2002
