Allgemeine Informationen

Veranstaltungsname	Vorlesung: I/O-effiziente Algorithmen
Veranstaltungsnummer	INF-0053
Semester	SS 2020
Aktuelle Anzahl der Teilnehmenden	10
Heimat-Einrichtung	Theoretische Informatik
beteiligte Einrichtungen	Fakultät für Angewandte Informatik
Veranstaltungstyp	Vorlesung in der Kategorie Lehre
Erster Termin	Mittwoch, 22.04.2020 08:15 - 09:45, Ort: (1054 N)
Teilnehmende	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
Sonstiges	Aktuelle Informationen zur Veranstaltungen erhalten Sie durch die Ankündigungs-Funktion von Digicampus.
ECTS-Punkte	5

Lehrende

Räume und Zeiten

(1054 N): Mittwoch: 08:15 - 09:45, wöchentlich (13x)
Keine Raumangabe: Mittwoch: 08:15 - 09:45, wöchentlich

Studienbereiche

Fakultät für Angewandte Informatik > Informatik

Kommentar/Beschreibung

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".