Książki z algorytmami na różne tematy

Zadanie polegało na zbudowaniu biblioteki książek na temat algorytmów dla naszej małej firmy (około 15 osób). Budżet wynosi ponad 5 000, ale na pewno mniej niż 10 000, więc mogę kupić sporo książek. Wszyscy tutaj mają co najmniej tytuł licencjata w dziedzinie CS lub ściśle powiązanej dziedzinie, więc chociaż dostanę podstawowy podręcznik, taki jak Cormen, bardziej interesują mnie dobre książki na zaawansowane tematy. (Zdobędę 4 tomy Knutha, BTW).

Oto lista tematów:

• Algorytmy sortowania

• Algorytmy grafowe

• Algorytmy łańcuchowe

• Algorytmy randomizowane

• Algorytmy rozproszone

• Algorytmy kombinatoryczne

• itp.

Zasadniczo szukam dobrych rekomendacji na książki dotyczące głównych tematów w CS związanych z algorytmami i strukturami danych. Szczególnie rzeczy, które wykraczają poza to, co zwykle obejmuje klasy algorytmów i struktur danych, w ramach studiów licencjackich w dobrej szkole. Wiem, że pytanie jest dość rozmyte, ponieważ szukam ogólnie przydatnego materiału. Oprogramowanie, które tworzymy, jest głównie na poziomie systemu i obsługuje duże ilości danych.

Ideałem byłoby również znalezienie czegokolwiek, co obejmowałoby całkiem nowe fajne struktury danych i algorytmy, o których większość ludzi może nie słyszeć.

EDYCJA: Oto kilka wstępnych książek, które moim zdaniem powinienem zdobyć:

• Wprowadzenie do algorytmów Cormena i in.

• Projektowanie algorytmów: Kleinberg, Tardos

• The Art of Computer Programming Vol 1-4 autorstwa Knuth

• Algorytmy aproksymacyjne autorstwa Vazirani

• Projektowanie algorytmów aproksymacyjnych autorstwa Williamsona, Shmoysa

• Randomized Algorytmy autorstwa Motwani, Raghavan

• Wprowadzenie do teorii obliczeń Sipsera

• Złożoność obliczeniowa Arora, Barak

• Komputery i nienaruszalność przez Garey i Johnson

• Optymalizacja kombinatoryczna Schrijvera

Kilka innych książek, których potrzebowali moi koledzy, dotyczących technik i algorytmów projektowania języka, kompilatorów i metod formalnych to:

• Rodzaje i języki programowania według Pierce

• Zasady sprawdzania modelu przez Baiera, Katoen

• Kompilatory: zasady, techniki i narzędzia autorstwa Aho, Lam, Sethi, Ullman

• Podręcznik projektowania kompilatorów: Optymalizacje i generowanie kodu maszynowego, wydanie drugie autorstwa Srikant, Shankar

• The Garbage Collection Handbook: The Art of Automatic Memory Memory - Jones, Hosking, Moss

Nie przeczytałem (prawie) wystarczającej liczby książek, aby wymienić je na 5000 dolarów. Dlatego zasugeruję kilka grup literatury, które powinieneś omówić, i skieruję cię do wybranych przedstawicieli. Nie mogę twierdzić, że sam przeczytałem większość książek, więc muszę polegać głównie na opisach, pobieżnym wrażeniu i reputacji. W pewnym stopniu przejrzałem większość z nich lub z nimi współpracowałem, lub poleciłem je ekspertom.

Zakładam, że chcesz, aby Twoi ludzie dowiedzieli się, co można zrobić i jak to zrobić, a nie dowiedzieć się, czego nie potrafią. W szczególności pominę książki o teorii obliczalności i złożoności jako takiej; Oczekuję, że wasz lud zabrał stosowne przesłania ze studiów licencjackich.

• Podstawy
  Chociaż Twoi ludzie nauczyli się ich w pewnym momencie, spodziewaj się, że sprawdzą podstawy. Ponieważ źródła takie jak Wikipedia są często niespełniające norm lub wręcz błędne, chcesz uzyskać odpowiednie teksty referencyjne.

  Popularne opcje obejmują

  • Wprowadzenie do algorytmów Cormen, Leiserson i in.
    Bardzo szerokie wprowadzenie obejmujące wiele podstawowych algorytmów i struktur danych, a także podstawowe techniki analizy. Standardowy tekst używany często do celów dydaktycznych i dostępny w trzecim wydaniu (więc większość błędów powinna już zostać usunięta). Dużo ćwiczeń.
  • Algorytmy Sedgewicka i Wayne'a
    Kolejny standardowy tekst w czwartym wydaniu. Mniej szeroki niż Cormen, ale z większą dbałością o szczegóły implementacji. Wiele materiałów online, w tym bezpłatny kurs na Coursera . Dużo ćwiczeń.
  • Wprowadzenie do algorytmów - twórcze podejście Udi Manbera
    Również dość wąski wybór tematów, ale przedstawiony z uwzględnieniem dydaktyki. Nacisk kładziony jest na strategie indukcyjne . Zawiera wiele ćwiczeń i rozwiązań (lub przynajmniej podpowiedzi) dla niektórych. Dobre wtórne odniesienie, jeśli nie lubisz zalecanego podręcznika ze względu na jego niezwykły styl.
  • Konkretna matematyka autorstwa Grahama, Knutha i Patashnika
    Obejmuje dyskretną matematykę stosowną do analizy algorytmów. Rzadko koncentruje się na potrzebach i rygorystyce informatyki . Bardzo wysoka jakość. Wiele ćwiczeń z rozwiązaniami.

• $O$

  • Wprowadzenie do analizy algorytmów Sedgewicka i Flajoleta
    Podstawowe techniki precyzyjnej analizy algorytmów. Napisane przez pionierów w tej dziedzinie. Posiada również bezpłatny kurs online .
  • Sztuka programowania przez Knuth odniesienia dla wysokiej jakości, niskim poziomie, dokładnie analizowane algorytmy dla całego szeregu problemów. Służy również jako odniesienie.
    

• Zaawansowane ankiety

  • Czysto funkcjonalne struktury danych Okasaki
    Classic i literatura podstawowa często koncentrują się na paradygmacie proceduralnym. Jeśli chcesz pracować w paradygmacie funkcjonalnym, potrzebne są nowe techniki wydajnych struktur danych. Ta książka jest szczegółowym przeglądem tego obszaru.
  • Zaawansowane struktury danych według mosiądzu
    Czasami podstawowe techniki nie są wystarczające. To jest przegląd zaawansowanych struktur danych, z kodem i wieloma referencjami.
  • Algorytmika trudnych problemów według Hromkoviča
    Teoria złożoności mówi nam (jako praktykom), że nie powinniśmy zawracać sobie głowy szukaniem dokładnych, ale skutecznych algorytmów dla wielu naturalnych problemów. Istnieje wiele technik praktycznego rozwiązywania tych problemów; ten tekst pokazuje, jak to zrobić.

• Literatura specjalistyczna

  • Kompilatory: zasady, techniki i narzędzia aka The Dragon Book autorstwa Aho i in.
    Jeśli kiedykolwiek będziesz potrzebować budować lub majstrować przy kompilatorze, jest to standardowy tekst w tym obszarze.
  • Przepływy sieci: teoria, algorytmy i aplikacje autorstwa Ahuji
    Wiele problemów można modelować jako problemy z przepływem sieci; ta książka daje pełny zasięg w terenie.
  • Probabilistyczne modele graficzne Kollera i Friedmana
    Modele graficzne są ważnym narzędziem w scenariuszach modelowania do uczenia maszynowego (między innymi) probabilistycznie. Jest to kompleksowy przegląd kompleksu. Istnieje powiązany bezpłatny kurs online .
  • Podręcznik dokładnych algorytmów dopasowywania ciągów według Charrasa i Lecrog Dopasowywanie
    ciągów jest bardzo ważnym zadaniem w przypadku danych. W tej książce wymieniono większość (jeśli nie wszystkie) odpowiednie algorytmy dla zadania, w tym opisy wysokiego poziomu oraz implementacje.
  • Kombinatoryka analityczna Sedgewicka i Flajoleta
    Głębokie nurkowanie matematyczne po „Wstępie do analizy algorytmów” tych samych autorów. Nie dla wszystkich, ale dla zainteresowanych złoto.
  • Algorytmy dotyczące ciągów, drzew i sekwencji według Gusfielda
    Jeśli kiedykolwiek będziesz musiał poradzić sobie z ogromną ilością danych ciągów (w szczególności w kontekście biologii), jest to książka, która zawiera przegląd odpowiednich struktur danych i algorytmów.

• Dla praktyka

  • Patterns for Parallel Programming autorstwa Mattson i in.
    W praktyce możesz skorzystać z wielu komputerów, aby poradzić sobie z dużymi problemami. Ta książka jest ogólnym, opartym na przykładach przeglądem sposobów na to, jak organizować i przenosić dane i agentów komputerowych. Omawia także sposoby ich wdrażania za pomocą istniejących narzędzi.
  • Przewodnik po algorytmach eksperymentalnych McGeocha
    Gdy analiza teoretyczna jest zbyt trudna lub zbyt gruba, musisz przeprowadzić eksperymenty. To jest wprowadzenie do prawidłowego projektowania eksperymentów na algorytmach.
  • Definitive ANTLR 4 Reference by Parr
    Często potrzebujesz specyficznych dla domeny języków i narzędzi do ich analizy. ANTLR jest dojrzałym i wygodnym generatorem kompilatorów i jest to książka, która najlepiej nadaje się do nauki korzystania z niego. Parr ma też kilka innych książek o DSL, które warto sprawdzić.

Jeśli chcesz mieć najświeższe materiały, powinieneś rozważyć zapewnienie swoim ludziom dostępu do czasopism i materiałów konferencyjnych, być może poprzez współpracę z biblioteką uniwersytecką. Możesz także pozwolić im uczestniczyć w konferencjach dotyczących odpowiednich dla nich tematów. Twoja firma.

Zastanów się też, czy nie zapytać swoich ludzi. Poproś, aby przeprowadzili własne badania (w tym bezpłatne próbki lub kopie w Internecie lub bibliotekach), a powiedzą ci, które książki uważają za istotne dla ich pracy. Nie ma sensu kupować rzeczy, których nikt nie przeczyta.

Oto losowy zbiór książek o zaawansowanych algorytmach oparty na tym, co uważam za świetną książkę o zaawansowanych algorytmach. Oczywiście to tylko moja osobista opinia i jest wiele innych dobrych książek.

• Algorytmy aproksymacyjne Vijay V. Vazirani
• Projektowanie algorytmów aproksymacyjnych autorstwa Davida P. Williamsona, Davida B. Shmoysa
• Geometria obliczeniowa: wprowadzenie przez losowe algorytmy Ketana Mulmuleya
• Randomized Algorytmy autorstwa Rajeev Motwani, Prabhakar Raghavan
• Algorytmy na strunach, drzewach i sekwencjach autorstwa Dana Gusfielda
• Optymalizacja kombinatoryczna: William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver

zdecydowanie powinieneś rozważyć książkę Kleinberg / Tardos, która jest po prostu świetnym podręcznikiem.

Powinieneś także wiedzieć, że na niektóre tematy istnieją „podręczniki”, które dają encyklopedyczny przegląd danego pola (na przykład Podręcznik geometrii obliczeniowej). pod redakcją JR Sack, J. Urrutia. Zauważ, że te podręczniki są drogie. Kupując je, możesz pomóc wydać 5 tys.

Nie określasz, w czym specjalizuje się Twoja firma, dlatego nie jest łatwo podać więcej niż ogólne rekomendacje. Ogólnie rzecz biorąc, uważam, że lista, którą stworzyłeś, jest całkiem dobra i nie usunę z niej niczego. Tylko kilka dodatków i komentarzy:

1) Cormen to standardowy tekst. Sedgewick to kolejny standardowy tekst. Zawsze czerpałem więcej z Sedgewick, ale z YMMV. Wygląda na to, że masz budżet. Kup oba.

2) Nie mam kopii „The Garbage Collection Handbook”, ale mam dobrze skopiowaną kopię wcześniejszej ankiety Jones & Lin na temat usuwania śmieci. Jeśli zamierzasz wykonać zautomatyzowane zarządzanie pamięcią, zdecydowanie powinieneś je kupić.

3) Masz także kilka przydatnych książek na temat analizy składniowej i teorii automatów, ale brakuje ci dwóch książek (trzech tomów), które uważam za najbardziej przydatne: Teoria analizowania Sippu i Soisalon-Soisinen oraz Techniki analizy Dicka Grune'a , praktyczny przewodnik . Pierwszy to świetny przegląd teorii, a drugi wyczerpujący przegląd praktyki. (Oczywiście, weź też książkę o smokach. Ale założę się, że będziesz więcej używał Grune.)

4) Każda biblioteka na strukturach danych wymaga kopii „Czysto funkcjonalnych struktur danych” Okasaki. Nie sądzę, żebym kiedykolwiek czytał tak szczupłą książkę z tyloma interesującymi pomysłami.

5) Nie posiadam kopii „Algorytmów na strunach” Maxime Crochemore, ale szkoda, że ​​nie. Bardzo praktyczne, wiele przydatnych pomysłów.

• Algorytmy w C ++ / Java / C (wybierz jeden), wydanie trzecie autorstwa Roberta Sedgewicka. Dwa tomy. Addison-Wesley, 2001.

• Podręcznik usuwania śmieci autorstwa Richarda Jonesa, Antony'ego Hoskinga i Eliota Mossa.

• Teoria parsowania autorstwa Seppo Sippu i Eljasa Soisalon-Soininena. Dwa tomy: tom. 1 Języki i parsowanie; Vol. 2 LR (k) i LL (k) parsowanie. Springer, 1988.

• Techniki parsowania, praktyczny przewodnik, drugie wydanie Dicka Grune i Ceriela JH Jacobsa. Springer, 2008.

• Czysto funkcjonalne struktury danych autorstwa Chrisa Okasaki. Cambridge, 1998.

• Algorytmy na strunach autorstwa Maxime Crochemore, Christophe Hancart, Thierry Lecroq. Cambridge, 2007.