Algorithmen in Python (eBook)

32 Klassiker vom Damenproblem bis zu neuronalen Netzen

David Kopec (Autor)

eBook Download: EPUB

2020 | 1. Auflage
292 Seiten
Rheinwerk Computing (Verlag)
978-3-8362-7749-5 (ISBN)

Infos

Algorithmen gehören zum Rüstzeug guter Entwickler. In diesem Buch lernen Sie eine große Menge problemlösender Techniken kennen und erfahren, wie Sie diese in Anwendungen implementieren. Die Spannbreite reicht von einfachen Algorithmen zur Verschlüsselung und für die Suche bis hin zu genetischen Algorithmen, k-Means-Algorithmen und neuronalen Netzen. Unter den zu lösenden Aufgaben finden Sie sowohl Informatik-Klassiker wie das Damenproblem und das Flussüberquerungsrätsel als auch neue Aufgaben. Selbst wenn Ihnen einiges bekannt vorkommen wird, werden Sie am Ende sagen: 'Ach so macht man das!' Dass Python hier die Sprache der Wahl ist, schließt niemanden aus. Von diesem Programmiertraining profitieren Sie auch dann, wenn Sie sonst eher in Java, C++ oder einer anderen Sprache programmieren. Die gekonnte Auswahl der Beispiele und der flotte Schreibstil sorgen dafür, dass das Ganze nicht nur lehrreich, sondern auch unterhaltsam ist.

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

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).

Textauszug

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) #...

Produkt-Details

• Erscheint lt. Verlag: 28.6.2020
• Sprache: deutsch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• ISBN-10: 3-8362-7749-2 / 3836277492
• ISBN-13: 978-3-8362-7749-5 / 9783836277495