Ich wurde beauftragt, eine Bibliothek mit Büchern über Algorithmen für unser kleines Unternehmen (ca. 15 Personen) aufzubauen. Das Budget beträgt mehr als 5.000, aber sicherlich weniger als 10.000, sodass ich eine ganze Reihe von Büchern kaufen kann. Alle Leute hier haben mindestens einen Bachelor-Abschluss in CS oder einem eng verwandten Bereich. Während ich also ein grundlegendes Lehrbuch wie Cormen bekomme, interessiere ich mich mehr für gute Bücher zu fortgeschrittenen Themen. (Ich werde übrigens Knuths 4 Bände bekommen.)
Einige Themenlisten wären:
Sortieralgorithmen
Graph-Algorithmen
String-Algorithmen
Randomisierte Algorithmen
Verteilte Algorithmen
Kombinatorische Algorithmen
etc.
Im Wesentlichen suche ich nach guten Empfehlungen für Bücher zu wichtigen Themen innerhalb von CS im Zusammenhang mit Algorithmen und Datenstrukturen. Insbesondere Dinge, die über das hinausgehen, was normalerweise in Algorithmus- und Datenstrukturklassen als Teil eines Bachelor-Abschlusses an einer guten Schule behandelt wird. Ich weiß, dass die Frage ziemlich verschwommen ist, da ich nach allgemein nützlichem Material suche. Die Software, die wir entwickeln, besteht hauptsächlich aus Dingen auf Systemebene, die große Datenmengen verarbeiten.
Das Ideal wäre auch, alles zu finden, was die neuesten coolen Datenstrukturen und Algorithmen abdeckt, von denen die meisten Menschen vielleicht noch nichts gehört haben.
EDIT: Hier sind einige vorläufige Bücher, von denen ich denke, dass ich sie bekommen sollte:
Einführung in Algorithmen von Cormen et al.
Algorithmus Design von Kleinberg, Tardos
Die Kunst der Computerprogrammierung Band 1-4 von Knuth
Approximationsalgorithmen von Vazirani
Das Design von Approximationsalgorithmen von Williamson, Shmoys
Randomisierte Algorithmen von Motwani, Raghavan
Einführung in die Theorie der Berechnung von Sipser
Computerkomplexität von Arora, Barak
Computer und Intraktabilität von Garey und Johnson
Kombinatorische Optimierung von Schrijver
Einige andere Bücher, die meine Kollegen wollten und die sich mit Techniken und Algorithmen für das Sprachdesign, Compiler und formale Methoden befassen, sind:
Typen und Programmiersprachen von Pierce
Prinzipien der Modellprüfung von Baier, Katoen
Compiler: Prinzipien, Techniken und Werkzeuge von Aho, Lam, Sethi, Ullman
Das Compiler Design Handbook: Optimierungen und Maschinencodegenerierung, 2. Auflage von Srikant, Shankar
Das Garbage Collection Handbook: Die Kunst der automatischen Speicherverwaltung von Jones, Hosking, Moss
Antworten:
Ich habe (fast) nicht genug Bücher gelesen, um sie im Wert von 5000 Dollar zu nennen. Daher werde ich einige Literaturgruppen vorschlagen, die Sie behandeln sollten, und Sie auf ausgewählte Vertreter hinweisen. Ich kann nicht behaupten, die meisten Bücher selbst vollständig gelesen zu haben, daher muss ich mich hauptsächlich auf Beschreibungen, flüchtige Eindrücke und den Ruf verlassen. Ich habe die meisten von ihnen untersucht oder mit ihnen gearbeitet oder sie von Experten empfehlen lassen.
Ich gehe davon aus, dass Sie möchten, dass Ihre Mitarbeiter lernen, was getan werden kann und wie es geht, anstatt zu lernen, was sie nicht tun können. Insbesondere werde ich Bücher über Berechenbarkeit und Komplexitätstheorie als solche weglassen; Ich gehe davon aus, dass Ihre Mitarbeiter die relevanten Botschaften aus ihrer Grundausbildung entfernt haben.
Die Grundlagen
Auch wenn Ihre Mitarbeiter sie irgendwann gelernt haben, sollten Sie von ihnen erwarten, dass sie die Grundlagen nachschlagen. Da Quellen wie Wikipedia häufig minderwertig oder völlig falsch sind, möchten Sie ihnen die richtigen Referenztexte geben.
Beliebte Optionen sind
Sehr breite Einführung, die viele elementare Algorithmen und Datenstrukturen sowie grundlegende Analysetechniken abdeckt. Ein Standardtext, der häufig für Unterrichtszwecke verwendet wird und in der 3. Ausgabe verfügbar ist (daher sollten die meisten Fehler inzwischen behoben sein). Viele Übungen.
Ein weiterer Standardtext in seiner vierten Ausgabe. Weniger breit als Cormen, aber mit mehr Aufmerksamkeit für Implementierungsdetails. Viel Material online, einschließlich eines kostenlosen Kurses über Coursera . Viele Übungen.
Auch eine eher schlanke Auswahl an Themen, die jedoch unter Berücksichtigung der Didaktik präsentiert werden. Der Fokus liegt auf induktiven Strategien. Enthält viele Übungen und Lösungen (oder zumindest Hinweise) für einige. Eine gute sekundäre Referenz, wenn Sie das empfohlene Lehrbuch wegen seines ungewöhnlichen Stils nicht mögen.
Behandelt diskrete Mathematik als relevant für die Algorithmusanalyse. Selten in seinem Fokus auf Informatikbedürfnisse und Strenge. Sehr hohe Qualität. Viele Übungen mit Lösungen.
Grundlegende Techniken zur präzisen Analyse von Algorithmen. Geschrieben von den Pionieren des Feldes. Hat auch einen kostenlosen Online-Kurs .
Die Referenz für qualitativ hochwertige, auf niedriger Ebene präzise analysierte Algorithmen für eine ganze Reihe von Problemen. Dient auch als Referenz.
Erweiterte Umfragen
Classic und der Basisliteratur konzentrieren sich häufig auf das prozedurale Paradigma. Wenn Sie im funktionalen Paradigma arbeiten möchten, werden neue Techniken für effiziente Datenstrukturen benötigt. Dieses Buch bietet einen detaillierten Überblick über die Region.
Manchmal reichen die grundlegenden Techniken nicht aus. Dies ist eine Übersicht über erweiterte Datenstrukturen mit Code und vielen Referenzen.
Komplexitätstheorie sagt uns (als Praktiker), wir sollten uns nicht die Mühe machen, nach exakten und dennoch effizienten Algorithmen für viele natürliche Probleme zu suchen. Es gibt viele Techniken, um diese Probleme praktisch zu lösen. Dieser Text zeigt Ihnen, wie.
Fachliteratur
Sollten Sie jemals einen Compiler erstellen oder daran basteln müssen, ist dies der Standardtext in diesem Bereich.
Viele Probleme können als Netzwerkflussprobleme modelliert werden. Dieses Buch bietet Ihnen eine vollständige Abdeckung des Feldes.
Grafische Modelle sind ein wichtiges Werkzeug bei der probabilistischen Modellierung von Szenarien für maschinelles Lernen (unter anderem). Dies ist eine umfassende Übersicht über den Komplex. Es gibt einen kostenlosen Online-Kurs .
String-Matching ist eine immer wichtige Aufgabe im Umgang mit Daten. In diesem Buch werden die meisten (wenn nicht alle) relevanten Algorithmen für den Job aufgelistet, einschließlich allgemeiner Beschreibungen sowie Implementierungen.
Der tiefe mathematische Tauchgang nach "Eine Einführung in die Analyse von Algorithmen" derselben Autoren. Nicht für jedermann, aber Gold für Interessierte.
Sollten Sie jemals mit großen Mengen von String-Daten (insbesondere in biologischen Kontexten) zu tun haben, ist dies das erste Buch, da es einen Überblick über die relevanten Datenstrukturen und Algorithmen bietet.
Für den Praktizierenden
In der Praxis möchten Sie möglicherweise mehrere Computer verwenden, um große Probleme zu lösen. Dieses Buch bietet einen allgemeinen, beispielhaften Überblick über die entsprechenden Vorgehensweisen, dh das Organisieren und Verschieben von Daten und Computeragenten. Es werden auch Möglichkeiten zur Implementierung mit vorhandenen Tools beschrieben.
Wenn die theoretische Analyse zu schwierig oder zu grob ist, müssen Sie Experimente durchführen. Dies ist eine Einführung in das richtige Entwerfen von Experimenten mit Algorithmen.
Sie benötigen häufig domänenspezifische Sprachen und Tools, um sie zu analysieren. ANTLR ist ein ausgereifter und praktischer Compiler-Generator, und dieses Buch eignet sich am besten, um zu lernen, wie man es benutzt. Parr hat auch einige andere Bücher über DSLs, die einen Besuch wert sind.
Wenn Sie aktuelles Material wünschen, sollten Sie in Betracht ziehen, Ihren Mitarbeitern Zugang zu Zeitschriften und Konferenzberichten zu verschaffen, möglicherweise durch die Zusammenarbeit mit einer Universitätsbibliothek. Sie können sie auch tatsächlich an Konferenzen zu für sie relevanten Themen teilnehmen lassen. Ihre Firma.
Fragen Sie auch Ihre Leute. Lassen Sie sie selbst recherchieren (einschließlich kostenloser Muster oder Kopien im Internet oder in Bibliotheken), und sie teilen Ihnen mit, welche Bücher sie für ihre Arbeit als relevant erachten. Es hat keinen Sinn, Dinge zu kaufen, die niemand lesen wird.
quelle
Hier ist eine zufällige Sammlung von Büchern über fortgeschrittene Algorithmen, basierend auf dem, was ich als großartiges Buch über fortgeschrittene Algorithmen betrachte. Natürlich ist dies nur meine persönliche Meinung und es gibt viele andere gute Bücher.
Sie sollten auf jeden Fall das Kleinberg / Tardos-Buch in Betracht ziehen, das einfach ein großartiges Lehrbuch ist.
Sie sollten auch wissen, dass es zu bestimmten Themen "Handbücher" gibt, die einen enzyklopädischen Überblick über ein Feld geben (zum Beispiel das Handbuch für Computergeometrie). herausgegeben von JR Sack, J. Urrutia. Beachten Sie, dass diese Handbücher teuer sind. Wenn Sie sie kaufen, können Sie die 5k ausgeben.
quelle
Sie geben nicht an, worauf sich Ihr Unternehmen spezialisiert hat, daher ist es nicht einfach, mehr als allgemeine Empfehlungen abzugeben. Insgesamt finde ich die Liste, die Sie zusammengestellt haben, ziemlich gut und ich würde nichts daraus entfernen. Nur ein paar Ergänzungen und Kommentare:
1) Cormen ist ein Standardtext. Sedgewick ist ein weiterer Standardtext. Ich habe immer mehr aus Sedgewick herausgeholt, aber YMMV. Sie scheinen das Budget zu haben. Kaufen Sie beide.
2) Ich habe keine Kopie von "The Garbage Collection Handbook", aber ich habe eine gut durchdachte Kopie von Jones & Lins früherer Umfrage zur Garbage Collection. Wenn Sie beabsichtigen, eine automatisierte Speicherverwaltung durchzuführen, sollten Sie diese unbedingt kaufen.
3) Sie haben auch einige nützliche Bücher über Parsing und Automatentheorie, aber Ihnen fehlen die zwei Bücher (drei Bände), die ich am nützlichsten fand: die Parsing-Theorie von Sippu & Soisalon-Soisinen und die Parsing-Techniken von Dick Grune . ein praktischer Leitfaden . Der erste ist ein guter Überblick über die Theorie und der zweite ein umfassender Überblick über die Praxis. (Holen Sie sich auf jeden Fall auch das Drachenbuch. Aber ich wette, Sie werden am Ende mehr Grune verwenden.)
4) Für jede Bibliothek zu Datenstrukturen ist eine Kopie von Okasakis "Rein funktionalen Datenstrukturen" erforderlich. Ich glaube nicht, dass ich jemals ein so schlankes Buch mit so vielen interessanten Ideen gelesen habe.
5) Ich besitze keine Kopie von Maxime Crochemores "Algorithms on Strings", aber ich wünschte, ich hätte es getan. Sehr praktisch, viele nützliche Ideen.
Algorithmen in C ++ / Java / C (wählen Sie einen aus), Dritte Ausgabe von Robert Sedgewick. Zwei Bände. Addison-Wesley, 2001.
Das Garbage Collection Handbook von Richard Jones, Antony Hosking und Eliot Moss.
Parsing-Theorie von Seppo Sippu und Eljas Soisalon-Soininen. Zwei Bände: Vol. 1 Sprachen und Analyse; Vol. 2 Parsing von LR (k) und LL (k). Springer, 1988.
Parsing Techniques, A Practical Guide, Zweite Ausgabe von Dick Grune und Ceriel JH Jacobs. Springer, 2008.
Rein funktionale Datenstrukturen von Chris Okasaki. Cambridge, 1998.
Algorithmen für Saiten von Maxime Crochemore, Christophe Hancart, Thierry Lecroq. Cambridge, 2007.
quelle