Podręcznik zaawansowanych algorytmów

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.

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).

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 

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

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

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. 

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.

ten artykuł poleca Lance Fortnow (na swoim blogu).

Jan van Leeuwen, redaktor. Podręcznik informatyki teoretycznej, tom A: Algorytmy i złożoność. MIT Press, 1994.