Home
Lehre
aktuelle Semester...
Sommersemester 18
Wintersemester 17/18
Personen
Research
Projects
Events
Jobs/Studienarbeiten
SiteMap
Puma
Impressum & Datenschutz
|
Grundlagen: Algorithmen und Datenstrukturen
 |
Dozent: | Prof. Dr. H. Seidl |
Ort/Zeit: | MI HS 1 / Di 12:00 - 13:30 und Do 12:15 - 13:00 |
ModulNummer: | IN0007 |
Beschreibung: | Es werden grundlegende Algorithmen und Datenstrukturen und ihre Anwendung erklärt. Die Komplexität der zugehörigen Operationen und von (moderat komplexen) Algorithmen werden analysiert. |
Übung zu GAD | Übung zu "Grundlagen: Algorithmen und Datenstrukturen" |
|

Inhalt:
- Grundlagen der Komplexitätsanalyse
- Komplexität der Operationen von Listen, Stacks und Schlangen
- generische Kollektions-Datenstrukturen (Java collections)
- binäre Bäume und Algorithmen (preorder, inorder, postorder)
- binäre Suchbäume und balancierte Suchbäume (AVL, B-Bäume)
- Priority Queue
- Hashing inklusive erweiterbarem Hashing für Hintergrundspeicher
- Sortieren (Bubble-, Heap- und Quick-Sort) und sortierbasierte Algorithmen (Mengendurchschnitt)
- externes Sortieren
- Hash-basierte Algorithmen (Mengendurchschnitt)
- Graph-Darstellung und Graphalgorithmen (topolog. Sortieren, kürzeste Wege, Kruskal, DFS, BFS, TSP)
- Pattern Matching, Datenkompression (Huffman, Lempel-Ziv)
Klausur:
- Datum: Samstag 25. Juli 2009
- Anmeldung: TUMonline
- Merkblatt zur Klausur (Version 3: Hörsaaleinteilung korrigiert; Version 2: Kapitel 11 ist auch klausurrelevant!)
- Einsicht: am Montag, dem 24.08.09, um 14 Uhr (bis mindestens 15 Uhr). MI HS 1
- Notenschlüssel (ohne Bonus):
49-50 Punkte: 1,0 |
|
43,5-45 Punkte:2,0 |
|
35,5-38 Punkte: 3,0 |
|
25-28,5 Punkte: 4,0 |
47,5-48,5 Punkte: 1,3 |
|
41-43 Punkte: 2,3 |
|
32,5-35 Punkte: 3,3 |
|
<25 Punkte: nicht bestanden |
45,5-47 Punkte: 1,7 |
|
38,5-40,5 Punkte: 2,7 |
|
29-32 Punkte: 3,7 |
|
|
Klausur im Wintersemester:
- Datum: Samstag 10. Oktober 2009
- Uhrzeit: 9:00 - 11:00
- Anmeldung: TUMonline
- Einsicht: am Montag, dem 02.11.09, um 13 Uhr (bis mindestens 14 Uhr). Raum: 02.07.034
- Notenschlüssel (ohne Bonus):
49-50 Punkte: 1,0 |
|
43,5-45 Punkte:2,0 |
|
35,5-38 Punkte: 3,0 |
|
25-28,5 Punkte: 4,0 |
47,5-48,5 Punkte: 1,3 |
|
41-43 Punkte: 2,3 |
|
32,5-35 Punkte: 3,3 |
|
<25 Punkte: nicht bestanden |
45,5-47 Punkte: 1,7 |
|
38,5-40,5 Punkte: 2,7 |
|
29-32 Punkte: 3,7 |
|
|
Aufzeichnungen:
Folien:
Korrekturen:
- Folien 21.04.09 Version 3: 2. Fehler im Bresenham-Algorithmus korrigiert.
- Folien 21.04.09 Version 2: Fehler im Bresenham-Algorithmus korrigiert.
Literaturvorschläge:
- K. Mehlhorn, P. Sanders.
Algorithms and Data Structures - The Basic Toolbox. Springer, May 2008.
- Michael T. Goodrich, Roberto Tamassia.
Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons, Inc., Hoboken, NJ, 2002.
- Volker Heun.
Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen. 2. Auflage, Vieweg, Braunschweig-Wiesbaden, 2003.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Introduction to Algorithms. 2. Auflage, MIT Press, Cambridge, MA, 2001.
- Jon Kleinberg, Eva Tardos.
Algorithm Design. Pearson Education, Boston, MA, 2005.
- Uwe Schöning.
Algorithmik. Spektrum Akademischer Verlag, Heidelberg, 2001.
- Robert Sedgewick.
Algorithmen in Java. Teil 1-4. 3., überarbeitete Auflage, Pearson Education, München, 2003.
Zur Diskussion von Entwurfsprinzipien implementierbarer Algorithmen:

|