Hugendubel.info - Die B2B Online-Buchhandlung 

Merkliste
Die Merkliste ist leer.
Bitte warten - die Druckansicht der Seite wird vorbereitet.
Der Druckdialog öffnet sich, sobald die Seite vollständig geladen wurde.
Sollte die Druckvorschau unvollständig sein, bitte schliessen und "Erneut drucken" wählen.

Algorithmen in Python

E-BookEPUB0 - No protectionE-Book
292 Seiten
Deutsch
Rheinwerk Verlag GmbHerschienen am28.06.20201. Auflage
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).mehr
Verfügbare Formate
BuchKartoniert, Paperback
EUR29,90
E-BookEPUB0 - No protectionE-Book
EUR29,90

Produkt

KlappentextAlgorithmen 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).
Details
Weitere ISBN/GTIN9783836277495
ProduktartE-Book
EinbandartE-Book
FormatEPUB
Format Hinweis0 - No protection
Erscheinungsjahr2020
Erscheinungsdatum28.06.2020
Auflage1. Auflage
ReiheRheinwerk Computing
Seiten292 Seiten
SpracheDeutsch
Dateigrösse3551 Kbytes
Artikel-Nr.5212968
Rubriken
Genre9200

Inhalt/Kritik

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 ... 285mehr
Leseprobe

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

mehr