Lehrstuhl Informatik II   
Sprachen und Beschreibungsstrukturen      
   Home Lehre Sommersemester 09 Vorlesungen Grundlagen: Algorithmen und Datenstrukturen login

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:

Die aufgezeichneten Vorlesungen befinden sich im TeleTeachingTool-Archiv.

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:

Forum:

Infler


TUM - Lehrstuhl Informatik II (Sprachen und Beschreibungsstrukturen) Thanks: Tango and TinyMCE     Generationszeit: 18 ms