E/A-effiziente Algorithmen, auch bekannt als Algorithmen für externen Speicher oder cache-oblivious Algorithmen, sind eine Klasse von Algorithmen, die für die effiziente Verarbeitung von Daten entwickelt wurden, die zu groß sind, um vollständig in den Hauptspeicher (RAM) eines Computers zu passen. Diese Algorithmen sind besonders nützlich, wenn es um große Datenmengen geht, wie sie bei der Verarbeitung großer Datenmengen, der Verwaltung von Datenbanken und Dateisystemen vorkommen. Operationen auf Daten werden teurer, wenn sich das Datenelement weiter oben 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 in einem externen Speicher befindet, der erst abgerufen werden muss. Diese Datenabrufe werden auch als E/A-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 für den effektiven Umgang mit solchen Problemen erforderlich sind. Wir werden mit einer vereinfachten Speicherhierarchie arbeiten, aber die Begriffe lassen sich natürlich auf realistischere Modelle übertragen.

Voraussetzungen: Um an diesem Kurs erfolgreich teilnehmen zu können, sollten Sie bereits über Grundkenntnisse in Algorithmen und Mathematik verfügen. Hier eine kurze Liste dessen, was Sie wissen sollten: - O-Notation, Ω-Notation, Θ-Notation; wie man Algorithmen analysiert - Grundrechenarten: Manipulation von Summen, Lösen von Rekursen, Arbeiten mit Logarithmen usw. - Grundlegende Wahrscheinlichkeitstheorie: Ereignisse, Wahrscheinlichkeitsverteilungen, Zufallsvariablen, Erwartungswerte usw. - Grundlegende Datenstrukturen: verknüpfte Listen, Stapel, Warteschlangen, Heaps - (Ausgewogene) binäre Suchbäume - Grundlegende Sortieralgorithmen, z.B. MergeSort, InsertionSort, QuickSort - Graphenterminologie, Darstellungen von Graphen (Adjazenzlisten und Adjazenzmatrix), grundlegende Graphenalgorithmen (BFS, DFS, topologische Sortierung, kürzeste Pfade) Das Material für diesen Kurs basiert auf den Kursnotizen, die Sie unter der Registerkarte Ressourcen finden. Wir werden nicht alles aus den Kursnotizen abdecken. 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 Videovorlesungen enthalten ein paar sehr kleine Fehler. Eine Liste dieser Fehler finden Sie unter Ressourcen. Wenn Sie glauben, einen Fehler gefunden zu haben, melden Sie das Problem, indem Sie auf die quadratische Flagge unten in der Vorlesung oder im Quiz klicken, in der Sie den Fehler gefunden haben.