Livros rigorosos sobre algoritmos

7

Gostei muito da minha classe de algoritmos, mas senti que faltava rigor. Na maioria das vezes, eu conseguia entender intuitivamente por que os algoritmos apresentados funcionavam e por que tinham a complexidade de tempo apresentada, mas eu gostaria de poder provar essas coisas. Como tal, eu gostaria de um livro que abordasse muitos algoritmos comuns e se concentrasse em provar a correção e a complexidade de tempo dos algoritmos. Alguma boa recomendação?

algorithms education books Budge
fonte
3
Os livros de Knuth costumam ter análises, então olhe para a arte da programação de computadores.
Pavel
2
Bem-vindo ao CS.SE! Essa questão é bastante ampla: existem muitos livros didáticos de algoritmos que têm um foco significativo nas provas de correção e complexidade de tempo. Que pesquisa você já fez? Que opções você considerou e por que as rejeitou? (Consulte cs.stackexchange.com/help/how-to-ask. ) Além disso, este site não funciona bem para recomendações, pois são inerentemente subjetivos; consulte nossa central de ajuda . Você consegue pensar em alguma maneira de editar a pergunta para resolver essas preocupações?
DW
4
Não tenho certeza de qual livro você usou nas aulas, mas Introdução aos algoritmos por Cormen et al. é considerado o livro mais popular para os cursos de graduação e pós-graduação em algoritmos. Abrange uma enorme quantidade de material, com uma grande quantidade de referências fornecidas. Eu não acho que você encontrará um livro melhor sobre algoritmos do que este, a menos que esteja procurando um tópico muito específico.
user340082710
2
Eu também encontrei este post que tem outras sugestões: cs.stackexchange.com/questions/2495/…
user340082710
2
Não temos uma política estrita para perguntas da lista, mas há uma aversão geral . Observe também esta e esta discussão; convém melhorar sua pergunta para evitar os problemas explicados lá. Se você não tem certeza de como melhorar sua pergunta, talvez possamos ajudá-lo no bate-papo de ciência da computação ?
Raphael

Respostas:

5

Nota: edite esta resposta e adicione-a, não crie novas respostas

Livros rigorosos:

A arte da programação de computadores por Knuth

Uma disciplina de programação por Dijkstra

Introdução aos algoritmos de Cormen, Leiserson, Rivest e Stein

Algoritmos de Sedgewick e Wayne

Os Livros Essenciais do Dr. Dobb sobre Algoritmos e Estruturas de Dados
Isso também incluiintroduction to algorithms

Algoritmos + Estruturas de Dados = Programas da Wirth e seu acompanhamento:
Algoritmos e Estruturas de Dados

A ciência da programação de Gries e
uma abordagem lógica da matemática discreta do mesmo autor

Algoritmos em Strings, Árvores e Sequências de Gusfield

Matemática concreta: uma fundação para a ciência da computação por Graham, Knuth e Patashnik

A teoria da análise, tradução e compilação (partes I e II) de Aho e Ullman

O Projeto e Análise de Algoritmos de Computador por Aho, Hopcroft e Ullman

Introdução à Teoria dos Autômatos, Idiomas e Computação por Hopcroft e Ullman

Obviamente, a lista pode ser estendida um pouco.
Observe que, à medida que o campo da ciência da computação se expandiu, os livros não conseguem acompanhar e, portanto, você terá que recorrer a trabalhos de pesquisa.

Johan
fonte
Pelo menos a minha versão da Introdução aos algoritmos de Cormen, Leiserson, Rivest e Stein não é rigorosa ao definir notações assintóticas, math.stackexchange.com/questions/2536528/… tenta definirΘ notação como um conjunto, mas, de alguma maneira estranha, adiciona um conjunto mais um polinômio como ex=1+x+θ(x2)
user2219896