I/O-effiziente Algorithmen | Das Universitätsnetzwerk

Beschreibung

Operationen an Daten werden teurer, wenn sich das Datenelement höher in der Speicherhierarchie befindet. Eine Operation an Daten in CPU-Registern ist etwa eine Million Mal schneller als eine Operation an einem Datenelement, das sich im externen Speicher befindet und zuerst abgerufen werden muss. Diese Datenabrufe werden auch als I/O-Operationen bezeichnet und müssen beim Entwurf eines Algorithmus berücksichtigt werden. Ziel dieses Kurses ist es, sich mit wichtigen algorithmischen Konzepten und Techniken vertraut zu machen, die zur effektiven Bewältigung solcher Probleme erforderlich sind. Wir werden mit einer vereinfachten Speicherhierarchie arbeiten, aber die Konzepte erstrecken sich natürlich auch auf realistischere Modelle.

Voraussetzungen:
Um diesen Kurs erfolgreich absolvieren zu können, sollten Sie bereits über Grundkenntnisse in Algorithmen und Mathematik verfügen. Hier ist eine kurze Liste dessen, was Sie wissen sollten:
- O-Notation, Ω-Notation, Θ-Notation; wie man Algorithmen analysiert
- Grundrechnung: Manipulieren von Summationen, Lösen von Wiederholungen, Arbeiten mit Logarithmen usw.
- Grundlegende Wahrscheinlichkeitstheorie: Ereignisse, Wahrscheinlichkeitsverteilungen, Zufallsvariablen, Erwartungswerte usw.
- Grundlegende Datenstrukturen: verknüpfte Listen, Stapel, Warteschlangen, Haufen
- (ausgeglichene) binäre Suchbäume
- Grundlegende Sortieralgorithmen, zum Beispiel MergeSort, InsertionSort, QuickSort
- Graphenterminologie, Darstellungen von Graphen (Adjazenzlisten und Adjazenzmatrix), grundlegende Graphalgorithmen (BFS, DFS, topologische Sortierung, kürzeste Wege)

Das Material für diesen Kurs basiert auf den Kursnotizen, die Sie auf der Registerkarte Ressourcen finden. Wir werden nicht alles aus den Kursnotizen behandeln. Die Kursnotizen sind sowohl für Studenten gedacht, die die Vorlesungen nicht vollständig verstanden haben, als auch für Studenten, die tiefer in die Themen eintauchen möchten.

Die Videovorträge enthalten einige sehr kleine Fehler. Eine Liste dieser Fehler finden Sie unter Ressourcen. Wenn Sie glauben, einen Fehler gefunden zu haben, melden Sie ein Problem, indem Sie auf die quadratische Flagge unten in der Vorlesung oder im Quiz klicken, in der Sie den Fehler gefunden haben.