Kopec Algorithmen in Python

32 Klassiker vom Damenproblem bis zu neuronalen Netzen
1. Auflage 2020
ISBN: 978-3-8362-7749-5
Verlag: Rheinwerk
Format: EPUB
Kopierschutz: 0 - No protection

E-Book, Deutsch, 292 Seiten

Reihe: Rheinwerk Computing

Programmieren trainieren mit Python-Algorithmen

Das Programmiertraining für alle, die ihre ersten Schritte in der Programmierung gemacht haben und jetzt richtig durchstarten wollen! David Kopec stellt Ihnen in diesem Buch eine umfassende, zeitgemäße Auswahl an Algorithmen vor. Beginnen Sie mit einfachen Algorithmen zur Verschlüsselung und für die Suche und vertiefen Sie Ihr Wissen bei genetischen Algorithmen und Neuronalen Netzen.

Jede problemlösende Technik wird an einem konkreten Beispiel anschaulich vorgeführt. Darunter sind viele bekannte Klassiker der Informatik, aber auch neue Aufgaben. An zahlreichen Code-Beispielen in Python lernen Sie, wie Sie die Algorithmen implementieren und selbst in Algorithmen denken. So ist das Buch eine wertvolle Hilfe für jeden, der professionell programmieren möchte.

Jetzt geht’s los: Lösen Sie das Damenproblem, helfen Sie den Missionaren über den Fluss, ohne von Kannibalen zu gefressen werden, und geben Sie dem Dieb Tipps, welche Stücke er in seinen Rucksack packen soll.

• Programmieren trainieren mit bekannten und modernen Klassikern!
• Von der Suche bis zu k-Means, vom Dreizeiler bis zur dynamischen Programmierung und KI
• Für Studium, Coding-Katas, Workouts oder in Eigeninitiative – für jeden ist etwas dabei
• Titel der Originalausgabe: "Classic Computer Science Problems in Python". Übersetzt aus dem Amerikanischen von Sascha Kersken.

Aus dem Inhalt:

• Die Fibonacci-Folge, einfache Komprimierung, unknackbare Verschlüsselung, Pi berechnen
• DNS durchsuchen, Wege durchs Labyrinth, Flussüberquerungsrätsel
• Damenproblem, Vier-Farben-Satz, Wortsuchrätsel
• grafische Algorithmen
• genetische Algorithmen
• k-Means-Algorithmen
• einfache neuronale Netze
• Tic-tac-toe, Vier gewinnt
• Das Rucksackproblem, Das Problem des Handlungsreisenden
• und außerdem: zahlreiche Code-Beispiele in Python, Hinweise zum Einsatz der Algorithmen, Übungen und Tipps für die Programmier-Praxis

Autoren/Hrsg.

Kopec, David

Inhaltsverzeichnis

  Vorwort ... 13


  Einleitung ... 17


  1.  Kleine Aufgaben ... 25


       1.1 ... Die Fibonacci-Folge ... 25

       1.2 ... Triviale Komprimierung ... 32

       1.3 ... Unknackbare Verschlüsselung ... 38

       1.4 ... Pi berechnen ... 41

       1.5 ... Die Türme von Hanoi ... 43

       1.6 ... Anwendungen im Alltag ... 47

       1.7 ... Übungsaufgaben ... 48



  2.  Suchaufgaben ... 49


       2.1 ... DNA-Suche ... 49

       2.2 ... Labyrinthe lösen ... 57

       2.3 ... Missionare und Kannibalen ... 77

       2.4 ... Anwendungen im Alltag ... 82

       2.5 ... Übungsaufgaben ... 83



  3.  Bedingungserfüllungsprobleme ... 85


       3.1 ... Ein Framework für Bedingungserfüllungsprobleme schreiben ... 86

       3.2 ... Die Landkarte Australiens einfärben ... 91

       3.3 ... Das Acht-Damen-Problem ... 94

       3.4 ... Wortsuche ... 97

       3.5 ... SEND+MORE=MONEY ... 101

       3.6 ... Leiterplatten-Layout ... 103

       3.7 ... Anwendungen im Alltag ... 104

       3.8 ... Übungsaufgaben ... 105



  4.  Graphenprobleme ... 107


       4.1 ... Eine Landkarte als Graph ... 107

       4.2 ... Ein Framework für Graphen schreiben ... 110

       4.3 ... Den kürzesten Pfad finden ... 116

       4.4 ... Die Kosten für den Aufbau des Netzwerks minimieren ... 119

       4.5 ... Den kürzesten Pfad in einem gewichteten Graphen finden ... 132

       4.6 ... Anwendungen im Alltag ... 138

       4.7 ... Übungsaufgaben ... 139



  5.  Genetische Algorithmen ... 141


       5.1 ... Biologischer Hintergrund ... 141

       5.2 ... Ein generischer genetischer Algorithmus ... 143

       5.3 ... Ein naiver Test ... 151

       5.4 ... Wiedersehen mit SEND+MORE=MONEY ... 154

       5.5 ... Listenkomprimierung optimieren ... 158

       5.6 ... Kritik an genetischen Algorithmen ... 160

       5.7 ... Anwendungen im Alltag ... 162

       5.8 ... Übungsaufgaben ... 163



  6.  k-Means-Clustering ... 165


       6.1 ... Vorbereitungen ... 165

       6.2 ... Der k-Means-Clustering-Algorithmus ... 168

       6.3 ... Gouverneure nach Alter und Längengrad clustern ... 174

       6.4 ... Michael-Jackson-Alben nach Länge clustern ... 179

       6.5 ... K-Means-Clustering-Probleme und -Erweiterungen ... 181

       6.6 ... Anwendungen im Alltag ... 182

       6.7 ... Übungsaufgaben ... 183



  7.  Einfache neuronale Netzwerke ... 185


       7.1 ... Biologische Grundlagen? ... 186

       7.2 ... Künstliche neuronale Netzwerke ... 187

       7.3 ... Vorbereitungen ... 195

       7.4 ... Das Netzwerk aufbauen ... 197

       7.5 ... Klassifikationsprobleme ... 204

       7.6 ... Neuronale Netzwerke beschleunigen ... 213

       7.7 ... Probleme und Erweiterungen neuronaler Netzwerke ... 214

       7.8 ... Anwendungen im Alltag ... 215

       7.9 ... Übungsaufgaben ... 217



  8.  Adversarial Search ... 219


       8.1 ... Grundkomponenten von Brettspielen ... 219

       8.2 ... Tic Tac Toe ... 221

       8.3 ... Vier gewinnt ... 231

       8.4 ... Minimax-Verbesserungen über die Alpha-Beta-Suche hinaus ... 240

       8.5 ... Anwendungen im Alltag ... 242

       8.6 ... Übungsaufgaben ... 243



  9.  Sonstige Aufgaben ... 245


       9.1 ... Das Rucksackproblem ... 245

       9.2 ... Das Problem des Handlungsreisenden ... 251

       9.3 ... Merkhilfen für Telefonnummern ... 257

       9.4 ... Anwendungen im Alltag ... 260

       9.5 ... Übungsaufgaben ... 261



  Anhang ... 263


       A ... Glossar ... 265

       B ... Weitere Ressourcen ... 271

       C ... Eine kurze Einführung in Type-Hints ... 277



  Index ... 285

Leseproben

1    Kleine Aufgaben

Zu Beginn betrachten wir einige einfache Aufgaben, die sich mit einigen relativ kurzen Funktionen lösen lassen. Auch wenn diese Aufgaben klein sind, erlauben sie uns doch, einige interessante Problemlösungstechniken zu erarbeiten. Betrachten Sie diese Aufgaben als gutes Aufwärmtraining.

1.1    Die Fibonacci-Folge

Die Fibonacci-Folge ist eine Folge von Zahlen, in der jede Zahl außer der ersten und der zweiten die Summe ihrer beiden Vorgänger ist:

0, 1, 1, 2, 3, 5, 8, 13, 21...

Der Wert der ersten Fibonacci-Zahl in der Folge ist 0. Der Wert der vierten Fibonacci-Zahl ist 2. Daraus folgt, dass man folgende Formel verwenden kann, um den Wert jeder beliebigen Fibonacci-Zahl n in der Reihe zu erhalten:

fib(n) = fib(n - 1) + fib(n - 2)

1.1.1    Ein erster rekursiver Ansatz

Die obige Formel zur Berechnung einer Zahl in der Fibonacci-Folge (grafisch dargestellt in Abbildung 1.1) ist eine Form von Pseudocode, die sich trivial in eine rekursive Python-Funktion übertragen lässt. (Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft.) Diese mechanische Übertragung dient als unser erster Ansatz, eine Funktion zu schreiben, die den angegebenen Wert der Fibonacci-Folge zurückliefert.

def fib1(n: int) -> int:
return fib1(n - 1) + fib1(n - 2)

Listing 1.1    fib1.py

Versuchen wir, diese Funktion auszuführen, indem wir sie mit einem Wert aufrufen.

if __name__ == "__main__":
print(fib1(5))

Listing 1.2    fib1.py (Fortsetzung)

Abbildung 1.1    Die Höhe jedes Strichmännchens ist die Summe der Höhe der beiden vorherigen Strichmännchen.

Oje! Wenn wir versuchen, fib1.py auszuführen, erzeugen wir einen Fehler:

RecursionError: maximum recursion depth exceeded

Das Problem ist, dass fib1() immer weiterlaufen wird, ohne je ein Ergebnis zurückzuliefern. Jeder Aufruf von fib1() erzeugt zwei weitere Aufrufe von fib1(), ohne dass ein Ende in Sicht wäre. Einen solchen Umstand nennt man Endlosrekursion (siehe Abbildung 1.2), das rekursive Gegenstück zu einer Endlosschleife.

Abbildung 1.2    Die rekursive Funktion »fib(n)« ruft sich selbst mit den Argumenten »n–2« und »n–1« auf.

1.1.2    Abbruchbedingungen verwenden

Wie Sie merken, gibt es keine Anzeichen aus Ihrer Python-Umgebung, dass irgendetwas mit fib1() nicht stimmt, solange Sie die Funktion nicht ausführen. Es ist Aufgabe des Programmierers, Endlosrekursionen zu vermeiden, nicht diejenige des Compilers oder Interpreters. Der Grund für die Endlosrekursion ist, dass wir nie eine Abbruchbedingung festgelegt haben. In einer rekursiven Funktion dient eine Abbruchbedingung als Haltepunkt.

Im Fall der Fibonacci-Funktion haben wir natürliche Abbruchbedingungen in Form der ersten beiden Folgewerte 0 und 1. Weder 0 noch 1 ist die Summe der vorigen beiden Zahlen in der Folge. Stattdessen handelt es sich um die speziellen ersten beiden Werte. Versuchen wir, sie als Abbruchbedingungen festzulegen.

def fib2(n: int) -> int:
if n < 2: # Abbruchbedingung
return n
return fib2(n - 2) + fib2(n - 1) # Rekursionsbedingung

Listing 1.3    fib2.py

Hinweis

Die fib2()-Version der Fibonacci-Funktion gibt 0 als nullte Zahl zurück (fib2(0)) und nicht etwa als erste Zahl, wie in unserem ursprünglichen Entwurf. In einem Programmierkontext ergibt das durchaus Sinn, weil wir es gewohnt sind, Folgen mit einem nullten Element zu beginnen.

fib2() kann erfolgreich aufgerufen werden und liefert korrekte Ergebnisse zurück. Versuchen Sie, sie mit einigen kleinen Werten aufzurufen.

if __name__ == "__main__":
print(fib2(5))
print(fib2(10))

Listing 1.4    fib2.py (Fortsetzung)

Versuchen Sie nicht, fib2(50) aufzurufen. Die Ausführung wird niemals enden! Warum? Jeder Aufruf von fib2() erzeugt zwei weitere Aufrufe von fib2() durch die rekursiven Aufrufe fib2(n - 1) und fib2(n - 2) (siehe Abbildung 1.3). Der Aufrufbaum wächst mit anderen Worten exponentiell. Ein Aufruf von fib2(4) erzeugt beispielsweise diese Gesamtmenge von Aufrufen:

fib2(4) -> fib2(3), fib2(2)
fib2(3) -> fib2(2), fib2(1)
fib2(2) -> fib2(1), fib2(0)
fib2(2) -> fib2(1), fib2(0)
fib2(1) -> 1
fib2(1) -> 1
fib2(1) -> 1
fib2(0) -> 0
fib2(0) -> 0

Abbildung 1.3    Jeder nicht in die Abbruchbedingung fallende Aufruf von »fib2()« erzeugt zwei weitere Aufrufe von »fib2()«.

Wenn Sie sie zählen (und wie Sie sehen werden, wenn Sie ein paar Ausgabebefehle hinzufügen), entstehen 9 Aufrufe von fib2(), um lediglich das vierte Element zu berechnen! Es wird schlimmer. 15 Aufrufe werden benötigt, um Element 5 zu berechnen, 177 Aufrufe, um Element 10 zu berechnen, und 21.891 Aufrufe für Element 20. Das können wir besser machen.

1.1.3    Memoisation eilt zu Hilfe

Memoisation ist ein Verfahren, bei dem Sie die Ergebnisse von Berechnungen speichern, sobald sie abgeschlossen sind, damit Sie sie nachschlagen können, wenn Sie sie erneut brauchen, statt sie ein zweites (oder millionstes) Mal berechnen zu müssen (siehe Abbildung 1.4).[ 4 ]

Abbildung 1.4    Die menschliche Memoisations-Maschine

Schreiben wir eine neue Version der Fibonacci-Funktion, die ein Python-Dictionary zum Zweck der Memoisation verwendet.

from typing import Dict
memo: Dict[int, int] = {0: 0, 1: 1} # Unsere Abbruchbedingungen
def fib3(n: int) -> int:
if n not in memo:
memo[n] = fib3(n - 1) + fib3(n - 2) # Memoisation
return memo[n]

Listing 1.5    fib3.py

Sie können fib3(50) jetzt sicher aufrufen.

if __name__ == "__main__":
print(fib3(5))
print(fib3(50))

Listing 1.6    fib3.py (Fortsetzung)

Ein Aufruf von fib3(20) erzeugt nur 39 Aufrufe von fib3() im Gegensatz zu den 21.891 Aufrufen von fib2(), die aus dem Aufruf von fib2(20) entstehen. memo wird mit den früheren Abbruchbedingungen 0 und 1 vorausgefüllt, was fib3() vor der Komplexität einer weiteren if-Anweisung bewahrt.

1.1.4    Automatische Memoisation

fib3() kann noch weiter vereinfacht werden. Python enthält einen eingebauten Decorator für die automatische Memoisation jeder beliebigen Funktion. In fib4() wird der Decorator @functools.lru_cache() mit genau demselben Code wie in fib2() verwendet. Jedes Mal, wenn fib4() mit einem bisher unbekannten Argument ausgeführt wird, sorgt der Decorator dafür, dass der Rückgabewert gecacht wird. Bei weiteren Aufrufen von fib4() mit demselben Argument wird der frühere Rückgabewert von fib4() aus dem Cache gelesen und zurückgegeben.

from functools import lru_cache
@lru_cache(maxsize=None)
def fib4(n: int) -> int: # Dieselbe Definition wie fib2()
if n < 2: # Abbruchbedingung
return n
return fib4(n - 2) + fib4(n - 1) #...

Über Autor(innen)

Kopec, David
David Kopec ist Hochschuldozent für Informatik und Innovation am Champlain College in Burlington, Vermont. Er ist der Autor von “Dart for Absolute Beginners” (Apress, 2014) und “Classic Computer Science Problems in Swift” (Manning, 2018).