Szukam zwięzłego tekstu wprowadzającego na temat algorytmów z omówioną teorią wysokiego współczynnika
Powinno zacząć się od początku, ale potem szybko postępować, nie poświęcając zbyt wiele czasu na przykłady z prawdziwego świata, elementarne techniki dowodowe itp. Jako matematyk badawczy mam solidne doświadczenie w matematyce, którą chętnie wykorzystuję do zrozumienia formalizmów i skondensowanych dowodów, na przykład .
Czy istnieją takie teksty? Jakieś rekomendacje?
ds.algorithms
Gregor
źródło
źródło
Odpowiedzi:
Bardzo podoba mi się ten podręcznik:
Sanjoy Dasgupta, Christos Papadimitriou i Umesh Vazirani: Algorytmy
opublikowane przez McGraw-Hill 2007.
Nie obliczam twojego sugerowanego współczynnika, ale myślę, że ci się spodoba :)
źródło
Jeff Erickson sam tego nie powie, ale jego notatki z wykładów są jednymi z najlepszych na temat podstaw projektowania algorytmów na poziomie, który nie patronuje czytelnikowi. Używam ich w mojej klasie algorytmów gradowych, a dla matematyka naukowego notatki te przekazują właściwy rodzaj (i poziom) intuicji, umożliwiając łatwe uzupełnienie szczegółów.
źródło
Knuth w „ Sztuka programowania ” będzie prawdopodobnie książka o najwyższym stosunku.
Jeśli chcesz mieć bardziej podręcznikową książkę, to „ Wprowadzenie do algorytmów ” Cormena, Leisersona, Rivesta i Steina byłoby moją propozycją dla matematyka.
Istnieje również wiele notatek z wykładów i kilka Wikibooks na temat algorytmów.
źródło
Algorytm zaprojektowany przez Kleinberga Tardosa Ta książka pomaga w konkretnym zrozumieniu, jak projektować dobre algorytmy i mówić o ich poprawności i wydajności. (Studiowałem to na pierwszym roku studiów, bardzo czytelne)
Aby otrzymać kopię online / notatki z wykładu / referencje (jak sugeruje Suresh Venkat), przejdź do notatek z wykładu Jeffa Eriksona . Są naprawdę niesamowite!
źródło
Pójdę do optymalizacji kombinatorycznej: Teoria i algorytmy - Korte & Vygen . To da ci dobry przegląd algorytmów ze stałym naciskiem na optymalizację. Ta książka jest przeznaczona dla osób o dużej skłonności matematycznej IMHO.
Myślę, że pasowałoby to do algorytmów: Dasgupta i Papdimitrou.
źródło
Napisałem dyspozycję na kurs algorytmów, w którym uczestniczyłem. Dokładnie taki był cel; być zwięzłą wersją najważniejszych tematów poruszonych w naszym polu tekstowym (którym był CLRS). Niechętnie publikuję go na Scribd.com lub gdziekolwiek indziej, dopóki nie dokładnie zbadam dokument i nie będę zadowolony z jego zawartości, ale kopię roboczą można uzyskać pod adresem stronie https://github.com/CasperBHansen/DIKU_AD_2013/ . Aby go przeczytać, musisz wiedzieć, jak zbudować dokument pdf ze źródła LaTeX, do czego służy repozytorium. Sam dokument ma tylko 65 stron.
Starszą kopię można pobrać bezpośrednio z mojej strony internetowej pod adresem http://casperbhansen.dk/files/ad-disposition.pdf - to oczywiście zawiera więcej literówek / błędów, które od tego czasu zostały poprawione.
Zawiera kilka literówek, ponieważ zostało napisane w ciągu zaledwie kilku dni, podczas gdy przechodzę kolejny egzamin i oczywiście przygotowuję się do egzaminu z algorytmów, ćwicząc dowody, a ja jeszcze nie załatałem literówek i błędów, ponieważ od tego czasu jestem bardzo zajęty. Ale jestem pewien, że każdy, kto ją przeczyta, z łatwością rozpozna błędy, ponieważ są one zwykle w sprzeczności z towarzyszącym tekstem lub formułami, więc łatwo to rozgryźć, gdy wystąpi literówka.
Mam nadzieję, że pomoże ci to zacząć.
źródło
oto dwa inne referencje, które mogą być pomocne.
Algorytmy Sedgewicka powiedziałeś „wprowadzenie”; ta książka jest czasami używana na licencjackich zajęciach z CS, chociaż może być używana na niektórych zajęciach dla absolwentów. Sedgewick ma inne bardzo techniczne referencje na temat TCS, a niektóre z tego matematycznego stylu znajdują odzwierciedlenie w Algorytmach i są ogólnie zwięzłe. zasięg jest bardzo istotny dla (T) CS (ale nie tak bardzo w obszarach zaawansowanych). napisał również „wpływ”, że napisał doktorat pod kierunkiem Knutha.
Komputery i trudność, przewodnik po teorii kompletności NP , starsze, ale wciąż bardzo istotne ref. skupia się oczywiście na kompletności NP, ale pod wieloma względami „to tam jest dużo akcji”. zakres jest szeroki i prawdopodobnie spodoba się matematykom, ponieważ koncentruje się na wielu obiektach matematycznych, np. grafach itp., i zwróć uwagę na rozdział dotyczący teorii liczb. jak twierdzi wikipedia
źródło
Opublikuję odpowiedź, która dała ogólny pogląd na przeczytane rozdziały. Handbook of Theoretical Computer Science: Algorytmy i złożoność, tom 1 pod redakcją Jana Leeuwena . Ma duże nazwiska, takie jak HW Lenstra, Valiant itp. To nie jest tekst jako taki. Jednak przeczytanie tego po wstępnym zrozumieniu daje więcej wglądu i porusza interesujące tematy w TCS. Jest również matematyczny, a każdy rozdział zawiera wprowadzenie do tematu przed zanurzeniem się w nim. Pamiętaj, że tematy poruszają się od momentu ukazania się książki1990 .
źródło
spróbuj Zwięzła encyklopedia informatyki , Wiley. niestety kompletny / dokładny spis treści dla tego ref nie wydaje się być dostępny w sieci [nieco niezwykłe pominięcie w dzisiejszych czasach, być może Wiley może to naprawić na żądanie], ale pełny indeks wydaje się możliwy do przeglądania w Amazon. ma zasięg znacznie szerszy niż TCS, takie jak koncepcje sprzętowe itp., ale wydaje się, że obejmuje znaczną część TCS, np .:
jest to skrócona wersja pełnej encyklopedii 902pp, Encyclopedia of Computer Science, wydanie 4 , 2064pp
źródło