Eines unserer interessantesten Python-Bücher im letzten Jahr war Classic Computer Science Problems in Python von David Kopec.
Für diejenigen, die noch keine Zeit hatten, sich mit diesem Buch vertraut zu machen, bieten wir seine Rezension an, die gemäß der Originalausgabe im Oktober 2019 verfasst wurde. Sie können sich auch eine kleine Diskussion über Reddit ansehen . Außerdem kann jeder seine Meinung zum zusätzlichen Druck äußern - dazu gibt es am Ende des Artikels eine Stimmabgabe.
Das Buch "Klassische Probleme der Informatik in Python" von David Kopec hat mir sehr gut gefallen. Es werden wirklich viele verschiedene Probleme angesprochen, detaillierte Informationen, auf die ich vorher noch nicht gestoßen bin. Nur einige Beispiele: Neuronale Netze, Probleme mit der Zufriedenheit mit Einschränkungen, genetische Algorithmen, Minimax-Algorithmus. Im Gegensatz zu vielen anderen Büchern über Algorithmen und Programmierprobleme zeigt dieses Buch vollständige (aber kleine) Programme, die Sie leicht selbst erkunden können.
Ich lerne gerne Algorithmen. Ich habe an dem Buch " Programmer's Career " gearbeitet und mehrere MOOC-Kurse besucht, insbesondere " Design and Analysis of Algorithms " vom Professor Tim Rafgarden . Dennoch gab es in Kopecs Buch auch solche Algorithmen, deren Erwähnung ich bisher noch nicht gesehen habe.
KAPITEL Ich mochte am meisten
Neuronale Netze . Mein Lieblingsabschnitt im Buch handelt von neuronalen Netzen. Der Autor beschreibt die Schaffung eines vollwertigen neuronalen Netzwerks. In der Zwischenzeit beschreibt er, wie alle seine Teile funktionieren - im Allgemeinen und im Besonderen. Beschreibt, wie Neuronen und Schichten angeordnet sind, wie die Aktivierungsfunktion funktioniert, wie die Rückausbreitung während des Lernens verwendet wird und wie Gewichte korrigiert werden.
Schließlich wird das neuronale Netzwerk als Beispiel für Fischers Iris verwendet. Dies ist ein klassischer Datensatz, der in den 1930er Jahren mit 150 Exemplaren von Blumen verschiedener Irisarten (jeweils 50 Exemplare) zusammengestellt wurde. Jede Probe wird von vier numerischen Werten begleitet: der Länge des äußeren Blütenhüllens; die Breite des äußeren Blütenhüllens; die Länge des inneren Blütenhüllens; die Breite des inneren Blütenhüllens. Die Werte werden zuerst normalisiert. Dann wird ein dreischichtiges Netz erstellt. Es gibt vier Neuronen in der Eingabeschicht (eines für jede Kategorie von Eingabewerten aus der Probe), in der verborgenen Schicht gibt es sechs Neuronen und in der Ausgabeschicht gibt es drei Neuronen (eines für jeden betrachteten Iristyp).
140 von 150 Proben wurden zufällig ausgewählt, die dann zum Trainieren des Netzwerks verwendet wurden. Das Training wird über 140 Proben in 50 Iterationen durchgeführt. Das Netzwerk wird dann verwendet, um vorherzusagen, zu welcher der drei Irisarten die verbleibenden 10 Proben gehören. In den meisten Fällen identifiziert das Netzwerk mindestens 8 von 10 Beispielen korrekt und ziemlich oft - und alle 10.
Ich mochte diese Erfahrung wirklich: ein ganzes neuronales Netzwerk von Grund auf neu zu programmieren, ohne auf Bibliotheken für maschinelles Lernen zurückzugreifen. Ich habe eine Weile mit diesem Programm experimentiert (der gesamte Code für das Buch ist auf GitHub veröffentlicht). Zum Beispiel habe ich einen Ausdruck aller Gewichte in allen Neuronen gedruckt, nachdem das Netzwerk vollständig trainiert wurde. Ich wollte sehen, ob es eine Ähnlichkeit zwischen den Gewichten zwischen verschiedenen Läufen geben würde. Es stellte sich heraus, dass die Gewichte von Lauf zu Lauf auffallend unterschiedlich waren, obwohl der Vorhersageerfolg in allen Fällen ähnlich blieb. Vielleicht ist dies eine elementare Wahrheit, aber ich war sehr daran interessiert, dies selbst zu sehen.
Widersprüchliche Suche... In diesem Kapitel werden wir in den Minimax-Algorithmus eingeführt. Er findet den besten Zug in einem Nullsummenspiel mit zwei Gegnern. Die Idee ist, mögliche Bewegungen zu analysieren und im Namen des einen oder anderen Gegners zu sprechen. Jeder Gegner reagiert auf den letzten Zug, bis das Spiel beendet ist (oder die maximale Rekursionstiefe erreicht ist). Im ersten Beispiel aus dem Buch spielt die KI Tic-Tac-Toe. In diesem Fall kann die gesamte Bewegungssequenz vollständig analysiert werden, da die Größe des Spielfelds nur 3 mal 3 Zellen beträgt.
Wie in den anderen Kapiteln wird hier zunächst die allgemeine Struktur entwickelt, die dann in Bezug auf komplexe Fälle diskutiert wird. Nach dem Beispiel mit Tic-Tac-Toe ist das Spiel " Vier in einer Reihe . " In diesem Fall ist die Auswertung von Zügen viel schwieriger als in "Tic-Tac-Toe", daher ist hier die Tiefensuche auf drei Züge beschränkt. Ich habe mich viel diesem Kapitel zugewandt, da ich noch nie zuvor eine Beschreibung des Minimax-Algorithmus gesehen hatte.
Zufriedenheitsaufgaben... Hier wird auch ein allgemeiner Rahmen entwickelt, der dann zur Lösung mehrerer Probleme verwendet wird. Das Herzstück dieser Struktur ist das rekursive Backtracking. Das erste in diesem Kapitel gelöste Problem ist das Ausmalen der Karte von Australien. Ist es möglich, mit nur drei Farben auszukommen und die Karte so zu färben, dass benachbarte Bereiche auf beiden Seiten einer Grenze zwischen Regionen unterschiedliche Farben haben? (Antwort: ja). Die zweite Aufgabe besteht darin, acht Königinnen auf das Schachbrett zu legen und sicherzustellen, dass keine Königin von einer anderen angegriffen wird. Die dritte Aufgabe besteht darin, die Wortliste in einem Raster so anzuordnen, dass ein Quadrat für die Suche nach Wörtern entsteht. Schließlich wird die Struktur verwendet, um das klassische krypto-arithmetische Puzzle SEND + MORE = MONEY zu lösen. Ziel ist es herauszufinden, welcher Ziffer jeder Buchstabe entspricht, damit die resultierende arithmetische Gleichheit korrekt ist.
Ich mochte dieses Kapitel, weil es viele sehr unterschiedliche Beispiele enthält und weil ich diesen Ansatz bisher nicht verwendet habe, um solche Probleme (zumindest systematisch) zu lösen.
Genetische Algorithmen . Bevor ich dieses Kapitel las, hatte ich nur eine sehr allgemeine Vorstellung davon, wie genetische Algorithmen funktionieren. Der Code für dieses Kapitel zeigt eine Chromosomenklasse, die durch zufällig ausgewählte Gene instanziiert wird. Ein Chromosom kann seine eigene Anpassungsfähigkeit an die Umgebung beurteilen und Kreuzungen (eine Kombination von sich selbst mit einem anderen Chromosom des gleichen Typs) implementieren sowie mutieren (kleine, völlig zufällige Änderungen an sich selbst vornehmen).
Der Algorithmus beginnt mit einer zufälligen Grundgesamtheit. In jeder Generation dieser Population prüft der Algorithmus (unter Verwendung der Fitnessfunktion), ob es eine ausreichend gute Lösung gibt (Fitness liegt über einem bestimmten Schwellenwert). Wenn es keine solche Lösung gibt, wird durch wiederholte Operationen des Kreuzens von Individuenpaaren eine neue Generation geschaffen (je höher die Fitness jedes einzelnen Individuums ist, desto wahrscheinlicher ist es, dass diese Individuen in Aktion treten). Ferner werden mehrere Individuen für Mutationen ausgewählt. Jetzt führen diese neuen Individuen zu einer neuen Population und erneut werden ihre Fitnessfunktionen getestet. Der Zyklus wiederholt sich für eine bestimmte Anzahl von Generationen.
Die folgenden Probleme werden als Beispiele betrachtet: Maximieren eines mathematischen Ausdrucks, das oben erwähnte Puzzle "SENDEN + MEHR = GELD" und Ordnen der Elemente in einer Liste, um die Größe der Liste beim Komprimieren zu minimieren. Das Verdienst dieses Kapitels ist, wie bei vielen anderen, dass alle Konzepte im Kontext einer kompakten und dennoch vollständigen Lösung gezeigt werden.
Suche... Die Algorithmen in diesem Kapitel waren für mich nicht neu (mit Ausnahme von A *), aber das Kapitel ist dank der darin enthaltenen Beispiele immer noch interessant. Der Autor demonstriert die Prinzipien der Breitensuche und der Tiefensuche am Beispiel des Verlassens eines Labyrinths. Labyrinthe sind gewöhnliche Gitter mit jeweils 9 mal 9 Zellen, in denen Hindernisse zufällig platziert werden. Wird auf dem Bildschirm nur mit ASCII-Zeichen angezeigt. Mit Hilfe von Algorithmen wird ein Pfad durch das Gitter gefunden, der diagonal verläuft und gleichzeitig Hindernissen ausweicht. Der so gefundene Weg wird auch durch das Labyrinth gezogen.
Sie können diese Programme einfach ändern, um zu testen, wie die Algorithmen in verschiedenen Szenarien funktionieren. Nachdem er sich mit Breadth First Search vertraut gemacht hat, spricht der Autor über A *. Der Unterschied besteht darin, dass die Pfade mit einer Heuristik (euklidischer Abstand) gezeichnet werden, die als Richtlinie verwendet wird und Ihnen sagt, welche Pfade zuerst gezeichnet werden sollen. Das letzte Beispiel in diesem Kapitel verwendet eine Suchfunktion, mit der Sie drei Missionare und drei Oger in einem Kanu über einen Fluss bringen können. Die Einschränkung besteht darin, dass die Anzahl der Kannibalen die Anzahl der Missionare weder am Ufer noch im Boot überschreiten darf, da sonst die Kannibalen die Missionare fressen. Ich denke, dies ist eine sehr clevere und interessante Anwendung des Suchalgorithmus.
ANDERE KAPITEL
Andere Kapitel enthalten Algorithmen, mit denen ich bereits vertraut bin.
Einfache Aufgaben (erstes Kapitel). Das erste Kapitel enthält viele kleine Beispiele. Zunächst werden die verschiedenen Methoden zur Berechnung von Fibonacci-Zahlen beschrieben (insbesondere rekursiv, mit Memoisierung, iterativ und mit einem Python-Generator). Im nächsten Abschnitt wird die Bitmanipulation für Komprimierungs- und XOR-Chiffren erläutert. Schließlich benötigen wir in diesem Kapitel eine Rekursion, um das Problem der Hanoi-Türme zu lösen.
Grafikprobleme . In Kapitel 4 werden Diagrammalgorithmen zum Ermitteln des kürzesten Pfads und des minimalen Spannbaums am Beispiel einer Karte der Vereinigten Staaten erläutert. Der Dijkstra-Algorithmus wird ebenfalls berücksichtigt.
K-Means Clustering... In diesem Kapitel erfahren Sie, wie Sie Datenpunkte basierend auf dem relativen Abstand von jedem Punkt zur Mitte des Clusters in eine vorgegebene Anzahl von Clustern gruppieren. Die Beispiele in diesem Kapitel waren für mich nicht so interessant wie die Beispiele in den anderen Kapiteln.
Andere Aufgaben . Das letzte Kapitel befasst sich mit dem Rucksackproblem, dem Problem des Handlungsreisenden und der Mnemonik von Telefonnummern.
WAS WÜRDEN SIE BEFESTIGEN?
Alle Programme verwenden Pythons Typhinweise. Ich habe eine ambivalente Einstellung zu solchen Tipps. Einerseits tragen Typen zu einem besseren Verständnis des Programms bei. Andererseits bin ich es nicht gewohnt, sie in Python zu sehen, und manchmal musste ich diese Hinweise zuerst verstehen, bevor ich anfing, die Logik des Programms zu verstehen.
Wenn Sie sich über einen Abschnitt beschweren möchten, dann über den, der über dynamische Programmierung spricht. Meiner Meinung nach fehlt es an Vollständigkeit. Dynamische Programmierung ist eine schwierige Sache, und wenn Sie sie in realen Lösungen verwenden möchten, benötigen Sie zusätzliche Beispiele zu diesem Thema.
FAZIT
Die Hauptgründe, warum mir dieses Buch wirklich gefallen hat, sind die Breite der betrachteten Algorithmen, vollwertige (gleichzeitig kompakte) Lösungen, die leicht selbst zu untersuchen sind, sowie interessante Beispiele, die zur Veranschaulichung der Algorithmen ausgewählt wurden.