23,99 €
Mehr erfahren.
- Herausgeber: Wiley-VCH Verlag GmbH & Co. KGaA
- Kategorie: Wissenschaft und neue Technologien
- Serie: ...für Dummies
- Sprache: Deutsch
Wir leben in einer algorithmenbestimmten Welt. Deshalb lohnt es sich zu verstehen, wie Algorithmen arbeiten. Das Buch präsentiert die wichtigsten Anwendungsgebiete für Algorithmen: Optimierung, Sortiervorgänge, Graphentheorie, Textanalyse, Hashfunktionen. Zu jedem Algorithmus werden jeweils Hintergrundwissen und praktische Grundlagen vermittelt sowie Beispiele für aktuelle Anwendungen gegeben. Für interessierte Leser gibt es Umsetzungen in Python, sodass die Algorithmen auch verändert und die Auswirkungen der Veränderungen beobachtet werden können. Dieses Buch richtet sich an Menschen, die an Algorithmen interessiert sind, ohne eine Doktorarbeit zu dem Thema schreiben zu wollen. Wer es gelesen hat, versteht, wie wichtige Algorithmen arbeiten und wie man von dieser Arbeit beispielsweise bei der Entwicklung von Unternehmensstrategien profitieren kann.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 605
Veröffentlichungsjahr: 2017
Ähnliche
WILEY-VCH Verlag GmbH & Co. KGaA
Algorithmen für Dummies
John Paul Mueller/Luca Massaron
Übersetzung aus dem Amerikanischen von Sarah Schmitt
Bibliografische Information der Deutschen Nationalbibliothek
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.
© 2017 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
Original English language edition Algorithms For Dummies © 2017 by Wiley Publishing, Inc. All rights reserved including the right of reproduction in whole or in part in any form. This translation published by arrangement with John Wiley and Sons, Inc.
Copyright der englischsprachigen Originalausgabe Algorithms For Dummies © 2017 by Wiley Publishing, Inc. Alle Rechte vorbehalten inklusive des Rechtes auf Reproduktion im Ganzen oder in Teilen und in jeglicher Form. Diese Übersetzung wird mit Genehmigung von John Wiley and Sons, Inc. publiziert.
Wiley, the Wiley logo, Für Dummies, the Dummies Man logo, and related trademarks and trade dress are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates, in the United States and other countries. Used by permission.
Wiley, die Bezeichnung »Für Dummies«, das Dummies-Mann-Logo und darauf bezogene Gestaltungen sind Marken oder eingetragene Marken von John Wiley & Sons, Inc., USA, Deutschland und in anderen Ländern.
Das vorliegende Werk wurde sorgfältig erarbeitet. Dennoch übernehmen Autoren und Verlag für die Richtigkeit von Angaben, Hinweisen und Ratschlägen sowie eventuelle Druckfehler keine Haftung.
Coverfoto © Olaf Schulz – Fotolia.com
Korrektur Petra Heubach-Erdmann, Düsseldorf
Satz/ePub Reemers Publishing Services GmbH, Krefeld
Print ISBN: 978-3-527-71381-3
ePub ISBN: 978-3-527-80977-6
mobi ISBN: 978-3-527-80976-9
Inhaltsverzeichnis
Cover
Über die Autoren
John Muellers Widmung
Luca Massarons Widmung
John Muellers Danksagung
Luca Massarons Danksagung
Einführung
Über dieses Buch
Konventionen in diesem Buch
Törichte Annahmen über den Leser
Symbole, die in diesem Buch verwendet werden
Wie es weitergeht
Teil I: Erste Schritte
Kapitel 1: Grundlegendes über Algorithmen
Algorithmen beschreiben
Definitionen zur Anwendung von Algorithmen
Algorithmen sind überall
Mit Computern Aufgaben lösen
Moderne CPUs und GPUs wirksam einsetzen
Arbeiten mit Spezialchips
Netzwerke wirksam einsetzen
Daten effektiv nutzen
Zwischen Aufgaben und Lösungen unterscheiden
Richtigkeit und Effizienz
Die Erkenntnis, dass nichts umsonst ist
Die Strategie an die Aufgabe anpassen
Algorithmen in einer Lingua franca beschreiben
Schwierige Aufgaben angehen
Daten für Lösungen strukturieren
Die Sichtweise eines Computers
Datenordnung muss sein
Kapitel 2: Algorithmendesign
Der Anfang der Problemlösung
Praxisaufgaben modellieren
Lösungen und Gegenbeispiele finden
Auf den Schultern von Riesen stehen
Teile und herrsche
Brute-Force-Lösungen vermeiden
Erster Schritt: Vereinfachen
Reduktion ist meist vorteilhaft
Erkennen, dass Gier gut sein kann
Gierig denken
Eine gute Lösung
Kostenberechnungen und Heuristiken
Das Problem in einem Raum darstellen
Zufällig und von Glück gesegnet
Heuristiken und Kostenfunktionen verwenden
Algorithmen auswerten
Simulationen mittels abstrakter Maschinen
Weitere Abstrahierungen
Mit Funktionen arbeiten
Kapitel 3: Mit Python Algorithmen verwenden
Die Vorteile von Python
Wie Python in diesem Buch verwendet wird
Mit MATLAB arbeiten
Andere Testumgebungen für Algorithmen
Python-Distributionen
Analytics Anaconda installieren
Enthought Canopy Express
Python(x,y)
WinPython
Python auf Linux installieren
Python auf MacOS installieren
Python auf Windows installieren
Datensätze und Beispielcode herunterladen
Jupyter Notebook benutzen
Das Coderepository definieren
Ein neues Notebook erstellen
Ein Notebook exportieren
Ein Notebook entfernen
Ein Notebook importieren
Die Datensätze in diesem Buch verstehen
Kapitel 4: Algorithmen mit Python programmieren: Grundlagen
Mit Zahlen und Logik arbeiten
Variablenzuordnungen vornehmen
Berechnungen durchführen
Datenvergleich durch boolesche Ausdrücke
Strings erstellen und verwenden
Mit Datumsangaben arbeiten
Funktionen erstellen und verwenden
Mehrfach aufrufbare Funktionen erstellen
Funktionen aufrufen
Bedingte Anweisungen und Schleifen verwenden
Entscheidungen mittels if-Befehl treffen
Mittels verschachtelter Entscheidungen zwischen mehreren Möglichkeiten auswählen
Iterative Aufgaben mittels for-Schleife ausführen
Der while-Befehl
Daten in Mengen, Katalogen und Tupeln speichern
Datasets erstellen
Listen erstellen
Tupel erstellen und verwenden
Nützliche Iteratoren definieren
Daten mittels Dictionaries indizieren
Kapitel 5: Grundlagen der Datenbearbeitung mit Python
Berechnungen mit Vektoren und Matrizen
Variablen- und Vektoroperationen verstehen
Vektoren multiplizieren
Der erste Schritt: Matrizen erstellen
Matrizen multiplizieren
Erweiterte Matrizenoperationen definieren
Der richtige Weg: Kombinationen erzeugen
Permutationen unterscheiden
Kombinationen erzeugen
Wiederholungen behandeln
Ergebnisse mit Rekursion erzielen
Die Funktionsweise der Rekursion
Endrekursionen entfernen
Prozesse schneller ausführen
Der »teile und herrsche«-Ansatz
Zwischen möglichen Lösungen unterscheiden
Teil II: Die Notwendigkeit des Suchens und Sortierens
Kapitel 6: Daten strukturieren
Die Notwendigkeit einer Struktur
Inhalt vereinfacht darstellen
Daten aus verschiedenen Quellen anpassen
Die Wichtigkeit der Datenbereinigung
Daten gestapelt und kumuliert anordnen
Stapelweise Anordnungen
Warteschlangen verwenden
Daten mittels assoziativen Datenfeldern finden
Mit Bäumen arbeiten
Grundlegendes über Bäume
Bäume erstellen
Relationen in Graphen darstellen
Über Bäume hinauswachsen
Graphen erstellen
Kapitel 7: Daten ordnen und durchsuchen
Daten mit Mergesort und Quicksort sortieren
Die Notwendigkeit des Sortierens
Daten naiv anordnen
Bessere Sortiertechniken einsetzen
Suchbäume und Heaps verwenden
Die Notwendigkeit einer effizienten Suche
Binäre Suchbäume erstellen
Spezialisierte Suchen mit einem binären Heap
Hashing verwenden
Alles in Buckets füllen
Kollisionen vermeiden
Hashfunktionen selbst erstellen
Teil III: Die Welt der Graphen
Kapitel 8: Die Grundlagen von Graphen
Die Wichtigkeit von Netzwerken
Grundlegendes über Graphen
Graphen sind überall
Die soziale Seite eines Graphen
Teilgraphen verstehen
Definitionen für das Zeichnen von Graphen
Die wichtigsten Eigenschaften von Graphen
Graphen zeichnen
Die Funktionalität eines Graphen
Kanten und Knoten zählen
Zentralität berechnen
Graphen in ein numerisches Format bringen
Graphen zu einer Matrix hinzufügen
Dünn besetzte Matrizen verwenden
Graphen durch Listen ausdrücken
Kapitel 9: Punkte verbinden
Graphen effizient durchsuchen
Einen Graphen erstellen
Breitensuche anwenden
Tiefensuche anwenden
Die Entscheidung für eine Methode
Die Elemente eines Graphen sortieren
Mit gerichteten azyklischen Graphen arbeiten
Topologische Sortierungen verwenden
Die Reduktion auf einen minimalen Spannbaum
Geeignete Algorithmen verwenden
Vorrangwarteschlangen kennenlernen
Den Algorithmus von Prim einsetzen
Den Algorithmus von Kruskal testen
Entscheiden, welcher Algorithmus am besten passt
Den kürzesten Weg finden
Definieren, was der kürzeste Weg ist
Der Dijkstra-Algorithmus: eine Erklärung
Kapitel 10: Die Geheimnisse der Graphen
Soziale Netzwerke als Graphen betrachten
Netzwerke in Gruppen clustern
Communitys entdecken
Einen Graphen durchlaufen
Grade der Trennung abzählen
Graphen zufällig durchlaufen
Kapitel 11: Die richtige Webseite finden
Die Welt in einer Suchmaschine
Datensuche im Internet
Die richtigen Daten finden
Die Funktionsweise des PageRank-Algorithmus
Die Logik hinter dem PageRank-Algorithmus
Das A und O von PageRank
PageRank implementieren
Pythonskripte implementieren
Der Kampf mit naiven Implementierungen
Langeweile und Teleportation
Das Leben einer Suchmaschine
Andere Verwendungsmöglichkeiten von PageRank
Über das PageRank-Paradigma hinaus
Semantisches Suchen
Ranking von Suchergebnissen mit künstlicher Intelligenz
Teil IV: Der Kampf mit Big Data
Kapitel 12: Big Data verwalten
Die Umwandlung von Strom in Daten
Die Auswirkungen von Moore
Daten sind überall
Algorithmen ins Geschäft bringen
Datenflüsse streamen
Streams korrekt analysieren
Die richtigen Daten auswählen
Lösungen aus Stream-Daten skizzieren
Datenstromelemente filtern
Bloomfilter darstellen
Die Anzahl der Elemente bestimmen
Elemente eines Streams abzählen
Kapitel 13: Abläufe parallelisieren
Die Handhabung großer Datenmengen
Die parallele Methode
Dateien und Vorgänge verteilen
Lösungen mit MapReduce
Operationen verteilen
Algorithmen für MapReduce erstellen
MapReduce-Simulationen erstellen
Anfragen durch Mapping
Kapitel 14: Daten komprimieren
Daten reduzieren
Codierungen verstehen
Die Folgen der Kompression
Die Entscheidung für eine Kompressionsart
Die Wahl einer vernünftigen Codierung
Codieren mit der Huffman-Kompression
Folgen merken mit dem LZW-Algorithmus
Teil V: Komplexe Aufgaben angehen
Kapitel 15: Mit gierigen Algorithmen arbeiten
Die Entscheidung, wann Gier Sinn macht
Die Vorteile der Gier
Gierige Algorithmen im Zaum halten
NP-vollständige Probleme
Herausfinden, wieso Gier nützlich ist
Daten im Cache anordnen
Der Kampf um Ressourcen
Noch mal zu Huffman-Codierungen
Kapitel 16: Dynamische Programmierung
Dynamische Programmierung – was ist das?
Die historische Grundlage
Probleme dynamisieren
Rekursion dynamisch auslegen
Memoisation verwenden
Die besten dynamischen Techniken
Den Rucksack packen
Städte bereisen
Näherungsweise nach Strings suchen
Kapitel 17: Randomisierte Algorithmen
Die Funktionsweise der Randomisierung
Die Notwendigkeit der Randomisierung
Das Wahrscheinlichkeitsprinzip verstehen
Verteilungen verstehen
Die Monte-Carlo-Simulation
Den Zufall in die Logik einbauen
Den Median durch Quickselect bestimmen
Monte-Carlo-Simulationen ausführen
Schneller sortieren mit Quicksort
Kapitel 18: Lokale Suchen durchführen
Lokale Suchen verstehen
Die Nachbarschaft kennen
Tricks bei der lokalen Suche
Bergsteigen und das Damenproblem
Die Funktionsweise des Simulated Annealing
Wiederholungen durch die Tabu-Suche vermeiden
Die Erfüllbarkeit boolescher Schaltkreise
2-SAT mittels Randomisierungen lösen
Die Code-Implementierung in Python
Die Wichtigkeit des Anfangspunkts
Kapitel 19: Lineare Optimierung
Lineare Funktionen – ein Werkzeug
Die mathematischen Grundlagen
Während des Planens vereinfachen
Das Simplex-Verfahren geometrisch bearbeiten
Die Grenzen der linearen Optimierung
Lineare Optimierung in der Praxis
PuLP auf dem eigenen Computer installieren
Produktionsvorgänge und Einnahmen optimieren
Kapitel 20: Heuristiken untersuchen
Unterschiedliche Heuristiken kennenlernen
Die Ziele heuristischer Verfahren
Von genetisch zu künstlich
Heuristische Routensuche bei Robotern
Unbekannte Gebiete erkunden
Entfernungsmessungen als Heuristiken verwenden
Pathfinding-Algorithmen verstehen
Einen Irrgarten erstellen
Die Suche nach dem besten Weg
Heuristische Bewegungen mit A*
Teil VI: Der Top-Ten-Teil
Kapitel 21: Zehn algorithmische Verfahren, die die Welt verändern
Sortierverfahren einsetzen
Suchen durchführen
Mit Zufallszahlen eine neue Ordnung herstellen
Datenkompressionen vornehmen
Die Geheimhaltung von Daten
Datenbereiche ändern
Zusammenhänge erkennen
Muster in Daten erkennen
Mit Automatisierung und automatischen Antworten arbeiten
Eindeutige Identifizierungen erstellen
Kapitel 22: Zehn bislang ungelöste Probleme
Textsuchen bearbeiten
Wörter unterscheiden
Herausfinden, wann eine Anwendung anhält
Einwegfunktionen erstellen und verwenden
Die Multiplikation großer Zahlen
Die Gleichverteilung von Ressourcen
Die Berechnungszeit der Editierdistanz reduzieren
Aufgaben schnell lösen
Das Paritätsspiel spielen
Räumliche Aufgabenstellungen verstehen
Stichwortverzeichnis
Wiley End User License Agreement
Abbildungsverzeichnis
Kapitel 2
Abbildung 2.1: Komplexität eines Algorithmus im Falle von bestem, durchschnittlichem und ungünstigstem Input
Kapitel 3
Abbildung 3.2: Geben Sie im Installationsassistenten an, wie Anaconda auf Ihrem System installiert werden soll.
Abbildung 3.1: Der Installationsprozess (auf Englisch) informiert Sie zu Anfang darüber, ob Sie die 64-Bit-Version haben.
Abbildung 3.4: Konfiguration der erweiterten Installationsoptionen
Abbildung 3.3: Wählen Sie einen Installationsort.
Abbildung 3.5: Mit Jupyter Notebook lassen sich Beispiele zum maschinellen Lernen sehr einfach erstellen.
Abbildung 3.6: Neue Ordner tragen die Bezeichnung .
Abbildung 3.7: Benennen Sie den Ordner um, damit Sie sich dessen Inhalt leichter merken können.
Abbildung 3.8: Ein Notebook besteht aus Zellen, die Code enthalten können.
Abbildung 3.9: Wählen Sie einen neuen Namen für Ihr Notebook.
Abbildung 3.10: Notebook speichert Ihren Code in Zellen ab.
Abbildung 3.11: Alle von Ihnen erstellten Notebooks erscheinen in der Repository-Liste.
Abbildung 3.12: Notebook warnt Sie, ehe es Dateien aus dem Repository löscht.
Abbildung 3.13: Die Dateien, die Sie zum Repository hinzufügen wollen, werden in einer Uploadliste angezeigt, die eine oder mehrere Dateien enthält.
Abbildung 3.14: Das Boston-Objekt enthält den importierten Datensatz.
Kapitel 5
Abbildung 5.1: Beim rekursiven Prozess ruft eine Funktion sich selbst so lange wiederholt auf, bis eine bestimmte Bedingung erfüllt ist.
Kapitel 6
Abbildung 6.1: Bäume in Python ähneln Bäumen in der Natur.
Abbildung 6.2: Knoten in Graphen können ganz unterschiedlich miteinander verbunden werden.
Kapitel 7
Abbildung 7.1: Die Anordnung der Schlüssel in einem BST
Abbildung 7.2: Die Anordnung der Schlüssel in einem binären Heap
Kapitel 8
Abbildung 8.1: Beispiel eines einfachen, ungerichteten Graphen
Abbildung 8.2: Die gerichtete Version des ersten Graphen
Abbildung 8.3: Gewichtete Graphen sind realistischer.
Abbildung 8.4: Durch die bildliche Darstellung wird der Inhalt des Graphen deutlich.
Abbildung 8.5: Durch das Plotten des Graphen wird die Gradzentralität deutlich.
Kapitel 9
Abbildung 9.1: Eine Darstellung des Beispielgraphen durch NetworkX
Abbildung 9.2: Der Beispielgraph ist nun gewichtet.
Abbildung 9.3: Der Beispielgraph ist gewichtet und gerichtet.
Kapitel 10
Abbildung 1.1: Netzwerkcluster der Beziehungen unter Freunden
Abbildung 1.2: Communitys enthalten häufig Cliquen, die sehr nützlich für die soziale Netzwerkanalyse sind.
Abbildung 1.3: Ein Beispielgraph für Suchzwecke
Kapitel 11
Abbildung 11.1: Ein stark zusammenhängendes Netz
Abbildung 11.2: Eine Sackgasse
Abbildung 11.3: Eine Spider Trap
Kapitel 12
Abbildung 12.1: Immer mehr Transistoren finden Platz in einem Prozessor.
Abbildung 12.2: Stichproben aus einer Urne
Abbildung 12.3: Windowing eines DNA-Datenstroms
Abbildung 12.4: Ein einzelnes Element wird zu einem Bit-Array hinzugefügt.
Abbildung 12.5: Durch Hinzufügen eines zweiten Elements entsteht eine Kollision.
Abbildung 12.6: Um herauszufinden, ob ein Element existiert, wird das Bit-Array nach 0-Einträgen durchsucht.
Abbildung 12.7: Mit einem Bloomfilter überprüfen, ob eine Webseite bereits besucht wurde
Abbildung 12.8: Anfangs-Nullen abzählen
Abbildung 12.9: So werden Werte in einem Count-Min-Sketch aktualisiert.
Kapitel 13
Abbildung 13.1: Durch assoziative und kommutative Eigenschaften parallel rechnen
Abbildung 13.2: Ein Schema, das einen Computercluster darstellt
Abbildung 13.3: Eine Liste von Zahlen quadrieren
Abbildung 13.4: Eine Zahlenliste auf ihre Summe reduzieren
Abbildung 13.5: Ein Überblick über den gesamten MapReduce-Vorgang
Kapitel 14
Abbildung 14.1: Ein Huffman-Baum und die entsprechende Zeichensatztabelle zur Umwandlung
Kapitel 15
Abbildung 15.1: Von einem balancierten (links) zu einem unbalancierten (rechts) Baum
Kapitel 16
Abbildung 16.1: Die Knoten des gewichteten Graphen stehen für Städte.
Abbildung 16.2: »Sunday« in »Saturday« umformen
Abbildung 16.3: Die ausgeführten Transformationen
Kapitel 17
Abbildung 17.1: Ein Histogramm einer Normalverteilung
Abbildung 17.2: Ein Histogramm einer Gleichverteilung
Abbildung 17.3: Die Ergebnisse einer Monte-Carlo-Simulation
Abbildung 17.4: Das Ergebnis einer Monte-Carlo-Simulation von Quickselect
Abbildung 17.5: Monte-Carlo-Simulationen bei zunehmender Inputgröße
Kapitel 18
Abbildung 18.1: Durch Änderungen der Endstrecken lassen sich in einem TSP-Problem bessere Ergebnisse erzielen.
Abbildung 18.2: Eine lokale Suche untersucht die Landschaft durch Bergsteigen.
Abbildung 18.3: Eine Lösung des Damenproblems
Abbildung 18.4: Symbole und Wahrheitstabellen der logischen Operatoren , und
Abbildung 18.5: Die Anzahl der unerfüllbaren Klauseln nimmt nach zufälligen Änderungen ab.
Abbildung 18.6: Die Laufzeit ist bei einem besseren Anfangspunkt kürzer.
Kapitel 19
Abbildung 19.1: Überprüfen, wo die Zielfunktion die zulässige Region berührt
Abbildung 19.2: Herausfinden, welche Ecke die richtige ist
Kapitel 20
Abbildung 2.1: A und B sind Koordinaten auf der Karte.
Abbildung 2.2: Ein Irrgarten, der eine topologische Karte mit Hindernissen darstellt
Abbildung 2.3: Ein komplexer Irrgarten, der durch eine Heuristik gelöst wird
Seitenverzeichnis
1-6
9-10
11-12
31-32
31-44
25-28
45-62
63-84
85-106
107-126
127-128
129-144
145-164
165-166
167-182
183-206
207-216
217-232
233-234
235-256
257-270
271-284
285-286
287-300
301-322
323-338
339-354
355-366
367-382
383-384
385-390
391-396
Über die Autoren
John Mueller ist freier Autor und technischer Lektor. Das Schreiben liegt ihm im Blut – er hat bisher 102 Bücher und über 600 Artikel veröffentlicht. Seine Themengebiete reichen dabei von Netzwerken über künstliche Intelligenz und Datenbankverwaltung bis hin zu reinem Programmieren. Unter seinen aktuellen Büchern ist ein Buch über Python für Anfänger, Python für Data Science sowie ein Buch über MATLAB. Darüber hinaus hat er Bücher über Amazon Web Services für Administratoren, über die Sicherheit von Webanwendungen, zur HTML5-Entwicklung mit JavaScript sowie über CSS3 geschrieben. Als technischer Lektor hat er Texten von über 63 Autoren den letzten Schliff gegeben. Überdies hat John Mueller Texte für mehrere technische Magazine lektoriert. John Muellers Blog (in englischer Sprache) finden Sie unter http://blog.johnmuellerbooks.com/.
Wenn John Mueller nicht vor seinem Computer sitzt, ist er in seinem Garten, hackt Holz oder genießt die Natur. Er keltert selbst Wein, backt gerne Kekse und strickt. Im Internet können Sie ihn unter [email protected] erreichen. Bitte schreiben Sie ihm in Englisch. Aktuell erstellt er unter http://www.johnmuellerbooks.com/ seine persönliche Webseite. Schauen Sie gerne einmal rein und geben Sie Ratschläge, wie er sie verbessern kann.
Luca Massaron ist als Data Scientist auf multivariate Statistik, maschinelles Lernen und Customer Insight spezialisiert. Über zehn Jahre hat er Erfahrungen im Lösen praxisnaher Aufgaben und in der Unterstützung unterschiedlicher Interessengruppen durch Analysen, Statistik, Data-Mining und Algorithmen gesammelt. Er interessiert sich brennend für alles, was Daten und Analysen betrifft, und vermittelt das Potenzial datenbasierten Wissens sowohl Experten als auch Laien mit großer Leidenschaft. Des Weiteren ist Luca Massaron Mitverfasser der Bücher Data Science mit Python für Dummies und Maschinelles Lernen mit Python und R für Dummies. Mehr als unnötige Raffinesse schätzt er Einfachheit; er ist der Meinung, dass man es mit dem Verständnis der einfachen Grundlagen und des Wesentlichen in jedem Bereich sehr weit bringen kann.
John Muellers Widmung
Dieses Buch ist Julie Thrond gewidmet, einer treuen und gütigen Freundin. Ich wünsche ihr, dass sie stets die Herausforderungen des Lebens meistern wird.
Luca Massarons Widmung
Ich widme dieses Buch meiner Frau Yukiko, die stets neugierig ist und sich keine Möglichkeit entgehen lässt, die Wunder dieser faszinierenden Welt zu bestaunen. Bleibe neugierig. Freue dich über große und kleine Überraschungen. Fürchte dich vor nichts und sorge dich nicht um unwichtige Details. Bleibe stets jung im Geist. Das wünsche ich dir von Herzen.
John Muellers Danksagung
Mein Dank geht an meine Frau Rebecca. Obwohl sie nicht mehr unter uns ist, lebt ihr Geist in jedem meiner Bücher und in jedem geschriebenen Wort weiter. Sie hat immer an mich geglaubt.
Dank gilt auch Russ Mullen für das technische Lektorat dieses Buches. Russ hat einen großen Beitrag zur Genauigkeit und Detailliertheit des Buchinhalts geleistet; er hat sehr engagiert an der Recherche für dieses Buch mitgewirkt, schwer auffindbare Webadressen gefunden und sehr viele Tipps gegeben.
Mehrere Menschen haben das gesamte Buch oder Teile dieses Buches gelesen, Verbesserungen zu methodischen Ansätzen vorgeschlagen, Skripte getestet oder allgemeine Anregungen für Inhalte gegeben, die sich jeder Leser wünscht. Diese unbezahlten Freiwilligen haben mich auf verschiedene Weisen unterstützt, die ich hier nicht alle aufzählen kann. Insbesondere bedanke ich mich bei Eva Beattie, Glenn A. Russell, Alberto Boschetti, Cristian Mastrofrancesco, Diego Paladini, Dimitris Papadopoulos, Matteo Malosetti, Sebastiano Di Paola, Warren B und Zacharias Voulgaris für ihre allgemeinen Anregungen, für das Lesen des gesamten Buches und ihre aufopferungsvolle Hingabe.
Luca Massarons Danksagung
Mein größter Dank geht an meine Familie, Yukiko und Amelia, für ihre Unterstützung, ihr Verständnis und ihre liebevolle Geduld während der langen Tage, Nächte, Wochen und Monate, in denen ich an diesem Buch gearbeitet habe.
Einführung
Wahrscheinlich müssen Sie sich im Rahmen Ihres Studiums oder Ihrer Arbeit mit dem Thema Algorithmen befassen. Womöglich haben Sie hierzu bereits Literatur gelesen, mussten jedoch enttäuscht feststellen, dass diese viel besser als Einschlaf- denn als Lernhilfe geeignet ist und Ihnen kaum etwas Neues beibringen kann. Selbst wenn Sie es in diesen Lehrbüchern an den obskuren Symbolen vorbeischafften, die der Hand eines exzentrischen Zweijährigen mit einer Vorliebe für Schnörkeleien zu entstammen schienen, hatten Sie am Ende vergessen, wozu Sie die Lektüre ursprünglich aufgeschlagen hatten. Ja, Mathematiktexte sind in der Tat langweilig! Algorithmen für Dummies ist hier anders. Zunächst wird Ihnen auffallen, dass das Buch keine komplizierten Symbole enthält (insbesondere keine verschnörkelten), die den Textfluss unterbrechen. Einige wenige Symbole werden Sie hier und da entdecken – Sie haben trotz allem gerade ein Mathematikbuch vor Augen –, jedoch finden Sie überall auch klare Bezeichnungen, Erklärungen und zahlreiche Tipps zu Algorithmen, mit denen sich Aufgaben erfolgreich lösen lassen. Sie werden einfache Programmiertechniken und mathematische Kunststücke erlernen, mit denen Sie Außerordentliches vollbringen und Ihre Freunde zum Staunen bringen. Und das alles, ohne Ihr Gehirn dabei übermäßig zu beanspruchen oder einzuschlafen – außer natürlich, wenn Ihnen wirklich danach ist.
Über dieses Buch
Algorithmen für Dummies ist das Mathematikbuch, das Sie sich während Ihres Studiums an der Uni immer wünschten und nicht finden konnten. In diesem Buch werden Sie unter anderem lesen, dass Algorithmen keine neue Erfindung sind. Bereits im Jahr 1600 v. Chr. entwickelten die Babylonier Algorithmen, um damit einfache Aufgaben zu lösen. Wenn schon die Babylonier mit Algorithmen arbeiten konnten, wird dies für Sie sicherlich auch kein Problem darstellen! Dieses Buch unterscheidet sich in drei wesentlichen Aspekten von den meisten anderen Mathematikbüchern:
Algorithmen tragen Eigennamen und haben eine historische Grundlage. Somit kann man sie sich leichter merken und die Motivation für ihre Entwicklung besser nachvollziehen.
Es enthält einfache Erklärungen, wie Algorithmen anspruchsvolle Aufgaben wie die Bearbeitung von Daten, Datenanalysen und Wahrscheinlichkeitsprognosen erfolgreich meistern.
Die Funktionsweise von Algorithmen wird durch Programmiercode veranschaulicht, der ganz ohne die mysteriösen Symbole auskommt, die nur Mathematiker entziffern können.
Ein wichtiger Aspekt jeder Arbeit liegt im richtigen Gebrauch des entsprechenden Werkzeugs. In diesem Buch benutzen wir zur Bearbeitung von Aufgaben die Programmiersprache Python. Diese Sprache verfügt über einige besondere Funktionalitäten, die das Arbeiten mit Algorithmen erheblich erleichtern werden. Beispielsweise erhalten Sie durch Python Zugang zu einer großen Anzahl an Programmpaketen, mit denen man alles nur denkbar Mögliche bewerkstelligen kann – und zu einigen weiteren Paketen für Aufgaben, an die Sie bislang nicht einmal gedacht hatten. Im Vergleich zu anderen Texten, die sich auf Python beziehen, wird Sie dieses Buch jedoch nicht unter einem Haufen von Programmpaketen begraben. Wir verwenden eine kleine Auswahl kostenloser Pakete, die hohe Flexibilität und Funktionalität garantieren. An keiner Stelle dieses Buches werden Sie zusätzliches Geld ausgeben müssen, um dem Inhalt folgen zu können.
Des Weiteren werden Sie in diesem Buch viele interessante Ansätze kennenlernen. Dabei sollen Sie nicht nur sehen, wie man Algorithmen für unterschiedliche Aufgaben einsetzt, sondern bekommen auch eine Erklärung ihrer Funktionsweise. Ganz im Gegenteil zu vielen anderen Büchern werden Sie mit Algorithmen für Dummies genau verstehen, was Sie gerade tun, ohne dass hierfür ein Doktorgrad in Mathematik nötig ist. Für jedes Beispiel wird der entsprechende Output angegeben und dessen Bedeutung erklärt. So werden Sie nicht das Gefühl haben, dass etwas ausgelassen wurde.
Möglicherweise haben Sie Bedenken, was das ganze Programmieren betrifft. Doch auch hier lässt Sie dieses Buch nicht im Stich. Ganz zu Anfang werden Sie eine komplette Installationsbeschreibung für Anaconda vorfinden. Hierbei handelt es sich um eine integrierte Entwicklungsumgebung (englisch integrated development environment, IDE) für Python, die wir für den Inhalt dieses Buches ausgewählt haben. Einfache Erklärungen mit Verweisen werden Ihnen die grundlegenden Programmiertechniken in Python näherbringen. Der Fokus liegt hierbei darauf, Sie anhand simpler und unkomplizierter Beispiele so schnell wie möglich in Gang zu bringen, ohne dass der Code dabei zu einem Hindernis auf dem Weg wird.
Konventionen in diesem Buch
Zum leichteren Verständnis verwendet dieses Buch die folgenden Formate:
Kursive Schrift wird zur Definition von Begriffen verwendet. Sie können die entsprechenden Informationen direkt dem danach folgenden Text entnehmen und müssen nicht nach anderen Quellen suchen.
Internetadressen, Programmiercode und Inhalte zum Eintippen sind in Monospace angegeben. Wörter zum Eintippen in kursiv sind Platzhalter. Das bedeutet, dass Sie sie durch etwas Passendes ersetzen sollen. Bei der Aufforderung »Geben Sie Ihren Namen ein und drücken Sie « sollten Sie also Ihren Namen durch Ihren tatsächlichen Namen ersetzen.
Menübefehle werden durch einen senkrechten Strich getrennt, zum Beispiel gibt Datei|Neue Datei an, dass Sie auf Datei und anschließend auf Neue Datei klicken sollen.
Törichte Annahmen über den Leser
Womöglich werden Sie kaum glauben können, dass wir bereits einige Annahmen über Sie getroffen haben – wir kennen Sie doch gar nicht! Obwohl Annahmen in der Regel tatsächlich unsinnig sind, mussten wir einige Annahmen treffen, um mit Ihnen einen gemeinsamen Ausgangspunkt für dieses Buch zu finden.
Die erste Annahme ist, dass Sie bereits ein wenig mit der Plattform vertraut sind, die wir in diesem Buch verwenden werden. Im Buch werden Sie diesbezüglich nur wenige weitere Ratschläge erhalten. In Kapitel 3 beschreiben wir, wie man Anaconda installiert; Kapitel 4 verschafft einen grundlegenden Überblick über die Programmiersprache Python; und in Kapitel 5 werden Sie lernen, wie man mit Python Datenverarbeitungsoperationen vornimmt. Um Ihnen so viele Informationen wie möglich zum Arbeiten mit Algorithmen und zum Programmieren mit Python zu geben, haben wir von plattformspezifischen Inhalten abgesehen. Sie sollten wissen, wie man Programme installiert, diese anwendet und wie Sie die gewählte Plattform bedienen, ehe Sie sich mit diesem Buch beschäftigen.
Bei diesem Buch handelt es sich nicht um ein Elementarwerk für Mathematik. Selbstverständlich werden Sie sehr viele Beispiele mit komplizierten mathematischen Inhalten vorfinden, jedoch liegt der Schwerpunkt nicht auf dem Erlernen mathematischer Theorien, sondern auf dem Bearbeiten algorithmenbasierter Aufgaben mit Python. Sie werden Erklärungen vieler Algorithmen vorfinden, sodass Sie deren Funktionsweise besser verstehen können. In den Kapiteln 1 und 2 werden Sie die für dieses Buch nötigen Grundlagen kennenlernen.
Weiter nehmen wir an, dass Sie über einen Internetzugang verfügen. An vielen Stellen des Buches finden sich Quellenangaben zu zusätzlichem Onlinematerial, mit dem Sie Ihr Wissen erweitern können.
Symbole, die in diesem Buch verwendet werden
In diesem Buch finden Sie an den Seitenrändern verschiedene Symbole, die Inhalte von besonderem Interesse markieren – oder auch nicht, je nachdem, wo Ihr Interesse liegt. Diese Symbole haben die folgenden Bedeutungen:
Durch Tipps kann man Zeit sparen und Aufgaben ohne viel zusätzlichen Aufwand lösen. Die Tipps in diesem Buch beschreiben besondere Techniken, mit denen Sie die Algorithmen- oder Datenanalyseaufgaben effizienter bearbeiten können, und geben Hinweise, wie Sie den größtmöglichen Nutzen aus Python ziehen können.
Ohne dabei allzu streng klingen zu wollen, möchten wir Ihnen nahelegen, die Warnungssymbole dieses Buches in jedem Fall zu beachten. Sonst könnte es sein, dass Ihr Programm nicht wie erwartet funktioniert, dass verlässliche Algorithmen plötzlich falsche Antworten ausgeben oder dass Sie – im schlimmsten Fall – Daten verlieren.
Dieses Symbol bezeichnet einen fortgeschrittenen Tipp oder eine raffinierte Methode. Es mag sein, dass Sie diese nützlichen Informationen eher langweilen werden oder dass Sie darin die Lösung für eine Ihrer Programmieraufgaben finden werden. Sie können die Informationen unter diesen Symbolen auch überspringen.
Wenn Sie in einem Kapitel oder in einem Abschnitt nicht mehr weiterkommen, sollten Sie den Inhalt unter diesem Symbol zurate ziehen. Der Text enthält in der Regel Prozessbeschreibungen oder wesentliche Informationen zum Arbeiten mit Python oder zum erfolgreichen Ausführen von Algorithmen- oder Datenanalyseaufgaben.
Wie es weitergeht
Nun ist es an der Zeit, Ihre Abenteuerreise über Algorithmen anzutreten! Wenn Algorithmen für Sie komplettes Neuland sind, sollten Sie bei Kapitel 1 anfangen und sich in einem für Sie angenehmen Tempo durch das Buch arbeiten und dabei so viel wie möglich vom Inhalt mitnehmen. Sie sollten sich im Vorfeld auf jeden Fall ein wenig Wissen zu Python anlesen, da diese Sprache für die Beispiele in diesem Buch verwendet wird.
Wenn Sie Anfänger sind, der es nicht abwarten kann, mehr zu Algorithmen zu erfahren, können Sie direkt mit Kapitel 3 anfangen. Seien Sie sich jedoch bewusst, dass Sie einige der späteren Themen vielleicht etwas verwirrend finden werden. Haben Sie Anaconda bereits installiert, reicht es, Kapitel 3 zu überfliegen. Um mit dem Inhalt dieses Buches arbeiten zu können, sollte die Version 3.4 von Python auf Ihrem Computer installiert sein. Da die 2.x-Version einige der erwähnten Pakete nicht unterstützt, werden die genannten Beispiele mit dieser Version von Python nicht funktionieren.
Leser, die bereits ein wenig mit Python vertraut sind und die entsprechenden Versionen installiert haben, können Zeit sparen und direkt bei Kapitel 6 einsteigen. Wenn Ihnen etwas unklar ist, können Sie bei Bedarf zu früheren Kapiteln zurückkehren. Sie sollten indes die Funktionsweise der einzelnen Methoden verstanden haben, ehe Sie sich mit der nächsten Methode beschäftigen. Jede Technik, jedes Programmierbeispiel und jede Vorgehensweise beinhaltet wertvolle Informationen – wenn Sie diese auslassen, werden Sie eventuell wesentliche Inhalte verpassen.
Dachten Sie wirklich, dass Sie den gesamten Code im Buch per Hand eingeben müssen? Die meisten Leser hätten sicherlich lieber mehr Zeit für die tatsächliche Arbeit mit Python, um Aufgaben mit Algorithmen zu bearbeiten und die vielen spannenden Möglichkeiten dieser Sprache kennenzulernen, als seitenweise Befehle abzutippen. Zum Glück sind alle Beispiele aus diesem Buch auch als Download erhältlich. Es reicht also aus, das Buch zu lesen, um mehr über die Verwendung unterschiedlicher algorithmischer Methoden zu lernen. Die entsprechenden Dateien finden Sie dann unter www.wiley-vch.de/publish/dt/books/ISBN3-527-71381-6.
Teil I
Erste Schritte
In diesem Teil …
Algorithmen zur Lösung praktischer Aufgaben einsetzen
Verstehen, wie Algorithmen aufgebaut sind
Python installieren und konfigurieren
Python verwenden, um mit Algorithmen zu arbeiten
Mit Python einfache Algorithmen erstellen
Kapitel 1
Grundlegendes über Algorithmen
In diesem Kapitel
Definieren, was ein Algorithmus ist
Algorithmen verwenden, um mithilfe von Computern Lösungen zu berechnen
Den Unterschied zwischen Aufgaben und Lösungen verstehen
Daten aufbereiten, um Lösungen zu finden
Wie die große Mehrheit aller Menschen sind womöglich auch Sie ein wenig verwirrt, wenn Sie dieses Buch öffnen, um Ihre Abenteuerreise über Algorithmen anzutreten. Die meisten Texte definieren weder, was ein Algorithmus genau ist, noch erklären sie, wofür Algorithmen nützlich sind. Stattdessen nehmen sie an, dass Sie bereits mit Algorithmen vertraut sind und lediglich zur Vertiefung oder Erweiterung Ihres Wissens mehr zum Thema lesen wollen. Viele Bücher enthalten verwirrende Definitionen, die alles andere als Klarheit verschaffen und Algorithmen einem abstrakten, numerischen oder symbolischen Ausdruck gleichsetzen.
Im ersten Teil dieses Kapitels wird erklärt, was der Ausdruck Algorithmus eigentlich bedeutet und welchen Nutzen Sie aus dem Gebrauch von Algorithmen ziehen können. Algorithmen sind keine Magie, sondern werden tagtäglich und überall eingesetzt. Mit größter Wahrscheinlichkeit benutzen auch Sie seit Jahren Algorithmen, die Ihren Alltag erleichtern, ohne sich dessen bewusst zu sein. In Wirklichkeit bilden Algorithmen mittlerweile das Rückgrat, das unsere zunehmend komplexe und technische Gesellschaft aufrechterhält und lenkt.
Dieses Kapitel beleuchtet auch, wie Computer mithilfe von Algorithmen Lösungen finden, was der Unterschied zwischen Aufgaben und Lösungen ist und wie sich Datenverarbeitungsmethoden effektiv in der Auffindung von Lösungen einsetzen lassen. Das Ziel dieses Kapitels ist es, den Unterschied zwischen Algorithmen und anderen Methoden, die häufig mit Algorithmen verwechselt werden, zu verdeutlichen. Kurz :Sie werden verstehen, wieso Algorithmen so wesentlich sind und wie sie sich auf Daten anwenden lassen.
Algorithmen beschreiben
Seit Tausenden von Jahren lösen Menschen Algorithmen von Hand. Je nachdem, wie komplex die zu lösende Aufgabe ist, kann dieser Prozess sehr zeitaufwendig sein und etliche numerische Berechnungen beinhalten. Algorithmen dienen dem Auffinden von Lösungen: je schneller und einfacher, desto besser. Zwischen den mathematischen Algorithmen, die von Genies wie Euklid, Newton oder Gauß entwickelt wurden, und den modernen Algorithmen, die an Universitäten sowie privaten Forschungs- und Testlabors entwickelt werden, besteht jedoch ein signifikanter Unterschied, der hauptsächlich im Gebrauch von Computern begründet ist. Computer können Rechenprozesse erheblich beschleunigen. Der Einsatz immer leistungsfähigerer Computersysteme hat in der Entwicklung neuer Algorithmen bereits einen großen Fortschritt bewirkt. Sie mögen bemerkt haben, dass Lösungen heutzutage immer schneller gefunden werden, was teilweise daran liegt, dass Computerleistung stetig zunimmt und gleichzeitig bezahlbar bleibt. Computer können komplexe Aufgaben mithilfe von Algorithmen lösen – manchmal in Form einer Spezialhardware – und sind mittlerweile allgegenwärtig.
In der Arbeit mit Algorithmen betrachtet man einen Input, den gewünschten Output sowie den Prozess (eine Abfolge von Aktionen), der den gewünschten Output zum gegebenen Input liefert. Wird nicht berücksichtigt, wie Algorithmen in der Praxis funktionieren, werden die wesentlichen Begriffe womöglich falsch verstanden und Algorithmen nicht richtig angewandt. Der dritte Teil des Kapitels widmet sich daher Algorithmen in Bezug auf die reale Welt. Hier werden die Begriffe untersucht, die dem Verständnis von Algorithmen dienen und die verdeutlichen, dass die Realität oft nicht ganz so perfekt ist. Durch die realistische Beschreibung von Algorithmen lassen sich allzu hohe Erwartungen herunterschrauben; so kann genauer überlegt werden, was ein Algorithmus in Wirklichkeit leisten kann.
Algorithmen können sehr vielseitig sein. Dieses Buch will einen Überblick verschaffen, wie Algorithmen unser Leben verändern und bereichern. Daher liegt der Fokus auf Algorithmen, die für die Datenverarbeitung durch einen Computer mit der nötigen Rechenleistung verwendet werden. Für die Algorithmen in diesem Buch muss der Dateninput stets in einer bestimmten Form vorliegen. Dies hat mitunter zur Folge, dass Daten verarbeitet werden müssen, um die Anforderungen des Algorithmus zu erfüllen. Dabei ändert sich der Inhalt nicht, wohl aber die Form und Art ihrer Darstellung. So macht der Algorithmus neue Muster sichtbar, die zuvor nicht erkennbar, jedoch bereits in den Daten vorhanden waren.
In der Literatur werden Algorithmen oftmals entweder zu kompliziert oder schlichtweg falsch und verwirrend dargestellt. Gerne werden Begriffe mit Algorithmen verwechselt, die eigentlich keine sind. Obwohl sich mitunter alternative Definitionen auffinden lassen, definiert dieses Buch die wichtigsten Begriffe wie folgt:
Gleichung: Zahlen und Symbole, die, als Ganzes betrachtet, für einen bestimmten Wert stehen. Eine Gleichung enthält stets ein Gleichheitszeichen, das verdeutlicht, dass die Zahlen und Symbole den Wert auf der anderen Seite des Gleichheitszeichens ergeben. Allgemein bestehen Gleichungen aus Informationen über Variablen, die in Form von Symbolen ausgedrückt werden, müssen jedoch nicht unbedingt Variablen enthalten.
Formel: Eine Kombination aus Zahlen und Symbolen, die Informationen oder Ideen ausdrückt. Formeln stehen normalerweise für ein mathematisches oder logisches Konzept wie zum Beispiel die Definition des größten gemeinsamen Teilers (ggT) zweier ganzer Zahlen. Allgemein zeigen sie eine Beziehung zwischen zwei oder mehreren Variablen auf. Für die meisten Menschen ist eine Formel eine besondere Form einer Gleichung.
Algorithmus: Eine Abfolge von Schritten, die der Lösung eines Problems dient. Dieser Vorgang ist insofern spezifisch, als dass er eine ganz bestimmte Lösung für die Aufgabenstellung liefert. Ein Algorithmus muss nicht mathematischer oder logischer Natur sein, 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, beispielsweise bei der Mitternachtsformel zur Lösung von quadratischen Gleichungen. Um als Algorithmus gelten zu können, muss ein Prozess die folgenden Eigenschaften haben:
Endlichkeit: Früher oder später muss der Algorithmus die Aufgabe lösen. In diesem Buch werden Aufgabenstellungen behandelt, deren Lösung bekannt ist. So können Sie beurteilen, ob der Algorithmus die Aufgabe richtig gelöst hat.
Wohldefiniertheit: Die Abfolge der Schritte muss präzise und leicht verständlich sein. In der Implementierung von Algorithmen kommen Computer zum Einsatz; um einen brauchbaren Algorithmus zu erzeugen, müssen Computer also alle erforderlichen Schritte nachvollziehen können.
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.
Vor diesem Hintergrund sollen die folgenden Abschnitte Algorithmen genauer beleuchten. Ziel ist hier nicht eine genaue Definition dessen, was ein Algorithmus ist. Vielmehr soll genauer dargelegt werden, wie Algorithmen in das Gesamtbild passen, damit Sie ein eigenes Verständnis entwickeln und nachvollziehen können, weshalb Algorithmen so wichtig sind.
Definitionen zur Anwendung von Algorithmen
Ein Algorithmus besteht stets aus einer Reihenfolge von Schritten zur Lösung einer mathematischen Formel, die jedoch nicht unbedingt ausgeführt werden müssen. Algorithmen können sehr umfangreich sein. Sie berechnen Aufgaben in den Naturwissenschaften, im medizinischen sowie im Finanzbereich, für die Industrieproduktion und -versorgung sowie im Informationsaustausch. Sie unterstützen uns in jedem Bereich unseres täglichen Lebens. Jede endliche, wohldefinierte und effiziente Aktionsabfolge innerhalb unseres Lebens ist ein Algorithmus. Beispielsweise steckt sogar hinter einem eigentlich trivialen und einfachen Toastbrot so etwas wie ein Algorithmus. Tatsächlich findet das Toasten von Brot im Informatikunterricht häufig Erwähnung, da es einen Algorithmus beschreibt:
1. Brot aus dem Schrank nehmen.
2. Brot in den Toaster stecken.
3. Toaster anschalten.
4. Wenn das Toastbrot hochfliegt, herausnehmen und buttern.
5. Essen und genießen.
Eine der wichtigsten Anwendungen von Algorithmen ist das Lösen von Formeln. Zum Beispiel lässt sich der größte gemeinsame Teiler zweier ganzer Zahlen per Hand ermitteln, indem man die Faktoren beider Zahlen aufschreibt und im Anschluss den größten Faktor auswählt, den beide Zahlen gemeinsam haben. So ist ggT(20, 25) die Zahl 5, da 5 die größte Zahl ist, die sowohl 20 als auch 25 teilt. Jeden ggT per Hand zu finden (auch eine Art von Algorithmus), ist jedoch sehr zeitaufwendig und zudem fehleranfällig. Daher entwickelte der griechische Mathematiker Euklid einen Algorithmus, der die Aufgabe über Division mit Rest effizienter löste.
Eine Formel aus Symbolen und Zahlen, die Informationen oder Ideen ausdrücken, kann mehrere Lösungen haben, von denen jede ein Algorithmus ist. So gibt es im Falle des ggT einen weiteren gebräuchlichen Algorithmus von Lehmer, der auf dem Algorithmus von Euklid beruht, ihn aber deutlich beschleunigt. Weil jede Formel auf verschiedene Arten gelöst werden kann, werden Algorithmen oft genau verglichen, um herauszufinden, welcher in einer gegebenen Situation am besten funktioniert.
Um in unserer hoch technisierten Welt, die sich immer schneller und schneller dreht, Schritt halten zu können, sind wir auf Algorithmen angewiesen. Wissenschaftliche Errungenschaften wie die Entschlüsselung des menschlichen Genoms wurden erst in unserer Zeit möglich, weil die Wissenschaftler Algorithmen schufen, die die Aufgabe schnell genug bewältigen konnten. Die Abwägung, welcher Algorithmus in einem bestimmten Fall oder in einer durchschnittlichen Gebrauchssituation besser ist, stellt ein komplexes und unter Informatikern häufig diskutiertes Thema dar.
In der Informatik kann ein und derselbe Algorithmus unterschiedliche Formen annehmen. So kann der Euklidische Algorithmus sowohl rekursiv als auch iterativ beschrieben werden. Stark verallgemeinert sind Algorithmen Methoden zur Lösung von Formeln. Es wäre jedoch ein Irrtum anzunehmen, dass es zu jeder Formel nur jeweils einen passenden Algorithmus gibt oder dass jeder Algorithmus nur eine akzeptable Darstellung besitzt. Die Verwendung von Algorithmen zur Berechnung von Lösungen unterschiedlicher Art hat eine lange Geschichte – und wurde nicht erst kürzlich neu erfunden.
Selbst wenn Sie sich auf Informatik, Datenanalyse, künstliche Intelligenz und andere technische Bereiche beschränken, werden Sie viele unterschiedliche Algorithmen antreffen – zu viele für ein einziges Buch. Beispielsweise umfasst Die Kunst der Computerprogrammierung von Donald E. Knuth 3.168 Seiten in vier Bänden und bringt es dennoch nicht fertig, das gesamte Thema abzudecken – der Autor wollte sogar noch weitere Bände schreiben. Hier sind einige interessante Anwendungsgebiete von Algorithmen:
Suchen: Die Suche nach Informationen und die damit einhergehende Überprüfung, ob es sich bei der gefundenen Information tatsächlich um die gewünschte Information handelt, ist eine wichtige Aufgabe. Ohne diese Option wären viele Vorgänge im Internet unmöglich, beispielsweise wenn Sie eine Webseite suchen, die die perfekte Kaffeetasse für das Büro anbietet.
Sortieren: Heutzutage leiden viele Menschen unter dem allgegenwärtigen Informationsüberfluss. Es ist daher wichtig, eine Reihenfolge festzulegen, in der Informationen dargestellt werden sollen. Durch das Ordnen von Informationen wird das Datenchaos reduziert. Als Kind haben Sie sicherlich gelernt, dass es leichter ist, ein bestimmtes Spielzeug unter Ihren Spielzeugen wiederzufinden, wenn die Spielzeuge ordentlich aufgeräumt und nicht überall verstreut sind. Stellen Sie sich vor, Sie finden bei Amazon Tausende von Kaffeetassen im Angebot, ohne sie nach Preis oder positiven Bewertungen sortieren zu können. Viele komplexe Algorithmen benötigen sogar eine bestimmte Datenordnung, um überhaupt verlässlich angewandt werden zu können. Sortieren ist daher eine wichtige Voraussetzung für den Lösungsfindungsprozess.
Umformungen: Einen Datentyp in einen anderen umformen zu können, ist wesentlich für das Verständnis und den effektiven Gebrauch von Daten. Zum Beispiel könnte es sein, dass Sie mit dem metrischen Messsystem umgehen können, in Ihren Quellen jedoch das britische System verwendet wird. Umformungen von einem System in das andere erleichtert das Verständnis der Daten. Genauso transformiert die schnelle Fourier-Transformation (FFT) Signale von der Zeitdomäne in die Frequenzdomäne, was beispielsweise in W-LAN-Routern zum Einsatz kommt.
Planung: Die angemessene Bereitstellung von Ressourcen ist ein weiterer Bereich, aus dem Algorithmen mittlerweile nicht mehr wegzudenken sind. So sind Ampeln an Straßenkreuzungen seit Langem keine simplen Vorrichtungen mehr, die die Sekunden zwischen den Lichtphasen zählen. Moderne Ampeln berücksichtigen viele weitere Aspekte wie Tageszeit, Wetterbedingungen und Verkehrsfluss. Die Planungsmethoden können hierbei unterschiedliche Formen annehmen. Bedenken Sie, dass Ihr Computer gleichzeitig mehrere Aufgaben erledigen kann. Ohne einen Planungsalgorithmus würde das Betriebssystem womöglich alle zur Verfügung stehenden Ressourcen beanspruchen und weitere Programme daran hindern, ausgeführt zu werden.
Kurvenanalyse: Die Bestimmung der kürzesten Verbindung zwischen zwei Punkten hat etliche Anwendungen. Ohne diesen Algorithmus würde Ihr GPS keine Routenplanung vornehmen können, weil es Sie niemals durch die Straßen der Stadt führen könnte, ohne die kürzeste Strecke zwischen Punkt A und Punkt B auszuwählen.
Kryptografie: Daten vor Hackerangriffen zu sichern, ist ein ständiger Kampf. Mithilfe von Algorithmen können Daten analysiert, verschlüsselt und am Ende wieder in ihre ursprüngliche Form gebracht werden.
Generieren pseudo-zufälliger Zahlen: Stellen Sie sich ein Spiel vor, das immer gleich abläuft. Sie fangen jedes Mal am selben Ort an und machen dieselben Schritte auf dieselbe Art und Weise. Ohne die Möglichkeit der Generierung scheinbar zufälliger Zahlen wären viele Computerprozesse unmöglich.
Diese Liste stellt lediglich eine stark gekürzte Übersicht dar. Algorithmen werden für viele Zwecke und sehr unterschiedlich verwendet, und Menschen entwickeln ununterbrochen neue Algorithmen, um sowohl bereits vorhandene als auch neue Problemstellungen zu lösen. Der wichtigste Aspekt in der Arbeit mit Algorithmen ist der folgende: Ein bestimmter Input erzeugt einen daraus zu erwartenden Output. Zweitrangige Aspekte sind die Menge der nötigen Ressourcen sowie die Zeit, die für die Lösung benötigt wird. Je nach Problemstellung und gewähltem Algorithmus spielen eventuell auch Aspekte wie Genauigkeit und Konsistenz eine Rolle.
Algorithmen sind überall
Nicht ohne Grund wurde im vorigen Abschnitt der Toasteralgorithmus genannt. Es handelt sich hierbei vermutlich um den beliebtesten Algorithmus, der jemals erdacht wurde. Bereits Grundschulkinder kennen eine eigene, äquivalente Variante des Toasteralgorithmus, ehe sie die elementarsten Mathematikaufgaben lösen können. Unzählige Varianten des Toasteralgorithmus mit entsprechenden Outputs sind denkbar. Je nach Person und Kreativität können die Ergebnisse ganz unterschiedlich ausfallen. Zusammenfassend lässt sich festhalten, dass Algorithmen in einer großen Vielfalt und an oftmals unerwarteten Stellen auftreten.
Jede mithilfe eines Computers ausgeführte Aufgabe beinhaltet Algorithmen. Einige Algorithmen sind bereits fester Bestandteil der Computerhardware; sie sind darin eingebettet – daher der Begriff eingebettete Systeme. Bereits das Einschalten eines Computers erfordert einen Algorithmus. Auch in Betriebssystemen, Anwendungen und anderen Softwarearten sind sie zu finden. Benutzer verlassen sich auf Algorithmen. Anleitungen beschreiben Aufgaben in aufeinanderfolgenden Schritten, jedoch könnten diese Schritte genauso gut Anweisungen oder Nutzungsbedingungen sein.
Auch Tagesroutinen gleichen Algorithmen. Überlegen Sie nur, wie Sie Ihren Tag verbringen. Geht es Ihnen wie den meisten Menschen, so besteht Ihr Alltag in erster Linie aus denselben täglich wiederholten Handlungen, die Sie in derselben Reihenfolge ausführen. Ihr Tag wird so zu einem Algorithmus, der die Aufgabe löst, erfolgreich weiterzuleben, ohne dabei unnötig Energie zu verschwenden. Denn Routine bezweckt dies: Sie macht uns effizient.
Sofortmaßnahmen beruhen häufig auf Algorithmen. Im Flugzeug nehmen Sie etwa die Notfalltafel aus der Rückenlehne vor Ihnen. Darauf abgebildet ist eine Reihe von Piktogrammen, die veranschaulichen, wie die Nottür geöffnet und die Rutschbahn ausgefahren wird. Wahrscheinlich müssen Sie nicht einmal die Sätze lesen, da Sie bereits anhand der Abbildungen verstehen, wie Sie möglichst schnell aus dem Flugzeug gelangen. In diesem Buch finden Sie für jeden Algorithmus immer dieselben drei Punkte:
1. Beschreibung der Aufgabe.
2. Aufstellen einer Abfolge von Schritten, die die Aufgabe lösen (wohldefiniert).
3. Ausführung der Schritte zum Erreichen des gewünschten Ergebnisses (endlich und effektiv).
Mit Computern Aufgaben lösen
Der Begriff Computer mag auf manche Leser zu technisch und etwas überfordernd wirken, doch in Wirklichkeit bewegen wir uns tagtäglich in der Welt der Computer. Die meiste Zeit über tragen Sie mindestens einen Computer mit sich, nämlich Ihr Smartphone. Verwenden Sie ein Spezialgerät wie beispielsweise einen Herzschrittmacher, so befindet sich darin ein weiterer Computer. Ihr Smart-TV enthält mindestens einen Computer, das Gleiche gilt für Ihr Heimnetzwerk. In einem Auto können sich bis zu 30 Computer in Form von eingebetteten Mikroprozessoren befinden, die Benzinverbrauch, Motorverbrennung, Übertragung, Steuerung und Stabilität regulieren und mehr Programmcode benötigen als ein Kampfjet (laut einem Artikel in der New York Times, zu finden in englischer Sprache unter http://www.nytimes.com/2010/02/05/technology/05electronics.html). Die automatisierten Autos, die nach und nach auf dem Automobilmarkt auftauchen, werden eine noch größere Anzahl an eingebetteten Mikroprozessoren und weit komplexere Algorithmen erfordern. Computer wurden dazu erfunden, Aufgaben schnell und mit geringem Aufwand zu lösen. Es sollte Sie daher nicht überraschen, dass auch in diesem Buch Computer verwendet werden, um genauer zu erklären, was Algorithmen sind.
Computer können sich stark voneinander unterscheiden. Der Computer in Ihrer Armbanduhr ist sehr klein, während der auf Ihrem Schreibtisch recht groß ist. Supercomputer sind gigantisch und enthalten viele weitere kleine Computer, die alle darauf abgestimmt sind, gemeinsam komplexe Themen wie die Wettervorhersage für morgen zu bearbeiten. Die komplexesten Algorithmen verwenden besondere Computerfunktionen, um Lösungen für Aufgaben zu finden, die die Anwender ihnen vorgeben. In der Tat könnten hier erhebliche Ressourcen gespart werden, doch würde dies längere Wartezeiten oder ungenauere Ergebnisse bedeuten. In manchen Fällen ist die Wartezeit so endlos, dass das Ergebnis am Ende nicht mehr interessiert. Unter Berücksichtigung von Geschwindigkeit und Genauigkeit beleuchten die folgenden Abschnitte einige Besonderheiten von Computern, die Auswirkungen auf Algorithmen haben können.
Moderne CPUs und GPUs wirksam einsetzen
Universalprozessoren (englisch: CPUs) dienten ursprünglich der Durchführung von Berechnungen mithilfe von Algorithmen. Aufgrund ihrer allgemeinen Natur können sie jedoch eine Vielzahl anderer Aufgaben erledigen, wie zum Beispiel Daten verschieben oder mit externen Apparaten interagieren. Prozessoren können zwar alle Schritte innerhalb eines Algorithmus ausführen, doch nicht unbedingt schnell. Die Besitzer der ersten Universalprozessoren statteten ihr System daher gerne mit mathematischen Koprozessoren aus, um die Rechenarbeit zu beschleunigen. Heutzutage sind mathematische Koprozessoren bereits in allen Universalprozessoren enthalten, sodass Sie beim Kauf eines Intel-i7-Prozessors eigentlich mehrere Prozessoren in einem erwerben.
Interessanterweise vermarktet Intel immer noch Erweiterungen für Spezialprozessoren wie den Xeon-Phi-Prozessor, der mit Xeon-Chips arbeitet. Der Xeon-Phi-Chip wird zusammen mit einem Xeon-Chip verwendet, wenn rechenintensive Prozesse wie maschinelles Lernen durchgeführt werden sollen (um zu verstehen, wie man im Rahmen des maschinellen Lernens Algorithmen einsetzt, die anhand von Daten Prognosen erstellen und Informationen sinnvoll organisieren, siehe Maschinelles Lernen für Dummies von John Mueller und Luca Massaron).
Sie fragen sich womöglich, wieso in diesem Teil Grafikprozessoren (Graphics Processing Units, kurz: GPUs
