Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Algorithmen für die Speicherhierarchie (WS 07/08)

• Dozent:
  Dr. Riko Jacob

• Modul: IN2159

• Bereich:
  2+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
  

• Zeit und Ort:
  Montag 14:00 - 15:30, Hörsaal 00.013.009A

• Übung:
  2 SWS Übung zur Vorlesung
  Dienstag 12:30 - 14:00, Raum 03.11.018
  Übungsleitung: Michael Schnupp
  Übungsschein: Einen Schein erhält, wer am Ende der Vorlesung die mündliche Prüfung erfolgreich besteht.

• Klausur:
  

• Hörerkreis:
  Studierende im Hauptstudium der Informatik

• ECTS: 5 Punkte

• Voraussetzungen:
  Stoff des Informatik Grundstudiums
  Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.

• Inhalt:
  
  • Modellbildung Speicherhierarchie (I/O-Modell, cache-oblivious Modell),
  • elementare I/O-Algorithmen (Scannen, Sortieren, Permutieren)
  • I/O-Datenstrukturen (Listen, Arrays, B-Bäume)
  • I/O-Graphenalgorithmen (DFS, BFS, kürzeste Pfade, minimale Spannbäume)
  • untere Schranken im I/O-Modell (Sortieren, Permutieren, Matrix-Multiplikation)
  • geometrische I/O-Algorithmen
  • Textalgorithmen und Datenstrukturen im I/O-Modell
  • Verbindung zu parallelen Algorithmen

• Weiterführende bzw. verwandte Vorlesungen:
  Effiziente Algorithmen und Datenstrukturen I und II

• Skript:

• Literatur:
  

• Sprechstunde:
  siehe hier