Estudo de algoritmos - Assuntos Gerais - GUJ
Veneno 2009-09-03 23:25:19 UTC #1
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.
Andre_Brito 2009-09-03 23:58:15 UTC #2
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?
Paulo_Silveira 2009-09-04 02:09:31 UTC #3
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!).
juliocbq 2009-09-04 09:09:20 UTC #4
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.
http://pt.wikipedia.org/wiki/Algoritmo_genético
aqui, um pacote escrito em java
Veneno 2009-09-04 09:17:12 UTC #5
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
Veneno 2009-09-04 09:18:11 UTC #6
juliocbq 2009-09-04 09:25:25 UTC #7
Essa é a parte da Ciência da Computação. O objetivo é esse.
Tchello 2009-09-04 10:20:40 UTC #8
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.
juliocbq 2009-09-04 10:32:06 UTC #9
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.
Tchello 2009-09-04 10:47:57 UTC #10
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 2009-09-04 11:04:43 UTC #11
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 2009-09-04 12:00:51 UTC #12
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).
Andre_Brito 2009-09-04 12:15:45 UTC #13
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.
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.
elciok 2009-09-04 13:09:55 UTC #14
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.
Andre_Brito 2009-09-04 13:33:03 UTC #15
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.
juliocbq 2009-09-04 14:15:08 UTC #16
Para otimização, os algoritmos genéticos são os melhores, até hoje. Não se pode usar AGs em problemas de busca, mesmo porque ele não foi desenhado para isso, e realmente se torna lento. A arquitetura correta de rede de perceptrons, Fuzzy e Ags resolvem qualquer problema. Para se ter uma idéia, um amigo usou Ags para turbinar a fórmula do COCOMO, na sua pós em engenharia de software. Os ags procuram as melhores equações para ela, e o resultado é superior ao COCOMO. Os orientadores não tinham sequer idéia de que isso era possível.
juliocbq 2009-09-04 14:20:28 UTC #17
IA é usada para resolver problemas do mundo real, sem a intervenção humana. Com certeza não cabe a uma variedade de coisas. No caso desse post, AG seria a melhor opção, ao meu ver.
Andre_Brito 2009-09-04 16:58:10 UTC #18
Opa Julião.
Para otimização, os algoritmos genéticos são os melhores, até hoje. Não se pode usar AGs em problemas de busca, mesmo porque ele não foi desenhado para isso, e realmente se torna lento.
Meça bem suas palavras cara (de boa mesmo, sem ofensa. Espero que não leve pra esse lado). Algoritmo Genético é para otimização E busca. Existe um espaço de busca em um problema que você deseja otimizar o resultado e o AG é o responsável por fazer a busca nesse espaço. Acho que você se referiu em busca em grafos. Daí nem tem porque usar AG: DFS, BFS, Dijkstra, FMB, BigM...
A arquitetura correta de rede de perceptrons, Fuzzy e Ags resolvem qualquer problema.
Não resolvem não. Se resolvessem, P seria igual a NP, concorda? Além disso, o Genético que implementamos ainda não achou o melhor resultado (o resultado dos valores acima da curva ROC encontrado é de 0.70, enquanto que na literatura existem resultados como 0.78 ).
AGs são interessantes. Mas pra determinados problemas (como o de enzimas e proteínas do corpo humano, onde as possibilidades são de 20 elevado a 300, e esse que nos deparamos no projeto), são técnicas válidas, mas não são as melhores. Portanto AG não é a melhor técnica pra tudo. Tanto que até mesmo o AM (memético, que falei anteriormente) pode não achar os melhores resultados. Dessa forma, é necessário testar diversas técnicas de IA pra ver qual destas consegue o melhor resultado.
Vai por mim: programming challenges não requerem IA. AG é uma técnica de otimização e busca, que se enquadra em Computação Natural, que é um campo de Inteligência Artificial.
juliocbq 2009-09-04 17:18:37 UTC #19
[quote=juliocbq]A arquitetura correta de rede de perceptrons, Fuzzy e Ags resolvem qualquer problema.[/quote]
[quote=juliocbq]IA é usada para resolver problemas do mundo real, sem a intervenção humana. Com certeza não cabe a uma variedade de coisas. No caso desse post, AG seria a melhor opção, ao meu ver.[/quote]
Claro que eu concordo com você. Com certeza outras técnicas de ia se adaptam melhores que outras.
Exemplo disso, é o cacheiro viajante, que pode ser resolvido com rna, mas ags resolvem em tempo hábil, se compararmos.
Sei que programming challenges, não requer ia. Mas ia realmente pode ajudar.
mochuara 2009-09-05 16:28:04 UTC #20
Nunca precisei estudar algoritmos gerais, apenas aqueles básicos de introdução a programação. Depois disso, no máximo caia em algum pesquisando pra alguma aplicação que estava desenvolvendo. Mas não me lembro de ter conseguido aproveitar alguma idéia diretamente no meu código. Minha impressão que estudar algoritmos não te torna mais hábil para criar novos algoritmos, assim como contemplar uma obra de arte não te ajuda a formar um artista. Ninguém precisa estar familiarizado com algoritmos prontos para ter criado o page rank por exemplo. Considerando que é muito chato estudar algo que não vou usar no dia a dia (e convenhamos, algoritmo não é bem o que espero estar contemplando), simplesmente não vejo motivos em faze-lo.