Estudo de algoritmos

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?

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

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

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

espero ter ajudado.

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.

opa, valeu Julio!

Veneno:

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.

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.

Tchello:

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.

juliocbq:

Tchello:

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.

Tchello:

juliocbq:

Tchello:

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.

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).

juliocbq:

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.

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.

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.

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.

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.

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.

Opa Julião.

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…

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.

Andre Brito:

Opa Julião.

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…

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.

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.

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.

E vc, estuda algoritmos pra que?

mochuara:

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.

E vc, estuda algoritmos pra que?

Pode parecer que eu pago pau mesmo pra ele e mimimi, mas não me importo. O negócio é que eu, depois que comecei a resolver problemas e estudar mais algoritmos, deu uma boa melhorada na lógica. Não sei que influência tem diretamente e nem sei o porquê de ajudar, mas a minha maneira de programar melhorou muito.

mochuara, antes de começar tentar resolver esses problemas, também não me interessava e nem via porque estudar. Como o Andre disse para CRUD não precisa. Mas agora que estou estudando algoritmos, fazer sistemas até perdeu um pouco a graça, não sei se é fase, mas acho muito mais interessante algoritmos.

Não é nem questão de fase. Se não se conhece algoritmos não se conhece computação. Eu trabalho com muitos algoritmos, em processamento de imagens, para poder filtrar ruídos, recuperar informações. Transformações de furrier, laplacianos etc…
Precisa saber algoritmos para processar corretamente, e em tempo ótimo. Imagina uma aplicação de segurança que deveria gravar vídeo, mas não gravou porque demorou a processar uma cena?

Quanto ao contemplar as obras de arte os professores das escolas de arte discordam profundamente de sua opinião.

eu andei pensando sobre o tópico que postaram uma vez sobre a revista info, falando sobre fábricas de software. Realmente aquilo é verdade.

Então, tenho a segunda edição do Introduction to Algorithms do Cormen em PDF, mas nunca li ele.
Estava pensando em comprar a terceira edição em papel, acham que vale a pena? A leitura é muito pesada?

Valeu!

Gabriel:

Então, tenho a segunda edição do Introduction to Algorithms do Cormen em PDF, mas nunca li ele.
Estava pensando em comprar a terceira edição em papel, acham que vale a pena? A leitura é muito pesada?

Valeu!

o que é?

o que é?

Eles disseram na reportagem, que os programadores de software não tem noção do projeto, e que são condicionados a repetirem tarefas, que nem peão de obra.
Não havia concordado, mas comecei a pensar e percebi que realmente acontece isso.

Quanto ao contemplar as obras de arte os professores das escolas de arte discordam profundamente de sua opinião.

Eu falei como programador, não como analista de sistema. Qual seria a opinião do artista?

Continuo sem saber como estudar algoritmos me tornaria mais produtivo. Apesar de que na última aplicação que eu desenvolvi tive que criar um algoritmo que me deixou orgulhoso.

Quanto ao contemplar as obras de arte os professores das escolas de arte discordam profundamente de sua opinião.

Eu falei como programador, não como analista de sistema. Qual seria a opinião do artista?

Continuo sem saber como estudar algoritmos me tornaria mais produtivo. Apesar de que na última aplicação que eu desenvolvi tive que criar um algoritmo que me deixou orgulhoso.

Nem analistas de sistemas precisam se preocupar com algoritmos. O trabalho deles não exige isso. O que uma transformação de furrier serviria para eles?

Esse tipo de coisa é para quem trabalha na área de exatas e engenharia.

mochuara:

Continuo sem saber como estudar algoritmos me tornaria mais produtivo. Apesar de que na última aplicação que eu desenvolvi tive que criar um algoritmo que me deixou orgulhoso.

Um amigo meu trabalhava numa empresa que tinha um problema que estava custando muita grana para eles, e duas equipes de analistas, de dois países diferentes não resolviam, deram uma solução meio ruim que levava horas para ser calculada e nem sempre trazia resultados bons. Ele puxou para ele a responsa e usando o que ele conhecia de algoritmos de grafos resolveu o problema deles. Não é uma empresa pequena, é uma multinacional bem conhecida. Se não fosse por ele, a empresa teria duas opções: 1- sentar e chorar; 2- contratar alguns consultores muito caros e que nem sempre resolveriam o problema.
Estudar algoritmos não vai te tornar mais produtivo, mas pode te tornar capaz de resolver algum problema real que ninguém mais tem a coragem de botar a mão. Mas, claro, para ser bem realista, é bem difícil de surgir algo assim no dia a dia de um analista de sistemas comum.

elciok:

mochuara:

Continuo sem saber como estudar algoritmos me tornaria mais produtivo. Apesar de que na última aplicação que eu desenvolvi tive que criar um algoritmo que me deixou orgulhoso.

Um amigo meu trabalhava numa empresa que tinha um problema que estava custando muita grana para eles, e duas equipes de analistas, de dois países diferentes não resolviam, deram uma solução meio ruim que levava horas para ser calculada e nem sempre trazia resultados bons. Ele puxou para ele a responsa e usando o que ele conhecia de algoritmos de grafos resolveu o problema deles. Não é uma empresa pequena, é uma multinacional bem conhecida. Se não fosse por ele, a empresa teria duas opções: 1- sentar e chorar; 2- contratar alguns consultores muito caros e que nem sempre resolveriam o problema.
Estudar algoritmos não vai te tornar mais produtivo, mas pode te tornar capaz de resolver algum problema real que ninguém mais tem a coragem de botar a mão. Mas, claro, para ser bem realista, é bem difícil de surgir algo assim no dia a dia de um analista de sistemas comum.

bem falado.

elciok:

mochuara:

Continuo sem saber como estudar algoritmos me tornaria mais produtivo. Apesar de que na última aplicação que eu desenvolvi tive que criar um algoritmo que me deixou orgulhoso.

Um amigo meu trabalhava numa empresa que tinha um problema que estava custando muita grana para eles, e duas equipes de analistas, de dois países diferentes não resolviam, deram uma solução meio ruim que levava horas para ser calculada e nem sempre trazia resultados bons. Ele puxou para ele a responsa e usando o que ele conhecia de algoritmos de grafos resolveu o problema deles. Não é uma empresa pequena, é uma multinacional bem conhecida. Se não fosse por ele, a empresa teria duas opções: 1- sentar e chorar; 2- contratar alguns consultores muito caros e que nem sempre resolveriam o problema.
Estudar algoritmos não vai te tornar mais produtivo, mas pode te tornar capaz de resolver algum problema real que ninguém mais tem a coragem de botar a mão. Mas, claro, para ser bem realista, é bem difícil de surgir algo assim no dia a dia de um analista de sistemas comum.

Certa vez eu trabalhei num projeto que estava custando muito grana porque tinha um programador que queria de toda maneira resolver o problema utilizando um algoritmo de grafos que ele havia aprendido na faculdade recentemente. Como não foi dada uma solução mais simples para o problema eu tive que chamar a responsa e usei meu conhecimento da Java Collections Framework que resolveu o problema. Essa empresa também era uma grande multinacional.

Putz, provavelmente esse cara que você falou aprendeu a usar um martelo e passou a enxergar prego em tudo quanto é coisa.

mochuara:

Certa vez eu trabalhei num projeto que estava custando muito grana porque tinha um programador que queria de toda maneira resolver o problema utilizando um algoritmo de grafos que ele havia aprendido na faculdade recentemente. Como não foi dada uma solução mais simples para o problema eu tive que chamar a responsa e usei meu conhecimento da Java Collections Framework que resolveu o problema. Essa empresa também era uma grande multinacional.

Vou te dar um exemplo:

Você possui uma lista de cidades, esta lista tmb contém a distância de cada uma delas. Você precisa percorrer todas as cidades pelo caminho mais curto, de maneira a poupar tempo, pois vc usa um avião com pouco combustível e precisa tomar decisões em microsegundos. Como resolveria?

juliocbq:

mochuara:

Certa vez eu trabalhei num projeto que estava custando muito grana porque tinha um programador que queria de toda maneira resolver o problema utilizando um algoritmo de grafos que ele havia aprendido na faculdade recentemente. Como não foi dada uma solução mais simples para o problema eu tive que chamar a responsa e usei meu conhecimento da Java Collections Framework que resolveu o problema. Essa empresa também era uma grande multinacional.

Vou te dar um exemplo:

Você possui uma lista de cidades, esta lista tmb contém a distância de cada uma delas. Você precisa percorrer todas as cidades pelo caminho mais curto, de maneira a poupar tempo, pois vc usa um avião com pouco combustível e precisa tomar decisões em microsegundos. Como resolveria?

Traçaria a rota mais curta entre cada ponto e voaria acima da troposfera pq?

mochuara:

juliocbq:

mochuara:

Certa vez eu trabalhei num projeto que estava custando muito grana porque tinha um programador que queria de toda maneira resolver o problema utilizando um algoritmo de grafos que ele havia aprendido na faculdade recentemente. Como não foi dada uma solução mais simples para o problema eu tive que chamar a responsa e usei meu conhecimento da Java Collections Framework que resolveu o problema. Essa empresa também era uma grande multinacional.

Vou te dar um exemplo:

Você possui uma lista de cidades, esta lista tmb contém a distância de cada uma delas. Você precisa percorrer todas as cidades pelo caminho mais curto, de maneira a poupar tempo, pois vc usa um avião com pouco combustível e precisa tomar decisões em microsegundos. Como resolveria?

Traçaria a rota mais curta entre cada ponto e voaria acima da troposfera pq?

a questão é como.
E dito no problema, você não tem gasolina.
E mais, imagine essa lista com milhões de possibilidades(Uma árvore, para falar a verdade).

juliocbq:

a questão é como.
E dito no problema, você não tem gasolina.
E mais, imagine essa lista com milhões de possibilidades(Uma árvore, para falar a verdade).

É um bom dever de casa, mas pra mim se não vem acompanhado de um modelo de receita não é um problema que vale a pena perder meu tempo. rsrs

mochuara:

juliocbq:

a questão é como.
E dito no problema, você não tem gasolina.
E mais, imagine essa lista com milhões de possibilidades(Uma árvore, para falar a verdade).

É um bom dever de casa, mas pra mim se não vem acompanhado de um modelo de receita não é um problema que vale a pena perder meu tempo. rsrs

juliocbq:

mochuara:

juliocbq:

a questão é como.
E dito no problema, você não tem gasolina.
E mais, imagine essa lista com milhões de possibilidades(Uma árvore, para falar a verdade).

É um bom dever de casa, mas pra mim se não vem acompanhado de um modelo de receita não é um problema que vale a pena perder meu tempo. rsrs

Então fique sabendo que te pagariam $1.000.000, se fizesse um software que resolvesse esse problema em tempo real.
Com certeza você não é um engenheiro, nem cientista da computação. Essa é a diferença entre eles e os analistas.

Se voce analisar, esse valor é pouco.

mochuara:

juliocbq:

mochuara:

juliocbq:

a questão é como.
E dito no problema, você não tem gasolina.
E mais, imagine essa lista com milhões de possibilidades(Uma árvore, para falar a verdade).

É um bom dever de casa, mas pra mim se não vem acompanhado de um modelo de receita não é um problema que vale a pena perder meu tempo. rsrs

Então fique sabendo que te pagariam $1.000.000, se fizesse um software que resolvesse esse problema em tempo real.
Com certeza você não é um engenheiro, nem cientista da computação. Essa é a diferença entre eles e os analistas.

Se voce analisar, esse valor é pouco.

eu estaria feliz com 1 milhão de dólares, por um problema. fora trabalho na nasa ou outra instituição como essa.
Sem querer ofender, mas vc ganha mais que isso?

mochuara:

Certa vez eu trabalhei num projeto que estava custando muito grana porque tinha um programador que queria de toda maneira resolver o problema utilizando um algoritmo de grafos que ele havia aprendido na faculdade recentemente. Como não foi dada uma solução mais simples para o problema eu tive que chamar a responsa e usei meu conhecimento da Java Collections Framework que resolveu o problema. Essa empresa também era uma grande multinacional.

Esse valor mal da pra comprar uma quota do orkut. :lol:

tá certo. rs.

Fala aí galera, estou lendo o livro Programming Chanllenge, tentei submiter os codigos e ta dando resposta errada em um site e em outro erro em tempo de execução, mas acredito que não esteja, alguem sabe como submiter?
Estou achando que o segredo é descobrir como submiter ao inves de resolver o algoritmo rsrs.

Tentei nesses dois sites http://www.programming-challenges.com ou http://online-judge.uva.es

Achei meio estranho a forma de ler os inputs, não se se está certo, segui um exemplo que tem no site.

vlw!!!

Só alguns comentários. Muitas soluções excelentes não poderão ser usadas em challenges como o Google Code Jam nesses eventos também existem severas limitações sobre o tamanho do binário, tempo para o desenvolvimento, etc.

Acho que os algoritmos desenvolvidos lá podem ser considerados um exemplo de técnica, mas não necessariamente um exemplo de boas práticas. Na vida real, você acaba tendo que abrir mão da enxutes e performances absolutas em prol de manutenção, encapsulamento, facilidade de uso, etc.

Além do mais, é bom lembrar que algoritmos são só parte da solução do problema. Decisões arquiteturais são outra parte. Usar os algoritmos certos com uma arquitetura errada pode ser tão prejudicial quanto usar os algoritmos errados numa arquitetura correta.

O bom desenvolvedor deve saber balancear os dois.

Opa VinyGodoy, valeu pela dica! Tava lendo mesmo a respeito disso no livro, ele da varias dicas de como programar em challenges, o que usar o que não usar. Mas a solução que fiz não usei nada de mais, apenas uma recursividade. Estranho esses dois sites, não tem nada explicando o procedimento.

vlw!

Veneno:

Fala aí galera, estou lendo o livro Programming Chanllenge, tentei submiter os codigos e ta dando resposta errada em um site e em outro erro em tempo de execução, mas acredito que não esteja, alguem sabe como submiter?
Estou achando que o segredo é descobrir como submiter ao inves de resolver o algoritmo rsrs.

Tentei nesses dois sites http://www.programming-challenges.com ou http://online-judge.uva.es

Achei meio estranho a forma de ler os inputs, não se se está certo, segui um exemplo que tem no site.

vlw!!!

é 110101 no Programming Challenge e 100 no UVa.

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=36
http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html

fiz em Java.

Acho que o propósito desse problema e ‘pegar’ os iniciantes. Ele parece ser bem inocente mas, na verdade, não é. Se você não usar uma técnica chamada parecida com outra chamada Memoization, ele não passa (passar passa, mas é difícil). Essa técnica de Memoization é bem simples: memorize o que você já fez. Por exemplo, pra calcular o fatorial de 2, o computador resolve bem rápido. 2 * 1 = 2. De 3, também: 3 * 2 * 1. De 10, já parece demorar um pouco mais. Agora imagine de 10000. Demora bastante se você não usar Memoization.

Nesses problemas eles geralmente dizem o maior valor que será entrado De posse disso, você pode criar uma estrutura de dados pra armazenar o resultado dos valores já entrado, não precisando ‘percorrer todo o caminho’. Ainda, no fatorial, se pedissem pra calcular o fatorial de um número gigantesco depois de calcular o fatorial de diversos outros números menores, você pode tirar vantagem disso.

Supondo que n seja a entrada, e 100 (cem) seja o maior valor entrado (geralmente é muito maior, mas dependendo da quantidade de dígitos do resultado você deve usar outras técnicas, como Big Num, mas isso é mais tarde). Você pode criar um vetor de Long (em Java) ou long long em C++. Long porque int não consegue ‘aguentar’ o tranco, ou seja, não consegue suportar a quantidade de dígitos do resultado (alguns chegam a 10, 15 dígitos).

Certo. Criamos o vetor de Long. E agora? Agora, inicializamos as duas primeiras posições dele:

vetor[0] = 1;

vetor[1] = 1;

Agora, basta armazenar o resultado das entradas:

Entrou 2.

vetor[2] = 2 * vetor[1];

vetor[2] = 2;

Entrou 3.

vetor[3] = 3 * vetor[2];

vetor[3] = 6;

Entrou 5:
se vetor[4] for nulo (ou nil, ou 0), pegamos o vetor[3] e fazemos o mesmo procedimento.

Pra entradas pequenas parece ser muito inútil. Mas imagine que você tenha calculado o fatorial de 10 e seja pedido o de 11. Em vez de você fazer 11!, você faz 11 * fatorial de 10. Isso dá MUITA diferença no tempo com que o resultado final é impresso. Acho que mais confundi que expliquei

Tem muito desse tipo de problema. Quando é simples, como o 3n + 1 ou esse do fatorial, é tranquilo de ver que é necessário usar uma estrutura pra memorizar os resultados.

Acho que eu tenho esse problema resolvido (não veja se quiser tentar por si próprio, que é o melhor) num repositório pra códigos no Google Code criado pela minha pessoa. A proposta do repositório era manter a nossa equipe da maratona de programação atualizada, mas ninguém se interessou. Se você andar mais pra trás nos diretórios vai ver que tem alguns problemas resolvidos no SPOJ (na verdade, tem bem pouco no uva). Hoje em dia ando meio sem tempo de resolver, mas quando puder coloco alguns novos lá.

Aliás, outro forum ótimo pra comentar sobre esses problemas é o do spoj. Tem o do uva e o do spoj polonês (que é tudo em inglês) também.

Sobre usar Java, nunca consegui resolver um direito :\ Tanto que aprendi o que sei de C++ pra usar na maratona (e é bem pouca coisa).

Abraço.

Opa André, uia não sabia que tinha que usar as tecnicas certas pra resolver. Entendi o que você falou, realmente faz bastante diferença mesmo, nunca tinha pensado em usar, é simple e bem util né? Vou mudar aqui pra ver se funciona. O duro desse site é que não tem como saber o que aconteceu, se é a sua lógica ou se falta usar alguma tecnica. O bom do GCJ é que ele disponibiliza o input, aí ja da pra ver se é problema de performance pelo menos hehe.
Legal em , voce tem uma equipe pra participar dessas maratonas?

vlw Abraço…

Eu tinha. Hoje ou eles estão muito ocupados ou se desinteressaram. Tem um colega que ainda participa do TopCoder. Acho que ano que vem eu volto a participar deste último.

Alguns sites falam o tipo do erro. Alguns exemplos de erro (tem outros no livro): se o formato da saída está incorreto (tinha que pular uma linha entre cada resposta, por exemplo), se excedeu o tempo limite (TLE - Time Limit Exceed - geralmente precisa de uma ou outra otimização pra diminuir o tempo). Tem alguns erros mais ‘cabreiros’. O SPOJ apresenta também se o erro foi por falha de segmentação (o segfault, que muita gente já se deparou em C e C++).

Na universidade tínhamos uma disciplina complementar que era Maratona de Programação. A gente aprendia todo o embasamento teórico por trás dos problemas - grafos, programação dinâmica, backtracking, etc - e simulávamos maratonas dividindo a turma em equipes de 3 programadores. Foi uma das disciplinas mais proveitosas que cursei.

Inclusive, esse tópico aqui tem links pra sites - alguns já citados aqui - com problemas de computação:
http://www.guj.com.br/posts/list/80031.java

Tínhamos tmb, e posso dizer que não somente essa maratona, como a iniciação científica, são essenciais no curso.

Veneno:

é 110101 no Programming Challenge e 100 no UVa.

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=36
http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html

fiz em Java.

Uma resposta possível para esse problema (descontando o fato que este programa não lê um arquivo) é:

import java.util.*;
class The3n1problem {
    int max;
    public The3n1problem (int max) {
        this.max = max;
        cl = new long [max + 1];
        cl [1] = 1;
    }

    public int cycleLength (int num) {
        long next = num;
        int count = 0;
        while (next >= max || cl[(int) next] == 0) {
            count++;
            next = next % 2 == 0 ? (next / 2) : (3 * next + 1);
        }
        int ret = (int) (count + cl [(int) next]);
        cl [num] = ret;
        return ret;
    }

    public int maxCycleLength (int a, int b) {
        int max = -1;
        for (int i = a; i <= b; ++i) {
            int x = cycleLength (i);
            if (max < x) { 
                max = x;
            }
        }
        return max;
    }
    private long[] cl;

    public static void main(String[] args) {
        The3n1problem t = new The3n1problem (1000000);
        System.out.println (t.cycleLength (1)); // 1
        System.out.println (t.cycleLength (10)); //
        System.out.println (t.cycleLength (22)); // 16
        System.out.println (t.maxCycleLength (1, 10)); // 20
        System.out.println (t.maxCycleLength (100, 200)); // 125
        System.out.println (t.maxCycleLength (201, 210)); // 89
        System.out.println (t.maxCycleLength (900, 1000)); // 174
        System.out.println (t.maxCycleLength (1, 1000000)); // 525
    }
}

Obviamente o pior caso é quando i = 1 e j = 1000000.

Legal pra caramba galera, na minha faculdade infelizmente não tive isso =/. Tenho que aprender agora.

Fiz da seguinte forma, mas ainda não funcionou lá no site, vou desistir desse site hehe…

Map<Long, Long> ciclosRealizados = new HashMap<Long, Long>();

	public void run() {

		ciclosRealizados.put(1L, 1L);

		// segundo numero do intervalo
		long ultimoNumero = 0;
		// primeiro numero do intervalo
		long primeiroNumero = 0;
		long tamanhoMaximo = 0;

		String linha = null;
		while ((linha = Main.ReadLn(50)) != null && linha.trim().length() > 0) {

			linha = linha.trim();
			String[] entrada = linha.split(" ");

			primeiroNumero = Long.parseLong(entrada[0]);
			ultimoNumero = Long.parseLong(entrada[1]);

			if (ultimoNumero < primeiroNumero) {
				long temp = primeiroNumero;
				primeiroNumero = ultimoNumero;
				ultimoNumero = temp;
			}


			for (long i = ultimoNumero; i >= primeiroNumero; i--) {

				long qtdCiclos = calcula(i);

				// recupera o maior ciclo da sequencia
				if (tamanhoMaximo < qtdCiclos)
					tamanhoMaximo = qtdCiclos;
			}

			System.out.println(Long.parseLong(entrada[0]) + " "
					+ Long.parseLong(entrada[1]) + " " + tamanhoMaximo);

			ultimoNumero = 0;
			primeiroNumero = 0;
			tamanhoMaximo = 0;

		}
	}

	long calcula(long numeroAtual) {
		Long numeroOriginal = numeroAtual;
		if (!ciclosRealizados.containsKey(numeroAtual)) {
			if (numeroAtual % 2 == 0) {
				numeroAtual /= 2;
			} else {
				numeroAtual = (numeroAtual * 3) + 1;
			}
			ciclosRealizados.put(numeroOriginal, 1 + calcula(numeroAtual));
		}
		return ciclosRealizados.get(numeroOriginal);
	}

vlw!!

Seu Veneno, o seu programa não vai passar no site porque provavelmente eles usam a entrada (1, 1000000). O seu programa tem problemas de recursividade para um determinado número (que não lembro mais qual é), mas que excede os limites do Java.
Experimente rodá-lo. (É por isso que meu programa não usa recursividade. A primeira versão do meu programa era praticamente igual à sua, até que descobri essa pegadinha de que o Java não aceita muitos níveis de recursividade e esse problema precisa de muitos níveis (talvez mais de 600), ou seja, não pode ser feito de maneira recursiva para uma linguagem que não aceita um número indefinido de níveis de recursividade.

Um analista de sistemas, que foca no desenvolvimento de Sistemas de Informacao com certeza nao precisa ‘perder’ tempo estudando algoritmos para desenvolver sistemas excelentes. O Foco é outro.

Mas a verdade é: um Cientista poderia facilmente substituir um Analista. A recíproca nao é verdadeira.

enantiomero:

Seu Veneno, o seu programa não vai passar no site porque provavelmente eles usam a entrada (1, 1000000). O seu programa tem problemas de recursividade para um determinado número (que não lembro mais qual é), mas que excede os limites do Java.
Experimente rodá-lo. (É por isso que meu programa não usa recursividade. A primeira versão do meu programa era praticamente igual à sua, até que descobri essa pegadinha de que o Java não aceita muitos níveis de recursividade e esse problema precisa de muitos níveis (talvez mais de 600), ou seja, não pode ser feito de maneira recursiva para uma linguagem que não aceita um número indefinido de níveis de recursividade.

Legal!! também não sabia disso não… Quanto mais aprendemos, mais vemos que não sabemos nada.

Uma coisa que queria comentar:
Dei uma olhada no codigo dos caras do codejam, e vi que eles tem varias funções prontas, que podem ajudar bastante nos problemas. Seria bom ter isso né? Pois depois de identificar o problema e saber o que tem que usar (que acho que é o mais dificil), é só executar, já que o tempo é curto.

Obrigado a todos.