Zasób do nauki Algorytmy dla stopni nie-CS/matematyki

Question

Zostałem poproszony o zalecenie zasobu (on-line, książki lub samouczek) do nauki algorytmów (w sensie MIT Intro to Algorithms) dla CS lub matematyka. Oczywiście książka MIT jest zbyt zaangażowana, a niektóre z lżejszych metod leczenia (takich jak algorytmy OReilly w skrócie) wciąż wydają się być potrzebne w analizie algorytmicznej. Czy istnieje zasób, który przedstawia materiał w taki sposób, aby przydatne okazały się twórcy, którzy nie mają podstaw teoretycznego informatyki?

Answer 1

Uważam, że najlepszym sposobem poznania algorytmów są różne witryny konkurencji.

• USACO - mój osobisty faworyt, ponieważ daje jasną drogę przez materiał
• TopCoder - wspomnianego już
• Sphere Online Judge - wielki, jeśli chcesz pracować w innym języku niż C/C++/Java

Jeśli chodzi o książki, najlepsze pojedyncze intro, jakie widziałem dla specjalisty nie matematycznego, to Data Structures and Algorithms. Przeprowadza cię przez algorytm po linii i pokazuje, jak rozkłada się on matematycznie, coś, co jest poza tym doskonałą sekcją analizy CLRS.

Skiena Algorithm Design Manual jest również doskonała, podobnie jak jego Programming Challenges, która jest w zasadzie tutorialem przez Valladolid Online Judge.

Szczerze mówiąc, uważam, że najbardziej przydatną rzeczą, jaką może zrobić początkujący, jest implementacja różnych algorytmów - sortowanie scalone, powiedzmy, a następnie Quicksort - i ustawianie ich na różne wejścia o różnej wielkości. Utwórz arkusz kalkulacyjny z wykresem, który pokazuje ich wzrost w czasie. Bardzo niewielu nie-specjalistów będzie miało cierpliwość lub know-how, aby ustalić relację i rozwiązać problem. Ale musisz zrozumieć wpływ, powiedzmy, wzrostu w czasie, i nie ma lepszego sposobu, aby się tego nauczyć, niż obserwować, jak twój własny program przebija swój stos pamięci. :)

Mówię to jako programista spoza matematyki, który nie spędził wiele czasu z matematyką, który spędził dobre kilka miesięcy, owijając mój umysł wokół analizy algorytmicznej.

Answer 2

Nie jestem pewien, do której książki MIT się powołujesz, ale tekst kanoniczny brzmi: CLRS. Nie sądzę, że to naprawdę ma jakiekolwiek pochodzenie oprócz matematyki w szkole średniej.

Osobiście odkryłem, że w ciągu ostatnich kilku lat zrobiłem TopCoder konkursy algorytmów, aby być najlepszym sposobem na nauczenie się wspólnych algorytmów i zastosowanie ich w praktyce. Być może powinieneś spróbować tego samego. Cokolwiek robisz, sugeruję, byś spędzał dużo więcej czasu na klawiaturze, realizując rzeczy, których się uczysz, niż czas w głowie, ponieważ jest to sposób na internalizację różnych technik.

Answer 3

Poszedłem po Algorithm Design Manual, przez Stevena Skienę. Jest bardzo czytelny i zaczyna się od podstaw w łatwy do zrozumienia sposób. Na przykład bardzo dobrze tłumaczy notację big-o. Nacisk kładzie się na praktyczne zastosowanie, co jest dużą premią dla początkujących, którzy pochodzą z dziedziny nie-teoretycznej.

Druga część książki jest odniesieniem do typowych problemów z algorytmem i praktycznych podejść do ich rozwiązań. Uważam to za nieocenione jako pomoc do nauki, a teraz jako punkt odniesienia.