Algorithmen in einer Kurzfassung, 2.

Vorwort zur zweiten Auflage

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

Ein Buch für eine neue Ausgabe zu überarbeiten, ist immer eine mühsame Aufgabe. Wir wollten sicherstellen, dass wir alle guten Eigenschaften der ersten Ausgabe, die 2009 erschienen ist, beibehalten, gleichzeitig aber einige Mängel beheben und zusätzliches Material hinzufügen. Wir halten uns weiterhin an die in der ersten Ausgabe beschriebenen Grundsätze:

• Verwende echten Code, nicht nur Pseudocode, um Algorithmen zu beschreiben

• Trenne den Algorithmus von dem zu lösenden Problem

• Gerade genug Mathematik einführen

• Mathematische Analyse empirisch unterstützen

Bei der Aktualisierung dieser zweiten Ausgabe haben wir die Länge unserer Textbeschreibungen reduziert und das Layout vereinfacht, um Platz für neue Algorithmen und zusätzliches Material zu schaffen. Wir glauben, dass wir weiterhin eine Nutshell-Perspektive auf einen wichtigen Bereich der Informatik bieten, der erhebliche Auswirkungen auf praktische Softwaresysteme hat.

Änderungen in der zweiten Ausgabe

Bei der Aktualisierung dieses Buches für die zweite Auflage haben wir uns an diese Grundsätze gehalten:

Neue Algorithmen auswählen

Nach der Veröffentlichung der ersten Ausgabe erhielten wir oft Kommentare wie "Warum wurde Merge Sort ausgelassen?" oder "Warum habt ihr die Fast Fourier Transform (FFT) nicht behandelt?" Es war unmöglich, alle diese Wünsche zu erfüllen, aber wir konnten die folgenden Algorithmen hinzufügen:

• Fortune's Algorithmus, um das Voronoi-Diagramm für eine Menge von Punkten zu berechnen ("Voronoi-Diagramm")

• Merge Sort, sowohl für interne Speicherdaten als auch für externe Dateien ("Merge Sort")

• Multithreaded Quicksort ("Parallele Algorithmen")

• AVL Balanced Binary Tree Implementierung ("Lösung")

• Ein neues Kapitel über räumliche Algorithmen(Kapitel 10) enthält R-Trees und Quadtrees

Insgesamt behandelt das Buch fast 40 wichtige Algorithmen.

Präsentation rationalisieren

Um Platz für das neue Material zu schaffen, haben wir fast jeden Aspekt der ersten Ausgabe überarbeitet. Wir haben das Templating zur Beschreibung der einzelnen Algorithmen vereinfacht und die begleitenden Beschreibungen reduziert.

Python-Implementierungen hinzufügen

Anstatt bestehende Algorithmen in Python neu zu implementieren, haben wir bewusst Python verwendet, um die meisten der neuen Algorithmen zu implementieren.

Code-Ressourcen verwalten

Der Code für die erste Ausgabe wurde als ZIP-Datei zur Verfügung gestellt. Inzwischen sind wir auf ein GitHub-Repository umgestiegen. Im Laufe der Jahre haben wir die Qualität des Codes und seiner Dokumentation verbessert. Wir haben eine Reihe von Blogeinträgen eingearbeitet, die nach der Veröffentlichung der ersten Ausgabe geschrieben wurden. Es gibt über 500 Unit-Testfälle und wir verwenden Code-Coverage-Tools, um eine Abdeckung von 99 % unseres Java-Codes sicherzustellen. Insgesamt besteht das Code-Repository aus über 110 KLOC.

Publikum

Wir möchten, dass dieses Buch dein primäres Nachschlagewerk ist, wenn du praktische Informationen darüber suchst, wie du einen Algorithmus implementieren oder verwenden kannst. Wir behandeln eine Reihe bestehender Algorithmen zur Lösung einer großen Anzahl von Problemen und halten uns an die folgenden Grundsätze:

• Bei der Beschreibung der einzelnen Algorithmen verwenden wir ein stilisiertes Template, um die Diskussion richtig einzurahmen und die wesentlichen Punkte jedes Algorithmus zu erklären

• Wir verwenden eine Vielzahl von Sprachen, um jeden Algorithmus zu implementieren (darunter C, C++, Java und Python). Auf diese Weise machen wir die Diskussion über Algorithmen konkret und sprechen in Sprachen, mit denen du bereits vertraut bist

• Wir beschreiben die erwartete Leistung der einzelnen Algorithmen und liefern empirische Belege für diese Behauptungen

Wir möchten, dass dieses Buch vor allem für Software-Praktiker, Programmierer und Designer nützlich ist. Um deine Ziele zu erreichen, brauchst du eine qualitativ hochwertige Quelle, die echte Lösungen für praktische Algorithmen erklärt, die du zur Lösung echter Probleme brauchst. Du weißt bereits, wie man in einer Vielzahl von Programmiersprachen programmiert. Du kennst die wichtigsten Datenstrukturen der Informatik, wie Arrays, verknüpfte Listen, Stapel, Warteschlangen, Hashtabellen, Binärbäume sowie ungerichtete und gerichtete Graphen. Du musst diese Datenstrukturen nicht selbst implementieren, da sie in der Regel von Codebibliotheken bereitgestellt werden.

Wir erwarten, dass du mit diesem Buch bewährte Lösungen kennen lernst, um Probleme effizient zu lösen. Du lernst einige fortgeschrittene Datenstrukturen und neue Wege kennen, um Standarddatenstrukturen anzuwenden und die Effizienz von Algorithmen zu verbessern. Deine Problemlösungsfähigkeiten werden sich verbessern, wenn du die Schlüsselentscheidungen für jeden Algorithmus erkennst, die für effiziente Lösungen sorgen.

In diesem Buch verwendete Konventionen

In diesem Buch werden die folgenden typografischen Konventionen verwendet:

Code

All code examples appear in this typeface.

This code is replicated directly from the code repository and reflects real code. All code listings are “pretty-printed” to highlight the appropriate syntax of the programming language.

Kursiv

Kennzeichnet Schlüsselbegriffe, die zur Beschreibung von Algorithmen und Datenstrukturen verwendet werden. Wird auch verwendet, wenn auf Variablen innerhalb einer Pseudocode-Beschreibung eines Beispiels verwiesen wird.

Constant width

Gibt den Namen von tatsächlichen Softwareelementen innerhalb einer Implementierung an, z. B. einer Java-Klasse, den Namen eines Arrays innerhalb einer C-Implementierung und Konstanten wie true oder false.

Wir zitieren im gesamten Buch zahlreiche Bücher, Artikel und Websites. Diese Zitate werden im Text in Klammern gesetzt, wie z. B. (Cormen et al., 2009), und jedes Kapitel schließt mit einer Auflistung der in diesem Kapitel verwendeten Referenzen. Wenn die Quellenangabe unmittelbar auf den Namen des Autors/der Autorin im Text folgt, wird der Name in der Quellenangabe nicht verdoppelt. So verweisen wir auf die Art of Computer Programming-Bücher von Donald Knuth (1998), indem wir einfach das Jahr in Klammern setzen.

Alle im Buch verwendeten URLs wurden im Januar 2016 überprüft, und wir haben versucht, nur URLs zu verwenden, die noch einige Zeit Bestand haben dürften. Kleine URLs wie http://www.oreilly.com werden direkt in den Text eingefügt, ansonsten erscheinen sie in Fußnoten und in den Referenzen am Ende eines Kapitels.

Code-Beispiele verwenden

Zusätzliches Material (Code-Beispiele, Übungen usw.) steht unter https://github.com/heineman/algorithms-nutshell-2ed zum Download bereit .

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. Wenn du eine CD-ROM mit Beispielen aus den O'Reilly-Büchern verkaufst oder verteilst, ist eine Genehmigung erforderlich. 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 eine Erlaubnis erforderlich.

Wir schätzen die Namensnennung, verlangen sie aber nicht. Eine Quellenangabe umfasst normalerweise den Titel, den Autor, den Verlag und die ISBN. Zum Beispiel:"Algorithms in a Nutshell, Second Edition by George T. Heineman, Gary Pollice, and Stanley Selkow. Copyright 2016 George Heineman, Gary Pollice und Stanley Selkow, 978-1-4919-4892-7."

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

Safari® Bücher Online

Hinweis

Safari Books Online ist eine digitale On-Demand-Bibliothek, die Experteninhalte in Buch- und Videoform von weltweit führenden Autoren aus den Bereichen Technologie und Wirtschaft liefert.

Technologieexperten, Softwareentwickler, Webdesigner sowie Geschäftsleute und Kreative nutzen Safari Books Online als Hauptressource für Recherchen, Problemlösungen, Lernen und Zertifizierungsschulungen.

Safari Books Online bietet eine Reihe von Plänen und Preisen für Unternehmen, Behörden, Bildungseinrichtungen und Privatpersonen.

Mitglieder haben Zugang zu Tausenden von Büchern, Schulungsvideos und Manuskripten von Verlagen wie O'Reilly Media, Prentice Hall Professional, Addison-Wesley Professional, Microsoft Press, Sams, Que, Peachpit Press, Focal Press, Cisco Press, John Wiley & Sons, Syngress, Morgan Kaufmann, IBM Redbooks, Packt, Adobe Press, FT Press, Apress, Manning, New Riders, McGraw-Hill, Jones & Bartlett, Course Technology und Hunderten mehr in einer vollständig durchsuchbaren Datenbank. Wenn du mehr über Safari Books Online erfahren möchtest, besuche uns bitte online.

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 http://bit.ly/algorithms_nutshell_2e aufrufen .

Wenn du Kommentare oder technische Fragen zu diesem Buch stellen möchtest, sende eine E-Mail an [e-mail].

Weitere Informationen zu unseren Büchern, Kursen, Konferenzen und Neuigkeiten findest du auf unserer Website unter http://www.oreilly.com.

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

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

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

Danksagungen

Wir möchten uns bei den Buchrezensenten für ihre Aufmerksamkeit und ihre Vorschläge bedanken, die die Darstellung verbessert und Fehler aus früheren Entwürfen beseitigt haben: Von der ersten Ausgabe: Alan Davidson, Scot Drysdale, Krzysztof Duleba, Gene Hughes, Murali Mani, Jeffrey Yasskin und Daniel Yoo. Für die zweite Ausgabe: Alan Solis, Robert P. J. Day und Scot Drysdale.

George Heineman möchte sich bei denjenigen bedanken, die ihm geholfen haben, seine Leidenschaft für Algorithmen zu wecken, darunter die Professoren Scot Drysdale (Dartmouth College) und Zvi Galil (Columbia University, jetzt Dean of Computing an der Georgia Tech). Wie immer dankt George seiner Frau Jennifer und seinen Kindern Nicholas (der jetzt angefangen hat, programmieren zu lernen) und Alexander (der gerne Origami-Kreationen aus den gedruckten Entwürfen dieser Ausgabe bastelt).

Gary Pollice möchte sich bei seiner Frau Vikki für 46 tolle Jahre bedanken. Er möchte sich auch bei der Informatikabteilung des WPI für ein tolles Umfeld und einen großartigen Job bedanken .

Stanley Selkow möchte sich bei seiner Frau Deb bedanken. Dieses Buch war ein weiterer Schritt auf ihrem langen gemeinsamen Weg.