Algorithmen für Dummies

John Paul Mueller, Luca Massaron

• Verlag: Wiley-VCH
• Jahr: 2017
• ISBN:
  9783527809776
• Auflage: 1
• Thema: Computer Science
• Thema: Programming Algorithms

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.

31-44

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 – un...

Inhaltsverzeichnis

• Cover
• Über die Autoren
• Teil I: Erste Schritte
• Kapitel 1: Grundlegendes über Algorithmen
• Einführung
• Kapitel 2: Algorithmendesign
• Kapitel 3: Mit Python Algorithmen verwenden
• Kapitel 4: Algorithmen mit Python programmieren: Grundlagen
• Kapitel 5: Grundlagen der Datenbearbeitung mit Python
• Teil II: Die Notwendigkeit des Suchens und Sortierens
• Kapitel 6: Daten strukturieren
• Kapitel 7: Daten ordnen und durchsuchen
• Teil III: Die Welt der Graphen
• Kapitel 8: Die Grundlagen von Graphen
• Kapitel 9: Punkte verbinden
• Kapitel 10: Die Geheimnisse der Graphen
• Kapitel 11: Die richtige Webseite finden
• Teil IV: Der Kampf mit Big Data
• Kapitel 12: Big Data verwalten
• Kapitel 13: Abläufe parallelisieren
• Kapitel 14: Daten komprimieren
• Teil V: Komplexe Aufgaben angehen
• Kapitel 15: Mit gierigen Algorithmen arbeiten
• Kapitel 16: Dynamische Programmierung
• Kapitel 17: Randomisierte Algorithmen
• Kapitel 18: Lokale Suchen durchführen
• Kapitel 19: Lineare Optimierung
• Kapitel 20: Heuristiken untersuchen
• Teil VI: Der Top-Ten-Teil
• Kapitel 21: Zehn algorithmische Verfahren, die die Welt verändern
• Kapitel 22: Zehn bislang ungelöste Probleme
• Stichwortverzeichnis
• Wiley End User License Agreement