Digicampus
Lecture: I/O-effiziente Algorithmen - Details
You are not logged into Stud.IP.
Lehrveranstaltung wird online/digital abgehalten.

General information

Course number INF-0053
Semester SS 2020
Current number of participants 34
Home institute Theoretische Informatik
participating institutes Fakultät für Angewandte Informatik
Courses type Lecture in category Teaching
First date Wed , 22.04.2020 08:15 - 09:45, Room: (1054 N)
Participants Diese Vorlesung mit Übung ist für Master-Studierende der Informatik wie der Mathematik.
Pre-requisites Gutes Verständnis des Informatik III-Stoffes
Performance record 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
Miscellanea Aktuelle Informationen zur Veranstaltungen erhalten Sie durch die Ankündigungs-Funktion von Digicampus.
ECTS points 5

Course location / Course dates

(1054 N) Wednesday: 08:15 - 09:45, weekly (13x)
n.a Wednesday: 08:15 - 09:45, weekly

Module assignments

Comment/Description

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