Manuel d'algorithmes avancés

11

Je recherche des ressources (de préférence un manuel) sur des sujets avancés en algorithmes (sujets au-delà de ce qui est couvert dans les manuels d'algorithmes comme CLRS et DPV).

Le type de matériel qui peut être utilisé pour enseigner un sujet dans un cours d'algorithmes comme le cours d'Erik Demaine et le cours d'algorithmes avancés de David Karger .

Des ressources qui donneraient une vue d'ensemble du domaine (comme un manuel) sont préférables, mais des ressources plus ciblées comme le livre "Approximation Algorithms" de Vijay Vazirani sont également très bien.

ds.algorithms reference-request survey books Kaveh
la source
Ceci est similaire à ma question précédente sur les structures de données: manuel des structures de données avancées . Je voudrais les utiliser comme pointeurs pour que mes élèves apprennent des sujets plus avancés en algorithmes. Les ressources disponibles en ligne pour les étudiants sont préférables.
Kaveh
Recherchez dans les archives du MIT .
Tommy
1
Johan Håstad (également) a des notes de cours sur les algorithmes avancés: nada.kth.se/~johanh/algnotes.pdf
Huck Bennett

Réponses:

6

The Design of Approximation Algorithms par Williamson & Shmoys ( http://www.designofapproxalgs.com/ ) est un excellent livre pour de nombreuses méthodes d'approximation telles que les algorithmes gourmands, la programmation semi-définie, etc. En outre, il couvre certains sujets de complexité qui sont étroitement liés liés aux algorithmes d'approximation (inapproximabilité, dureté unique basée sur les jeux de MAX-CUT).

rahulmehta95
la source
5

Vous pouvez trouver intéressant les manuels récents suivants. La gamme de sujets couverts va bien au-delà du CLRS, et le matériel est bien adapté pour les diplômés et les doctorants. étudiants, même si vous pouvez choisir quelques sujets sélectionnés pour les étudiants de premier cycle avancés.

Manuel d'algorithmes et de théorie du calcul, deuxième édition (sujets et techniques spéciaux)

Manuel d'algorithmes appliqués Résolution des problèmes scientifiques, d'ingénierie et pratiques

Manuel des algorithmes d'approximation et des métaheuristiques 

Massimo Cafaro
la source
revue et table des matières de la 1ère réf Atallah / Blanton
vzn
4

J'ai plutôt aimé "Algorithmics for Hard Problems" de Juraj Hromkovic

n00b
la source
4

Géométrie informatique: Mark de Berg, Marc van Kreveld, Mark Overmars et Otfried Cheong. Géométrie informatique: algorithmes et applications; Notes de cours de David Mount .

Algorithmes randomisés: Motwani et Raghavan. Algorithmes randomisés; Excellentes notes de James Aspnes ; Mitzenmacher et Upfal. Probabilité et informatique.

Flux de réseau: Ahuja, Magnanti et Orlin. Flux de réseau.

Algorithmes d'approximation: Dorit Hochbaum. Algorithmes d'approximation pour les problèmes NP-difficiles. 

Jinx
la source
1
Puisqu'il pourrait ne pas y avoir un seul "Manuel des algorithmes avancés", une réponse wiki communautaire dans ce sens (par sujet d'algorithmes avancés) serait bien.
Huck Bennett
O(mn)
0

pas exactement ce qui est souhaité mais similaire à votre exemple, considérez CS G399: Gemmes de l'informatique théorique; Notes de cours du printemps 2009 de Viola. sa perspective est davantage axée sur la preuve, mais la plupart sont essentiellement des algorithmes avancés dans des domaines de recherche frontaliers clés. (Notez également que les preuves des limites inférieures peuvent être considérées comme des algorithmes de compression.)

Ce cours couvre certains des progrès les plus passionnants et récents en informatique théorique. Il présente des résultats de pointe sur des domaines de recherche actifs et enseigne les techniques de preuve associées. Une liste provisoire de sujets comprend:

  • Limites inférieures pour les circuits à profondeur constante.
  • Le générateur pseudo-aléatoire de Nisan-Wigderson.
  • Cryptographie en temps parallèle constant.
  • La complexité des équilibres de Nash.
  • Connectivité non dirigée dans l'espace logarithmique (SL = L).
  • Complexité de la communication.
  • Primes est en P.
  • Multiplication matricielle rapide.
vzn
la source
2
beau parcours, mais beaucoup plus large que ce que le PO demandait
Alessandro Cosentino