Diese Vorlesung mit Übung ist für Master-Studierende der Informatik wie der Mathematik.
Voraussetzungen
Gutes Verständnis des Informatik III-Stoffes
Leistungsnachweis
mündliche Prüfung
Studierende der Mathematik müssen sich für die Prüfung persönlich in ihrem Prüfungsamt anmelden, da eine STUDIS-Anmeldung derzeit für sie nicht möglich ist.
Online/Digitale Veranstaltung
Veranstaltung wird online/digital abgehalten.
Hauptunterrichtssprache
deutsch
Literaturhinweise
Skript
J.S. Vitter, Algorithms and Data Structures for External Memory, Foundations and Trends in Theoretical Computer Science 2 (2008), pp. 305 - 474
Das klassische Berechnungsmodell der Random-Access-Maschine (RAM) stößt zunehmend an seine Grenzen. Der Grund ist, dass moderne Rechner nicht über den "flachen" Speicher der RAM verfügen, bei dem alle Speicherzellen "gleichberechtigt" sind, sondern eine ausgefeilte Speicherhierarchie mit Caches, Hauptspeicher und Hintergrundspeicher(n) besitzen.
Im Allgemeinen sind "näher am CPU" gelegene Speicher deutlich schneller, dafür aber kleiner, und ein effizienter Algorithmus muss versuchen, häufig benutzte Daten in Speichern mit kurzen Zugriffszeiten zu halten.
In der Vorlesung werden wir uns, nach einer Einführung geeigneter Speichermodelle, aus theoretischer Sicht mit sogenannten I/O-effizienten oder "speicherbewussten" Algorithmen befassen, die die Anzahl der Datentransporte zwischen Stufen der Speicherhierarchie möglichst gering halten. Bereits für das Problem des Sortierens wird sich herausstellen, dass die "I/O-effiziente Welt" ganz anders aussieht als die "RAM-Welt".
Anmelderegeln
Diese Veranstaltung gehört zum Anmeldeset "Anmeldung gesperrt (global)".
