LEA

Algorithmen für die Speicherhierarchie (Sommer 2009)

  • Dozent:
    Dr. Riko Jacob

  • Modul: IN2159

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

  • Zeit und Ort:
    Mittwoch, 13:30-15:00, Raum 03.11.018

  • Übung:
    2 SWS Übung zur Vorlesung
    Mittwoch 15:00 - 16:30, Raum 03.11.018
    1. Blatt
    2. Blatt
    3. Blatt
    4. Blatt
    5. Blatt
    6. Blatt
    7. Blatt
    8. Blatt
    9. Blatt
    10. Blatt
    11. Blatt
    12. Blatt
    Übungsleitung: Gero Greiner
    Übungsschein: Einen Schein erhält, wer am Ende der Vorlesung die mündliche Prüfung erfolgreich besteht.

  • 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: Stunde am 22.04.2009: Modellbildung Folien
    Stunde am 29.04.2009: Sortieren, Permutieren Folien
    Stunde am 06.05.2009: Dichtbesetzte Matrizen Folien
    Stunde am 13.05.2009: einfache Datenstrukturen, basiert auf Kapitel 2 von LNCS 2625 , Stacks, Queue, List, B-Tree, lower bound searching.
    Stunde am 20.05.2009: Cache-Oblivious Modell: Matrix Operations
    Stunde am 27.05.2009: Cache-Oblivious B-Trees
    Stunde am 3.06. und 17.06.2009: Cache-Oblivious Sorting (Brodal, Fagerberg: "Cache Oblivious Distribution Sweeping" ICALP 02)
    Stunde am 24.06.2009: List Ranking (in Kapitel 3 LNCS 2625)
    Stunde am 1.07.2009: Buffer-Tree (in Kapitel 2 LNCS 2625)
    Stunde am 8.07.2009: einfaches BFS (in Kapitel 4 LNCS 2625)
    Stunde am 15.07.2009: Euler-Tour Technik, verbessertes BFS (in Kapitel 4 LNCS 2625)

  • Vorlesungsfolien von Gerth Stølting Brodal & Rolf Fagerberg:
    http://www.daimi.au.dk/~gerth/emF03/
  • Literatur:

  • Sprechstunde:
    siehe hier