WILEY END USER LICENSE AGREEMENT

Algorithmus

Beschreibung

A*-Suche

Der Algorithmus berechnet während der Untersuchung der Knoten fortlaufend die damit verbundenen Kosten. Dies geschieht anhand der Gleichung f(n) = g(n) + h(n), wobei:

n für den Knoten steht,

g(n) die entstandenen Kosten bis zum Erreichen des Knotens sind,

h(n) die geschätzten Kosten vom Knoten bis zum Ziel sind und

f(n) die geschätzten Kosten des Wegs von n bis zum Ziel sind.

Die Idee hierbei ist, zuerst die aussichtsreichsten Wege zu durchsuchen und kostenintensive Wege zu vermeiden.

Balancierter Baum

Eine besondere Art von Baum, der durch Umordnen eine balancierte Struktur bewahrt. Hierdurch lassen sich Aufrufzeiten reduzieren. Die Anzahl der Elemente auf der linken Seite unterscheidet sich von der Anzahl der Elemente auf der rechten Seite höchstens um 1.

Bidirektionale Suche

Bei dieser Technik wird gleichzeitig vom Wurzelknoten und vom Zielknoten aus gesucht, bis sich die Wege beider Suchen in der Mitte treffen. Ein Vorteil dieses Ansatzes ist, dass er nicht sehr zeitaufwändig ist, weil er die Lösung schneller als viele andere Brute-Force-Ansätze findet. Zudem ist er im Vergleich zu anderen Ansätzen sparsamer hinsichtlich des Speicherplatzverbrauchs und findet garantiert eine Lösung. Der größte Nachteil ist die Kom­­plexität der Implementierung.

Binärer Baum

Bei dieser Art von Baum ist ein Knoten jeweils mit keinen (im Fall eines Blattknotens), einem oder zwei (bei inneren Knoten) anderen Knoten verbunden. Durch jeden Knoten werden drei wichtige Aspekte definiert: Datenspeicher, linke und rechte Verbindung.

Breitensuche

Diese Technik setzt am Wurzelknoten an und untersucht zunächst jeden der Kinderknoten. Anschließend geht sie zur nächsten Ebene über. So durchläuft sie Ebene für Ebene, bis eine Lösung gefunden wurde. Der Nachteil dieses Algorithmus ist, dass jeder Knoten abgespeichert werden muss, was bei großen Knotenmengen entsprechend viel Speicherplatz beansprucht. Die Breitensuche kann doppelt vorkommende Knoten finden, was Zeit spart. Eine Lösung ist immer garantiert.

Brute-Force-Methode

Bei diesem Ansatz wird jede mögliche Lösung ausprobiert, um darunter die beste Lösung zu finden. Brute-Force-Techniken finden immer die beste Lösung, sind jedoch dermaßen zeitaufwändig in der Implementierung, dass sie meistens nicht verwendet werden.

Dijkstra

Dieser Algorithmus findet den kürzesten Weg in einem gerichteten, positiv gewichteten Graphen.

Gierige Bestensuche

Dieser Algorithmus wählt stets diejenige Strecke aus, die sich am nächsten zum Zielpunkt befindet. Dies geschieht anhand der Gleichung f(n) = h(n). Der Algorithmus findet in der Regel sehr schnell eine Lösung, kann jedoch auch in Schleifen hängen bleiben. Aus diesem Grund stellt er oftmals keinen optimalen Lösungsansatz dar.

Gieriger Algorithmus

Bei dieser Technik wird für die Gesamtlösung das beste Ergebnis aus jedem einzelnen Schritt des Lösungsprozesses genommen. Gierige Algorithmen gehen von zwei Annahmen aus:

Es ist möglich, in jedem Schritt die eine optimale Wahl zu treffen.

Trifft man in jedem Schritt die optimale Wahl, lässt sich hierdurch eine optimale Lösung des Gesamtproblems finden.

Graph

Ein Graph ist eine Art Erweiterung eines Baums. Wie auch bei Bäumen können zwischen den Knoten eines Graphen Verbindungen bestehen. Anders als bei binären Bäumen können bei Graphen jedoch mehr als eine oder zwei Verbindungen von einem Knoten ausgehen. Graphknoten haben oftmals sogar sehr viele Verbindungen. Sie werden beispielsweise in GPS-Karten und in vielen anderen Anwendungen eingesetzt, wo der Top-Down-Ansatz für Bäume nicht funktioniert.

Hashing

Bei dieser Methode wird vorhergesagt, wo sich ein bestimmtes Datenobjekt in einer beliebigen Datenstruktur befindet, bevor man mit der eigentlichen Suche beginnt. Hierzu werden Schlüssel eingesetzt, die in einem Index abgelegt sind: Der Schlüssel wird zunächst durch eine Hashfunktion in einen numerischen Wert umgewandelt, den der Algorithmus in einer Hashtabelle ablegt. Anhand der Hashtabelle lässt sich ein Index erstellen, der auf die Elemente in der Datenstruktur verweist, sodass der Algorithmus die Position der Daten leicht vorhersagen kann.

Heap

Hierbei handelt es sich um eine raffinierte Baumstruktur, in die sich Daten einfügen lassen. Durch dieses Einfügen lässt sich der Sortiervorgang beschleunigen. Die Bäume können weiter in sogenannte Max-Heaps und Min-Heaps unterteilt werden, je nachdem, ob der Heap sofort den maximalen oder den minimalen Wert im Baum ausgibt.

Heuristik

Diese Problemlösetechnik beruht auf Erfahrungen und gibt Ergebnisse aus, die zwar nicht optimal, jedoch gut genug sind, sodass eine bessere Lösung nicht mehr nötig ist. Hierbei lässt man sich durch den Algorithmus potentiell nützliche Lösungswege aufzeigen. Anschließend ist man jedoch trotzdem auf menschliche Intuition und Vernunft angewiesen, um zu wissen, ob es sich bei dem Ergebnis tatsächlich um die richtige Lösung handelt.

MapReduce

Mithilfe dieser Grundstruktur können Algorithmen auf mehreren vernetzten Computern parallele Berechnungen ausführen, wodurch Ergebnisse schneller erzielt werden.

Mergesort

Mergesort ist eine universelle, vergleichsbasierte Methode des Datensortierens. Zur Ausführung macht man von einem Teile-und-herrsche-Ansatz Gebrauch.

Nash-Gleich­gewicht

Dies ist ein Begriff aus der Spieltheorie. Er beschreibt eine Situation, in der jedem Spieler die Strategie der anderen Spieler bekannt ist, sodass kein Spieler durch die Änderung seiner Strategie einen Vorteil hat. Diese Theorie wird auf Konfliktsituationen angewandt, bei denen ein Spieler die Entscheidungen aller beteiligten Spieler berücksichtigen muss, wenn er das Spiel gewinnen will.

PageRank

Der PageRank-Algorithmus misst die Wichtigkeit eines Knotens in einem Graphen. Dieser Algorithmus bildet die wesentliche Grundlage für die Kernalgorithmen von Google, die die relevantesten Ergebnisse einer Suchanfrage ausgeben.

Quicksort

Dies ist ein allgemeines Sortierverfahren, bei dem ein Datenarray durch einen Teile-und-herrsche-Ansatz in kleinere Datenarrays zerlegt wird.

Rein heuristische Suche

Dieser Algorithmus durchläuft die Knoten in der Reihenfolge ihrer Kosten und legt dabei zwei Listen an. Eine geschlossene Liste enthält bereits besuchte Knoten, während eine offene Liste diejenigen Knoten enthält, die noch besucht werden müssen. Bei jeder Iteration wählt der Algorithmus den Knoten mit den niedrigsten Kosten aus. Alle Kinderknoten dieses Knotens werden in der geschlossenen Liste abgelegt und die jeweiligen Kosten berechnet. Der Algorithmus legt sodann alle Kinderknoten mit niedrigen Kosten wieder in der offenen Liste ab und löscht die Kinderknoten mit hohen Kosten. So führt er eine intelligente, kostenbasierte Suche nach der Lösung aus.

Teile und herrsche

Bei diesem Lösungsansatz wird die Aufgabe in kleinstmögliche Teile zerlegt und mithilfe des einfachsten Ansatzes gelöst. Dies spart im Vergleich zu anderen Ansätzen wie etwa dem Brute-Force-Ansatz viel Zeit und Ressourcen. Jedoch ist eine optimale Lösung nicht immer garantiert.

Tiefensuche

Diese Technik setzt am Wurzelknoten an und untersucht dann eine Menge von verbundenen Kinderknoten, bis sie einen Blattknoten erreicht. Sie durchläuft Zweig um Zweig, bis sie eine Lösung findet. Der Nachteil dieses Algorithmus ist, dass er nicht nach doppelt vorkommenden Knoten suchen kann; das bedeutet, dass er die gleichen Knotenwege mehr als einmal durchlaufen könnte. Es kann sogar sein, dass dieser Algorithmus gar keine Lösung findet, sodass Sie eine obere Grenze definieren müssen, damit der Algorithmus nicht ewig weitersucht. Ein Vorteil dieses Ansatzes ist, dass er speicherplatzfreundlich ist.

Unbalancierter Baum

Bei diesem Baum werden je nach Bedarf neue Datenelemente eingefügt, ohne dass dabei die Balance des Baums berücksichtigt wird. Durch diese Methode des Hinzufügens wird der Baum schneller aufgebaut, bei Such- oder Sortiervorgängen jedoch langsamer abrufbar.

Begriff

Beschreibung

Gleichung

Eine Gleichung enthält stets ein Gleichheitszeichen. Dieses bedeutet, dass die Zahlen und Symbole auf beiden Seiten den gleichen Wert ergeben. 5 + 2 = 7 ist eine sehr einfache Form einer Gleichung. 7 = 3 + 4 wäre auch eine Gleichung. In der Regel aber enthalten Gleichungen Variablen, die mit Symbolen dargestellt sind! Ob die Gleichung wahr oder falsch ist, hängt dann von den Werten der Variablen ab. Werte, die die Gleichung erfüllen, heißen Lösungen der Gleichung. Wenn a + 2 = 7, ist a = 5 eine Lösung der Gleichung.

Formel

Formeln sind eine Kombination aus Zahlen und Symbolen und definieren normalerweise ein mathematisches oder logisches Konzept wie zum Beispiel der berühmte Satz des Pythagoras über die Seitenlängen in einem rechtwinkligen Dreieck: a² + b² = c². Allgemein zeigen Formeln eine Beziehung zwischen zwei oder mehreren Variablen auf. Für die meisten Menschen ist eine Formel eine besondere Sorte von Gleichung.

Algorithmus

Eine Abfolge von Schritten zur Lösung eines Problems. Algorithmen sind nicht immer mathematischer oder logischer Natur, obgleich die Beispiele in diesem Buch oftmals in diese Kategorie fallen, weil Algorithmen in der Regel auf diese Weise verwendet werden. Bei einigen Spezialformeln handelt es sich auch um Algorithmen, wie etwa bei der Mitternachtsformel zur Lösung quadratischer Gleichungen. Um als Algorithmus gelten zu können, muss ein Verfahren die folgenden Eigenschaften erfüllen:

Endlichkeit: Früher oder später muss der Algorithmus die Aufgabe lösen können.

Wohldefiniertheit: Die Abfolge der Schritte muss klar und verständlich sein. Insbesondere müssen die Schritte für Computer nachvollziehbar sein, damit der Algorithmus mithilfe einer Programmiersprache implementiert werden kann.

Effektivität: Ein Algorithmus muss für jeden Fall, den die Aufgabenstellung vorsieht, Ergebnisse berechnen können. Er sollte stets die Aufgabe lösen, für die er entwickelt wurde. Obwohl dabei Fehler auftreten können, sind diese eher eine Seltenheit und tauchen nur in Situationen auf, die im Rahmen des beabsichtigten Einsatzes akzeptabel sind.

Aufgabe

Besonderheit

Ablaufplanung

Die gerechte Verteilung von Ressourcen unter mehreren beteiligten Parteien stellt ein großes Anwendungsgebiet für Algorithmen dar. Moderne Ampelschaltungen berücksichtigen beispielsweise unter anderem die Tageszeit, die Wetterbedingungen und den Verkehrsfluss. Denken Sie auch an Ihren Computer, der mehrere Aufgaben gleichzeitig ausführen kann. Ohne einen Algorithmus zur Ablaufplanung würde das Betriebssystem alle verfügbaren Ressourcen in Anspruch nehmen und andere Anwendungen von der Arbeit abhalten.

Analyse von Graphen

In vielen unterschiedlichen Bereichen benötigt man die kürzeste Strecke zwischen zwei Punkten. Beispielsweise würde Ihr GPS ohne diesen besonderen Algorithmus nicht funktionieren, da es in einer Stadt niemals des kürzesten Weg zwischen Punkt A und B finden würde.

Erzeugung pseudozufälliger Zahlen

Stellen Sie sich ein Spiel vor, das immer gleich ist: Sie würden jedes Mal am gleichen Anfangspunkt beginnen und immer nach dem gleichen Schema die gleichen Schritte ausführen. Das wäre doch langweilig! Ohne die Möglichkeit, scheinbar zufällige Zahlen zu erzeugen, wären viele Computeraufgaben sinnlos oder schier unmöglich.

Kryptographie

Angesichts von Hackerangriffen ist die Sicherung von Daten heutzutage ein wichtiges Thema. Mit Algorithmen lassen sich Daten analysieren, in eine andere Form umwandeln (verschlüsseln) und am Ende wieder in ihre ursprüngliche Form bringen.

Sortieren

Angesichts der heutigen Datenmengen ist es wichtig, Informationen in einer bestimmten Reihenfolge anordnen zu können. Nur so lassen sich die Informationsfluten in eine reduzierte, übersichtlichere Form bringen. Stellen Sie sich vor, Sie suchen bei Amazon nach Kaffeetassen und finden dort Tausende Tassen im Angebot, die Sie jedoch nicht nach dem Preis oder nach positiven Bewertungen sortieren können. Viele komplexe Algorithmen benötigen Daten in einer bestimmten Reihenfolge, um überhaupt zuverlässig funktionieren zu können, sodass das Sortieren eine wichtige Voraussetzung für das Lösen von immer mehr Problemen darstellt.

Suchen

Die Suche nach Informationen und die Überprüfung, dass es sich bei den angezeigten Informationen tatsächlich um die gewünschten Informationen handelt, sind wesentliche Aufgaben in verschiedenen Bereichen. Ohne diese Algorithmen wäre eine Internetsuche nicht durchführbar.

Umformungen

Für den sinnvollen Gebrauch von Daten ist es mitunter unabdingbar, dass man Daten einer bestimmten Form in eine andere Form umwandeln kann. So könnte es etwa sein, dass Sie an das metrische Maßsystem gewöhnt sind, Ihre Daten jedoch im angloamerikanischen Maßsystem vorliegen. Durch eine Umrechnung der Daten werden die Daten verständlicher. Genauso lassen sich mithilfe der schnellen Fourier-Transformation Zeitsignale in Frequenzsignale umwandeln, was sich Ihr WLAN-Router zunutze macht.

Komplexitätsklasse

Beschreibung

Konstante Komplexität O(1)

Hier ist die Laufzeit immer gleich und hängt nicht von der Menge des Inputs ab. Jeder einzelne Input besitzt eine festgelegte Ausführzeit.

Logarithmische ­Komplexität O(log n)

Die Anzahl der Operationen wächst langsamer an als der Input, wodurch der Algorithmus bei kleineren Inputs nicht so effizient, bei größeren Inputs jedoch umso effizienter ist. Ein Beispiel ist die binäre Suche.

Lineare Komplexität O(n)

Die Menge der benötigten Operationen wächst im Verhältnis 1:1 mit der Inputmenge. Ein typisches Beispiel ist die Iteration, bei der der Input einmal überprüft und auf jedem seiner Elemente eine Operation ausgeübt wird.

Super-lineare Komplexität O(n·log n)

Diese Komplexität ist eine Mischung aus logarithmischer und linearer Komplexität. Sie findet sich typischerweise bei Sortierverfahren wie Mergesort, Heapsort und Quicksort.

Quadratische Komplexität O(n²)

Die Anzahl der Operationen nimmt mit dem Quadrat der Inputmenge zu. Wenn es eine Iteration innerhalb einer anderen gibt, so liegt quadratische Komplexität vor. Einige der weniger effizienten Sortieralgorithmen wie Bubblesort, Selectionsort und Insertionsort gehören zu dieser Komplexitätsklasse. Es könnte sein, dass ihr Algorithmus stunden- oder tagelang rechnen muss, bis er eine Lösung findet.

Kubische Komplexität O(n³)

Hier nehmen die Operationen noch stärker zu als bei quadratischer Komplexität, weil es mehrfach verschachtelte Iterationen gibt. Algorithmen von dieser Komplexität können für die Verarbeitung einer recht kleinen Datenmenge von 100.000 Elementen Jahre brauchen. Ist die Anzahl der nötigen Operationen eine Potenz des Inputs, spricht man von einer polynomiellen Laufzeit.

Exponentielle Komplexität O(2ⁿ)

Dieser Algorithmus benötigt für jedes neue Element die doppelte Anzahl der vorigen Operationen. Bei Algorithmen dieser Komplexität können sogar kleine Aufgaben unendlich lange Laufzeiten haben. Viele Algorithmen, die umfangreiche Suchen ausführen, sind von exponentieller Laufzeit. Ein klassisches Beispiel für dieses Komplexitätsniveau ist die Berechnung der Fibonacci-Zahlen.

Faktorielle Komplexität O(n!)

Algorithmen von dieser Komplexität sind aufgrund der vielen möglichen Kombinationen der Elemente untereinander ein wahres Grauen. Angenommen, Ihr Input besteht aus 100 Objekten und eine Operation auf Ihrem Computer dauert 10^-6 Sekunden, was eine normale Geschwindigkeit für heutige Computer ist. Dann dauert die Ausführung der Aufgabe etwa 10¹⁴⁰ Jahre – ein Ding der Unmöglichkeit: Das Alter unseres Universums wird gerade mal auf 10¹⁴ Jahre geschätzt. Ein berühmtes Problem mit faktorieller Komplexität ist das Problem des Handlungsreisenden, bei dem ein Handlungsreisender die kürzeste Verbindungsstrecke zwischen mehreren Städten finden muss.