Estudo de algoritmos  XML
Índice dos Fóruns » Assuntos gerais necessariamente ligados a tecnologia
Autor Mensagem
Veneno
JavaGuru
[Avatar]

Membro desde: 12/09/2006 11:36:42
Mensagens: 239
Offline

Fala aí galera, ultimamente tenho me interessado bastante por algoritmos, percebi que são muito importantes e desafiadores rsrs.
Estou tentado resolver diversos problemas do google codejam do ano passado, alguns problemas que parecem ser bem basicos, no final quando testado com uma massa de dados muito grande, se torna mais complexo, tendo uma performance muito ruim. Tambem tem alguns que podem ser resolvidos com tecnicas existentes.
Estava pesquisando e vi que existem varias tecnicas pra resolver esses tipos de problema.
Gostaria de saber se alguem tem alguma dica de como estudar, bibliografias ou qualquer outra coisa que seja importante.

ja ouvi do falar do livro Introduction to Algorithms, mas não sei se é bom.

Obrigado.

Matheus Luis Ramos de Souza
[MSN]
Andre Brito
JWizard

Membro desde: 21/07/2007 17:44:31
Mensagens: 2485
Localização: Paraná
Offline

Na minha opinião, existem algumas referências básicas:
- Introduction to Algorithms, de Cormen et al (procura no Google que você acha fácil);
- The Art of Computer Programming (são 4 edições, escrito por Donald Knuth) e;
- Concrete Mathematics, de Graham, Knuth e Patashnik.

Além desses, eu recomendo fortemente livros de Matemática Discreta.

Sobre o GoogleCodeJam... São problemas um pouco complexos de passar. Se você está, de fato, começando, eu indico o SPOJ brasileiro e, mais tarde o polonês. Com base nisso e depois de algum tempinho, você consegue tranquilamente resolver problemas no TopCoder. Lá tem problemas de todos os tipos e é mais fácil de submeter (eu acho, pelo menos). São problemas que tem a 'cara' dos problemas do GCJ. Aliás, se você procurar no YouTube por Google Code Jam 2009, vai achar muita gente do TopCoder lá nas finais (o ACRush, o Petr, o tomek e mais alguns venceram no TopCoder Open E no GCJ). No TopCoder tem a parte de tutorial também.

Os livros que citei não têm tipo uma parte só pra problemas de computação. Eles mostram técnicas pra resolver determinados problemas. Se você quer um 'cookbook' de resolução de problemas computacionais, eu sugiro o livro Programming Challenges, que explica as técnicas e dá exemplos de problemas e como resolvê-los. É um livro muito bom e fácil de entender , recomendo fortemente.

Agora, BEM sinceramente, você pode ler todos esses livros sem encostar em um problema de computação. O resultado: você não vai ter muita facilidade em saber como resolver. O que eu quero dizer é que não são text books, não são livros de se ler do começo ao fim e entender tudo. O importante é você se jogar cara... pegar umonte e ir resolvendo, matando um a um. O interessante é, na verdade, você conhecer Teoria de Grafos, Probabilidade, Geometria Computacional e os tópicos abordados no livro do Cormen. Depois disso... Você vai pegar os problemas e vai ver de que tipo eles são (de grafos ou matemática ou geometria e por aí vai). Daí você recorre aos livros. Certo?

This message was edited 11 times. Last update was at 04/09/2009 00:10:01


Como organizar o GUJ.
Meu Twitter.
Meu blog.
Future proofing means making code easy to change, not trying to anticipate every possible way your code might need to change.
[WWW]
Paulo Silveira
Administrador
[Avatar]

Membro desde: 07/08/2002 18:38:50
Mensagens: 4393
Localização: São Paulo
Offline

O Andre Brito deu excelentes sugestoes, e sem duvida o mais interessante de todos para comecar é o do Cormen (3a edicao acaba de ser lancada!).

abracos

http://www.caelum.com.br
Casa do Código - Livros para o Programador
[Email] [WWW]
juliocbq
GUJ Expert

Membro desde: 13/11/2008 12:10:18
Mensagens: 4974
Offline

Os algoritmos, sem sombra de dúvida, são o que há de mais importante na computação. A linguagem de programação é insignificante.

Esses problemas de performance e otimização podem ser resolvidos com Inteligência artificial, sendo mais específico, AGs (Algotitmos genéticos).
Eles são usados, para buscar a melhor resposta, por meio da seleção natural. Com certeza pode otimizar esse tipo de problema que citou logo acima.


teoria
http://pt.wikipedia.org/wiki/Algoritmo_genético
http://www.obitko.com/tutorials/genetic-algorithms/portuguese/

aqui, um pacote escrito em java
http://jgap.sourceforge.net/


espero ter ajudado.
Veneno
JavaGuru
[Avatar]

Membro desde: 12/09/2006 11:36:42
Mensagens: 239
Offline

Muito legal Andre, valeu pelas dicas em.
Já encontrei o Introduction to Algorithms, vou ver se consigo os outros tambem. Vou estudar mais matemática tambem, varios que vi envolvem matemática e se não souber não tem como resolver hehe. Esses sites eu não conhecia, valeu mesmo.
Mais legal tentar resolver esses algoritmos do que fazer sistemas, não é não?rsrs

Abraço.

Matheus Luis Ramos de Souza
[MSN]
Veneno
JavaGuru
[Avatar]

Membro desde: 12/09/2006 11:36:42
Mensagens: 239
Offline

opa, valeu Julio!

Matheus Luis Ramos de Souza
[MSN]
juliocbq
GUJ Expert

Membro desde: 13/11/2008 12:10:18
Mensagens: 4974
Offline

Veneno wrote:Muito legal Andre, valeu pelas dicas em.
Já encontrei o Introduction to Algorithms, vou ver se consigo os outros tambem. Vou estudar mais matemática tambem, varios que vi envolvem matemática e se não souber não tem como resolver hehe. Esses sites eu não conhecia, valeu mesmo.
Mais legal tentar resolver esses algoritmos do que fazer sistemas, não é não?rsrs

Abraço.


Essa é a parte da Ciência da Computação. O objetivo é esse.
Tchello
GUJ Master
[Avatar]

Membro desde: 07/06/2008 14:41:04
Mensagens: 1772
Offline

Julio, muito bem citado Algoritmos Genéticos.
Vi em funcionamento e posso dizer que é fantástico o que se consegue com isso.
Vale lembrar que eles sugerem uma boa solução, não necessariamente A melhor, mas sempre uma boa/excelente/ótima solução.

Abraços.
juliocbq
GUJ Expert

Membro desde: 13/11/2008 12:10:18
Mensagens: 4974
Offline

Tchello wrote: Julio, muito bem citado Algoritmos Genéticos.
Vi em funcionamento e posso dizer que é fantástico o que se consegue com isso.
Vale lembrar que eles sugerem uma boa solução, não necessariamente A melhor, mas sempre uma boa/excelente/ótima solução.

Abraços.


Vi um sistema, em um workshop na faculdade, tem uns 7 anos. Ele usava algoritmos genéticos e lógica fuzzy para estacionar um carro, em uma garagem, sem motorista. O AG calculavam o melhor ângulo das rodas, para o carro iniciar, e fuzzy e sensores faziam o resto.

This message was edited 1 time. Last update was at 04/09/2009 10:33:28

Tchello
GUJ Master
[Avatar]

Membro desde: 07/06/2008 14:41:04
Mensagens: 1772
Offline

juliocbq wrote:
Tchello wrote: Julio, muito bem citado Algoritmos Genéticos.
Vi em funcionamento e posso dizer que é fantástico o que se consegue com isso.
Vale lembrar que eles sugerem uma boa solução, não necessariamente A melhor, mas sempre uma boa/excelente/ótima solução.

Abraços.


Vi um sistema, em um workshop na faculdade, tem uns 7 anos. Ele usava algoritmos genéticos e lógica fuzzy para estacionar um carro, em uma garagem, sem motorista. O AG calculavam o melhor ângulo das rodas, para o carro iniciar, e fuzzy e sensores faziam o resto.

É lindo, não?
O sistema que vi foi pra calcular o jogo das N rainhas, ele sempre trazia um bom resultado com um mínimo de movimentos adotando estratégias distintas em alguns pontos, mas sempre uma ótima solução. O legal é que da pra aumentar o número de gerações e critérios de seleção pra "refinar" o resultado final mas chega num ponto que as variaçõe são mínimas, ainda mais num conjunto tão limitado.
juliocbq
GUJ Expert

Membro desde: 13/11/2008 12:10:18
Mensagens: 4974
Offline

Tchello wrote:
juliocbq wrote:
Tchello wrote: Julio, muito bem citado Algoritmos Genéticos.
Vi em funcionamento e posso dizer que é fantástico o que se consegue com isso.
Vale lembrar que eles sugerem uma boa solução, não necessariamente A melhor, mas sempre uma boa/excelente/ótima solução.

Abraços.


Vi um sistema, em um workshop na faculdade, tem uns 7 anos. Ele usava algoritmos genéticos e lógica fuzzy para estacionar um carro, em uma garagem, sem motorista. O AG calculavam o melhor ângulo das rodas, para o carro iniciar, e fuzzy e sensores faziam o resto.

É lindo, não?
O sistema que vi foi pra calcular o jogo das N rainhas, ele sempre trazia um bom resultado com um mínimo de movimentos adotando estratégias distintas em alguns pontos, mas sempre uma ótima solução. O legal é que da pra aumentar o número de gerações e critérios de seleção pra "refinar" o resultado final mas chega num ponto que as variaçõe são mínimas, ainda mais num conjunto tão limitado.

Isso mesmo, mas um prefessor de ia que tive, sempre me dizia para deixar um gene fraco ter chance de reproduzir. Pois a melhor solução poderia ser ele.
bobmoe
GUJ Ranger

Membro desde: 11/07/2006 20:45:48
Mensagens: 816
Localização: Sampa
Offline

Na época da faculdade eu só estudava o material do professor. Porém, depois que terminei, fui atrás dos livros do Donald Knuth. Putz, é muito difícil! Além disso, pesquisando um pouco mais, descobri que estava perdendo meu tempo, pois tinha muita gente que falava a mesma coisa de forma mais fácil (e eficaz).

Roberto Nogueira
[WWW]
Andre Brito
JWizard

Membro desde: 21/07/2007 17:44:31
Mensagens: 2485
Localização: Paraná
Offline

juliocbq wrote:Os algoritmos, sem sombra de dúvida, são o que há de mais importante na computação. A linguagem de programação é insignificante.

Esses problemas de performance e otimização podem ser resolvidos com Inteligência artificial, sendo mais específico, AGs (Algotitmos genéticos).
Eles são usados, para buscar a melhor resposta, por meio da seleção natural. Com certeza pode otimizar esse tipo de problema que citou logo acima.

Pois então... É um tanto complicado falar nisso... Existem técnicas avançadas de Programação Dinâmica (muita matemática) que resolvem alguns problemas bem básicos, que os AGs também resolvem, mas demoram. O negócio é que surgem tantos problemas com um espaço de busca tão gigantesco que as soluções mais matemáticas ficam estagnadas. Só que existe, ainda, MUITA coisa que a matemática resolve, principalmente com Programação Linear e Não-Linear (e com Dinâmica, Inteira e por aí vai). Para problemas mais complexos (i.e., com um vasto campo de busca, ou seja, infinitas (ou quase infinitas) combinações possíveis), é interessante utiliza técnicas de IA e Computação Natural.

Agora, sobre AGs... Tá defasado. Eu estive em um projeto de pesquisa que envolvia Genéticos e Fuzzy. Além de AGs serem lentos demais, não estão mais encontrando muitos resultados satisfatórios (é até raro encontrar trabalhos que envolvem AG em publicações, mas ainda encontra). O que acontecia foi que não foram encontrados resultados bons com AGs, então inventaram os Algoritmo Meméticos (ou Miméticos, ou ainda Algoritmos Genéticos Híbridos), que nada mais são que um AG com uma busca local (ou seja, aplica novamente um operador, de maneira diferente, visando melhorar o resultado final). Depois disso, surgiram algumas técnicas baseadas na natureza mesmo, como PSO (Otimização por Enxame de Partículas), Evolução Diferencial (esse acho que nem entra na lista), ACO (Otimização por Colônia de Formigas), BSO (Otimização por Enxames de Abelhas) e por aí vai. Outra técnica MUITO importante e que, na minha opinião, é a mais inteligente são os Algoritmos Culturais.

Mas pra resolver os problemas no TC, GCJ e SPOJ não precisa disso não. Só precisa de muito algoritmo e muita matemática. Só.
Essa área é mais interessante que a de IA, na minha opinião.

Abraço.

Bob,
O TAOCP é trash mesmo. O Concrete Mathematics também (pra você ter uma ideia não tem nem sub-tópicos, pra marcar onde ficou uheheh). Mas ainda assim, acho que vale a pena. O do Cormen já é nota 10.

This message was edited 1 time. Last update was at 04/09/2009 12:18:47


Como organizar o GUJ.
Meu Twitter.
Meu blog.
Future proofing means making code easy to change, not trying to anticipate every possible way your code might need to change.
[WWW]
elciok
Entusiasta Java

Membro desde: 02/06/2009 16:28:55
Mensagens: 22
Offline

Queria ver alguém tentando usar algoritmos genéticos no google code jam...
Acho muito legal algoritmos heurísticos, e até escrevi um post sobre algoritmos genéticos, mas acho que esse tipo de solução deve ser sempre a última coisa que você puxa do seu cinto de utilidades, quando você realmente quebrou muito a cabeça tentando arrumar um algoritmo determinístico que encontre de fato uma solução (ou mesmo uma boa aproximação) e você precisa mesmo resolver aquilo. Mas aí você precisa rezar um pouco também, porque eles não funcionam bem para todos os problemas. Acho que muita gente publica trabalhos usando algoritmos heurísticos com a mentalidade "não sei resolver isto, vou jogar em um algoritmo genético para ver se dá certo", e provavelmente às vezes que dá certo a pessoa publica. Não que não seja útil isso, mas é um bocado mais fácil do que o trabalho de alguém que precisa provar teoricamente, usando matemática, que o algoritmo dele funciona.

E sobre o livro do Cormen, também recomendo. Vale a pena vender um rim para ter esse livro se você gosta de algoritmos.

http://tisimples.wordpress.com
Andre Brito
JWizard

Membro desde: 21/07/2007 17:44:31
Mensagens: 2485
Localização: Paraná
Offline

Exatamente, elciok! Pra te falar bem a verdade, o exercício mais difícil que já peguei pra resolver no TopCoder envolvia DFS com Programação Dinâmica. Pra essa parte de maratona e challenges, não precisa de IA.

Como organizar o GUJ.
Meu Twitter.
Meu blog.
Future proofing means making code easy to change, not trying to anticipate every possible way your code might need to change.
[WWW]
 
Índice dos Fóruns » Assuntos gerais necessariamente ligados a tecnologia
Ir para:   
Powered by JForum 2.1.8 © JForum Team