Algorithmen lernen

Vorwort

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Für wen dieses Buch ist

Wenn du dieses Buch liest, gehe ich davon aus, dass du bereits über Kenntnisse in einer Programmiersprache wie Python verfügst. Wenn du noch nie programmiert hast, ermutige ich dich, zuerst eine Programmiersprache zu lernen und dann zurückzukommen! Ich verwende Python in diesem Buch, weil es für Programmierer und Nicht-Programmierer gleichermaßen zugänglich ist.

Algorithmen wurden entwickelt, um allgemeine Probleme zu lösen, die in Softwareanwendungen häufig auftreten. Wenn ich Studierenden Algorithmen beibringe, versuche ich, die Kluft zwischen dem Hintergrundwissen der Studierenden und den Algorithmenkonzepten, die ich unterrichte, zu überbrücken. Viele Lehrbücher haben sorgfältig geschriebene, aber immer zu kurze Erklärungen. Ohne einen Leitfaden, der erklärt, wie man sich in diesem Material zurechtfindet, sind die Schüler/innen oft nicht in der Lage, Algorithmen selbständig zu lernen.

In einem Absatz und in Abbildung P-1 zeige ich dir, welches Ziel ich mit dem Buch verfolge. Ich stelle eine Reihe von Datenstrukturen vor, die erklären, wie man Informationen mit primitiven Typen fester Größe organisiert, z. B. 32-Bit-Ganzzahlwerte oder 64-Bit-Gleitkommawerte. Einige Algorithmen, wie z. B. Binary Array Search, arbeiten direkt mit Datenstrukturen. Kompliziertere Algorithmen, insbesondere Graphenalgorithmen, stützen sich auf eine Reihe grundlegender abstrakter Datentypen, die ich je nach Bedarf einführe, wie z. B. Stapel oder Prioritätswarteschlangen. Diese Datentypen bieten grundlegende Operationen, die durch die Wahl der richtigen Datenstruktur effizient implementiert werden können. Am Ende dieses Buches wirst du verstehen, wie die verschiedenen Algorithmen ihre Leistung erreichen. Für diese Algorithmen zeige ich entweder vollständige Implementierungen in Python oder verweise dich auf Python-Pakete von Drittanbietern, die eine effiziente Implementierung bieten.

Wenn du dir die zugehörigen Code-Ressourcen ansiehst, die dem Buch beiliegen, wirst du sehen, dass es für jedes Kapitel eine book.py Python-Datei gibt, die ausgeführt werden kann, um alle Tabellen im Buch zu reproduzieren. Wie man in der Branche so schön sagt: "Es kommt darauf an, wie du dich entscheidest", aber die allgemeinen Trends werden immer wieder auftauchen.

Abbildung P-1. Zusammenfassung des technischen Inhalts des Buches

Am Ende jedes Kapitels im Buch findest du Aufgaben, in denen du dein neues Wissen unter Beweis stellen kannst. Ich möchte dich ermutigen, diese selbst auszuprobieren, bevor du dir meine Beispiellösungen ansiehst, die du im Code-Repository des Buches findest.

Über den Kodex

Der gesamte Code für dieses Buch ist im zugehörigen GitHub-Repository zu finden: http://github.com/heineman/LearningAlgorithms. Der Code ist mit Python 3.4 oder höher kompatibel. Wo es sinnvoll ist, halte ich mich an die bewährten Methoden von Python und verwende doppelte Unterstriche, wie __str()__und __len()__. In den Codebeispielen im Buch verwende ich eine Einrückung mit zwei Leerzeichen, um die Breite des Codes auf der gedruckten Seite zu verringern; das Code-Repository verwendet die Standard-Einrückung mit vier Leerzeichen. In einigen wenigen Codelisten formatiere ich den Code mit einer abgekürzten einzeiligen if Anweisung wie if j == lo: break.

Der Code verwendet drei extern verfügbare, quelloffene Python-Bibliotheken:

• NumPy Version 1.19.5

• SciPy Version 1.6.0

• NetworkX Version 2.5

NumPy und SciPy gehören zu den am häufigsten verwendeten Open-Source-Python-Bibliotheken und haben ein breites Publikum. Ich verwende diese Bibliotheken, um die empirische Laufzeitleistung zu analysieren. NetworkX bietet eine breite Palette effizienter Algorithmen für die Arbeit mit Graphen (siehe Kapitel 7) und eine gebrauchsfertige Implementierung von Graphendatentypen. Die Verwendung dieser Bibliotheken stellt sicher, dass ich das Rad nicht unnötig neu erfinden muss. Wenn du diese Bibliotheken nicht installiert hast, ist das kein Problem, denn ich biete Umgehungslösungen an.

Alle in diesem Buch vorgestellten Ergebnisse zur Zeitmessung verwenden das Modul timeit, das die wiederholte Ausführung eines Codeschnipsels verwendet. Oft wird das Code-Snippet mehrmals ausgeführt, um sicherzustellen, dass es genau gemessen werden kann. Nach einer Reihe von Durchläufen wird die minimale Zeit als Zeitleistung verwendet, nicht der Durchschnitt aller Durchläufe. Dies wird allgemein als die effektivste Methode angesehen, um eine genaue Zeitmessung zu erhalten, da der Durchschnitt einer Reihe von Durchläufen die Zeitmessungsergebnisse verfälschen kann, wenn einige Leistungsläufe von externen Faktoren beeinflusst werden, z. B. von anderen ausgeführten Aufgaben des Betriebssystems.

Wenn die Leistung eines Algorithmus stark von seiner Eingabe abhängt (wie bei Insertion Sort in Kapitel 5), gebe ich deutlich an, dass ich den Durchschnitt aller Leistungsläufe nehme.

Das Code-Repository enthält über 10.000 Zeilen Python-Code mit Skripten zur Ausführung aller Testfälle und zur Berechnung der im Buch vorgestellten Tabellen; viele der Diagramme und Grafiken können ebenfalls reproduziert werden. Der Code ist mit den Python-Docstring-Konventionen dokumentiert, und die Codeabdeckung liegt bei 95 % ( https://coverage.readthedocs.io).

Wenn du eine technische Frage oder ein Problem mit den Codebeispielen hast, sende bitte eine E-Mail an [e-mail].

Dieses Buch soll dir helfen, deine Arbeit zu erledigen. Wenn in diesem Buch Beispielcode angeboten wird, darfst du ihn in deinen Programmen und deiner Dokumentation verwenden. Du musst uns nicht um Erlaubnis fragen, es sei denn, du reproduzierst einen großen Teil des Codes. Wenn du zum Beispiel ein Programm schreibst, das mehrere Teile des Codes aus diesem Buch verwendet, brauchst du keine Erlaubnis. Der Verkauf oder die Verbreitung von Beispielen aus O'Reilly-Büchern erfordert jedoch eine Genehmigung. Die Beantwortung einer Frage mit einem Zitat aus diesem Buch und einem Beispielcode erfordert keine Genehmigung. Wenn du einen großen Teil des Beispielcodes aus diesem Buch in die Dokumentation deines Produkts aufnimmst, ist eineGenehmigung erforderlich.

Wir freuen uns über eine Namensnennung, verlangen sie aber in der Regel nicht. Eine Quellenangabe umfasst normalerweise den Titel, den Autor, den Verlag und die ISBN. Zum Beispiel: "Algorithmen lernen: A Programmer's Guide to Writing Better Code " von George T. Heineman (O'Reilly). Copyright 2021 George T. Heineman, 978-1-492-09106-6."

Wenn du der Meinung bist, dass die Verwendung von Code-Beispielen nicht unter die Fair-Use-Regelung oder die oben genannte Erlaubnis fällt, kannst du uns gerne unter [e-mail] kontaktieren .

In diesem Buch verwendete Konventionen

In diesem Buch werden die folgenden typografischen Konventionen verwendet:

Kursiv

Kennzeichnet neue Begriffe, URLs, Dateinamen, Dateierweiterungen und Punkte, die ich hervorheben möchte.

Constant width

Wird für Programmlistings und innerhalb von Absätzen verwendet, um auf Programmelemente wie Variablen- oder Funktionsnamen, Datentypen, Anweisungen und Schlüsselwörter hinzuweisen.

Tipp

Dieses Element, das durch ein Bild eines Ringelschwanzlemuren gekennzeichnet ist, ist ein Hinweis oder eine Andeutung. Ich verwende dieses Bild, weil Lemuren ein kombiniertes Gesichtsfeld von bis zu 280° haben, also ein breiteres Gesichtsfeld als anthropoide Primaten (wie der Mensch). Wenn du dieses Tipp-Symbol siehst, fordere ich dich buchstäblich auf, deine Augen weiter zu öffnen, um eine neue Tatsache oder Python-Fähigkeit zu lernen.

Hinweis

Dieses Element, das durch das Bild einer Krähe gekennzeichnet ist, steht für einen allgemeinen Hinweis. Zahlreiche Forscher haben festgestellt, dass Krähen intelligente, problemlösende Tiere sind - manche benutzen sogar Werkzeuge. Ich verwende diese Hinweise, um einen neuen Begriff zu definieren oder dich auf ein nützliches Konzept aufmerksam zu machen, das du verstehen solltest, bevor du zur nächsten Seite weitergehst.

Warnung

Dieses Element, das durch ein Bild eines Skorpions gekennzeichnet ist, weist auf eine Warnung oder Vorsicht hin. Wie im richtigen Leben gilt: Wenn du einen Skorpion siehst, bleib stehen und schau hin! Ich verwende den Skorpion, um auf die wichtigsten Herausforderungen aufmerksam zu machen, die du bei der Anwendung von Algorithmen bewältigen musst.

O'Reilly Online Learning

Hinweis

Seit mehr als 40 Jahren bietet O'Reilly Media Schulungen, Wissen und Einblicke in Technologie und Wirtschaft, um Unternehmen zum Erfolg zu verhelfen.

Unser einzigartiges Netzwerk von Experten und Innovatoren teilt sein Wissen und seine Erfahrung durch Bücher, Artikel und unsere Online-Lernplattform. Die Online-Lernplattform von O'Reilly bietet dir On-Demand-Zugang zu Live-Trainingskursen, ausführlichen Lernpfaden, interaktiven Programmierumgebungen und einer umfangreichen Text- und Videosammlung von O'Reilly und über 200 anderen Verlagen. Weitere Informationen erhältst du unter http://oreilly.com.

Wie du uns kontaktierst

Bitte richte Kommentare und Fragen zu diesem Buch an den Verlag:

• O'Reilly Media, Inc.
• 1005 Gravenstein Highway Nord
• Sebastopol, CA 95472
• 800-998-9938 (in den Vereinigten Staaten oder Kanada)
• 707-829-0515 (international oder lokal)
• 707-829-0104 (Fax)

Wir haben eine Webseite für dieses Buch, auf der wir Errata, Beispiele und zusätzliche Informationen auflisten. Du kannst diese Seite unter https://oreil.ly/learn-algorithms aufrufen .

Schreib eine E-Mail an [e-mail], um Kommentare oder technische Fragen zu diesem Buch zu stellen.

Neuigkeiten und Informationen über unsere Bücher und Kurse findest du unter http://oreilly.com.

Finde uns auf Facebook: http://facebook.com/oreilly

Folge uns auf Twitter: http://twitter.com/oreillymedia

Schau uns auf YouTube: http://youtube.com/oreillymedia

Danksagungen

Für mich ist das Studium der Algorithmen der beste Teil der Informatik. Danke, dass du mir die Möglichkeit gibst, dir dieses Material zu präsentieren. Ich möchte auch meiner Frau Jennifer für ihre Unterstützung bei einem weiteren Buchprojekt danken und meinen beiden Söhnen Nicholas und Alexander, die jetzt beide alt genug sind, um das Programmieren zu lernen.

Meine O'Reilly-Redakteurinnen und -Redakteure - Melissa Duffield, Sarah Grey, Beth Kelly und Virginia Wilson - haben das Buch verbessert, indem sie mir geholfen haben, die Konzepte und Erklärungen zu ordnen. Meine technischen Prüfer - Laura Helliwell, Charlie Lovering, Helen Scott, Stanley Selkow und Aura Velarde - haben mir geholfen, zahlreiche Unstimmigkeiten zu beseitigen und die Qualität der Algorithmusimplementierungen und Erklärungen zu verbessern.Für alle verbleibenden Mängel bin ichverantwortlich.