Manual de algoritmos avanzados

11

Estoy buscando recursos (preferiblemente un manual) sobre temas avanzados en algoritmos (temas más allá de lo que se cubre en los libros de texto de algoritmos como CLRS y DPV).

El tipo de material que se puede usar para enseñar un tema en un curso de algoritmos como Erik Demaine y el curso de Algoritmos Avanzados de David Karger .

Los recursos que darían una visión general del campo (como un manual) son preferibles, pero los recursos más enfocados como el libro "Algoritmos de aproximación" de Vijay Vazirani también están bien.

ds.algorithms reference-request survey books Kaveh
fuente
Esto es similar a mi pregunta anterior sobre estructuras de datos: manual de estructuras de datos avanzadas . Me gustaría usarlos como punteros para que mis alumnos aprendan sobre temas más avanzados en algoritmos. Los recursos que están disponibles en línea para los estudiantes son preferibles.
Kaveh
Buscar en los archivos del MIT .
Tommy
1
Johan Håstad (también) tiene notas de clase sobre algoritmos avanzados: nada.kth.se/~johanh/algnotes.pdf
Huck Bennett

Respuestas:

6

El diseño de algoritmos de aproximación de Williamson & Shmoys ( http://www.designofapproxalgs.com/ ) es un gran libro para muchos métodos de aproximación como algoritmos codiciosos, programación semidefinida, etc. Además, cubre algunos temas dentro de la complejidad que están muy cerca relacionado con algoritmos de aproximación (inaplicabilidad, dureza basada en juegos únicos de MAX-CUT).

rahulmehta95
fuente
5

Puede encontrar interesantes los siguientes manuales recientes. La gama de temas cubiertos va mucho más allá de CLRS, y el material es adecuado para graduados y doctores estudiantes, aunque puede elegir algunos temas seleccionados para estudiantes avanzados de pregrado.

Manual de Algoritmos y Teoría de la Computación Segunda Edición (Temas y Técnicas Especiales)

Manual de algoritmos aplicados para resolver problemas científicos, de ingeniería y prácticos

Manual de algoritmos de aproximación y metaheurística ur

Massimo Cafaro
fuente
revisión y tabla de contenido de la primera referencia Atallah / Blanton
vzn
4

Me gustó bastante "Algoritmos para problemas difíciles" de Juraj Hromkovic

n00b
fuente
4

Geometría computacional: Mark de Berg, Marc van Kreveld, Mark Overmars y Otfried Cheong. Geometría Computacional: Algoritmos y Aplicaciones; Notas del curso de David Mount .

Algoritmos aleatorizados: Motwani y Raghavan. Algoritmos aleatorizados; Excelentes notas de James Aspnes ; Mitzenmacher y Upfal. Probabilidad y Computación.

Flujos de red: Ahuja, Magnanti y Orlin. Flujos de red.

Algoritmos de aproximación: Dorit Hochbaum. Algoritmos de aproximación para problemas NP-Hard. 

Gafe
fuente
1
Como puede que no haya un solo "Manual de algoritmos avanzados", una respuesta wiki comunitaria en este sentido (por tema de algoritmos avanzados) sería bueno.
Huck Bennett
+1 para Ahuja, et. Alabama. Gran libro: desafortunadamente, no cubre muchos de los resultados recientes, como el algoritmo de tiempo Orlin y el algoritmo de Madry que resuelve los laplacios para los flujos eléctricos. O(mn)
rahulmehta95
0

no exactamente lo que se desea pero similar a su ejemplo, considere CS G399: Gems of Theoretical Computer Science; Notas de conferencia de primavera de 2009 de Viola. es más una perspectiva centrada en la prueba, sin embargo, la mayoría son algoritmos esencialmente avanzados en áreas clave de investigación de fronteras. (también tenga en cuenta que las pruebas de límites inferiores pueden considerarse algoritmos de compresión).

Este curso cubre algunos de los avances más emocionantes y recientes en informática teórica. Presenta resultados de vanguardia en áreas de investigación activa y enseña técnicas de prueba relacionadas. Una lista tentativa de temas incluye:

  • Límites inferiores para circuitos de profundidad constante.
  • El generador pseudoaleatorio Nisan-Wigderson.
  • Criptografía en tiempo paralelo constante.
  • La complejidad de los equilibrios de Nash.
  • Conectividad no dirigida en espacio logarítmico (SL = L).
  • Complejidad de la comunicación.
  • Primes está en P.
  • Multiplicación rápida de matrices.
vzn
fuente
2
bonito curso, pero mucho más amplio de lo que pedía el OP
Alessandro Cosentino