Manual de algoritmos avançados

11

Estou procurando recursos (de preferência um manual) sobre tópicos avançados em algoritmos (tópicos além do que é abordado em manuais de algoritmos como CLRS e DPV).

O tipo de material que pode ser usado para o ensino de tópicos em um curso de algoritmos, como o Erik Demaine e o curso de Algoritmos Avançados de David Karger .

Os recursos que dariam uma visão geral do campo (como um manual) são preferíveis, mas recursos mais focados, como o livro "Algoritmos de aproximação" de Vijay Vazirani, também são bons.

ds.algorithms reference-request survey books Kaveh
fonte
Isso é semelhante à minha pergunta anterior sobre estruturas de dados: manual de estruturas de dados avançadas . Eu gostaria de usá-los como ponteiros para meus alunos aprenderem sobre tópicos mais avançados em algoritmos. Os recursos disponíveis on-line para os alunos são preferíveis.
Kaveh #
Pesquise os arquivos do MIT .
Tommy #
1
Johan Håstad (também) tem notas de aula em algoritmos avançados: nada.kth.se/~johanh/algnotes.pdf
Huck Bennett

Respostas:

6

O Design de algoritmos de aproximação de Williamson & Shmoys ( http://www.designofapproxalgs.com/ ) é um ótimo livro para muitos métodos de aproximação, como algoritmos gananciosos, programação semidefinida, etc. Além disso, abrange alguns tópicos de complexidade intimamente relacionados. relacionados a algoritmos de aproximação (inadequação, dureza baseada em jogos únicos de MAX-CUT).

rahulmehta95
fonte
5

Você pode achar interessante os seguintes manuais recentes. A gama de tópicos abordados vai muito além do CLRS, e o material é adequado para graduação e doutorado. alunos, mesmo que você possa escolher alguns tópicos selecionados para estudantes avançados de graduação.

Manual de Algoritmos e Teoria da Computação Segunda Edição (Tópicos e Técnicas Especiais)

Manual de Algoritmos Aplicados que Resolvem Problemas Científicos, de Engenharia e Práticos

Manual de Algoritmos de Aproximação e Metaheurísticas 

Massimo Cafaro
fonte
revisão e índice da 1ª ref Atallah / Blanton
vzn 5/11/2013
4

Eu gostei bastante de "Algoritmia para problemas difíceis", de Juraj Hromkovic

n00b
fonte
4

Veja a Enciclopédia de Algoritmos de Kao (Editor). Ele contém mais de 500 entradas e muitas delas contêm algoritmos avançados.

Mohammad Al-Turkistany
fonte
sumário
vzn 5/11/2013
4

Geometria Computacional: Mark de Berg, Marc van Kreveld, Mark Overmars e Otfried Cheong. Geometria Computacional: Algoritmos e Aplicações; Notas do curso de David Mount .

Algoritmos Aleatórios: Motwani e Raghavan. Algoritmos Aleatórios; Excelentes notas de James Aspnes ; Mitzenmacher e Upfal. Probabilidade e computação.

Fluxos de rede: Ahuja, Magnanti e Orlin. Fluxos de rede.

Algoritmos de aproximação: Dorit Hochbaum. Algoritmos de aproximação para problemas NP-difíceis. 

Jinx
fonte
1
Como pode não haver um único "Manual de algoritmos avançados", uma resposta do wiki da comunidade nesse sentido (por tópico sobre algoritmos avançados) seria legal.
Huck Bennett #
O(mn)
0

não exatamente o que é desejado, mas semelhante ao seu exemplo, considere CS G399: Gemas da Ciência da Computação Teórica; Notas da aula da primavera de 2009 de Viola. é uma perspectiva mais centrada na prova, porém a maioria são algoritmos essencialmente avançados nas principais áreas de pesquisa de fronteira. (observe também que as provas de limites inferiores podem ser consideradas como algoritmos de compactação.)

Este curso abrange alguns dos progressos mais empolgantes e recentes em ciência da computação teórica. Apresenta resultados avançados em áreas de pesquisa ativas e ensina técnicas de prova relacionadas. Uma lista provisória de tópicos inclui:

  • Limites inferiores para circuitos de profundidade constante.
  • O gerador pseudo-aleatório de Nisan-Wigderson.
  • Criptografia em tempo paralelo constante.
  • A complexidade dos equilíbrios de Nash.
  • Conectividade não direcionada no espaço logarítmico (SL = L).
  • Complexidade da comunicação.
  • Primes está em P.
  • Rápida multiplicação de matrizes.
vzn
fonte
2
agradável claro, mas muito maior do que o que o OP estava pedindo
Alessandro Cosentino