Podręcznik zaawansowanych algorytmów

11

Szukam zasobów (najlepiej podręcznika) na zaawansowane tematy w algorytmach (tematy wykraczające poza to, co są omówione w podręcznikach algorytmów, takich jak CLRS i DPV).

Rodzaj materiału, który można wykorzystać do nauczania tematów w kursie algorytmów, takich jak Erik Demaine i kurs Davida Kargera Advanced Algorytmy .

Preferowane są zasoby, które dałyby przegląd pola (np. Podręcznik), ale bardziej ukierunkowane zasoby, takie jak książka Vijay Vazirani „Algorytmy aproksymacyjne” są również w porządku.

ds.algorithms reference-request survey books Kaveh
źródło
Jest to podobne do mojego poprzedniego pytania o struktury danych: podręcznik zaawansowanych struktur danych . Chciałbym wykorzystać je jako wskazówki dla moich uczniów, aby dowiedzieć się o bardziej zaawansowanych tematach w algorytmach. Preferowane są zasoby dostępne online dla studentów.
Kaveh
Przeszukaj archiwa MIT .
Tommy,
1
Johan Hastad (również) ma notatki wykładowe na zaawansowanych algorytmach: nada.kth.se/~johanh/algnotes.pdf
Huck Bennett

Odpowiedzi:

6

Projektowanie algorytmów aproksymacyjnych Williamsona i Shmoysa ( http://www.designofapproxalgs.com/ ) jest świetną książką dla wielu metod aproksymacyjnych, takich jak chciwe algorytmy, programowanie półfinałowe itp. Ponadto obejmuje niektóre ściśle złożone tematy związane z algorytmami aproksymacji (niedocenianie, twardość oparta na unikalnych grach z MAX-CUT).

rahulmehta95
źródło
5

Interesujące mogą być następujące najnowsze podręczniki. Zakres tematów wykracza znacznie poza CLRS, a materiał jest odpowiedni dla absolwentów i doktorantów. studenci, nawet jeśli możesz wybrać kilka wybranych tematów dla zaawansowanych studentów.

Podręcznik algorytmów i teorii obliczeń wydanie drugie (specjalne tematy i techniki)

Podręcznik stosowanych algorytmów rozwiązywania problemów naukowych, inżynierskich i praktycznych

Podręcznik algorytmów aproksymacji i metaheurystyki 

Massimo Cafaro
źródło
recenzja i spis treści pierwszego
odsyłacza
4

Raczej podoba mi się „Algorytmika dla trudnych problemów” Juraja Hromkovicia

n00b
źródło
4

Zajrzyj do Encyklopedii algorytmów Kao (redaktor). Zawiera ponad 500 wpisów, a wiele z nich zawiera zaawansowane algorytmy.

Mohammad Al-Turkistany
źródło
spis treści
dniu
4

Geometria obliczeniowa: Mark de Berg, Marc van Kreveld, Mark Overmars i Otfried Cheong. Geometria obliczeniowa: algorytmy i zastosowania; Notatki z kursu Davida Mounta .

Algorytmy randomizowane: Motwani i Raghavan. Algorytmy randomizowane; Doskonałe nuty Jamesa Aspnesa ; Mitzenmacher i Upfal. Prawdopodobieństwo i informatyka.

Przepływy sieciowe: Ahuja, Magnanti i Orlin. Przepływy sieciowe.

Algorytmy aproksymacyjne: Dorit Hochbaum. Algorytmy aproksymacyjne dla problemów NP-trudnych. 

Pech
źródło
1
Ponieważ może nie istnieć ani jeden „Podręcznik zaawansowanych algorytmów”, odpowiedź społeczności wiki na ten temat (według tematu zaawansowanych algorytmów) byłaby miła.
Huck Bennett,
O(mn)
0

nie do końca to, co jest pożądane, ale podobne do twojego przykładu, rozważ CS G399: Gems of Theoretical Computer Science; Wiosenne notatki z wykładów Violi. jest to bardziej skoncentrowana na dowodach perspektywa, jednak większość to zasadniczo zaawansowane algorytmy w kluczowych obszarach badań pionierskich. (zwróć również uwagę, że dowody w dolnych granicach można uznać za algorytmy kompresji).

Kurs obejmuje jedne z najbardziej ekscytujących i najnowszych postępów w informatyce teoretycznej. Prezentuje najnowsze wyniki w aktywnych obszarach badawczych i uczy powiązanych technik dowodowych. Wstępna lista tematów obejmuje:

  • Dolne granice dla obwodów o stałej głębokości.
  • Generator pseudolosowy Nisan-Wigderson.
  • Kryptografia w stałym czasie równoległym.
  • Złożoność równowag Nasha.
  • Niekierowana łączność w przestrzeni logarytmicznej (SL = L).
  • Złożoność komunikacji.
  • Primes jest w P.
  • Szybkie mnożenie macierzy.
vzn
źródło
2
fajny kurs, ale znacznie szerszy niż to, o co prosił OP
Alessandro Cosentino