Ich habe nach einem guten Online-Kurs für Datenstrukturen gesucht, aber festgestellt, dass Google auch Ergebnisse für Algorithmus-Kurse zurückgibt, die folgende Informationen enthalten:

In diesem Kurs lernen Sie einige grundlegende Prinzipien des Algorithmusdesigns kennen: Divide-and-Conquer-Methoden, Graph-Algorithmen, praktische Datenstrukturen (Heaps, Hash-Tabellen, Suchbäume) , randomisierte Algorithmen und mehr. [Quelle]

und

Am Ende dieses Kurses werden Sie die wichtigsten Konzepte verstehen, die erforderlich sind, um neue Algorithmen für Diagramme und andere wichtige Datenstrukturen zu entwickeln und die Effizienz dieser Algorithmen zu bewerten. [Quelle]

und

Dieser Kurs bietet eine Einführung in die mathematische Modellierung von Rechenproblemen. Es werden die gängigen Algorithmen, algorithmischen Paradigmen und Datenstrukturen behandelt, die zur Lösung dieser Probleme verwendet werden . [Quelle]

Meine Frage ist: Sind Algorithmen und Datenstrukturen eng miteinander verknüpft, was bedeutet, dass sie zusammen verstanden werden müssen, oder ist ein Thema grundlegender als das andere?

EDIT: Wenn Sie diese Frage schließen möchten, können Sie mir bitte sagen, warum und vielleicht, wie Sie diese Frage verbessern können. Zu lernen, die richtigen Fragen zu stellen, ist Teil des Bildungsprozesses.

Es gibt alle Arten von Gemischen. Sie haben Datenstrukturen, die nicht mit Algorithmen verknüpft sind, Algorithmen, die keine (realen) Datenstrukturen erfordern, aber meistens sind beide in einem Paket enthalten.

Bearbeiten: Wie @Doval richtig hervorhob, sind Datenstrukturen per se nicht mit Operationen verknüpft. Das Kombinieren von Datenstruktur und Algorithmus bildet einen abstrakten Datentyp.

Datenstrukturen ohne Algorithmen

Betrachten Sie zum Beispiel eine Datenstruktur zum Speichern von zweidimensionalen Koordinaten, die entsprechend aufgerufen wird Point. Es gibt nicht viel in Bezug auf Algorithmen für einen Punkt zu tun und es ist wirklich nur ein Container für einen xund yWert. Aufgrund dieser Datenstruktur können Sie jetzt natürlich alle möglichen Algorithmen hinzufügen (Entfernungsberechnung, konvexe Rümpfe, What-Have-You).

Sie können an viele Datenstrukturen denken, die einfach eine Ansammlung einzelner Daten sind. Während diese in der Praxis häufig vorkommen, sind sie kein gutes Lehrmaterial, da daraus nichts zu lernen ist, sobald Sie verstanden haben, dass einzelne Datenelemente in einer neuen Datenstruktur akkumuliert werden können (wie das, was Sie lernen) PointWenn ich Ihnen nach dem obigen Beispiel diese fantastische Datenstruktur mit dem Namen zur Verfügung stelle Point3D, die das Gleiche für den dreidimensionalen Raum tun kann?)

Algorithmen ohne (reale) Datenstrukturen

"Real", weil offensichtlich jeder interessante Algorithmus primitive Datentypen wie Ganzzahlen oder Boolesche Werte benötigt und wir diese in diesem Zusammenhang nicht als Datenstrukturen betrachten möchten. Ähnlich wie oben sind diese Algorithmen typischerweise eher einfache. Insbesondere haben sie keinerlei komplizierten Zustand, da dieser normalerweise in eine Datenstruktur eingeht (siehe nächster Abschnitt).

Ein Beispiel für einen solchen Algorithmus wäre die Berechnung des größten gemeinsamen Teilers zweier Zahlen. Euklids Algorithmen für die GCD müssen eigentlich nur zwei ganze Zahlen enthalten und diese manipulieren.

Sobald die Dinge interessanter werden, betreten Sie jedoch sehr bald die Welt der abstrakten Datentypen. Beispielsweise basiert das Sieb von Eratosthenes auf einem Array. Wir könnten jetzt diskutieren, ob ein Array noch primitiv ist, oder ob eine Ganzzahl noch keine Datenstruktur ist. In jedem Fall sind Algorithmen, die vollständig ohne Datenstrukturen existieren, ziemlich langweilig, selbst wenn Sie ihre isolierte Existenz akzeptieren.

Algorithmen kombiniert mit Datenstrukturen, auch abstrakte Datentypen genannt

Dies sind die interessanten, aber aus zwei sehr unterschiedlichen Gründen. Normalerweise können Sie sich diesen aus zwei Richtungen nähern: Datenstruktur zuerst oder Algorithmus zuerst.

Während ein abstrakter Datentyp durch die Kombination von Datenstruktur + Algorithmen / Operationen definiert wird, betrachten wir sie häufig mit einem Fokus auf eine dieser beiden und betrachten die andere als Enabler.

Datenstruktur, dann Algorithmus

Sie werden auf abstrakte Datentypen stoßen, die recht einfach zu verwenden sind, jedoch mehr oder weniger komplizierte Algorithmen enthalten, damit sie intern funktionieren. Zum Beispiel ist a HashMaptrivial in der Verwendung, beinhaltet aber eine raffinierte Hash-Funktion und den Umgang mit den Hash-Kollisionen im Inneren. Aus Ihrer Sicht als Benutzer ist es Ihnen jedoch wichtig, dass Daten für Sie gespeichert werden, und nicht, dass etwas für Sie getan wird.

Im Gegensatz zur letzten Gruppe setzen diese Datenstrukturen ihre Benutzer diesen Algorithmen nicht aus. Sie müssen die HashMapinterne Hash-Funktion von a nicht kennen und sich auch nicht darum kümmern, um sie verwenden zu können. (Um es effektiv zu nutzen, möchten Sie vielleicht diese Dinge wissen;)

Algorithmus, dann Datenstruktur

Die andere Richtung bedeutet, dass Sie einen Algorithmus haben, den Sie einfach verwenden möchten, der jedoch intern Datenstrukturen benötigt, damit er wie beabsichtigt funktioniert. Ein Beispiel wäre ein BSP-Algorithmus (Binary Space Partitioning), den Sie einfach Pointaus einer großen Menge von Punkten, die einem bestimmten Abfragepunkt am nächsten liegen, zweidimensional abfragen können. Sie benötigen jedoch eine Baumstruktur (und sogar zusätzliche Algorithmen wie Entfernungsberechnungen) im Inneren, um den Algorithmus tatsächlich zu schreiben.

Im Allgemeinen kann man sagen, dass Algorithmen in dieser Gruppe involvierte Datenstrukturen für ihre interne Zustandsdarstellung verwenden. Ich würde argumentieren, dass diese Gruppe von Algorithmen am vielfältigsten ist und Sie viele, viele verschiedene finden, die zu diesem allgemeinen Schema passen. In Bezug auf die Sichtweise sehen wir diese als interessant an, da sie etwas (z. B. Sortieren) für uns tun und sich nicht so sehr um den Datenbestandsteil kümmern.

Eng verwandte Datenstrukturen und Algorithmen

Schließlich haben Sie Datenstrukturen, die sehr eng mit Algorithmen verwandt sind, die direkt mit ihnen korrespondieren. Ein typisches Beispiel ist ein binärer Baum, der, wenn Sie etwas Sinnvolles damit anfangen möchten, das Thema der Tree-Walking-Algorithmen auf sich zieht (Tiefe zuerst, Breite zuerst, was auch immer).

In diesen Fällen ändern wir den Fokus unserer Sicht auf die resultierenden abstrakten Datentypen von Zeit zu Zeit. Manchmal interessiert Sie die Struktur Ihres Baums, ein paar Minuten später möchten Sie eine Suchoperation ausführen, dann möchten Sie einen Knoten löschen und gleich wissen, wie die Struktur danach aussieht. Dies gilt zwar auch für die anderen obigen Abschnitte, ist jedoch nicht das Hauptaugenmerk, das Sie beim Speichern / Abrufen von Daten in / aus einer Mapoder beim Sortieren einer verknüpften Liste haben.

Datenstrukturen beeinflussen häufig die Details eines Algorithmus. Aus diesem Grund gehen die beiden oft Hand in Hand.

Betrachten Sie zum Beispiel einen Algorithmus zum Schneiden Ihres Rasens. Wie Sie Ihren Rasen schneiden, hängt wahrscheinlich von der tatsächlichen Struktur Ihres Rasens ab. Wenn Sie in einem kleinen Haus in einem dicht besiedelten Vorort wohnen und Ihr Rasen nur ein kleines Rechteck mit einer Fläche von wenigen Quadratmetern ist, ziehen Sie es wahrscheinlich vor, Ihren Rasen mit einem Schubmäher anstelle eines Traktors / Aufsitzmähers zu schneiden. Wenn Ihr Rasen viele Morgen flaches Wiesenland umfasst, bevorzugen Sie möglicherweise den Reitmäher im Gegensatz zum Schubmäher (obwohl jeder Mäher möglicherweise irgendwann seine Arbeit erledigt). Wenn Ihr Rasen mehrere Hektar Land mit großen flachen Flächen, aber ein paar kleinen Hügeln und einer Reihe von Bäumen umfasst, können Sie einen interessanteren Algorithmus zum Schneiden des Rasens entwickeln, bei dem sowohl ein Reitmäher als auch ein Schubmäher oder ein anderes Gras zum Einsatz kommen Schneidtechniken.

Letztendlich kann die Struktur Ihrer Daten jedoch einen erheblichen Einfluss auf Ihre Entscheidungen zur Entwicklung Ihres Algorithmus (oder der zu verwendenden Algorithmen) haben. Aus diesem Grund gehen die beiden Themen oft Hand in Hand.

Und umgekehrt: Manchmal beeinflusst der Algorithmus, den wir verwenden möchten (zumindest zu Beginn der Berechnung), die Datenstrukturen, die Sie zur Unterstützung des Algorithmus entwickeln. Gehen Sie beispielsweise von einer Array-Liste zur Idee einer verknüpften Liste und schließlich zu einer BST, um eine geordnete Liste zu speichern, die eine schnelle Suche ermöglicht.