Czy istnieje encyklopedia algorytmów? [Zamknięte]

34

Czy istnieje encyklopedia algorytmów podobnych stylem do Handbook of Mathematics? Przydatne wydaje się mieć ich dużą liczbę w jednym miejscu. Wiem, że sztuka programowania komputerowego jest uważana za dobre źródło, ale nie wydaje się ona encyklopedyczna, a jedynie pouczająca.

Uwaga moderatora

Szukamy długich odpowiedzi, które zawierają wyjaśnienia i kontekst. Nie wymieniaj tylko książki: wyjaśnij, dlaczego polecasz książkę lub zasób. Odpowiedzi, które niczego nie wyjaśniają, zostaną usunięte. Aby uzyskać więcej informacji, zobacz Dobry subiektywny, zły subiektywny .

Inżynier świata
źródło
Mały Googling przeszedłby długą drogę w kierunku odpowiedzi na to pytanie. Przynajmniej dostarczyłaby listę dobrych kandydatów, których można by następnie użyć, aby zadać bardziej szczegółowe pytanie.
Caleb

Odpowiedzi:

41

Nie jestem pewien, czy tego właśnie szukasz, ale NIST ma słownik algorytmów i struktur danych . Jest to dość obszerny słownik dla struktur danych i algorytmów (doh) i zwykle dobrze jest go sprawdzić, gdy znajdę coś, o czym nigdy wcześniej nie słyszałem.

Vitor Py
źródło
Twoja odpowiedź jest dokładnie tym, czego szukam. Dodatkowe punkty za bycie wolnym.
Inżynier świata
Zabawne jest to, że w ciągu ostatnich kilku dni NIST DADS jest zamknięty do odwołania, z powodu zamknięcia rządu USA! A potem, gdy usłyszeli tysiące programistów krzyczących jednocześnie ...
szlema,
11

Książka Skiena jest dobrym odniesieniem również: http://www.algorist.com/

Książka obejmuje wszystko, od tła po różne obszary problemów (struktury danych, wyszukiwanie / sortowanie, problemy z grafem, kombinacje / permutacje / heurystyka), a nawet problemy P-NP-zupełne.

Szczególnie istotna część książki na to pytanie to katalog ~ 70-75 różnych algorytmów, rodzaje danych wejściowych, których zazwyczaj wymagają, ogólny opis problemu, który rozwiązuje dany algorytm, oraz konkretne przykłady aplikacji (na przykład sekcja poświęcona drzewom sufiksów omawia użycie prób oraz ich zastosowanie do podciągów i wyszukiwania). Tam, gdzie to możliwe, autor identyfikuje również istniejące implementacje dla różnych popularnych języków (c, c ++, Java i niektórych innych).

Joe
źródło
To najbliższa encyklopedii algorytmicznej, o której mogę myśleć. Doskonała książka!
Charalambos Paschalides,
8

Struktura i interpretacja programów komputerowych oraz sztuka programowania komputerowego są najbliższe temu, czego szukałem.

SICP przechodzi przez wspólne struktury danych i algorytmy. Chociaż nie jest to encyklodpeda, całkiem nieźle obejmuje szeroki obszar terytorium na ograniczonej przestrzeni.

Co można powiedzieć o sztuce programowania komputerowego, czego jeszcze nie było. Zachowaj ostrożność, gdy go odbierzesz, możesz przejść do niego na konkretny temat, a kilka godzin później zdać sobie sprawę, że przeczytałeś tom od deski do deski. To świetny sposób, aby naprawdę przenieść swoje programowanie na wyższy poziom.

Michael Brown
źródło
5
SICP to wspaniała książka, ale nie sądzę, aby była to rozsądna sugestia dla kogoś, kto szuka „encyklopedii algorytmów”. SICP nie próbuje być czymś takim. Co więcej, OP napisał, że ACP „nie wydaje się encyklopedyczne, a jedynie pouczające”, dlatego powinno być jasne, że SICP nie jest tym, czego on lub ona szuka.
Caleb
Świetna książka, ale nie encyklopedyczna.
haylem,
Jestem całkiem pewien, że powiedziałem, że to nie jest encyklopedyczne, ale daje dobry przegląd algorytmów. „Chociaż nie jest encyklopedyczny, całkiem nieźle obejmuje szeroki obszar terytorium na ograniczonej przestrzeni”. Tak właśnie powiedziałem.
Michael Brown
8

Cormen, Leiserson, Rivest, Stein - „Intodukcja algorytmów”

Wprowadzenie do algorytmów, bardziej powszechnie znanych jako CLRS, to standardowy podręcznik algorytmów na wielu uniwersytetach. Obejmuje szereg algorytmów dla różnych aplikacji, w tym sortowania, wyszukiwania, teorii grafów i podstawowych obliczeń numerycznych. Zawiera także szczegółowe omówienie notacji Big O, Big Omega i Big Theta. Powszechną krytyką jest to, że tak naprawdę nie przygotowuje się do zaprojektowania nowych algorytmów, ale jako encyklopedia lub słownik algorytmów jest więcej niż wystarczająca.

Powinienem również zauważyć, że CLRS daje również porady, jakiego algorytmu użyć, i nie tylko przedstawia ogólny indeks algorytmów i struktur danych. Jest to przydatne, gdy masz zadanie, które chcesz wykonać, i potrzebujesz porady, jak najlepiej go wykonać. Są lepsze zasoby, gdy wiesz, jak chcesz robić to, co robisz i potrzebujesz tylko pseudokodu.

- od komentarzy @ quanticle poniżej

Dmitrij Matwiejew
źródło
4
Czy możesz rozszerzyć swoją odpowiedź, aby uwzględnić to, co w tej książce spełnia cel tego pytania?
2
Wprowadzenie do algorytmów , bardziej znane jako CLRS, jest standardowym podręcznikiem algorytmów na wielu uniwersytetach. Obejmuje szereg algorytmów dla różnych aplikacji, w tym sortowania, wyszukiwania, teorii grafów i podstawowych obliczeń numerycznych. Zawiera także szczegółowe omówienie notacji Big O, Big Omega i Big Theta. Powszechną krytyką jest to, że tak naprawdę nie przygotowuje się do zaprojektowania nowych algorytmów, ale jako encyklopedia lub słownik algorytmów jest więcej niż wystarczająca.
kwantowo
1
Powinienem również zauważyć, że CLRS daje również porady, jakiego algorytmu użyć, i nie tylko przedstawia ogólny indeks algorytmów i struktur danych. Jest to przydatne, gdy masz zadanie, które chcesz wykonać, i potrzebujesz porady, jak najlepiej go wykonać. Są lepsze zasoby, gdy wiesz, jak chcesz robić to, co robisz i potrzebujesz tylko pseudokodu.
kwantowo
Wskazówka do Dmitry: po prostu skopiuj komentarze @ quanticle do treści odpowiedzi, aby Twoja odpowiedź była o 1000% bardziej niesamowita.
nohat
5

Na studiach fizyki bardzo podobały mi się Przepisy numeryczne w C. Oczywiście nie obejmuje wszystkich algorytmów, ale daje doskonałe wyjaśnienia wielu, które są niezwykle przydatne w naukach:

http://www.nr.com/

Książka obejmuje sposoby rozwiązywania:

Równania liniowe

  1. Równania liniowe
  2. Interpolacja i ekstrapolacja
  3. Integracja funkcji
  4. Ocena funkcji
  5. Funkcje specjalne, w tym funkcja gamma, funkcja beta, silnia
  6. Liczby losowe - w tym dobre wyjaśnienie, co to oznacza
  7. Algorytmy sortowania
  8. Znajdowanie pierwiastków i równań nieliniowych
  9. Minimalizacja i maksymalizacja funkcji
  10. Eigensystems
  11. Szybkie transformaty Fouriera
  12. FFT i analiza spektralna
  13. Opis statystyczny danych
  14. Modelowanie danych
  15. Całkowanie zwykłych równań różniczkowych
  16. Problemy z dwoma punktami granicznymi
  17. Równania całkowe i odwrotna teoria granic
  18. Równania różniczkowe cząstkowe
  19. „Inne” algorytmy, takie jak kontrole CRC i kompresja danych

Wszystko to jest bardzo matematyczne, dobre zarówno dla naukowców, jak i osób projektujących silniki fizyki do gier. I nie tylko podaje algorytmy, ale wyjaśnia, dlaczego się za nimi kryją, abyś mógł z nich poprawnie korzystać. Nie typowy tekst kodowy, ale dokładnie to, czego potrzebujesz, kiedy jest potrzebny.

Bardzo na nim polegałem, gdy korzystałem z metody simpleks zjazdowej w wielowymiarowości (ameba) do analizy danych. Wciąż mam w nim ślady ołówka. Ahh, dobre czasy!

Dr Daniel Williams
źródło
1
Czy możesz rozszerzyć swoją odpowiedź, aby uwzględnić to, co w tej książce spełnia cel tego pytania?
4

Jeśli szukasz „encyklopedii algorytmów”, trudno byłoby pomylić się z Encyklopedią algorytmów . Nie mogę powiedzieć, że przeczytałem (399 USD, jest to encyklopedia tanio ), ale napis wygląda obiecująco:

Encyklopedia algorytmów zapewnia studentom i badaczom kompleksowy zestaw rozwiązań ważnych problemów algorytmicznych, w tym rozwiązania o dużej skuteczności z ostatniej dekady.

Ktoś już cytował podręcznik projektowania algorytmu Stevena Skieny , ale nie sądzę, aby ktokolwiek jeszcze wspomniał o powiązanej stronie internetowej Skieny, The Stony Brook Al algorytm Repository . Ze strony internetowej:

Ta strona WWW ma służyć jako kompleksowy zbiór implementacji algorytmów dla ponad siedemdziesięciu najbardziej podstawowych problemów algorytmów kombinatorycznych.

Książka jest czymś więcej niż katalogiem znanych algorytmów; jest to także rodzaj tutoriala (w najlepszym tego słowa znaczeniu), w jaki sposób zdecydować, który algorytm zastosować w celu najlepszego dopasowania do problemu i sytuacji. Z drugiej strony repozytorium ma charakter bardziej encyklopedyczny. Niekoniecznie zawiera wiele szczegółowych informacji na temat samodzielnego wdrażania każdego algorytmu, ale wyjaśnia, co robi algorytm i jak działa ogólnie, czytelne terminy często zaczerpnięte z książki i zapewnia linki do rzeczywistych implementacji dla każdego algorytmu algorytm.

Caleb
źródło
2

Rosetta Kod Wiki jest wielki zbiór wspólnych wdrożeń algorytmów w kilku językach. Nie jest to całkowicie akademickie, ale bardzo pouczające i zabawne przewracanie.

Innymi słowy:

Rosetta Code to strona programująca chrestomathy . Chodzi o to, aby przedstawić rozwiązania tego samego zadania w jak największej liczbie różnych języków, aby pokazać, jak języki są podobne i różne, oraz pomóc osobie, która ma podstawy w jednym podejściu do problemu w nauce drugiego.

Jego główną przewagą nad innymi zasobami (takimi jak Słownik algorytmów i struktur danych NIST ) jest to, że pozwala spojrzeć na kilka implementacji dla różnych języków. Które mogą być przydatne do różnych celów (porównanie ekspresji, weryfikacja wykonalności w jednym lub innym języku itp.).

Na przykład strona QuickSort zapewnia (na dzień 2013-10-07) co najmniej 89 implementacji.

Haylem
źródło
czy mógłbyś wyjaśnić więcej na temat tego, co robi i dlaczego polecasz to jako odpowiedź na zadane pytanie? „Tylko odpowiedzi” nie są mile widziane na Stack Exchange
gnat
@gnat: Zwykle się zgadza, ale czym różni się to od odpowiedzi „tylko do odwołania”? Myślę też, że „zbiór implementacji popularnych algorytmów w kilku językach” obejmuje w zasadzie to, co robi. Jest także tak (lub tak mało) szczegółowy, jak zaakceptowana odpowiedź, jeśli spojrzysz wystarczająco blisko :)
haylem
@gnat: w każdym razie dodałem trochę więcej.
haylem,
@AnnaLear: przepraszam, myślę, że twoja edycja była w zupełności słuszna, aby mój post był krótki i zgodny z planem, ale wydawało się, że warto przywrócić porównanie w odniesieniu do zmian na żądanie gnata.
haylem,
0

Chociaż istnieją doskonałe i ponadczasowe pouczające książki na ten temat, nie sądzę, że znajdziesz taką encyklopedię.

  • Encyklopedia matematyczna obejmuje tysiące badań. Z drugiej strony algorytmy nie są badane przez sto lat (mówiąc na większą skalę). Cała dziedzina informatyki jest ledwo zrozumiana przez nikogo, a większość rzeczy wciąż się rozwija. Gdyby istniała encyklopedia w tej chwili, myślę, że możesz wyrzucić 90% przez okno w ciągu 10-20 lat. A z 10% wartych zachowania ponad połowa została już wydrukowana pół wieku temu. Ogromne części podręcznika matematyki będą aktualne za sto lat.

  • Matematyka jest czysta i samodzielna. Nie dotyczy to „pola algorytmów”. W rzeczywistości trudno go uznać za pole, ponieważ pole zwykle działa na dobrze zdefiniowanej przestrzeni problemowej, podczas gdy algorytmy faktycznie działają tylko w obrębie mniej zdefiniowanej przestrzeni rozwiązań.
    Jeśli więc skompilujemy encyklopedię na temat algorytmów, nie jest do końca jasne, co należy uwzględnić, jeśli naprawdę chcemy, aby była kompleksowa. Teoria grafów? Algebra liniowa? Analiza numeryczna?

IMHO, obecnie najlepszym zasobem, który spełnia rolę encyklopedii, jest „internet” (oto). Encyklopedia ma indeksowane, kompleksowe repozytorium wiedzy z możliwością wyszukiwania (na pewien temat). Osobiście uważam, że zarówno ta lista, jak i ta lista są przytłaczające. Również w innych odpowiedziach połączono wiele doskonałych baz danych algorytmów.

Tak więc, chociaż nie możesz oczekiwać takiego samego poziomu jakości, jak od encyklopedii, która wypełnia twój regał, otrzymujesz poziom terminowości wymagany do zrekompensowania młodości z dziedziny, o której chcesz wiedzieć.

back2dos
źródło
0

Jeśli chodzi o istniejące źródła, myślę, że Wikipedia jest najbliższa temu, czego szukasz. W tym celu przydatne może być utworzenie bardziej zdefiniowanego „szablonu algorytmu” na Wikipedii w tym celu, ale o tym należy porozmawiać z redaktorami Wikipedii, a nie tutaj.

Krótka uwaga na temat sztuki programowania komputerowego : kiedy zostanie ukończona, powinna zawierać „podsumowanie” i chociaż to ci teraz nie pomoże, może być w przybliżeniu tym, czego szukasz. TAOCP jest encyklopedyczny w odniesieniu do tego, co obejmuje, ale nie jest jeszcze kompletny, a osobowość Knutha jest taka, że ​​nie będzie uwzględniał rzeczy, chyba że wyczerpująco je zbadał.

bardzo głupie
źródło