Projeto e complexidade de algoritmos - Como pensar dessa maneira?

15

Minha pergunta é geral: como começo a pensar em termos de design e complexidade de algoritmos? Vou fazer um Curso de Pós-Graduação em Design de Algoritmos. Eu me matriculei mais cedo, mas desisti depois, porque não conseguia acompanhá-lo. Eu tenho que fazer este curso como um requisito.

Existe um 'truque' para pensar dessa maneira? Sei que isso está colocando de maneira bem grosseira, mas às vezes uma nova perspectiva ajuda a pensar sobre um assunto de maneira diferente.

O principal problema que tenho com este curso (e com cursos teóricos semelhantes) é: Como sei que as soluções apresentadas são corretas? Eu acho a parte teórica arbitrária, especialmente quando 'provar' que um determinado algoritmo age ou se comporta de uma certa maneira?

Nosso curso usará o texto padrão: Introdução aos Algoritmos pelo CLRS.

Existem livros / sites / livros / etc. que pode oferecer uma maneira de se tornar confiante nesse campo?

Obrigado a todos,

Jason Dane

Jason Dane
fonte
2
Sugiro dar uma olhada neste post . Sugiro especialmente o livro de Udi Manber.
MS Dousti
11
Esta discussão no StackOverflow oferece várias sugestões: stackoverflow.com/questions/2256721/…
Jeffε
2
Eu apóio a recomendação de Manber. Também confira Como pensar em algoritmos Jeff Edmonds: amazon.com/Think-About-Algorithms-Jeff-Edmonds/dp/0521614104
Jeffε
"Como sei que as soluções apresentadas são corretas?" Você quer dizer que (1) você criou um algoritmo, mas não sabe como provar que está correto, ou (2) você tem uma prova, mas não tem certeza se está correto?
Jukka Suomela 01/01
Etapa 1: pare de fornecer respostas diretas e, em vez disso, consulte as soluções de outras pessoas. ;)
Raphael

Respostas:

18

Eu acho que os cursos sobre design de algoritmos e complexidade computacional são sempre desafiadores para os estudantes que não estão familiarizados com essas disciplinas, porque exigem algum grau de maturidade matemática e habilidade para resolver problemas. No meu primeiro curso de graduação em "complexidade computacional", um amigo meu que se formou em matemática pura me contou como ficou surpreso pelo fato de que, embora esse curso não exigisse muita formação em matemática (pelo menos foi o que foi dito em o esquema do curso), na verdade, exigia quase todas as habilidades que ele adquiriu em toda a sua graduação em matemática pura!

Eu descobri que conhecia "o caminho" mais (quando eu comecei meu curso de graduação) lendo e fazendo exercícios do livro de Sipser . Certifique-se de fazer os exercícios, porque a habilidade em resolver problemas e a maturidade matemática é o que você deseja aprender e não apenas um monte de fatos ou definições.

No entanto, o livro de Sipser é bom apenas para itens de complexidade e de completude NP, não basta substituir o livro do CLRS. O único problema com o livro do CLRS é que sua vantagem de cobertura abrangente pode se tornar sua fraqueza, pois o livro pode parecer bastante assustador ou esmagador para os alunos. Portanto, meu conselho é que você realmente vá à biblioteca e pesquise livros sobre algoritmos, escaneie um por um e escolha os que mais se encaixam no seu padrão de pensamento. E, novamente, não se esqueça de fazer exercícios!

Para algoritmos, eu pessoalmente sugiro os seguintes livros (além dos sugeridos por Sadeq e JeffE):

  • O livro muito legível e bonito Algoritmos de S. Dasgupta, CH Papadimitriou e UV Vazirani.
  • As notas assassinas (ou rascunho de livro) de Jeff Erickson. (Como JeffE é modesto demais para sugerir suas próprias anotações, eu tenho que fazer isso sozinho.)

Em geral, sempre que você estuda um determinado algoritmo ou estrutura de dados, se de alguma forma a exposição em seu livro não é clara o suficiente para você, a melhor maneira é pesquisar no google por notas de aula sobre esse tópico em particular. Em alguns casos, explicações diferentes da mesma coisa acabam fornecendo uma imagem completa. Pelo menos, é assim que funciona para mim.

Dai Le
fonte
8
+1 nas notas de assassino de Jeff. Eu sempre gosto de lê-los. A caligrafia árabe da palavra algoritmo é muito bonita.
Mohammad Al-Turkistany 01/01