Resolvi mudar o meu blog, levá-lo um pouco mais a sério, e dispor de um pouco mais de recursos.
O novo endereço do meu blog é este:
http://crbonilha.com
Layout novo, host novo e até domínio novo!
Os posts que eu julgava mais interessantes foram e alguns ainda serão transferidos para lá.
Não farei mais nenhum post aqui, apenas lá.
Considerem este blog aposentado.
Não vou excluí-lo, porém, pois há bastante conteúdo bacana aqui ainda.
Vejo vocês lá.
Mostrando postagens com marcador Algoritmo. Mostrar todas as postagens
Mostrando postagens com marcador Algoritmo. Mostrar todas as postagens
segunda-feira, 17 de março de 2014
sexta-feira, 15 de novembro de 2013
Inverting Huffman
Pra quem não sabe, semana passada, 9 de novembro, aconteceu a fase final da maratona de programação em toda a américa latina, antecedendo apenas a fase mundial que acontecerá [em breve], e o campeão foi o time Ñtemtempabobagi, da USP.
Mais informações aqui: http://maratona.ime.usp.br/resultados13/
Nesse post vou falar sobre o exercício I da fase final, Inverting Huffman, o qual, curiosamente, ninguém resolveu.
Vocês podem baixar o PDF dele e submeter o código para teste neste link:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=615&page=show_problem&problem=4544
A codificação de Huffman trata-se de uma forma de re-codificar os caracteres de um texto, de modo que o comprimento do código de cada caractere seja proporcional ao seu número de ocorrências no texto. Por exemplo, na palavra "Abacate", a letra 'a' receberia um código curto, pois aparece várias vezes, enquanto todas as outras letras, que aparecem apenas uma vez, iriam receber um código longo.
Mais informações: http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/huffman.html
Ok, mas o que pedia o exercício I da maratona? Para se codificar um texto?
Quase. O exercício trata-se de uma variação bem criativa da codificação de Huffman, na qual, em vez de lhe passar a frequência das letras para que se monte a árvore, passa-lhe a árvore para que se descubra a frequência das letras.
O único requisito para se resolver o exercício é ter um conhecimento de como a árvore é montada, para que seja possível atribuir valores consistentes nos nós, de tal modo que a árvore pudesse ser montada pelo algoritmo de Huffman.
Ok, como ele funciona? No enunciado do exercício há uma explicação do funcionamento do algoritmo de Huffman junto com uma sequência de passos, mas eu vou citar aqui algumas considerações.
- Entenda por "valor" a frequência de ocorrência do caractere no texto. O valor de 'a' acima seria 3.
- Todos os caracteres são folhas, por mais que no exercício não nos preocupemos em si com os caracteres, mas sim com o seu valor e seu nível.
- Os nós que não são folhas são nós criados no decorrer do algoritmo, de tal modo que o seu valor é consequência do valor de ambos os filhos.
- Na nossa lista, sempre haverá no mínimo um par de nós no nível mais abaixo da árvore, a não ser que estejamos no último nó (Figura B).
Vamos ao exercício: Como atribuir consistentemente um valor a um nó folha, de modo que a árvore seja montada da forma especificada? Basta simular o funcionamento do algoritmo!
Lembre-se que se deseja o menor valor possível paraa soma de todos os nós.
Digamos que a entrada do exercício seja:
4
1 2 3 3
A estrutura da árvore ficará assim:
Mais informações aqui: http://maratona.ime.usp.br/resultados13/
Nesse post vou falar sobre o exercício I da fase final, Inverting Huffman, o qual, curiosamente, ninguém resolveu.
Vocês podem baixar o PDF dele e submeter o código para teste neste link:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=615&page=show_problem&problem=4544
A codificação de Huffman trata-se de uma forma de re-codificar os caracteres de um texto, de modo que o comprimento do código de cada caractere seja proporcional ao seu número de ocorrências no texto. Por exemplo, na palavra "Abacate", a letra 'a' receberia um código curto, pois aparece várias vezes, enquanto todas as outras letras, que aparecem apenas uma vez, iriam receber um código longo.
Mais informações: http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/huffman.html
Figura A
Ok, mas o que pedia o exercício I da maratona? Para se codificar um texto?
Quase. O exercício trata-se de uma variação bem criativa da codificação de Huffman, na qual, em vez de lhe passar a frequência das letras para que se monte a árvore, passa-lhe a árvore para que se descubra a frequência das letras.
O único requisito para se resolver o exercício é ter um conhecimento de como a árvore é montada, para que seja possível atribuir valores consistentes nos nós, de tal modo que a árvore pudesse ser montada pelo algoritmo de Huffman.
Ok, como ele funciona? No enunciado do exercício há uma explicação do funcionamento do algoritmo de Huffman junto com uma sequência de passos, mas eu vou citar aqui algumas considerações.
- Entenda por "valor" a frequência de ocorrência do caractere no texto. O valor de 'a' acima seria 3.
- Todos os caracteres são folhas, por mais que no exercício não nos preocupemos em si com os caracteres, mas sim com o seu valor e seu nível.
- Os nós que não são folhas são nós criados no decorrer do algoritmo, de tal modo que o seu valor é consequência do valor de ambos os filhos.
Figura B
- Na nossa lista, sempre haverá no mínimo um par de nós no nível mais abaixo da árvore, a não ser que estejamos no último nó (Figura B).
Vamos ao exercício: Como atribuir consistentemente um valor a um nó folha, de modo que a árvore seja montada da forma especificada? Basta simular o funcionamento do algoritmo!
Lembre-se que se deseja o menor valor possível paraa soma de todos os nós.
Digamos que a entrada do exercício seja:
4
1 2 3 3
A estrutura da árvore ficará assim:
Figura C
O algoritmo de Huffman cria uma lista com os valores de cada nó, e escolhe os dois com os menores valores para criar um nó pai e construir a árvore.
Está vendo aqueles dois nós no nível 3? Se eles estão lá embaixo, devem ter sido escolhidos primeiro na execução do tal algoritmo de Huffman, e, consequentemente, o valor de seus nós deve ser baixo, bem baixo. Que tal 1?
Figura D
O algoritmo de Huffman agora monta-lhes o nó pai, sendo o valor a soma dos nós filhos.
Figura E
Os nós folhas são removidos da lista, e o nó pai adicionado. O algoritmo agora irá escolher os dois nós com o menor valor da lista, e continuar sua execução.
Atente a essa situação da árvore: Que valor poderia ser atribuído ao nó sinalizado de forma que pudéssemos conduzir o algoritmo de Huffman a montar a árvore como planejamos?
Figura F
Se atribuíssimos um valor muito baixo, talvez o algoritmo não tivesse se comportado conforme planejávamos até aquele momento. Por exemplo, se atribuíssemos o valor 2, o algoritmo, no passo anterior, não teria escolhido os nós de valor 3 e 5, mas sim os nós com valor 2 e 3, mudando a estrutura da árvore que esperávamos.
Figura G
Qual seria o menor valor que eu poderia colocar ali então?
O resto eu deixo com vocês.
domingo, 13 de outubro de 2013
Ajude seu General
“Porque recalcular um caminho do
início, se eu já sei metade?”, eis a questão que justifica o
post de hoje.
Figura A
Para os interessados, eu escrevi um
exercício, e o mesmo está disponível para ser resolvido no portal
do URI, no seguinte link:
Ajude seu General foi um exercício
escrito com o propósito de estimular a implementação de formas
mais eficientes de se calcular o famoso caminho mínimo em um grafo,
dado um devido contexto.
Figura A
Todos estamos acostumados com o contexto padrão: Temos um grafo, e nos é requisitado descobrir qual é o caminho mínimo do vértice S até o vértice D (Figura A).
Para isso usamos os nossos velhos amigos DFS, BFS, Bellman-Ford, Dijkstra, entre outros.
Mas e se o contexto mudar um pouco? E
se o nosso grafo fosse dinâmico? E se as arestas pudessem sumir ou
aparecer? Eis o contexto DSSSP (Dynamic Single Source Shortest Path).
Figura B.1
Conforme ilustrado pela Figura B.1, a
remoção de uma aresta pode inutilizar nosso antigo caminho mínimo,
nos forçando a encontrar outro, assim como a inserção de uma nova
aresta (Figura B.2) pode nos apresentar um novo caminho, nos forçando a aos menos
tentar encontrá-lo.
Figura B.2
A primeira vista, não
parece nos restar escolha: devemos recalcular todo nosso grafo,
sempre que uma aresta é inserida ou removida, pois só assim podemos
ter certeza que o nosso caminho mínimo é de fato o caminho mínimo.
Uma coisa é clara: Tal
solução é cara.
E mais: Muito cara.
Figura C
Note que ao remover a
aresta em vermelho, temos que recalcular o caminho mínimo para todos
os vértices, em especial para o vértice D, entre os N vértices do
grafo. Ou seja, custo N (multiplicado pela complexidade do seu
algoritmo preferido).
Note ainda que tal aresta
não compunha o caminho mínimo (caminho em azul). Poxa, fomos
enganados! Recalculamos todo o nosso grafo, e nem precisávamos!
Uma solução mais viável
seria tentar “isolar” um conjunto de vértices que realmente
fossem “afetados” pela inserção/remoção, conforme ilustrado
na Figura D.
Figura D
O fato de não haver uma
aresta direcionada saindo do conjunto B em direção ao conjunto A
torna fácil perceber que há uma imensa diferença entre tais dois
grupos:
a) O caminho mínimo para
qualquer que seja o vértice do conjunto A não foi alterado.
b) O caminho mínimo para
qualquer que seja o vértice do conjunto B pode ou não ter sido
alterado, assim como o caminho mínimo até o vértice D.
Resumindo: Porque recalcular um caminho do início, se eu já sei metade?
Resumindo: Porque recalcular um caminho do início, se eu já sei metade?
Isolamos, então, um
conjunto de vértices “afetados” pela remoção de uma aresta, e
um recálculo sobre tal conjunto me parece uma escolha bem prudente.
A brecha foi aberta, basta
explorá-la. Para isso recomendo lerem o artigo dos cientistas da
computação Ramalingam e Reps, que descreve um algoritmo que aborda
o tema DSSSP, e resolve o problema descrito com eficácia.
http://pages.cs.wisc.edu/~ramali/jl-algorithms.html
domingo, 12 de maio de 2013
Curso do MIT
Essa semana dei de cara com um ótimo curso do MIT, disponibilizado online e o melhor, de graça.
Tratam-se de aulas dadas para um grupo de estudantes do MIT, que cobrem tópicos da ciência da computação, tal como algoritmos clássicos, estruturas de dados, paradigmas de programação, entre outros. As aulas foram gravadas e disponibilizadas no site do MIT, neste link:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/
Há também algum conteúdo na página, tal como alguns exercícios complementares, notas dos autores, e se não me engano, alguns testes.
Os vídeos estão em inglês, porém caso você não entenda o idioma, o youtube consegue traduzir a fala e ativar legendas. É claro que a legenda automática não é perfeita, mas já passou da hora de você estudar inglês, não? Não há desculpa para não falar inglês hoje em dia, visto que boa parte do conteúdo de qualidade está disponibilizado em inglês, o "idioma universal".
Bom, é isso, estudem!
Tratam-se de aulas dadas para um grupo de estudantes do MIT, que cobrem tópicos da ciência da computação, tal como algoritmos clássicos, estruturas de dados, paradigmas de programação, entre outros. As aulas foram gravadas e disponibilizadas no site do MIT, neste link:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/
Há também algum conteúdo na página, tal como alguns exercícios complementares, notas dos autores, e se não me engano, alguns testes.
Os vídeos estão em inglês, porém caso você não entenda o idioma, o youtube consegue traduzir a fala e ativar legendas. É claro que a legenda automática não é perfeita, mas já passou da hora de você estudar inglês, não? Não há desculpa para não falar inglês hoje em dia, visto que boa parte do conteúdo de qualidade está disponibilizado em inglês, o "idioma universal".
Bom, é isso, estudem!
segunda-feira, 22 de abril de 2013
O Algoritmo de Dijkstra
Já ouviu falar do algoritmo de Dijkstra?
O algoritmo de Dijkstra é famoso por resolver o problema de caminhos mínimos em um tempo bem considerável. Haviam outros algoritmos com o mesmo objetivo antes dele, e surgiram mais após ele, mas em questão de complexidade de implementação e testes com o pior caso, ele continua sendo o mais conveniente.
Mas vamos ao que interessa. Em maratonas de programação, é crucial conhecer esse algoritmo e saber implementá-lo em pouco tempo, pois, como diz Steven Halim (uma espécie de gênio, reconhecido por participações na maratona de programação), não basta "lembrar do algoritmo, mas não saber implementá-lo". Um bom maratonista conhece N algoritmos e implementa todos em uma velocidade alta, para que não haja perda de tempo com coisas simples, e sobre mais tempo para os problemas mais difíceis da maratona.
Portanto, você que diz conhecer o algoritmo, se desafie a implementá-lo em em menos de 5 minutos, e caso não consiga, pratique.
Agora, para quem não conhece, trate de estudar. Esse algoritmo cai em muitos exercícios, e sua lógica é muito peculiar, uma vez que abre um novo ponto de vista para quem o aprende.
Aqui estão alguns exercícios do site URI que envolvem o algoritmo Dijkstra:
Fácil:
http://www.urionlinejudge.com.br/judge/problems/view/1148
Médio:
http://www.urionlinejudge.com.br/judge/problems/view/1123
Difícil:
http://www.urionlinejudge.com.br/judge/problems/view/1085
Nota:
Nenhum problema vai estampar na cara que utiliza o algoritmo de Dijkstra, e raramente vai ser uma simples implementação de Dijkstra. Um bom problema vai envolver um pouco de interpretação de contexto, e pequenas modificações em como os grafos são representados e corridos. As vezes também será necessário uma modificação no próprio algoritmo de Dijkstra, como no terceiro caso.
Nota 2:
O algoritmo de Dijkstra faz a busca pelo grafo. A forma como o grafo é montado, é outra história. Nos primeiros dois exercícios citados, os grafos são montados com peculiaridades diferentes, porém o Dijkstra funciona da mesma maneira nos dois casos, uma vez que o grafo está montado.
Em relação ao terceiro exercício, o grafo fica ainda mais complexo, e acredito que uma modificação no Dijkstra se faça necessário. Não tenho certeza, pois ainda não resolvi, mas me disseram que o Dijkstra resolve, então vamos lá.
Por hoje é isso, estudem o Dijkstra, é importante, e no Google tem material sobrando.
Até mais.
O algoritmo de Dijkstra é famoso por resolver o problema de caminhos mínimos em um tempo bem considerável. Haviam outros algoritmos com o mesmo objetivo antes dele, e surgiram mais após ele, mas em questão de complexidade de implementação e testes com o pior caso, ele continua sendo o mais conveniente.
Mas vamos ao que interessa. Em maratonas de programação, é crucial conhecer esse algoritmo e saber implementá-lo em pouco tempo, pois, como diz Steven Halim (uma espécie de gênio, reconhecido por participações na maratona de programação), não basta "lembrar do algoritmo, mas não saber implementá-lo". Um bom maratonista conhece N algoritmos e implementa todos em uma velocidade alta, para que não haja perda de tempo com coisas simples, e sobre mais tempo para os problemas mais difíceis da maratona.
Portanto, você que diz conhecer o algoritmo, se desafie a implementá-lo em em menos de 5 minutos, e caso não consiga, pratique.
Agora, para quem não conhece, trate de estudar. Esse algoritmo cai em muitos exercícios, e sua lógica é muito peculiar, uma vez que abre um novo ponto de vista para quem o aprende.
Aqui estão alguns exercícios do site URI que envolvem o algoritmo Dijkstra:
Fácil:
http://www.urionlinejudge.com.br/judge/problems/view/1148
Médio:
http://www.urionlinejudge.com.br/judge/problems/view/1123
Difícil:
http://www.urionlinejudge.com.br/judge/problems/view/1085
Nota:
Nenhum problema vai estampar na cara que utiliza o algoritmo de Dijkstra, e raramente vai ser uma simples implementação de Dijkstra. Um bom problema vai envolver um pouco de interpretação de contexto, e pequenas modificações em como os grafos são representados e corridos. As vezes também será necessário uma modificação no próprio algoritmo de Dijkstra, como no terceiro caso.
Nota 2:
O algoritmo de Dijkstra faz a busca pelo grafo. A forma como o grafo é montado, é outra história. Nos primeiros dois exercícios citados, os grafos são montados com peculiaridades diferentes, porém o Dijkstra funciona da mesma maneira nos dois casos, uma vez que o grafo está montado.
Em relação ao terceiro exercício, o grafo fica ainda mais complexo, e acredito que uma modificação no Dijkstra se faça necessário. Não tenho certeza, pois ainda não resolvi, mas me disseram que o Dijkstra resolve, então vamos lá.
Por hoje é isso, estudem o Dijkstra, é importante, e no Google tem material sobrando.
Até mais.
domingo, 24 de fevereiro de 2013
Path Finding
Eae, como estão?
Essa semana passei um sufoco tentando implementar um protótipo de jogo de RPG pra android, e me deparei com a necessidade de implementar um esboço de uma inteligência artificial em um personagem.
Se você apenas joga jogos, e nunca imaginou como seria programar um, vou dar uma breve explicação do que seria uma inteligência artificial, a qual você interagiu o tempo todo.
De acordo com o livro 'Programming Game AI by Example', "...se o jogador acredita que o seu adversário é inteligente, então ele é inteligente..." (tradução livre).
Ou seja, se o seu adversário no jogo apresenta ações que são satisfatoriamente coerentes com a situação, então há a impressão de que ele tomou uma decisão inteligente, e a partir dai, ele se tornou inteligente.
Sabe aqueles inimigos nos jogos de luta que se defendem ou até se esquivam de seu golpe? Essa simples ação que o computador executa está contidas no código do jogo, e cada uma é acionada seguindo um padrão, fazendo com que cada ação esteja intimamente ligada com a situação, e simulando ao máximo uma decisão humana, criando assim a ilusão de inteligência.
Esse tópico sobre inteligência artificial ainda vai muito longe, e existem vários livros por aí muito mais coerentes e didáticos do que eu, portanto aconselho-os que os procurem.
O que eu queria falar hoje é sobre o algoritmo Path Finding.
Que algoritmo é esse? Bom, esse é um nome dado a um algoritmo o qual busca por um caminho, desde um ponto (x, y) até outro ponto (x, y) de um mapa, desviando de obstáculos e, em alguns casos, encontrando o caminho mais curto.
Esse tipo de algoritmo é implementado em jogos de múltiplos gêneros, porém com mais ênfase em jogos de RPG.
Ok, mas esse algoritmo é importante ou dispensável? Deveria eu, como programador, prestar atenção a ele ou simplesmente implementá-lo de forma porca?
Na minha humilde opinião, esse algoritmo é importantíssimo, e deveria, assim como qualquer aspecto de seu jogo, ser testado e implementado com cuidado, para evitar bugs.
Quando ele funciona, os jogadores mal notarão, porém quando ele buga, com certeza eles notarão, e como qualquer bug, não deixarão barato. Veja um exemplo do famoso jogo Skyrim, uma super produção que não escapou do bug do PathFinding.
Ok, é importante, mas por onde eu começo?
Bom, me fiz a mesma pergunta alguns dias atrás.
Há algum tempo que eu aprendi um pouco sobre grafos, e conheci um algoritmo chamado A*, o qual na época achei complexo demais.
Essa semana me vi forçado a implementá-lo, e depois de um pouco de suor, consegui.
Aconselho, para aqueles que ainda não conhecem nenhuma técnica, estudem esse algoritmo citado, o A*. Aqui está uma página bem teórica e didática, que explica passo a passo os fundamentos do algoritmo:
http://www.policyalmanac.org/games/aStarTutorial_port.htm
Outro site muito interessante que oferece uma boa explicação, exemplos e até um simulador, é o site do Abrindo o Jogo, nessa pagina: http://abrindoojogo.com.br/inteligencia-artificial-nos-games-%E2%80%93-pathfinding
Bom, acho que isso era tudo que eu tinha pra falar sobre. Caso eu grave o resultado da minha experiência, eu postar aqui mesmo, para que possam ter uma ideia de como ficou.
Até mais.
Essa semana passei um sufoco tentando implementar um protótipo de jogo de RPG pra android, e me deparei com a necessidade de implementar um esboço de uma inteligência artificial em um personagem.
Se você apenas joga jogos, e nunca imaginou como seria programar um, vou dar uma breve explicação do que seria uma inteligência artificial, a qual você interagiu o tempo todo.
De acordo com o livro 'Programming Game AI by Example', "...se o jogador acredita que o seu adversário é inteligente, então ele é inteligente..." (tradução livre).
Ou seja, se o seu adversário no jogo apresenta ações que são satisfatoriamente coerentes com a situação, então há a impressão de que ele tomou uma decisão inteligente, e a partir dai, ele se tornou inteligente.
Sabe aqueles inimigos nos jogos de luta que se defendem ou até se esquivam de seu golpe? Essa simples ação que o computador executa está contidas no código do jogo, e cada uma é acionada seguindo um padrão, fazendo com que cada ação esteja intimamente ligada com a situação, e simulando ao máximo uma decisão humana, criando assim a ilusão de inteligência.
Esse tópico sobre inteligência artificial ainda vai muito longe, e existem vários livros por aí muito mais coerentes e didáticos do que eu, portanto aconselho-os que os procurem.
O que eu queria falar hoje é sobre o algoritmo Path Finding.
Que algoritmo é esse? Bom, esse é um nome dado a um algoritmo o qual busca por um caminho, desde um ponto (x, y) até outro ponto (x, y) de um mapa, desviando de obstáculos e, em alguns casos, encontrando o caminho mais curto.
Ok, mas esse algoritmo é importante ou dispensável? Deveria eu, como programador, prestar atenção a ele ou simplesmente implementá-lo de forma porca?
Na minha humilde opinião, esse algoritmo é importantíssimo, e deveria, assim como qualquer aspecto de seu jogo, ser testado e implementado com cuidado, para evitar bugs.
Quando ele funciona, os jogadores mal notarão, porém quando ele buga, com certeza eles notarão, e como qualquer bug, não deixarão barato. Veja um exemplo do famoso jogo Skyrim, uma super produção que não escapou do bug do PathFinding.
Ok, é importante, mas por onde eu começo?
Bom, me fiz a mesma pergunta alguns dias atrás.
Há algum tempo que eu aprendi um pouco sobre grafos, e conheci um algoritmo chamado A*, o qual na época achei complexo demais.
Essa semana me vi forçado a implementá-lo, e depois de um pouco de suor, consegui.
Aconselho, para aqueles que ainda não conhecem nenhuma técnica, estudem esse algoritmo citado, o A*. Aqui está uma página bem teórica e didática, que explica passo a passo os fundamentos do algoritmo:
http://www.policyalmanac.org/games/aStarTutorial_port.htm
Outro site muito interessante que oferece uma boa explicação, exemplos e até um simulador, é o site do Abrindo o Jogo, nessa pagina: http://abrindoojogo.com.br/inteligencia-artificial-nos-games-%E2%80%93-pathfinding
Bom, acho que isso era tudo que eu tinha pra falar sobre. Caso eu grave o resultado da minha experiência, eu postar aqui mesmo, para que possam ter uma ideia de como ficou.
Até mais.
sexta-feira, 7 de setembro de 2012
Max interval sum
Bom pessoal, eu já fiz alguns exercícios aqui, na verdade dois, onde eu disse que implementei o algoritmo max interval sum, ou, intervalo de maior soma.
Esse algoritmo é bem útil, simples, e é recomendado que vocês tenham ele na sua bagagem de algoritmos.
Caso você ainda não o conheça, acessem esse tópico aqui, da marathoncode, e façam bom uso.
Pode ser útil em:
Bolo de apostas
Mário
Esse algoritmo é bem útil, simples, e é recomendado que vocês tenham ele na sua bagagem de algoritmos.
Caso você ainda não o conheça, acessem esse tópico aqui, da marathoncode, e façam bom uso.
Pode ser útil em:
Bolo de apostas
Mário
terça-feira, 28 de agosto de 2012
Algoritmos variados
Dae pessoal, tudo certo?
Eu tava pesquisando na internet conteúdo pra mim estudar, e então eu ouvi fala desse livro, "Competitive Programming", e acabei entrando no site dele.
Entrando lá encontrei algumas ferramentas muito interessantes, que servem para demonstrar mais facilmente como funcionam determinados algoritmos.
Eu vou deixar aqui o link dos algoritmos de ordenação, que são sempre úteis.
Reparem que existem 5 tipos de ordenação para demonstrar, basta escolher um e clicar em Sort para ver a mágica acontecer.
Existem lá, claro, algoritmos bem mais complexos, que particularmente eu conheço poucos. Vale a pena dar uma conferida, clicando aqui.
Aliás, comprem esse livro, é muito recomendado por ai, basta saber um pouco de inglês, e já era.
Bom, é isso, só queria divulgar isso por hora.
Até mais.
Eu tava pesquisando na internet conteúdo pra mim estudar, e então eu ouvi fala desse livro, "Competitive Programming", e acabei entrando no site dele.
Entrando lá encontrei algumas ferramentas muito interessantes, que servem para demonstrar mais facilmente como funcionam determinados algoritmos.
Eu vou deixar aqui o link dos algoritmos de ordenação, que são sempre úteis.
Reparem que existem 5 tipos de ordenação para demonstrar, basta escolher um e clicar em Sort para ver a mágica acontecer.
Existem lá, claro, algoritmos bem mais complexos, que particularmente eu conheço poucos. Vale a pena dar uma conferida, clicando aqui.
Aliás, comprem esse livro, é muito recomendado por ai, basta saber um pouco de inglês, e já era.
Bom, é isso, só queria divulgar isso por hora.
Até mais.
terça-feira, 14 de agosto de 2012
Bubble Sort (pt.2)
Bom, hoje irei explicar a segunda optimização para o algoritmo de ordenação Bubble Sort.
Recomendo que leiam o primeiro post que explica o básico e a primeira optimização, clicando neste link.
Vamos rever alguns conceitos do algoritmo, para então darmos enfase à segunda optimização.
Vejamos como exemplo a seguinte cadeia de valores: (5, 3, 6, 4, 1).
Se prestarmos atenção, notaremos que existe um valor que é maior que todos os outros, o 6.
Nesta cadeia em particular ele é o maior, apenas mantenham isso em mente.
Agora façamos a primeira varredura, que trará o seguinte resultado: (3, 5, 4, 1, 6).
Notem que o maior número (o 6) foi mandado, já na primeira varredura, para a última posição, posição à qual ele realmente pertence.
Isso faz com que, na próxima varredura, possamos ignorar a verificação da última posição, visto que ela já está ocupada pelo valor correto.
Aí está a optimização.
O fato de ignorarmos o último valor, nos poupará o trabalho de verificarmos algo que já está correto.
Vale lembrar que isso vale para as seguintes varreduras também, ou seja, agora ignoramos o maior valor (6), na próxima varredura traremos o segundo maior valor (5) para a penúltima posição, e então o ignoraremos na próxima varredura, e por aí vai.
Ainda não entendeu a vantagem?
Pense numa cadeia de 100 valores, onde eu precisarei fazer a 50 varreduras, farei a verificação da posição 1 até o 100.
Agora implementamos essa optimização.
A cadeia tem 100 valores, e farei a varredura 50 vezes. Porém agora, a primeira verificação irá da posição 1 até o 100, a segunda vai da posição 1 até o 99, ... , e a quinquagésima varredura irá da posição 1 até o 50 apenas.
Pode não ser algo grandioso, mas de fato é uma economia significativa.
Pode não ser algo grandioso, mas de fato é uma economia significativa.
Bom, é isso aí, como prometido eu expliquei a segunda optimização do algoritmo Bubble Sort.
Caso surjam dúvidas, comentem.
Até a próxima.
segunda-feira, 6 de agosto de 2012
Bubble Sort
Bom, já que ontem eu dei uma boa estudada em algoritmos de ordenação, hoje vou postar o mais fácil (na minha opinião) para aqueles que ainda não conhecem.
Algoritmos de ordenação são muito básicos, e em alguns momentos eles podem ser muito úteis no seu programa.
Do que se trata?
Digamos que você receba uma quantidade N de valores, e você precisa colocá-los em ordem. Exemplo:
Você recebe os valores 4, 3, 6, 2, e 1, nesta mesma ordem, e agora precisa colocá-los em ordem crescente (1, 2, 3, 4, 6), ou decrescente (6, 4, 3, 2, 1).
É aí que entra o algoritmo de ordenação.
Existem vários algoritmos famosos de ordenação, cada um com um método, um nível de complexidade, um tempo de execução, etc.
Hoje eu vou explicar o mais básico, porém muito útil, algoritmo de ordenação, o Bubble Sort, ou, Método Bolha.
Na teoria, o bubble sort escolhe um valor na cadeia de valores e compara-o com o valor seguinte, para descobrir qual deles é maior, ou menor, e troca-os de lugar.
Vejamos um exemplo. A cadeia de valores está nesta ordem {5,3,2}. O algoritmo vai olhar primeiramente o primeiro valor da cadeia (5), e compará-lo com o segundo (3), para descobrir qual o maior. No caso, o primeiro valor é o maior, e como eu quero que a sequência fica em ordem crescente, eu vou trocá-los de lugar. Portanto a ordem agora é {3,5,2}. Logo após esta troca, o algoritmo vai olhar o próximo valor e compará-lo com o próximo do próximo, ou seja, primeiro ele olhou o primeiro e o segundo valor, agora ele vai olhar o segundo e o terceiro. No nosso caso ele vai olhar o segundo valor (5), compará-lo com o terceiro (2), e descobrir qual o maior. Novamente o primeiro valor é maior que o segundo, portanto ele vai trocá-los de lugar. Agora nossa sequência é {3,2,5}. Agora o algoritmo teoricamente iria olhar o terceiro e o quarto valor, correto? Porém vemos que não há quarto valor, portanto nossa primeira varredura chega ao fim. Podemos notar que o maior valor de toda a cadeia está agora em seu devido lugar, no final dela.
Esta foi a primeira parte do algoritmo, a varredura. Porém, como você deve ter notado, a sequência ainda não está em ordem, portanto será necessária mais varreduras. Esta é a segunda parte do algoritmo. Raramente uma varredura será suficiente para organizar a ordem. Mesmo que sejam só 3 valores, 1 varredura não foi suficiente, portanto vamos fazer mais uma.
Começa então a segunda varredura. O algoritmo volta a atenção para o primeiro valor (3) e o compara com o segundo (2). Vendo que o primeiro é maior, ele os troca de lugar, fazendo com que a ordem agora seja {2,3,5}. Agora o algoritmo vai para a próxima posição e faz a verificação. Verifica-se o segundo valor (3), e o terceiro (5). Como podemos ver, o segundo valor é menor que o terceiro, portanto não precisaremos trocá-los de lugar, pois já estão em ordem.
Finalmente, o algoritmo está em ordem {2,3,5}, e não será necessária mais uma varredura.
Aqui entra a primeira optimização do algoritmo: Quando saber que não serão mais necessárias varreduras, e que devo parar de fazê-las?
É muito simples, basta você ter uma variável de controle (recomendo uma variável booleana, ou seja, true or false).
Antes de iniciar a varredura, você ativa uma variável chamada Fim com o valor de True. Agora você inicia a varredura, e caso em algum momento da varredura você precise mudar 2 valores de posições, você também muda o valor da variável Fim para False. Após a varredura estar completa você cria uma condição perguntando se a variável Fim é True or False.
Caso seja True, significa que não houve nenhuma mudança, portanto o algoritmo está em ordem, e nenhuma varredura ou troca será mais necessária.
Caso o valor se False, significa que em algum momento houve uma troca, e ainda não há certeza que todos estejam em ordem, portanto é recomendado uma nova varredura.
Existe outra
optimização deste algoritmo que optimiza o tempo de execução, que você pode conferir neste link.
Caso alguém ainda tenha dúvidas, recomendo que procurem outros tutoriais na internet, e até alguns exemplos.
Um site que contém uma breve explicação e também exemplos em múltiplas linguagens de programação é o wikipédia, neste link.
Espero que tenham gostado da minha explicação, e peço que perguntem caso tenham dúvida, ou se quiserem que eu poste mais algoritmos é só pedi-los. Contanto que eu tenha domínio sobre tal eu o explicarei com todo prazer.
Até a próxima.
Assinar:
Postagens (Atom)