Preciso estudar sempre

Explicações, despedida e um novo começo

2021-02-19T06:16:00.000-08:00

Saudações a você que estiver lendo esta postagem. Faz um tempo que não escrevo, não é verdade ?! Caso você faça parte daquela minúscula parcela do meu público que me acompanhava deve estar estranhando ou até se sentindo surpreso pelo fato de eu estar escrevendo aqui mais uma vez. Fique tranquilo ! Tudo será explicado nesta postagem.

Se pararmos para analisar quando foi a última postagem do Preciso Estudar Sempre, chegaremos a conclusão de que foi em 3 de Dezembro de 2017. De lá pra cá muita coisa mudou, estamos falando de um hiato de mais de 3 anos sem publicações. Mas a pergunta que paira no ar é: porque? Por que parei de publicar ? Por que não soltei nenhuma nota para dizer ao público o motivo pelo qual eu estava sumido ? E, como já diz aquela velha e saudosa marchinha de carnaval: Parou porquê ? Por que parou ?

A resposta é simples, estava envolvido na construção do meu livro. E sim, você não leu errado. A história desse livro é um pouco engraçada porque ela começou da forma mais inusitada possível. Eu sempre quis escrever um livro mas nunca tinha encontrado uma oportunidade, até porque pra quem não é do meio escrever um livro parece impossível. Eu, pelo menos, pensava em um milhão de detalhes como “quem vai publicar ?”, “como vou registrar ?”, “como vou vender ?”, “onde imprimir ?” e etc.

Figura 1 - A capa do meu livro

Quem sempre me acompanhou sabe que teve uma época em que escrevia muito sobre a Teoria dos Grafos. Investi nesse tema por pura vontade, sempre gostei do assunto. Para cada publicação que eu escrevia, eu compartilhava o link dela em vários grupos de desenvolvimento no Facebook. Nessa época o Facebook ainda era a rede social badalada do momento. Essa era a minha forma de fazer a minha própria propaganda. Talvez nisso existisse um erro, talvez devesse investir mais na propaganda do blog, ter levado mais a sério esse ponto em específico. Sempre tive poucos acessos porque não dava a devida atenção a divulgação do conteúdo, eu só postava e compartilhava com aquele pequeno círculo de contatos.

Em um desses compartilhamentos um rapaz comentou na minha publicação dizendo que seria legal compilar as minhas postagens em um livro. Ele estava fazendo mestrado e precisava aprender sobre o assunto. Ele tinha criado uma afeição pelo material que eu produzia. Respondi que tinha interesse em criar este livro mas que não sabia como chegar lá. Então, ele me disse que já estava escrevendo um para a editora Casa do Código e eu automaticamente vi a chance que eu precisava. Pedi a ele um contato para que pudesse vender a ideia do meu livro e montei uma proposta. A proposta foi aceita e dei início a construção do livro. Isso tudo aconteceu em meados de Julho de 2017.

No início não dei a devida atenção que o livro merecia. Escrever um livro é uma tarefa que requer muita disciplina e no meu caso eu tive bastante sorte pois a editora não me cobrava tanto por material. Meu momento de vida naquela época era bastante corrido, tinha acabado de me casar, estava montando meu apartamento com minha esposa e tinha pouco dinheiro. Quem passou por isso sabe como é complicado.

Um outro fator que contribuiu muito para o meu êxito foi o apoio da minha esposa, familiares e amigos. Minha esposa teve um papel fundamental nesse processo pois em 2018 notei que o livro precisava “andar” e que ele não estava tão adiantado quanto eu esperava. Mas também, o que eu esperava ? Que tocar o blog, escrever um livro, ser marido, trabalhar e ter uma vida daria para ser feito todos ao mesmo tempo ? Nem preciso te dizer a resposta, né !?

Então tive que dar um tempo no Preciso Estudar Sempre para poder focar mais no livro e aí entra a disciplina que eu falei. Ficava todo dia depois do trabalho, das 18:00 até às 21:00. Chegava em casa quase às 23:00, era um pouco perigoso, mas eu segui em frente. Minha esposa ficava bastante preocupada comigo. O ano de 2018 foi de muito trabalho e provações porque durante a escrita do meu livro perdi minha avó por parte de pai e meu amado cão. Eles nunca sairão da minha mente e estão na seção de agradecimentos do livro.

Quando acabei de escrever o livro por completo em 2019, pensei: “acabei, agora é publicar né !?”. Mais uma vez errado. Iria ter início a revisão de português e escrita por parte da editora, e só depois de revisado por eles que o livro entraria na esteira para venda. Mas e a revisão técnica ? Quem faria ? Mais um novo desafio à frente.

Entrei em contato com o grande professor Orlando Bernardo da UERJ, aquele que me apresentou a Teoria dos Grafos. Ele disse que não teria como me ajudar devido a questões de tempo. Procurei também um outro professor, Heraldo Luís, da UFRJ, também sem tempo. Entretanto, dele saiu uma indicação, o grande professor Cláudio Esperança e bingo ! Consegui meu revisor técnico. Posso afirmar com toda certeza do mundo que tive sorte porque a vida sempre pôs pessoas muito boas no meu caminho, como essas três citadas acima. Infelizmente perdemos o professor Orlando na vida mundana, mas felizmente ele descansa ao lado do Pai celestial e está de lá ensinando com toda sua didática e carinho pelos alunos.

O professor Cláudio trouxe uma visão completamente diferente para o livro, uma visão mais simplista, mais focada na didática. Isso foi de grande valor até porque minha implementação era muito focada na linguagem de programação, o que trazia complicadores técnicos para um assunto que já é complicado por natureza. Refizemos praticamente a parte técnica do livro por completo, tanto a parte da teoria relacionada a grafos quanto ao projeto desenvolvido com o aluno. Em outras palavras, mais trabalho, especialmente em um ano desafiador pois tinha mudado de emprego em Março.

Depois de muito trabalho e debates técnicos, saí dessa experiência engrandecido tecnicamente e o livro, finalmente, terminado. A última etapa que faltava era mandar para a tal bendita revisão de português. É importante citar outra pessoa que foi crucial neste processo, minha editora chefe Vivian Matsui. A visão dela da obra e a paciência, digna de um monge, foram importantíssimos.

Meu livro foi lançado em Dezembro de 2020 e minha odisséia chegou ao fim, para minha felicidade. Fico muito grato de ter chegado neste ponto da minha vida. Fechei este ciclo de trabalho, empenho e disciplina, e pensei “preciso voltar para o meu blog” até porque o hiato durava mais de 3 anos, né !?

Durante o tempo que fiquei matutando como seria minha volta ao blog, pensei “se é para voltar quero voltar com tudo e fazendo o que eu quero fazer”. Com essa vontade criei o Tech Maida. Por que não continuar com o Preciso Estudar Sempre ? Demorei bastante pensando sobre este ponto e cheguei a conclusão que o Preciso Estudar Sempre representou uma parte da minha vida focada em soluções de desenvolvimento, até porque isso na época ia de encontro com a minha profissão. Atualmente, estou muito mais voltado para arquitetura, então precisava alçar voos maiores, sair um pouco da caixa, sabe !?

Com isso em mente, cheguei a conclusão de criar um blog novo, fora da plataforma do Blogger (que é horrível por sinal), onde lá iria por um conteúdo voltado para minha realidade atual e numa linguagem acessível a pessoas de fora do Brasil. O meu ponto fraco sempre foi a identidade visual, combinar cores é quase uma tortura, CSS nem se fale. Então, também gastei um tempo pesquisando uma plataforma que já me oferecesse coisas prontas sem que eu tivesse que reinventar a roda. Um amigo me indicou o GitHub Pages e a engine dele. Demorei um tempinho para aprender, mas foi, o barco andou.

O Preciso Estudar Sempre continuará existindo e eu continuarei ativo para os leitores dele, tirando dúvidas e respondendo comentários. Não posso ser ingrato e deixar de lado toda essa história. E é isso ! Essa postagem metade despedida metade início de um novo projeto termina aqui. Caso tenha chegado a este ponto do texto te agradeço por ter permanecido tanto tempo lendo o que escrevo, saiba que minhas palavras vem de um lugar de muito carinho.

E-mail: precisoestudarsempre@gmail.com

Projetando aplicações angulares - AngularJS 1.x

2017-12-03T07:37:00.000-08:00

Olá ! Meu nome é João Paulo Maida e bem-vindos ao blog Preciso Estudar Sempre.

Em um mundo de constante evolução e velocidade é necessário saber mudar e se adaptar. Tais características se tornaram decisivas nossas vidas profissionais, e assim como é o mercado de trabalho, também é a vida dos sistemas web. A vinte anos atrás o acesso a internet era raríssimo, era considerado privilégio e os sites eram escassos. Dez anos depois, a internet já era uma realidade assim como a banda larga, jogar e ver vídeos já era possível.

A construção de software voltado para a web também teve uma mudança absurda. A um tempo atrás desenvolver uma aplicação simples com algumas operações requeria uma certa quantidade de páginas HTML, alguns controladores implementados em uma linguagem de programação, usava alguns frameworks e um pouco de JavaScript para controlar o DOM. Se você fosse um cara bom, aprendia até JQuery e fazia a “roda rodar” mais rápida. Mas hoje, isso morreu e porque ?

Como eu disse no início do post, o mundo muda toda hora. Tudo o que tínhamos como idéia de desenvolvimento voltado para web era algo que levava muito tempo. Agora, queremos aplicações velozes, responsivas, fáceis de integrar com outros componentes, leves, multi-plataformas e testáveis. Como atingir tudo isso com velocidade ?

Eis que um novo tipo de aplicações surge: as Single Page Applications. Este novo tipo define que aplicações terão somente uma página aparente ao invés ao invés de várias, como as que conhecíamos até o momento usavam. Quando uso o termo aparente, me refiro a experiência do usuário. Ele terá a impressão de que está em uma única página, assim como são os aplicativos mobile e as aplicações desktop que possuem praticamente uma tela única. Obviamente sabemos que internamente existem várias páginas interagindo e manipulando conteúdo, e é aí que entra uma característica muito forte deste novo tipo, o uso em massa de requisições assíncronas.

Evidentemente estamos falando de AJAX e a esta altura do campeonato esta técnica não é mais uma surpresa. Através deste recurso é possível passar a ideia de que existe somente uma única página responsável por tudo, mas na verdade são várias requisições assíncronas sendo feitas, via JavaScript, para obter conteúdo, trabalhando em conjunto com outras páginas. A consequência disso é um não carregamento total da página, como já conhecido na requisições síncronas, provendo assim uma experiência melhor e uso mais fluido para o usuário. Agora não há mais necessidade de que o usuário tenha que pausar por completo o seu trabalho, pois enquanto um recurso é carregado ele pode executar outras tarefas.

Uma outra característica bem marcante das SPAs é o uso intenso de JavaScript, e isto pode ser justificado pela modernidade dos browsers lançados atualmente e pelo aumento da oportunidade de acesso à internet nos últimos anos. O primeiro fenômeno resulta em um maior poderio de processamento da linguagem, e com uma linguagem mais veloz o interesse em se apoiar mais nela para o desenvolvimento de sistemas aumenta, onde tudo isto é causado pela demanda crescente de acesso à internet. Lembre-se: a primeira porta de entrada para a rede mundial de computadores é um navegador.

Devemos considerar também que o cenário desta linguagem mudou bastante desde de sua concepção. Como já citado acima, antigamente era somente usada para validações de formulário e manipulações do DOM, mas hoje em dia o leque de opções foi expandido devido às inúmeras criações de toda uma comunidade de usuários interessados em recursos mais poderosos e à própria modernização da linguagem.

Uma dessas criações foi a concepção de frameworks, como o AngularJS, que mudam a forma de se construir aplicações para a web e dão vida às Single Page Applications. Este framework possui características bem marcantes como o uso do padrão de projeto MVC como pilar, a incorporação de diversos paradigmas e padrões de projeto, componentização, o alto foco em reuso de código, contextos e um data-binding espetacular. O projeto atualmente tem o suporte da Google, o que lhe dá uma ótima visibilidade para o mercado.

Abaixo temos um exemplo bem simples de uma aplicação AngularJS, que traz conceitos primordiais sobre o funcionamento do framework e analisaremos parte por parte dela para que não façamos confusão.

<!DOCTYPE html>
<html lang="pt" ng-app>
    <head>
        <meta charset="utf-8" /> 
        <meta name="viewport" content="width=device-width, initial-scale=1" />
        <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0-beta.2/css/bootstrap.min.css">
        
        <!-- Angular v1.6.6 -->
        <script src="angular/angular.js"></script>
    </head>
    <body>
        <div class="container">
            <h2>Minha Primeira Aplicação em AngularJS</h2>
            <div class="form-group">
                <label for="nome">Seu nome aqui:</label>
                <input id="nome" ng-model="nome" type="text" class="form-control" />
            </div>
            <div class="form-group">
                Meu nome é: {{nome}}
            </div>
        </div>
    </body>
    <!-- jQuery library -->
    <script src="https://ajax.googleapis.com/ajax/libs/jquery/3.2.1/jquery.min.js"></script>

    <!-- Popper JS -->
    <script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.12.6/umd/popper.min.js"></script>

    <!-- Latest compiled JavaScript -->
    <script src="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0-beta.2/js/bootstrap.min.js"></script>
</html>

O primeiro ponto que deve causar um impacto ao ser visto é o ng-app na tag <html>, após o doctype. O que seria ? Um novo atributo do HTML5 ? Não, meus amigos. Isto é tão pouco pertence ao HTML5 quanto é um atributo, isto na verdade, é uma diretiva, ou em inglês directive, do AngularJS. Impressionante, não ?!

Uma diretiva é uma forma de demarcação de limites de um contexto. Pondo em palavras mais claras, o Angular precisa definir um contexto raiz para criar sua árvore de contextos. Entenda um contexto como uma área de memória. Então, a partir do momento que assinalamos nossa tag <html> com esta diretiva, estamos dizendo ao Angular para marcar esta tag como o elemento raiz da nossa aplicação. Isto nos dá a liberdade de marcar qualquer tag ou a página toda como raiz da aplicação.

Na linha 9 fazemos o import do AngularJS. No exemplo desta postagem estamos utilizando a versão 1.6, mas nada impede que você utilize uma versão mais antiga que esta para aprender os conceitos que estamos discutindo aqui. A partir do momento em que o arquivo é carregado, um callback é registrado para ser executado quando o HTML for carregado por completo. Quando executado, o AngularJS varre a árvore de elementos do DOM à procura da diretiva ng-app. Caso encontre, ele inicializará a aplicação definindo aquele elemento como a raiz.

Dê uma olhada mais abaixo e vá para a linha 16. Mais uma diretiva do AngularJS. Um dos conceitos principais que já vimos acima é o data-binding que o AngularJS realiza. Mas o que seria data-binding ? Traduzindo ao pé da letra, data-binding significaria ligação ou conexão de dados, e é realmente isso que o AngularJS faz. Quando você estabelece uma diretiva ngModel em algum campo HTML de entrada de dados (<input>, <select>, etc.), o AngularJS em tempo de carregamento da página conecta o valor do campo de entrada, no nosso caso um <input>, à uma variável de modelo com o nome especificado dentro da diretiva ngModel e assim mantém os dois em sincronia.

Mas, calma aí, não especificamos nenhuma variável de modelo via JavaScript, como ele realiza essa conexão e mantém essa sincronia ? Ele realiza isso de forma interna, sem que você explicite. Obviamente, que em postagens posteriores veremos como criar controladores via AngularJS e nossas variáveis de modelo, mas agora nos prenderemos ao simples. Essa sincronia é conhecida como two-way data-binding, pois ela é uma via de mão dupla, ou seja, possui dois sentidos. O primeiro sentido já vimos, está na linha 16 e a segunda via está na linha 19.

Imagino que nesse momento mais uma dúvida surja porque o que aquelas chaves estão fazendo lá ? Esta é mais uma característica do AngularJS, conhecida como double-curly binding, e é o segundo sentido de que havíamos conversado. Em suma, representam a outra ponta do two-way data-binding e tornam a sincronia possível. Também aceitam expressões nos moldes JavaScript, que são avaliadas pelo AngularJS e tem seu resultado inserido no DOM. Então, no nosso exemplo, a partir do momento que alterarmos o valor da caixa de texto, uma atualização será feita e exibida abaixo, sem a necessidade de que tenhamos que nos preocupar com isso.

Por último temos que entender como os escopos do AngularJS funcionam porque isso será de grande importância quando você estiver construindo suas próprias aplicações. Existem três coisas muito importantes que acontecem durante a inicialização do AngularJS, são elas:

O injetor ou injector usado para a injeção de dependências é criado.
O injector criará o escopo raiz da aplicação que se tornará o contexto para o modelo da sua aplicação.
O AngularJS irá então compilar o DOM começando no elemento raiz marcado com ngApp, processando quaisquer diretivas e conexão de dados (data-binding) encontradas no caminho.

Uma vez que a aplicação foi inicializada, ela irá então esperar por eventos inesperados do browser que podem mudar o modelo. Uma vez que o evento ocorra, o AngularJS detecta se ele causou alguma mudança no modelo e se alguma mudança for encontrada, o AngularJS irá refletir ela na camada de visão através da atualização de todas as conexões feitas.

De fato, utilizar este framework para o desenvolvimento de SPAs é um fator que torna o processo de construção de um sistema bem veloz, pois como vimos com este simples exemplo, é possível fazer bastante com pouco. Porém, sua curva de aprendizado é bem pesada pois além de trabalhar com diversos padrões de projeto, como factory, injeção de dependências, inversão de controle, MVC, e etc., ele lida com invocações de web services, componentização, entre outros. Então, meu conselho para você que não tem esses conhecimentos tão amadurecidos na sua cabeça é, estude primeiro a teoria para não sair por aí construindo Frankensteins que irão te perseguir até o seu túmulo.

Evidentemente que eu dei uma limpada nos detalhes do framework, mas se eu trouxesse todos eles, a leitura se tornaria impraticável. Por tal motivo recomendo, uma leitura no guia de desenvolvimento ou no roteiro da API.

Como vocês já sabem, todos os links de referências e de download do projeto estão abaixo.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Recomendação de livro: Clean Code - A Handbook of Agile Software Craftsmanship

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

Download no GoogleDrive: clique aqui

Download no Dropbox:

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências:

Single Page Applications e outras maravilhas da web moderna - https://imasters.com.br/desenvolvimento/single-page-applications-e-outras-maravilhas-da-web-moderna/?trace=1519021197
Single Page Applications - https://www.codeschool.com/beginners-guide-to-web-development/single-page-applications
Tutorial AngularJS - https://docs.angularjs.org/tutorial/
Guia de desenvolvimento AngularJS - https://docs.angularjs.org/guide
Documentação AngularJS - https://docs.angularjs.org/api

Recomendação de livro: Clean Code - A Handbook of Agile Software Craftsmanship

2017-11-23T04:05:00.000-08:00

Olá ! Meu nome é João Paulo Maida e bem-vindos ao blog Preciso Estudar Sempre.

O livro que venho recomendar aqui hoje é um dos integrantes do hall de ouro da literatura do desenvolvimento de software. Ele compõe a base do que eu costumo chamar de “fonte de conhecimento”. Tenho este costume pois gosto de acreditar que quando estou em contato com este tipo de obra, estou me servindo diretamente da fonte e isto, para mim, é importantíssimo.

Assim como Indiana Jones perseguiu em uma das suas aventuras a fonte da juventude eterna, acho que é de igual importância a perseguição por conhecimento puro em nossas áreas de interesse. Quando digo puro, me refiro as obras iniciais que serviram como base para outros escritores construírem, posteriormente, suas contribuições.

Não sejamos radicais nesse momento. Evidentemente não estou dizendo que as outras obras que existem por aí não servem ou não são boas. Cada trabalho tem sua contribuição no mundo, como por exemplo, o ponto de vista do autor ou a forma de escrita usada no assunto. Porém, é perigoso se ater somente a esses autores. Pego esta situação e aplico à mim.

Possuo quase dez anos na área de T.I. e passei por diversas áreas, como infra-estrutura, desenvolvimento e qualidade e arquitetura. Imagine se eu me satisfizesse somente com os primeiros livros que li. O que aconteceria ? Uma coisa é certa, eu não possuiria o conhecimento que possuo hoje e provavelmente não teria chegado onde cheguei. Ter lido diversas obras sobre o mesmo assunto ou sobre coisas que eu já sabia, deu a mim o mecanismo da crítica e análise, pois eu conheci vários pontos de vista diferentes.

Isto é de imensa importância. Imagine um profissional com trinta anos de carreira onde ele conhece só uma perspectiva do que faz ? Evidentemente é uma pessoa limitada. Dele ou dela não virão soluções fantásticas e o motivo é claro. Quando não há uma preocupação em se beber direto da fonte criadora do assunto, possuir um raso entendimento e, consequentemente, limitado, é uma questão de tempo.

O livro Clean Code - A Handbook of Agile Software Craftsmanship é das fontes quando o assunto é código limpo. Ele introduz no leitor a idéia do software como uma criação artesanal e cíclica. Isto se traduz em tratar um software com o mesmo cuidado e esmero que um artesão trata sua obra de arte. O resultado deste processo é um código limpo e de alta qualidade, pois a construção de um requer uma análise repetitiva, ou seja, o que você fez hoje pode melhorar amanhã.

Figura 1 - Capa do livro

Apontar um único ou um grupo de capítulos seria complicado porque todos são excelentes. Eu li da primeira até a última página, e em todas eu aprendi técnicas e vi reflexões que me deixaram de boca aberta. O que mais me impressionou nesta leitura foi o toque humano que o autor possui em abordar os problemas. Quando digo “humano”, quero dizer que ele narra as dificuldades e dúvidas que teve de uma forma que me faz pensar que eu já passei o mesmo, me identificando assim com ele.

Isto é deveras importante, pois quando se lê uma obra de altíssima qualidade escrita por uma referência no assunto, no nosso caso Robert C. Martin (a.k.a Uncle Bob), a tendência é a idolatria ao autor e um afastamento da sua imagem à dele. Contudo, a partir do momento em que você lê sobre os mesmos problemas e questionamentos que ele já passou e que você tem ou teve, pensa: “cara, ele é tão humano quanto eu”. Neste momento você se identifica e se aproxima.

Minhas considerações finais são:

Leia o livro todo e não somente uma vez. Leia toda vez que sentir vontade ou esquecer algo porque você sempre vai aprender algo novo ali.
Tente sempre procurar beber da fonte sobre um determinado assunto que te interesse, mas faça isso sem ignorar as contribuições já feitas posteriores a contribuição do criador.
Lembre-se que todos os gigantes da orientação a objetos (Robert C. Martin, Erich Gamma, Martin Fowler, Kent Beck, etc.) se conhecem ou se citam. Então dê uma olhada nas obras citadas ao longo do texto, você vai aprender bastante ali.
Tente sempre encontrar a obra em questão em seu idioma original para que você não tenha problemas com traduções, como perda de informações. Mas caso você tenha problemas com línguas estrangeiras, leia a versão traduzida, é melhor que nada.

Abraços !
Até a próxima minha boa gente ! 😘 Leia nossa postagem anterior: Aprendendo a escolher bem o que por em ordem - O algoritmo Selection Sort Dúvidas !? Sugestões ?! Críticas ou elogios ?! Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook. E-mail: precisoestudarsempre@gmail.com Facebook: https://www.facebook.com/precisoestudarsempre/ Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Aprendendo a escolher bem o que por em ordem - O algoritmo Selection Sort

2017-10-11T05:06:00.000-07:00

Olá ! Meu nome é João Paulo Maida e bem-vindos ao blog Preciso Estudar Sempre.

Ordenar é de fato uma tarefa que às vezes nos deixa de cabelos em pé. Na literatura existem vários algoritmos que podem nos ajudar, cada um com suas características. As opções são tantas que o problema muda de achar uma solução para qual solução escolher.

Como já vimos aqui em várias situações, o que vai determinar a solução necessária para um certo problema é, de fato, o problema. Logo, se velocidade é o seu problema vá para o Quick Sort, mas se o problema for lidar com partes já ordenadas, use o Insertion Sort (clique aqui para dar uma lida), e assim segue.

Um dos algoritmos primordiais ensinados, seja na faculdade ou no cursinho técnico, é o Bubble Sort (clique aqui). Ele, junto com Insertion Sort e Selection Sort, compõem uma categoria conhecida como “Algoritmos de ordenação simples”. Não vá achando que simples signifique inútil. Ao contrário, esses algoritmos servem como base para algoritmos mais complexos como Quick Sort, Merge Sort e Shell Sort. O que difere a categoria dos básicos para dos complexos são as técnicas e estruturas de programação utilizadas.

Nosso foco hoje será exclusivamente o Selection Sort para assim fechar a categoria dos simples. Abordaremos seu conceito, sua implementação e características.

Imagine que exista uma fileira de lápis que possuem vários tamanhos e você quer por eles em ordem porque, assim como eu, tem TOC.

Figura 1 - Lápis desordenados

Para ordenar esses lápis utilizando a técnica do Selection Sort marcamos o primeiro lápis (à esquerda) com um marcador indicando que aquele é o menor lápis encontrado no momento. Após isso, verificamos um após o outro até o fim, a fim de encontrar algum lápis menor. Quando encontrado, é marcado como o menor lápis encontrado até o momento, mas a busca continua até o fim do conjunto. Caso algum lápis menor ainda seja encontrado, o marcador é movido para este. Caso contrário, a troca já pode ser feita e, o ciclo de ordenação do primeiro lápis está concluído. O marcador vai para o segundo lápis do conjunto.

No exemplo acima, o menor lápis encontrado em uma primeira instância seria o quarto, porém finalmente o sétimo seria revelado como o menor de todos. Os marcadores iriam ser movidos do primeiro para o quarto e posteriormente para o sétimo. Após finalizado o ciclo, o marcador voltaria para o segundo lápis para assim iniciar um novo ciclo, e este processo se repete até o conjunto todo estar ordenado.

A Figura 2 é um GIF animado que mostra todo o processo sendo feito.

Figura 2 - Funcionamento do algoritmo SelectionSort

Visto que já cobrimos toda a parte teórica do assunto, podemos partir para a prática.

Quem acompanha o blog sabe que eu sempre escolho a linguagem Java como alvo das minhas implementações, mas como o grande Mário Sérgio Cortela já diz:

Mudar é complicado mas acomodar é perecer (Cortella, Mário Sérgio).

Vamos implementar o nosso algoritmo em Javascript, afinal de contas é uma linguagem que funciona em todos os navegadores de todos os dispositivos, sejam eles computadores, notebooks, celulares ou tablets; e não é necessário um ambiente tão complexo de execução igual ao do Java.

for(out=0; out<qtd-1; out++){
    marcador = out;                             //primeiro elemento marcado
    for(ins=out+1; ins<qtd; ins++){             //varro os itens a direita procurando o menor de todos
        if(valores[ins] < valores[marcador]){   //encontrado item menor ?
            marcador = ins;                     //move o marcador
        }
    }
    _trocar(out, marcador);                     //acabaram os dois laços então posso fazer a troca
}

(LAFORE, ROBERT)

Note que o algoritmo é bem simples, não há nada extremamente complexo. Os dois laços for orquestram o processo descrito nos parágrafos acima. O primeiro começando do início e o segundo iniciando a partir do ponto de partida do primeiro, ou seja, se o primeiro laço começa em 0, o segundo começará em 1. Contudo, note que o primeiro laço só vai até qtd-1, porque ? Porque não ir até qtd ?

A resposta é simples se pararmos para analisar a situação como um todo. Com as consecutivas trocas dos valores, os maiores (no caso de ordenação crescente) são sempre jogados para o fim e o maior valor terá seu lugar trocado com alguém menor que ele, ocupando assim o último lugar. Por tais motivos não é necessário que o laço mais externo percorra todas posições do array.

Os nomes das variáveis controladoras de laço foram escolhidas devido ao fato de existirem um laço externo e um interno, logo respectivamente out e ins. O resto do código está bem claro e dispensa maiores explicações.

A ordenação por seleção executa o mesmo número de comparações que a ordenação pelo método bolha: N*(N-1)/2. Para grandes valores de N, os tempos de comparação predominarão, portanto a ordenação por seleção executa em tempo de O(n²), exatamente como a ordenação em bolha. Contudo, ela tende a ser bem mais rápida porque há poucas trocas. Para valores menos de N, a ordenação por seleção pode ser de fato mais rápida, especialmente se os tempos de troca forem muitos maiores que os tempos de comparação (LAFORE, ROBERT).

Chegamos ao fim de mais um post meus amigos. Espero que tenham gostado. Caso tenham sentido falta de algum detalhe, deixe nos comentários.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Cuidado com os comentários, eles são perigosos !!!

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

Download no GoogleDrive: clique aqui
Download no Dropbox: clique aqui

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

Cortella, Mário Sérgio; Mudar é complicado? Acomodar é perecer.; https://www.youtube.com/watch?v=Ry3_5Pl8qmk

LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004

Cuidado com os comentários, eles são perigosos !!!

2017-09-29T06:29:00.001-07:00

Olá ! Meu nome é João Paulo Maida e bem-vindos ao blog Preciso Estudar Sempre.

Mamãe sempre me disse que comentários são perigoso, e você já comentou o seu código alguma vez na vida ? Já se pegou escrevendo algo do tipo “aqui verifico se é diferente de nulo para não dar erro” ou “se condição igual true é porque idade é maior de 18” ? Se sim, não se desespere pois essa prática é muito comum para quem desenvolve software, porém não é uma das melhores e afirmar isso é o que realmente assusta a maioria das pessoas.

Figura 1 - Cuidado com comentários, eles são perigosos !!!

Mas como um simples comentariozinho seria algo tão grave assim ? Muitos podem afirmar que o que estou dizendo é non-sense ou bobagem, já que comentários são ignorados em processos de compilação. Entretanto, devemos nos lembrar que antes de estarmos escrevendo “linguagem de máquina”, estamos escrevendo texto que outros poderão ler. De que adianta para um autor escrever um livro que ele só entende, ou escrever um livro que para cada parágrafo ele precisa explicar o que realmente ele quis dizer ?

Se ele precisou explicar através de um comentário qual era sua verdadeira intenção, então ele falhou em escrever o texto pois o próprio por si só não consegue ser expressivo bastante para passar sua própria ideia. Em miúdos, podemos concluir que um código-fonte de qualquer linguagem que falhe em passar seu próprio propósito de existência para qualquer leitor é um código defeituoso.

Neste momento espero ser apedrejado até a morte !!!

Figura 2 - Eu sendo cruelmente apedrejado

Bom, se você está lendo isto é porque ainda não fui apedrejado 👌.

Então se você se encaixa no que disse acima, você produz um código defeituoso. Um software deve ser escrito de forma que outros possam lê-lo como se fosse um livro, suavemente. As intenções de todos os elementos, desde daquela minúscula variável até aquela classe mega complexa, devem estar claras ao ponto de que com uma simples passada de olhos um outro programador que nunca tenha visto aquilo possa entender ou ter uma ideia do que está sendo feito.

Como disse no início do texto, esse assunto sempre gera muita discussão, mas é uma das principais métricas quando o assunto é código limpo. Se a sua intenção é, assim como a minha, o self-improvement, ou seja, crescimento pessoal, não se ofenda com o fato de que o código que produz não ser tão bom quanto pensava. Eu já passei pelo mesmo, me surpreendi várias vezes e reaprendi coisas que eu já achava que sabia. Acredito que faz parte passar por isso, quem consegue aprender sem errar ?

O livro que abriu minha mente para a produção de um código mais limpo e expressivo foi o Clean Code, escrito por Robert C. Martin, conhecido também pelo apelido Uncle Bob. Um grande amigo me apresentou a obra e me emprestou o seu livro em português. Comecei a ler e fiquei abismado com a riqueza de detalhes que o simples nome de uma variável pode ter. Depois de um tempo abdiquei do livro emprestado por questões de mobilidade, e baixei o PDF para meu celular. Todo momento livre que eu tenho dou uma lidinha nele, nem que seja cinco minutos. Ele é aquele tipo de livro que você tem que ler várias vezes porque no fim das contas você sempre aprende algo novo.

Existe um capítulo dedicado sobre o estudo de comentários (capítulo 4), onde são abordados assuntos como consequências de um código comentado, categorização, como programar sem comentar, bons e maus comentários, entre outros. O que estamos discutindo aqui é somente uma fração do que o livro cobre. Logo, para mais detalhes dê uma lidinha neste capítulo, vale bem a pena 😊. Deixarei um link para download no fim do post.

Figura 3 - Clean Code escrito por Robert C. Martin

Não pense que sou contra Javadocs, sou muito a favor inclusive. Mas um Javadoc é algo completamente diferente de um comentário explicativo de uma linha de código, e mesmo assim se o Javadoc ferir algumas regrinhas que o livro aborda, então ele possui problemas. Adiante veremos um exemplo de código com o que considero um comentário ruim.

public class BadComment {
    /*valores*/
    private final int[] valores = {1,2,3};
   
    private void verificarValores(){
        //verifico se existem valores
        if(valores.length>0){
            System.out.println("Tem valores !!!");
        }
    }
   
    public static void main (String[] args){
        new BadComment().verificarValores();
    }
}

Para um tempinho e olhe bem a amostra de código acima. Me diga, para que raios uma pessoa cria um comentário (linha 2) com o mesmo nome do atributo da classe ? Pra que isso serve ? Do que adianta ? Qual vantagem traz ? Sinceramente, nunca consegui responder tais questões e já vi isso acontecer várias vezes.

Calma porque ainda vai piorar !

Um outro programador começou a trabalhar nessa classe e resolveu mudar de lugar o atributo valores mas esqueceu de levar o comentário junto. Olha só o que aconteceu.

public class BadComment {
    /*valores*/
    
    private void verificarValores(){
        //verifico se existem valores
        if(valores.length>0){
            System.out.println("Tem valores !!!");
        }
    }
    
    private final int[] valores = {1,2,3};
    
    public static void main (String[] args){
        new BadComment().verificarValores();
    }
}

Agora quem for trabalhar em cima dessa classe vai ficar confuso. Porque existe esse comentário na linha 2 ? O que ele está fazendo aí ? Essas são umas das perguntas que são feitas quando isso acontece. Tal fenômeno leva os programadores ao medo, pois é criado o receio de que se algo é mudado o sistema inteiro pode parar em produção. Um sistema que não pode sofrer alterações ou testes está doente.

Analise agora o comentário da linha 5 da amostra acima. Qual é a expressividade que ele nos traz ? Obviamente, ele explica o que está sendo feito e pode até ajudar em uma primeira instância. Porém, e se alguém mudar a instrução if da linha 6 de lugar ou mudar a condição ? Será que o comentário vai acompanhar a mudança ? Senão acompanhar, será que uma outra pessoa vai entender que ali havia uma verificação, ou talvez se a que existe ali condiz com o respectivo comentário ? Note que a teia de dúvidas não pára de ser tecida, está na hora de dar um basta nisso.

public class BadCommentConsequence {
    
    private final int[] valores = {1,2,3};
    
    private void verificarValores(){        
        if(temValores()){
            System.out.println("Tem valores !!!");
        }
    }        
    
    private boolean temValores(){
        return valores.length>0;
    }
    
    public static void main (String[] args){
        new BadCommentConsequence().verificarValores();
    }
}

Nossa classe deve ficar como mostrado acima. Antes de tudo, adeus para comentário de atributo, isso não faz o menor sentido. Um atributo ou uma variável deve mostrar o motivo de sua existência através de seu nome e não por um comentário.

O comentário da linha 5 também foi embora e a condição do if possui um método próprio com um nome bem expressivo, que mostra qual é o motivo dele estar ali. Agora sabemos que somente será impresso algo no console quando existirem valores. A consequência dessa refatoração é uma leitura muito mais limpa e simples.

Conclusão: Um código bem feito, limpo e enxuto passa muito significado. Esse é um dos fatores mais importantes no desenvolvimento de software e uma das maiores preocupações que devemos ter se nossa intenção é produzir um bom trabalho.

Não se preocupa em errar, todos erram ou erraram um dia. Saber que errou e permanecer no erro que é o verdadeiro problema. A construção de um bom código requer um ciclo de revisão contínuo, ou seja, o que você fez hoje pode ser melhorado amanhã .

O livro apresentado é uma das referências no assunto. Selo de recomendação de leitura do Maidão.

Terminamos mais um post !! 😀

Espero que você tenha gostado. Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Ausência do blog e férias

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

Download no GoogleDrive: clique aqui
Download no Dropbox: clique aqui

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

Ausência do blog e férias

2017-09-20T06:29:00.000-07:00

Olá ! Meu nome é João Paulo Maida e bem-vindos ao blog Preciso Estudar Sempre.

Você deve ter notado que eu dei uma parada nas postagens, uma sumida. Sim, eu estava de férias. Estava recarregando minhas baterias, descansando minha cabeça para voltar com potência total com novos assuntos e motivação lá nas alturas. Se você sentiu minha falta nesse período, fico feliz com sua preocupação e carinho até porque é isso que mantém nos trilhos e trabalhando.

Minhas férias foram repletas de novas descobertas, aprendi muito e me reinventei. Pensei sobre diversos pontos, um deles é a trajetória do blog. Devo confessar que senti uma pontada de vontade de engavetar o blog, dar uma parada, descansar mais. Contudo, tenho certeza de que essa seria uma péssima escolha, a qual iria me arrepender profundamente no futuro. O laço, que com muito custo consegui construir com vocês, leitores, é muito importante. Foram anos de dedicação em trazer novos assuntos e de esforço em divulgar o material aqui publicado. A consequência disso são os poucos porém valiosos comentários que tenho de pessoas reais dizendo que de fato eu ajudei elas. Isso, meus amigos, não tem preço.

Ter uma visão voltada para o futuro do blog se faz necessária nesse momento e para haver um futuro é necessário entender o passado, acredito. Um dos pilares que sustenta a idéia do blog é a vontade de se estudar qualquer assunto. Então, pense nas antigas civilizações e o quanto ainda temos que aprender com elas.

Os egípcios, por exemplo, são mestres na arte da engenharia e seu legado possui valor inestimável para a humidade. Contudo ainda existem questões não respondidas. Mais uma vez estamos diante do mesmo questionamento, é necessário entender o que aconteceu milhares de anos atrás para poder entender o presente e pensar em um futuro. Então é isso o que precisa ser feito aqui e agora.

Não quero me estender muito neste assunto até porque esse não é objetivo desta publicação e não temos tempo a perder. Esta declaração é apenas uma satisfação que acho que vocês, leitores, merecem por uma questão de consideração. Feito isso, me despeço e peço que aguardem pois novidades estão por vir.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Um roteiro para o estudo da teoria dos grafos

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Um roteiro para o estudo da teoria dos grafos

2017-08-03T11:35:00.000-07:00

Olá ! Meu nome é João Paulo Maida e bem-vindos ao blog Preciso Estudar Sempre.

Parabéns !!! 🎇🎇🎇🎈🎉🎉🎊

Você chegou ao fim de uma incrível jornada, passou e superou diversas intempéries e fez descobertas espetaculares, você merece estar aqui. Sinto neste momento muito orgulho de você.

Se esta é a sua primeira visita neste blog e não está entendendo muito bem o que está acontecendo, não se desanime e continue lendo pois logo vai entender.

Já parou para pensar que é de extrema importância existir, aqui no blog, um catálogo bem resumido e enxuto voltado para o estudo da teoria dos grafos ? Isso nunca foi feito antes. Uma forma de deixar um passo-a-passo, um guia, para as pessoas que estão perdidas e não sabem por onde começar. Se você acha que isto é uma bobeira, está enganado meu caro. Tal possui tanta importância assim como os assuntos já vistos aqui. Na verdade, na minha opinião, a internet carece de tal iniciativa a fim de facilitar a vida de pessoas que estão tentando entrar neste nova área de conhecimento.

Então, sem mais delongas, lhes apresento um guia feito por mim para o estudo da teoria dos grafos.

Se você quer um entendimento sólido e básico sobre o assunto, recomendo fortemente que siga de forma ordenada as etapas enumeradas. Todas foram feitas com muito carinho e esmero. Explicações detalhadas, exemplos e imagens são apenas uma mera fração da imensidão de conhecimento contido nestes tópicos.

Caso você seja um amante da matemática assim como eu, especialmente da teoria dos grafos e fique triste por termos chegado ao fim desta série. Entendo sua situação. Porém pense que seria muito complicado prender o blog e seu público somente a este assunto sabendo que há uma vastidão de assuntos ainda não explorados mas nada impede que futuramente entre em pauta novamente.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: O princípio da responsabilidade única - S.O.L.I.D

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

O princípio da responsabilidade única - S.O.L.I.D

2017-07-24T07:53:00.000-07:00

Olá ! Meu nome é João Paulo Maida e bem-vindos ao blog Preciso Estudar Sempre.

Pare por um instante e reflita sobre a seguinte frase:

Uma classe deve ter somente um único motivo para mudar. (MARTIN, ROBERT; MARTIN MICAH)

Este é o princípio da responsabilidade única (Single-Responsibility Principle - SRP em inglês) e se você for um iniciante no mundo da programação e achar esta declaração estranha, não se espante. Este conceito não é banal e tampouco é ensinado na faculdade, logo sua reação é normal. Na verdade, são poucos os programadores que sabem do que estou falando e isto de fato é preocupante, visto que o conceito que iremos discutir aqui hoje forma um dos pilares do que realmente a orientação a objetos trata.

Voltando à frase, conseguiu pensar ? Conseguiu ver a quantidade de conhecimento preso em uma única frase ? Não !? Bem, minha meta é abrir sua mente para o verdadeiro desafio de se construir software orientado a objetos.

Análise a situação abaixo.

Figura 1 - Modelo de classes acoplado

A classe AbridorDeGarrafas tem como responsabilidade abrir garrafas, sejam elas com tampa metálica, usadas nas garrafas de cerveja, ou com rolha de cortiça, usadas nas garrafas de vinho. Os objetos Taverna e Adega dependem destes métodos para funcionar. Queremos realizar uma modificação na implementação do método de abrir garrafas com tampa metálica sem causar impacto no funcionamento do método que abre garrafas com rolha. Será que isto é possível ? Não é preciso muito tempo para ver que a resposta é não porque será necessário recompilar, retestar e reimplantar todo este modelo para que esta mudança não resulte em problemas posteriores.

Então como alterar algo sem mexer no que já funciona ? Lembre-se que hoje somente o objeto Adega depende de AbridorDeGarrafas, mas amanhã pode existir uma gama de objetos com esta mesma dependência. Então, o que fazer ?

Isto tudo acontece por um único motivo, a classe AbridorDeGarrafas possui mais de 1 responsabilidade e tal nos leva a um modelo altamente acoplado, onde as mudanças feitas em um método afetam o funcionamento do outro. Isso é péssimo e não pode continuar 👎. Tudo isto fere o princípio da responsabilidade única, então a pergunta que nos sobra é: como corrigir o problema ?

Simples ! Devemos separar as responsabilidades da classe AbridorDeGarrafas. Entenda como responsabilidade uma razão para mudar e aqui existem duas para isso, são elas: atender solicitações de abertura de garrafas com tampa metálica e atender solicitações de abertura de garrafas com rolha. Entender essa separação é crucial para a montagem de um design que é ao mesmo tempo robusto e flexível, mas separar não significa que uma classe só deve conter um único método. Ao contrário, ela pode conter quantos métodos quiser desde que todos estejam relacionados a mesma responsabilidade. A partir do momento em que identificamos uma nova responsabilidade, a separação deve acontecer. Eis como o nosso modelo fica.

Figura 2 - Modelo de classes altamente coeso

Agora temos duas classes, uma que só abre garrafas com tampa metálica e outra que só abre garrafas com rolha e cada uma possui um método chamado abrirGarrafa(). Não há mais necessidade de especificar no nome do método que aquela abertura de garrafa é com tampa metálica ou de rolha, pois o nome da classe já tem essa expressividade. É dedutível que o abrirGarrafa() da classe AbridorDeGarrafasComTampaMetalica só abre garrafas com tampa metalica. Dessa forma podemos realizar quais mudanças quisermos sem afetar o que já funciona e isto é ótimo 👍.

Contudo, ainda falta um ponto para se pensar. Sempre que identificarmos mais de uma responsabilidade ela deve ser separada ? Levantar essa dúvida a esta altura pode parecer antagônico, mas não é. Este princípio é um dos mais difíceis e todos os outros da plataforma S.O.L.I.D se remetem à ele, logo esta indagação faz sentido e para respondê-la devemos levar em conta o contexto. Se uma alteração implica em mudar o todo não há necessidade de separar responsabilidades, pois para aquele contexto aquilo consiste uma única responsabilidade. Profundo, não !? 😕

Considere o seguinte exemplo: suponha que ao invés da mudança ser na abertura de garrafas com tampas metálicas, ela seria a adição de um mecanismo que melhora o encaixe do abridor na garrafa. Realmente deveríamos separar as responsabilidades aqui visto que a alteração afeta o todo ? A resposta é não, logo não faz sentido. Não existe uma fórmula mágica para todas as situações, cada uma deve ser avaliada separadamente.

Chegamos ao fim de mais um post. Nas próximas publicações veremos mais princípios da plataforma S.O.L.I.D e como eles se complementam. Como já é de costume, se inscreva no blog e no canal do youtube para ficar por dentro das novidades, indique para seus amigos e compartilhe em suas redes sociais.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: O algoritmo de Dijkstra - Grafos

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

MARTIN, ROBERT; MARTIN MICAH; Agile Principles, Patterns and Practices in C#; 2006

O algoritmo de Dijkstra - Grafos

2017-07-14T05:47:00.000-07:00

Olá ! Meu nome é João Paulo Maida e bem-vindos ao blog Preciso Estudar Sempre.

Você já pensou em alguma vez fazer uma daquelas viagens como mochileiro que você sai sem rumo de casa, só com mochila e dinheiro para a passagem do ônibus ? Seu destino final você decide a cada parada. Hoje você pode estar saindo do Rio de Janeiro e amanhã estar amanhecendo em alguma cidade do interior de Minas Gerais. A partir de lá você pode decidir ir para São Paulo, e de lá para o Mato Grosso. Em cada cidade que você pára, avalia quais podem ser seus destinos e quais são os mais baratos. Até porque para este tipo de viagem a grana é sempre curta.

Devo admitir que este tipo de aventura sempre foi um sonho para mim, mas acho que dificilmente um dia irei realizá-lo. Se você um dia já se aventurou de tal forma ou pensa em se aventurar, sabe que seria interessante ter uma relação das conexões das cidades baseadas em seus custos de transporte onde esses são baseados em suas distâncias, exemplo: ir do RJ para SP custa R$ 80, do RJ para MG custa R$60, de MG para MT custa R$30 e por aí vai. Com essa relação em mãos fica fácil decidir qual caminho tomar gastando pouco com passagem. Seria um sonho, não ?

Para nossa alegria e felicidade, este sonho sim é possível atingir. Mais uma vez a teoria dos grafos chega para salvar o dia com um algoritmo que nos dá exatamente a resposta que estamos procurando. Apresento o algoritmo de Dijkstra. A criação de Edsger Dijkstra é baseada na representação da matriz de adjacência de um grafo e não somente encontra o caminho mais curto a partir de um nó especificado até outro, como também os caminhos mais curtos do mesmo nó especificado até os outros (LAFORE, ROBERT).

Imaginemos a nossa viagem aventureira representada pela Figura 1 e não se prenda a detalhes de geografia.

Figura 1 - Mapa das cidades

Você está partindo do Rio de Janeiro e quer saber quais são os caminhos mais baratos para as próximas cidades, para assim chegar ao seu destino final pelo melhor caminho. Você sabe que em cada cidade que pára existe um agente da empresa de ônibus e que ele pode te informar os trajetos e tarifas. Então, você pega seu bloquinho (todo bom viajante deve ter um) e faz uma tabelinha com essa relação para que no final você tenha todas as informações “mastigadas”.

Tabela 1 - Tabela das viagens mais baratas

Então, assim como eu, você é um amante da teoria dos grafos e pensa: as cidades podem ser os vértices de um grafo e os trajetos entre elas as arestas. Eu sei que cada trajeto tem uma direção e um preço de passagem, então isso pode ser respectivamente a direção e o peso das arestas. No fim das contas, eu tenho um grafo ponderado orientado. Isso é ótimo !

É aí que entra o algoritmo de Dijkstra. Ele pega o seu grafo, analisa, e como resultado gera uma árvore. Esta árvore segue os conceitos básicos de uma árvore mas não é como uma árvore geradora mínima, a qual já vimos (clique aqui). Ela é diferente porque é montada levando em conta o somatório dos pesos a partir do nó inicial.

Abaixo estão relacionadas as etapas do algoritmo. Os detalhes de cada uma serão vistos mais à frente. Com o entendimento dessas etapas, entender o algoritmo em Java fica muito mais fácil.

Etapas do algoritmo:

Lembra da tabelinha da relação dos caminhos mais baratos ? Aqui ela toma a forma de um array, onde seu tamanho reflete a quantidade de vértices do grafo, cada posição representa um vértice e inicialmente é preenchido por completo com um valor muito grande (veremos o motivo disso mais à frente) que chamaremos de INFINITY. Chamaremos este array de array de menor caminho.
Após montado, o nó inicial, ou seja, nosso ponto de partida é analisado. São adicionados no array de menor caminho somente os vértices que são adjacentes ao nó inicial. Essa adição tem a forma de um objeto com informações sobre o vértice antecessor ao vértice analisado e o custo para chegar até ele. É necessário ter informações sobre o antecessor pois precisamos saber como chegamos ali (entenderemos esse ponto melhor a frente). Porque é assumido que estes vértices representam os melhores caminhos a partir do vértice inicial e podem ser inseridos no array de menor caminho ? A resposta é óbvia. Se os nós que são inseridos no array são aqueles adjacentes ao nó inicial, logo não existe nada que separe-os e assim se tornam os melhores custos neste trajeto. É importante citar que essas adições são feitas por cima dos valores que já existem em uma determinada posição do array.
Lembra que o resultado do algoritmo de Dijkstra é uma árvore ? Então, já podemos adicionar o primeiro nó (início) na árvore.
A partir dos nós restantes, verificamos 1 por 1 para averiguar qual tem o menor custo a partir do início.
Caso não haja nenhum é porque o nó inicial não tem conexões, ou seja, é inatingível ou todos já estão na árvore. Caso contrário, o nó com menor custo (adjacente ao inicial neste caso) é selecionado.
Uma vez selecionado, é adicionado na árvore e o array de menores caminhos é atualizado.
A atualização tem forma parecida com a adição citada no passo 2, ou seja, a mesma estrutura de objeto é citado. Consiste em analisar se o somatório de valores do início até o nó selecionado é menor que o valor já registrado. Isto deve ser feito por causa do passo 2.
Após esses passos terminados, o array de menor caminho está finalizado.

Após a aplicação do algoritmo, nossa tabela deverá ficar assim:

Tabela 2 -Tabela de viagens mais baratas preenchida

Através da Tabela 2 fica claro porque precisamos da informação do antecessor ? Com ela em mãos conseguimos refazer todo o caminho feito desde do nó inicial, ou seja, agora eu sei que o melhor caminho para a cidade de Bonito no estado do Mato Grosso do Sul é através de Ribeirão Preto em São Paulo e que o melhor caminho para este é via São Paulo capital, e para este o melhor é caminho é vir diretamente de Rio de Janeiro capital. Tudo mais claro agora não !?

Agora veremos a implementação desse algoritmo em Java e como já é de costume, é necessário dizer que é possível implementar este algoritmo em qualquer linguagem de programação. A linguagem Java foi escolhida somente por uma questão de afinidade.

O código abaixo é um dos mais difíceis já mostrados aqui no blog, mas não se espante que com calma tudo fica fácil. Não mostrarei o código inteiro aqui porque tal tornará a leitura complicada, visto que o que realmente importa são as três funções chave as quais compõem o algoritmo de Dijkstra.

findAllShortestPaths()

public void findAllShortestPaths(){
    int startTree = 0;
    vertexList[startTree].setIsInTree(true);                                //adiciono o primeiro vértice do grafo na árvore
    nTree = 1;                                                                //mudo o contador porque acabei de adicionar um nó na árvore

    for (int i=0; i<nVerts; i++) {                                            //inicializo o array de menores caminhos com as distâncias
        int distance = adjMat[startTree][i];                                //das adjacências do primeiro vértice
        shortestPathArray[i] = new ShortestPathObject(startTree, distance);
    }

    while (nTree < nVerts) {                                                        //até todos os nós estarem na árvore
        int shortestVertex = getMin();                                                //seleciona o vértice que tem o valor mínimo, essa função provê
        int shortestDistance = shortestPathArray[shortestVertex].getDistance();        //a direção que o algoritmo vai seguir

        if(shortestDistance == INFINITY){                                            //se todos forem infinito ou todos na árvore
            System.out.println("There are unreachable vertices");
            break;
        } else {
            currentVert = shortestVertex;
            startToCurrent = shortestDistance;
        }

        vertexList[currentVert].setIsInTree(true);                                    //coloca o vértice atual na árvore
        nTree++;                                                                    //mais um nó entrou na árvore
        updateShortestPathArray();                                                    //atualizo os valores mínimos
    }

    displayPaths();                                                                    //exibo todos os nós

    nTree = 0;                                                                        //limpa a ávore
    for (int i=0; i<nVerts; i++) {
        vertexList[i].setIsInTree(false);
    }        
}

Aqui é onde acontece toda a mágica. Como existem muitos detalhes que devem ser vistos, esta função divide essa responsabilidade com duas outras funções: getMin() e updateShortestPathArray(). Tentei deixar o código o mais explicado possível através de comentários, nomes de variáveis e métodos. Por causa disso não me estenderei em explicações aqui.

getMin() e updateShortestPathArray()

private int getMin(){
    int shortestDistance = INFINITY;
    int shortestVertex = 0;

    for (int i=1; i<nVerts; i++) {                                                                    //passo por todos os nós
        if (!vertexList[i].isInTree() && shortestPathArray[i].getDistance() < shortestDistance) {    //analiso se o nó já está na árvore e se a distância dele
            shortestDistance = shortestPathArray[i].getDistance();                                    //é a menor. Se for, atualizo as variáveis
            shortestVertex = i;
        }
    }
    return shortestVertex;
}

private void updateShortestPathArray(){
    int column = 1;
    while (column < nVerts) {                                                        //percorre todas as colunas da "tabelinha"
        if (vertexList[column].isInTree()) {                                        //se a coluna da "tabelinha" já estiver na árvore não há
            column++;                                                                //de atualizar sua entrada no array de valores mínimos
            continue;
        }

        int currentToTarget = adjMat[currentVert][column];                            //variável que guarda o valor da distância do nó atual(RJ) até um nó de destino que não está na árvore, nem sempre esse vértice de destino tem uma conexão de fato
        int startToTarget = startToCurrent + currentToTarget;                        //variável que guarda a distância total do início até o destino
        int shortestDistance = shortestPathArray[column].getDistance();                //recupera o valor do array de valores mínimos

        if (startToTarget < shortestDistance) {                                        //essa comparação é essencial pois se não há uma conexão de fato entre dois vértices, a soma total será INFINITY + algum valor de aresta e este é menor que somente INFINITY, logo não há necessidade de atualização nesse caso.
            shortestPathArray[column].setParentVert(currentVert);                    //caso a soma seja de valores que realmente possuem conexão (RJ-SP-RP-BN) ela será menor que INFINITY e logo há porque atualizar
            shortestPathArray[column].setDistance(startToTarget);
        }
        column++;
    }
}

Entender o que essas funções fazem é essencial para um entendimento total da implementação do algoritmo. Elas possuem tanta importância quanto a função findAllShortestPaths(). Basicamente, a função getMin() decide a direção de exploração no grafo escolhendo o nó com o melhor (menor no nosso caso) custo possível que ainda não está na árvore. Outro detalhe importante é que a ação de adicionar um vértice do grafo em uma árvore apartada é o fator determinante para que aquele vértice não seja mais analisado pelo algoritmo.

A função updateShortestPathArray() atua na atualização do array de menores caminhos e avalia se o custo de um trajeto inteiro vale a pena ou não de ser computado como ou não como um melhor caminho. Sem essa função não teríamos os resultados que tanto desejamos. No fim das contas, o que esperamos é a Tabela 2, já mostrada acima, e a Figura 3 que representa a árvore gerada pelo algoritmo.

Figura 3 - Árvore montada pelo algoritmo de Dijkstra

Com isso fechamos a série Grafos do blog. Se olharmos para trás veremos que falamos e aprendemos muito. Começamos de forma humilde para que no fim pudéssemos fechar de forma triunfal. E a idéia sempre foi essa, discutir e aprender cada vez mais. Se você chegou até esse ponto da leitura fico feliz, espero ter feito a diferença e agradado.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Você já parou para pensar sobre controle transacional ?

Download do código-fonte
Github: https://github.com/PrecisoEstudarSempre/Graphs.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004

Você já parou para pensar sobre controle transacional ?

2017-06-23T05:59:00.001-07:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Começo este post com a seguinte pergunta: você já parou para pensar sobre controle transacional ? Já tirou cinco minutos do seu dia para pensar no assunto ?

Minha pergunta pode parecer descabida ou até um pouco sentimental pois não fiz nenhuma apresentação sobre o tema. Contudo, faço essa pergunta porque em minha vivência de mercado já me deparei com muitos programadores que não tem a mínima idéia sobre o assunto. Obviamente eles sabem o que é uma transação, um commit ou um rollback. Porém pouquíssimos sabem implementar estruturas de controle transacionais do zero.

Interessante !

Tal fato além de ser extremamente preocupante na minha opinião, ocorre porque este tipo de questionamento não é mais necessário no mercado de trabalho atualmente. A maioria senão todos os projetos utilizam tecnologias que através da inversão de controle (IoC) implementam seu próprio controle transacional. Como resultado, oferecem interfaces bem definidas e limpas para seus usuários, tornando assim trabalho deles mais fácil e ágil. Aí está o ponto que me causa preocupação, o excesso de facilidade. Excesso o qual tende a tornar as pessoas, no caso desenvolvedores, mais preguiçosos causando um esquecimento de conceitos importantes.

Se você acabou de ler o parágrafo acima está pensando que estou falando de tecnologias como Spring, EJB 3 ou Hibernate. Acertou, estou falando exatamente disso ! Mas não vá pensar que estou condenando o uso de tais ferramentas. Pelo contrário, acho super correto utilizá-las e se você não as conhece, recomendo que estude-as. Entretanto, nunca se esqueça disso: não fique preso somente ao funcionamento das ferramentas existentes, entenda como elas funcionam ! O ponto central do meu raciocínio é justamente este, é necessário entender como “por detrás dos panos” o Spring, por exemplo, consegue executar rollback em uma transação inteira, onde nesta várias tabelas sofreram operações. Obviamente não podemos esquecer que ele não somente consegue fazer isso, mas como ainda disponibilizar uma forma que você escreva sua camada DAO (Data Access Object) de forma não acoplada a sua fachada de negócio, ou serviço.

A esta altura do campeonato você já deve ter notado que esta não é uma discussão trivial. Estamos lidando com uma situação arquitetural complexa com vários padrões de projeto, conceitos e preocupações. Logo algumas amostras de código e um diagrama de classes poderiam ajudar a trazer para a realidade o que estou propondo.

Figura 1 - Diagrama de classes proposto

É importante deixar claro aqui que o modelo proposto não é a solução para todos os problemas do universo. Como sempre digo, não existem balas de prata na computação. Talvez você leia esta postagem, encontre vários erros e monte um modelo melhor. Isso acontece, soluções desse tipo são de caráter evolutivo. Então, fique a vontade para contribuir.

Começaremos a explicação deste modelo analisando a classe DAO. Como o nome já mostra, ela segue o padrão DAO (Data Access Object), logo sua responsabilidade é lidar com abstrações de acesso à dados na base de dados. Trabalhando em conjunto com ela existe a classe HelperDAO, e como o seu nome também deixa claro, ela é uma classe auxiliar. Sua responsabilidade é a de prover métodos auxiliares de fechamento de statements e result sets. A interface ConnectionInjector possui um único método, responsável pela injeção da instância do objeto de conexão de banco de dados na classe DAO. Esta injeção de fato ocorre pela implementação da interface pela classe. Mais a frente entenderemos o motivo disso.

As classes que tratam o negócio são representadas pela classe BusinessFacade e é nela que todo o controle transacional acontece. Ali deve estar o nosso foco. Neste momento você pode estar se questionando da seguinte forma: se um contexto transacional é relacionado diretamente a operações de banco de dados, porque implementá-lo na camada de negócio ? Isto não tornaria a implementação altamente acoplada ?

Não te condeno por tal dúvida, pois eu já a tive algum tempo atrás, mas refletindo sobre assunto cheguei a conclusão de que eu estava errado. O negócio é o elemento que dita o que deve estar ou não na transação, por exemplo: toda vez que um usuário for cadastrado no sistema X, ele deve ser imediatamente cadastrado na lista de usuários que tem dívidas em aberto. Então em nossa transação devem existir instruções de escrita nas tabelas de usuários e de devedores. Caso haja algo de errado nesta operação como um todo, todas as operações devem ser desfeitas. Agora imagine se para cada operação uma nova transação fosse aberta, como controlar todo o contexto de negócio ? Se uma operação falhar como comunicar a próxima ou a anterior ? Essas são as reais preocupações que devem tomar a mente de um desenvolvedor/arquiteto quando ele planeja montar seu contexto transacional.

Para que a classe de negócio não tenha mais de uma responsabilidade, fato que fere o primeiro princípio da S.O.L.I.D, ela utiliza a ajuda de uma classe helper, ou seja, uma classe auxiliar. É aí que a classe HelperTransactionalControl ganha espaço, pois nela estão concentradas todas as funções necessárias para se criar ou não um contexto transacional, e caso criado, controlá-lo. Lembre-se que leituras em banco podem ser feitas e não há a necessidade de uma transação para isso.

Um ponto interessante nesta classe é o método injectConnection(ConnectionInjector…). Note que ele recebe um varargs do tipo ConnectionInjector e que esta é a interface que todas as classes DAO implementam. Na implementação deste método ele faz uma chamada ao método injectConnection(Connection) da interface ConnectionInjector, ou seja, ele injeta um objeto de conexão em todas as instâncias DAO utilizadas. Então, na classe de negócio a única preocupação que deve ser considerada é a de invocar este método da classe helper, passando como parâmetro todos as instâncias DAOs utilizadas no momento. Fiz essa escolha de projeto pois não me agradava o fato de talvez passar como parâmetro, no construtor de todas as instâncias DAOs, um objeto do tipo Connection. Não é responsabilidade da classe que trata o negócio lidar com esse objeto, logo escolhi fazer isso “por debaixo dos panos”.

A interface que a classe de negócio implementa é uma simples escolha de programação orientada a interface. Com este recurso posso facilmente trocar a implementação de um contexto de negócio sem ter que me preocupar com quem já consumia informações a partir dele.

--------------------------------------------------------------------------------------------------------------------------

OBSERVAÇÃO: O varargs da linguagem Java é uma categoria de tipo de dados que se comporta como se fosse um array. Logo, se o seu método recebe um varargs do tipo inteiro, você pode passar os valores tanto separados por vírgula como por um array, exemplo: foo(1,2,3,4,5) ou foo(new int[]{1,2,3,4,5}).

--------------------------------------------------------------------------------------------------------------------------

Acredito que com as amostras de código abaixo tudo o que foi discutido ficará mais claro.

ConnectionInjector.java

package src.model.dao;
 
import java.sql.Connection;
 
public interface ConnectionInjector {
 void injectConnection(Connection connection);
}

Classe HelperDAO.java

package src.model.dao.helper;
 
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;
 
public class HelperDAO {
 
 public void closeStatement(Statement statement)
   throws SQLException {
  if (statement == null) {
   throw new IllegalArgumentException(
     "Errorcode: 102 - Statement nulo.");
  }
  try {
   statement.close();
  } catch (SQLException e) {
   throw new SQLException("Errorcode: 102 - Erro no fechamento do objeto Statement.", e);
  }
 }
 
 public void closeStatementAndResultSet(Statement statement,
   ResultSet resultSet) throws SQLException {
  this.closeStatement(statement);
  if (resultSet == null) {
   throw new IllegalArgumentException(
     "Errorcode: 102 - ResultSet nulo.");
  }
  try {
   resultSet.close();
  } catch (SQLException e) {
   throw new SQLException("Errorcode: 102 - Erro no fechamento do objeto ResultSet.", e);
  }
 }
}

DAO.java

package src.model.dao;
 
import src.model.dao.helper.HelperDAO;
import java.util.List;
import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
 
public class DAO implements ConnectionInjector{
 private Connection connection;
 private HelperDAO helperDAO;
 
 public DAO(){
  this.helperDAO = new HelperDAO();
 }
 
 @Override
 public void injectConnection(Connection connection) {
  this.connection = connection;
 }
 
 public List findAll() throws IntegrationException {  
  PreparedStatement preparedStatement = null;
  ResultSet resultSet = null;
  List results = new ArrayList<>();
  try{
   String sql = "SELECT COLUMN1, COLUMN2, COLUMN3 FROM TABLE";  
   preparedStatement = this.connection.prepareStatement(sql);
   resultSet = preparedStatement.executeQuery(sql);
   while (resultSet.next()) {
    MyObject myObject = new MyObject();
    myObject.setMyProperty1(resultSet.getLong("COLUMN1"));
    myObject.setMyProperty2(resultSet.getString("COLUMN2"));
    myObject.setMyProperty3(resultSet.getString("COLUMN3"));
    
    results.add(myObject);
   }
   return results;
  } catch (SQLException e){
   throw new SQLException("Errorcode: 104 - Erro de SQL na listagem de todos os objetos.", e);
  } finally {
   helperDAO.closeStatementAndResultSet(preparedStatement, resultSet);
  }
 }
 
 private void insert(MyObject myObject) throws SQLException {
  PreparedStatement preparedStatement = null;
  try {
   int paramPos = 0;
   String sql = "INSER INTO TABLE (COLUMN1, COLUMN2, COLUMN3) VALUES (?,?,?)");
   preparedStatement = this.connection.prepareStatement(sql);
   preparedStatement.setLong(paramPos++, myObject.getProperty1());
   preparedStatement.setString(paramPos++, myObject.getProperty2());
   preparedStatement.setString(paramPos++, myObject.getProperty3());
   preparedStatement.execute();
  } catch (SQLException e) {
   throw new SQLException(
     "Errorcode: 104 - Erro de SQL no cadastro do objeto.",
     e);
  } finally {
   helperDAO.closeStatement(preparedStatement);
  }
 }
}

HelperTransactionalControl.java

package src.model.business.helper;
 
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;
 
import src.model.dao.ConnectionInjector;
import src.model.exception.IntegrationException;
 
public class HelperTransactionalControl {
 
 private static final String USER_DATABASE = "USER";
 private static final String PASSWORD_DATABASE = "PASSWORD";
 
 private Connection connection;
 
 public void openConnection() throws IntegrationException {
  try {
   Class.forName("com.jdbc.mysql.Driver");
   this.connection = DriverManager.getConnection(
     "jdbc:mysql://localhost:3306/DATABASE",
     USER_DATABASE, PASSWORD_DATABASE);
  } catch (SQLException | ClassNotFoundException e) {
   throw new IntegrationException("Errorcode: 100 - Erro na criação de uma conexão ao banco de dados.", e);
  }
 }
 
 public void injectConnection(ConnectionInjector... daosObject){
  for (ConnectionInjector daoObject : daosObject) {
   daoObject.injectConnection(connection);
  }
 }
 
 public void endConnection() throws IntegrationException {
  if (connection == null) {
   throw new IllegalArgumentException(
     "Errorcode: 102 - Connection nula.");
  }
  try {
   connection.close();
  } catch (SQLException e) {
   throw new IntegrationException("Errorcode: 102 - Erro no fechamento do objeto Connection.", e);
  }
 }
 
 public void beginTransaction() throws IntegrationException{
  try {
   connection.setAutoCommit(false);
  } catch (SQLException e) {
   throw new IntegrationException("Errorcode: 103 - Erro na abertura da transação de banco.", e);
  }
 }
 
 public void commitTransaction() throws IntegrationException{
  try {
   connection.commit();
  } catch (SQLException e) {
   throw new IntegrationException("Errorcode: 103 - Erro na commit da transação de banco.", e);
  }
 }
 
 public void rollbackTransaction() throws IntegrationException{
  try {
   connection.rollback();
  } catch (SQLException e) {
   throw new IntegrationException("Errorcode: 103 - Erro no rollback da transação de banco.", e);
  }
 }
}

BusinessFacade.java

package src.model.business;
 
import java.sql.SQLException;
import java.util.List;
 
import src.model.dao.DAO;
import src.model.exception.IntegrationException;
import src.model.business.helper.HelperTransactionalControl;
 
public class BusinessFacade implements IBusinessFacade{
 
 private HelperTransactionalControl helper;
 
 public BusinessFacade() {
  helper = new HelperTransactionalControl();
 }
 
 @Override
 public MyObject insert(MyObject myObject) throws IntegrationException {
  try {
   DAO dao = new DAO();
   
   helper.openConnection();
   helper.beginTransaction();
   helper.injectConnection(dao);
   dao.insert(myObject);
   helper.commitTransaction();
   
   return myObject;
  } catch (SQLException e) {
   helper.rollbackTransaction();
   throw new IntegrationException(e);
  } finally {
   helper.endConnection();
  }
 }
 
 @Override
 public List findAll() throws IntegrationException{
  try {
   DAO dao = new DAO();
      
   this.helper.openConnection();
   this.helper.injectConnection(dao);
   return dao.findAll();
  } catch (SQLException e) {
   throw new IntegrationException(e);
  } finally {
   this.helper.endConnection();
  }
 }
}

Note que como consequência da implementação do projeto de software proposto, a classe de tratamento do negócio ficou bem enxuta e com responsabilidades bem definidas. Não achei necessário expor aqui o código-fonte da exceção especializada (IntegrationException) e da interface IBusinessFacade porque seus conteúdos são bastante triviais e iriam causar mais volume na postagem, talvez tornando a leitura mais cansativa.

Como dito anteriormente, sinta-se livre para criticar, existem várias formas de se fazer o mesmo e é isso que engrandece um projeto de software, mas se você quiser elogiar não se acanhe 😋.

Chegamos ao fim de mais um post e neste aqui devo grandes agradecimentos a um amigo e mentor, o imenso Luís Marcelo Bruckner. Muito obrigado meu amigo.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Grafos ponderados - Grafos

Download do código-fonte

GoogleDrive: clique aqui

Dropbox:

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Grafos ponderados - Grafos

2017-05-31T08:27:00.003-07:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

A partir de agora, reserve sua mente para um novo conceito. Pegue tudo o que você já aprendeu e guarde, pois será necessário. Você está prestes a conhecer um novo tipo de grafo, com novas características e ferramentas. Conheça os Grafos Ponderados.

Resumidamente, grafos ponderados são grafos com pesos em suas arestas (Figura 1). Entenda pesos como valores e não como quilos. São utilizados para determinar qual o melhor trajeto adotar dado o problema. Pense na seguinte situação: você quer sair do centro da cidade do Rio de Janeiro e chegar no Cristo Redentor. Como chegar lá ? Existem vários caminhos. Qual deles é o melhor ? Isso depende de você. Se está com pressa por causa de tempo, talvez aquele caminho mais curto porém mais perigoso seja melhor do que aquele mais seguro e longo, ou talvez se um trajeto com mais paisagens for mais importante do que rapidez, um outro caminho pode ser o ideal. Visto que podem existir diversas possibilidades de caminhos a serem feitos, um critério de escolha deve ser escolhido e em cima dele as diversas arestas que conectam o ponto A ao ponto B ganharão seus respectivos pesos.


Figura 1 - Diferenças entre um grafo ponderado e não ponderado

Um grafo ponderado pode ser tanto orientado quanto não orientado (Figura 2) e essa orientação é a mesma já vista anteriormente, logo os problemas que essa característica traz também são os mesmos e obviamente acabam se acumulando com os novos desafios oriundos das arestas ponderadas. Estruturas como matrizes ou listas de adjacências também aparecem aqui, logo nenhuma surpresa quanto a isso. O que realmente vai diferenciar este tipo de grafo são seus pesos em suas arestas e os algoritmos originados a partir da análise dos mesmos. Tais diferenciais tornam a implementação um pouco diferente do que já estávamos acostumado.

Figura 2 - Diferenças entre um grafo ponderado orientado e um não orientado

WeightedGraph.java
Como dito antes, alguns métodos não são lá uma surpresa, contudo alguns destaques podem ser feitos. Note que não existe inicialização com 0’s da matriz de adjacência aqui, pois ela não é mais uma matriz de inteiros e sim de objetos do tipo Edge. Como é de conhecimento de todos, variáveis de instância em Java tem seu valor default como null, logo automaticamente a matriz tem valores nulos em todas as suas posições e isso é o bastante para saber se existe uma aresta ali ou não.

O método de adição de aresta deixa claro através de seu nome que são arestas não orientadas que são adicionadas e ele recebe como parâmetro o peso da aresta. Realizei a mudança no nome com a finalidade de deixar o código mais intuitivo. Lembre-se que pelo fato das arestas não serem orientadas é preciso marcar a matriz duas vezes e que agora será inserido um objeto do tipo Edge ao invés de um inteiro. O resto da classe é mais do mesmo que já estamos acostumados.

Edge.java

Esta classe representa uma aresta, podendo ser orientada ou não, de um grafo ponderado. Lembre-se que a orientação é ditada na matriz. Dentro dela estão todas as informações necessárias de uma aresta, como: vértice de origem, destino e seu peso.

WeightedGraphApp.java

Classe cliente, tendo como responsabilidades a criação e exibição de um grafo ponderado.

Com isso, chegamos ao fim de mais uma postagem.

Estamos chegando ao fim da série Grafos. Faltam somente mais alguns assuntos para encerramento total desta série, não perca nenhum deles. Após esta série de assuntos começaremos uma nova com um novo formato que ainda é surpresa para tornar a nossa experiência a mais dinâmica possível.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Indicações de livros - Estruturas de dados e Algoritmos em Java

Download do código-fonte
Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/Graphs.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Indicações de livros - Estruturas de dados e Algoritmos em Java

2017-05-17T06:21:00.001-07:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Para dar aquela quebrada na rotina, neste mês trago a indicação de um excelente livro através de um vídeo do nosso canal do YouTube (links lá embaixo). Não perca, ficou muito bom. :D

Livro: Estruturas De Dados E Algoritmos em Java
Autor: Robert Lafore
Editora: CIENCIA MODERNA
Sumário:

Capítulo 1 - Visão geral
Capítulo 2 - Vetores (se você já sabe, pode pular)
Capítulo 3 - Ordenação simples (recomendo muito)
Capítulo 4 - Pilhas e filas (importante para qualquer desenvolvedor)
Capítulo 5 - Listas encadeadas (importante para qualquer desenvolvedor)
Capítulo 6 - Recursão (diferencia homens de meninos)
Capítulo 7 - Ordenação avançada (recomendo muito)
Capítulo 8 - Árvores binárias (importante para qualquer desenvolvedor)
Capítulo 9 - Árvores rubro-negras (inside the matrix)
Capítulo 10 - Árvores 2-3-4 e armazenamento externo (inside the matrix)
Capítulo 11 - Tabelas Hash (importante para qualquer desenvolvedor)
Capítulo 12 - Heaps (inside the matrix)
Capítulo 13 - Grafos (se você gosta de assuntos mais complicados, aqui é o lugar)
Capítulo 14 - Grafos ponderados (se você gosta de assuntos mais complicados, aqui é o lugar)
Capítulo 15 - Quando usar o que ? (um dos melhores capítulos)

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: O algoritmo Warshall - Grafos

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

O algoritmo Warshall - Grafos

2017-04-28T05:36:00.001-07:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Até este momento já vimos bastante coisa sobre grafos. Estudamos seus conceitos mais fundamentais, tipos de buscas, árvores geradoras mínimas e por último, orientação. A orientação se torna um grande divisor de águas quando o assunto é grafos. Isto acontece pelo simples fato de que a adição de direção nas arestas muda completamente as regras do jogo. Se antes era possível iniciar um trajeto em um determinado ponto e terminar em outro, agora não é mais, e tal fato se torna uma pergunta. Como determinar todos os caminhos possíveis de um grafo ? Quais são as aplicações disso no mundo real ?

Bem, a segunda pergunta é fácil de responder. Basta pensar em um aeroporto, como o aeroporto do Galeão no Rio de Janeiro, e tentar determinar quais viagens são possíveis de fazer a partir dele. Cada aeroporto representaria um nó e cada trajeto direto (sem escalas) possível uma aresta. Logo, se existe uma viagem que parte do Galeão e vai para Frankfurt na Alemanha, teremos dois nós G e F (representados pelas primeiras letras dos aeroportos) ligados por uma seta iniciando em G e indo para F. Em seguida, se somente a partir de Frankfurt é possível ir para Varsóvia, na Polônia, então será necessário realizar o trajeto Galeão -> Frankfurt -> Varsóvia. Não existe outro caminho possível.

Para o nossa primeira pergunta o que era problema se torna trivial, pois estamos analisando um exemplo muito pequeno mas imagine um cenário real, onde você pode ir para qualquer lugar do mundo e muitas vezes só existem caminhos de ida e não de volta. Acredito que as coisas se compliquem um pouco. Então determinar um procedimento capaz de realizar esse mapeamento completo se torna crucial.

Figura 1 - Grafo orientado G com sua tabela de conectividade

Para o grafo da Figura 1 é fácil determinar quais caminhos podem ser feitos, pois ele é pequeno e junto à ele é apresentado sua tabela de conectividade. Esta tabela tem como função mostrar quais nós são alcançáveis a partir de um determinado nó, representado pela primeira letra da sequência. Logo, a partir de A é possível ir até B, C e E. Isto já representa um avanço, visto que possuímos um catálogo completo sobre quais caminhos podemos fazer. Contudo, o foco deve ser em fornecer uma forma direta de saber se um caminho é possível ou não, exemplo: é possível a partir de A chegar à D ?

Analisando rapidamente a tabela é possível concluir que isto é uma inverdade, e somente é possível chegar a essa conclusão pois vimos letra após letra da sequência que começa com A. Tal processo é custoso visto que leva tempo O(N), onde N é o número médio de nós alcançados a partir de um determinado nó. Mas, conforme citado acima, procuramos uma forma direta de obter essa informação, procuramos uma forma que leve tempo O(1) (LAFORE, ROBERT).

Tal almejada forma é o algoritmo de Warshall e sua ideia é extremamente simples. Ele utiliza uma estrutura já conhecida, a matriz de adjacência, e insere novas informações nela, a fim de torná-la mais rápida. A matriz melhorada gera um grafo chamado de fechamento transitivo do grafo original (LAFORE, ROBERT).

Para entendermos como funciona o algoritmo, antes precisamos tomar conhecimento da matriz de adjacência do grafo atual.

Figura 2 - Matriz de adjacência do grafo G

----------------------------------------------------------------------------------------------------------------
LEMBRETE: As linhas representam as origens de uma aresta e as colunas os fins, ou seja, se na célula AB existe o número 1 logo existe uma aresta de A para B.
----------------------------------------------------------------------------------------------------------------

O algoritmo deve percorrer todas as células da matriz. Caso encontre 1 em alguma célula, ele saberá que ali existe uma aresta. Para cada aresta encontrada ele deve percorrer todas as células da coluna correspondente à sua linha, ou seja, se foi encontrado 1 na célula AB, a coluna A deverá ser percorrida completamente. Caso nesta coluna exista algum 1, ele saberá que existe uma aresta chegando naquele nó, onde a origem será a linha dessa célula. Neste exato momento é concluído que existem dois caminhos que partilham um mesmo nó. Então, se existe tal caminho ele pode ser “encurtado” em um caminho só, logo um 1 é adicionado na célula correspondente a esse caminho. Confuso ? Nem um pouco. A Figura 3 mostra como o processo funciona.


Figura 3 - Funcionamento do algoritmo de Warshall

Acredito que com a imagem a explicação do parágrafo acima ficou mais fácil de ser entendida. Em uma primeira instância o algoritmo encontra a aresta A -> B, mas verificando a coluna A conclui que não existem arestas chegando nele logo a partir deste nó só partem arestas. A verificação da linha A foi terminada, a linha B vem em seguida.

A verificação começa e a aresta B -> C é descoberta. A coluna B é verificada e a aresta A -> B é encontrada, logo o nó B é comum as duas arestas e através dele é possível conectar A à C. Por fim, a célula AC é marcada com 1 para representar que existe uma aresta que liga esses dois nós. Este procedimento é repetido para todos os nós das linhas da matriz. Quando não houver mais linhas para serem processadas, o algoritmo chegou ao fim.

Abaixo apresento uma implementação feita em Java para este algoritmo. Como já é de costume é importante deixar bem claro que escolhi Java por uma questão de afinidade e nada impede que você escolha uma linguagem de seu gosto. Nosso foco aqui não é realizar as melhores práticas da linguagem, mas sim aprender como o algoritmo funciona.

Graph.java
O algoritmo é bem simples visto que são três laços de repetição com algumas condicionais. O primeiro laço consiste na varredura das linhas da matriz, o segundo das colunas. Caso haja uma aresta, a procura na coluna correspondente é feita no terceiro laço. Se todas as correspondências forem encontradas o novo caminho é gravado na matriz. Todo este procedimento é repetido para todas as linhas da matriz fazendo com que o algoritmo chegue ao fim e torne o acesso à caminhos de um grafo O(1).

WarshallAlgorithm.java
Esta classe é apenas uma classe cliente, sua única responsabilidade é criar grafos, adicionar arestas e vértices, e executar o algoritmo de Warshall. Exibir o fechamento transitivo do grafo original e checar possíveis caminhos também são operações realizadas aqui.

A partir dessa postagem entraremos em uma outra classe de grafos, os grafos ponderados. Aqui veremos que é possível atribuir pesos para as arestas e ver qual é o melhor caminho a ser feito, assim como os programas de GPS fazem. Mais um passo no longo caminho do entendimento desta extraordinária teoria foi dado.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: A orientação em grafos - Grafos

Download do código-fonte
Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/Graphs.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004

A orientação em grafos - Grafos

2017-04-24T06:52:00.000-07:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Já estudamos anteriormente que é possível mapear diversas situações do mundo real em grafos (clique aqui para ler a nossa primeira postagem sobre grafos). Trajetos, labirintos, linhas de transmissão de energia, linhas férreas, jogos e até uma viagem em família são grandes exemplos da presença desse ramo da matemática no nosso dia-a-dia. Contudo, em todos esses exemplos uma característica ainda não foi analisada, a direção. Até agora não nos preocupamos com este ponto especificamente porque todos os nossos exemplos cabiam em grafos não orientados.

Porque a direção seria importante em um grafo ? A resposta é simples. Imagine que você está mapeando em um grafo o trajeto de carro que parte de um ponto A e vai para um ponto B. Como você sabe as ruas têm direções e muitas vezes quando se está dirigindo só é permitido seguir um tipo de sentido. Logo, tal característica também deve ser refletida em um grafo, pois a orientação mostra quais os trajetos são possíveis de um ponto origem para um ponto destino.

Quando estávamos estudando grafos não orientados podíamos simples sair de um nó A passar em vários outros até chegar ao nó Z, por exemplo. Bastava somente que existisse arestas que fizessem essa conexão, direta ou indiretamente. Contudo, com grafos orientados a história é outra. Se existir um único caminho que leve de A à Z, é esse que deve ser seguido e não há a possibilidade de fazer esse trajeto sem ser por esse caminho. Se houver mais de um caminho, sem problemas, os dois podem ser percorridos. Mas, se não houver caminho que ligue A à Z, ele se torna inalcançável a partir de sua origem.

A Figura 1 mostra dois grafos com a mesma disposição de nós e arestas, só que o grafo acima é orientado e o abaixo é não orientado.


Figura 1 - Um grafo orientado e um grafo não orientado

Conforme já comentado anteriormente, em um grafo orientado pode ser que só exista um caminho que liga um nó a outro. Na Figura 1 tal situação acontece e é representada pelo seguinte trajeto: A-B-E-F-J-H-Z.

Um outro ponto que também deve ser analisado é como a orientação de um grafo se reflete em sua matriz ou lista de adjacências, quais são os impactos disso. Antes tínhamos de nos preocupar em representar de forma bidirecional a conexão entre dois nós, ou seja, se A fosse conectado à B tínhamos que fazer uma marcação nas células AB e BA da matriz, onde a primeira letra representa a linha e a segunda a coluna. Agora isso não é mais necessário pois a direção da aresta dita qual célula deve ser preenchida, característica a qual não existia antes em grafos não orientados. Se em A houver uma aresta que parte para B, então somente a célula AB receberá a marcação. Caso contrário, somente a célula BA recebe. No caso de uma lista de adjacências o comportamento descrito acima se repete, logo o que mudaria é que uma das posições da lista não teria a conexão oposta pois o sentido é único. Caso o assunto seja estranho para você, recomendo a leitura do nosso segundo post sobre grafos.

Figura 2 - Grafos orientado e não orientado com suas respectivas matrizes de adjacência

Com a Figura 2 a diferença entre as matrizes de adjacência se torna muito óbvia, pois o fenômeno descrito no parágrafo acima é representado. Para um grafo não orientado, metade da matriz de adjacência espelha a outra metade, portanto, a metade das células se tornam redundantes. Porém, para um grafo orientado, toda célula da matriz transmite uma informação única (LAFORE, ROBERT). Não utilizei o grafo da Figura 1 porque ele possui muitos nós e arestas, e isso concluiria em uma matriz muito extensa, atrapalhando assim o nosso exemplo.
Levar toda essa teoria para a prática resulta na criação de um simples método que faz a marcação explicada na matriz de adjacência. Como sempre, é possível obter todo o código desenvolvido até essa postagem no repositório GitHub (link no fim do post) do projeto. Faça o download, dê uma olhada e deixe aí sua opinião. A frente, estudaremos algoritmos específicos para este tipo de grafo, não perca.

Com isso chegamos ao fim de mais uma postagem. Se você gostou compartilhe com seus amigos, se inscreva no blog e curta a página no Facebook.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Árvores geradoras mínimas - Grafos

Download do código-fonte
Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/Graphs.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004

Árvores geradoras mínimas - Grafos

2017-03-24T12:52:00.001-07:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Esta é a quarta publicação da série Grafos, onde abordaremos mais um assunto desta incrível teoria. Caso você seja novo por aqui e não leu nenhuma postagem ainda, recomendo que você clique aqui e comece pela primeira publicação desta série, onde entendemos o que é um grafo e do que ele é composto. Mas, se você já é um leitor assíduo do blog e leu a penúltima postagem, se delicie agora com mais um conteúdo voltado para você, amante do estudo.

Na teoria dos grafos, as árvores geradoras mínimas servem para gerar representações onde, o foco é eliminar o excesso de arestas. Entenda por excesso o fato de existirem mais arestas que o necessário para conectar o grafo inteiramente. A Figura 1 mostra um grafo com oito vértices e um número excessivo de arestas, ao passo que a Figura 2 mostra um grafo com os mesmos oito vértices, mas com um número mínimo de arestas necessárias para conectá-lo de forma completa.

Figura 1 - Grafo com arestas em demasiado


Figura 2 - Árvore geradora mínima do grafo acima

Diferentes árvores podem ser geradas a partir do momento que escolhemos pontos de partidas diferentes. No nosso caso, o ponto de partida escolhido foi o nó A, logo o resultado só pode ser este, mas caso escolhêssemos o nó B, o resultado seria outro completamente diferente.

Lembre-se que nossa preocupação aqui não é o comprimento das arestas, não estamos tentando encontrar o menor caminho, e sim reduzir a quantidade de arestas (LAFORE, ROBERT).

Outro ponto a ser notado é a possibilidade de se calcular o número de arestas de uma árvore geradora mínima através da expressão abaixo, onde E é a quantidade de arestas e V é a quantidade de vértices.

E = V - 1

Quais seriam as aplicações possíveis para uma árvore mínima geradora ? Muitas, basta somente um pouco de reflexão sobre os problemas do cotidiano. Imagine uma imensa rede de transmissões de linhas telefônicas que conecte todas as cidades de um país. Uma cidade pode se conectar diretamente ou indiretamente a outra cidade, por exemplo Rio de Janeiro - Belo Horizonte ou Rio de Janeiro - São Paulo - Belo Horizonte. Em um determinado momento é decretada uma ordem de redução de custos de cabeamento pelo presidente da empresa, e todas as conexões redundantes precisam ser eliminadas, logo a conexão direta Rio de Janeiro - Belo Horizonte teria seu fim decretado, visto que a conexão alternativa (RJ - SP - BH) atinge o mesmo propósito e ainda traz outra cidade para o novo grafo de conexões.

Este exemplo pode parecer um pouco incomum visto que este presidente estaria jogando o dinheiro da companhia fora quando manda remover os cabos e que talvez as distâncias entre as cidades não compensariam tal trabalho. Porém, isto é somente um exemplo imaginário de um problema real.

O algoritmo usado para criar a árvore geradora mínima é quase idêntico ao usado para buscar. Ele pode ser tanto baseado na busca em profundidade quanto na busca em largura. Neste post, abordaremos uma implementação baseada na busca em profundidade (LAFORE, ROBERT), pois o caminho armazenado na pilha desse tipo de busca é automaticamente a árvore geradora mínima. A única diferença entre a busca e o algoritmo da árvore geradora mínima é que o segundo deve registrar de alguma forma as arestas pelas quais passa.

Um outro motivo da árvore geradora mínima ser facilmente derivada da busca em profundidade é porque essa busca visita todos os nós, mas apenas uma vez. Ele nunca vai para um nó que já tenha sido visitado. Quando ele ver uma aresta que tenha um nó visitado no final, não irá segui-la. Ele nunca viaja por uma aresta que não seja necessária. Assim, o caminho percorrido pela busca tem que ser uma árvore geradora mínima (LAFORE, ROBERT).

Escolhi Java como a linguagem de programação para estes algoritmos por uma questão de afinidade, mas nada impede que você utilize uma versão do Java diferente da minha ou até outra linguagem.

Este é o método responsável pela geração da árvore geradora mínima. Como dito antes, este algoritmo se assemelha muito com o algoritmo de busca em profundidade, e isto é visível no trecho de código acima. A única diferença que deve ser ressaltada é a exibição dos nó atual e o adjacente à ele juntamente com o espaço em branco, o qual facilita a visualização do resultado final.

Caso você não tenha conhecimento sobre as buscas em profundidade, já abordamos esse assunto aqui no blog. Clique aqui e tire suas dúvidas. Recomendo a leitura.
A classe acima tem como propósito final criar e montar um grafo para depois executar a geração da árvore mínima geradora nele. O resultado esperado, como já visto na Figura 2, é um grafo com o mínimo de arestas possíveis que conectem todos os seus vértices.

Chegamos ao fim de mais uma postagem da série Grafos. Ainda temos muito conteúdo para discutir e muitas coisas novas para aprender, estamos somente no início de uma longa jornada. Então se prepare para as novidades que vem por aí.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Busca em largura - Grafos

Download do código-fonte
Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/Graphs.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004

Busca em largura - Grafos

2017-03-15T12:42:00.000-07:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Na nossa última postagem abordamos uma das formas de se realizar uma busca em um grafo, a busca em profundidade. Caso você não tenha lido, clique aqui. Mas, se você for um total iniciante no assunto, recomendo que você comece lendo a primeira postagem dessa nova série, clicando aqui.

Já informo de antemão que utilizarei a linguagem de programação Java para a construção das implementações dos algoritmos e que nada impede que você utilize uma outra versão do Java diferente da minha ou, até uma outra linguagem. Agora, sem mais delongas, vamos ao assunto.

A necessidade e as restrições que envolvem este assunto são as mesmas que envolviam o assunto da postagem anterior. Dado um grafo G desconhecido, quais nós são possíveis de atingir a partir de um determinado nó N ? Esta pergunta, obviamente, já foi respondida, mas aqui veremos uma outra forma de respondê-la.

Analisemos o grafo mostrado na Figura 1.

Figura 1 - Grafo de exemplo

Assim como já foi discutido previamente, é necessário que um ponto de partida seja escolhido, pois o grafo analisado é desconhecido de primeira mão, estamos às cegas. Só teremos o conhecimento de um ponto inicial, o nó A no nosso caso. Tal condição não somente viabiliza a pergunta feita acima, mas como nos deixa à frente de grandes problemas, como: O que fazer ? Qual nó adjacente visitar primeiro ?

Ao contrário de sua irmã, a busca em largura não visita a fundo todo um caminho de arestas até chegar em um ponto que não consiga ir mais adiante, ela se comporta de uma forma completamente diferente. Ela visita todos os nós adjacentes ao nó inicial e apenas então vai mais adiante. A estrutura que serve como alicerce para tudo isso é uma fila do tipo FIFO, pois é ela que vai registrar qual é o caminho atual percorrido. Caso você não seja conhecedor de tal estrutura, recomendo fortemente o estudo dela antes de continuar a leitura deste post e peço desculpas por não deixar uma referência de post do próprio blog sobre o assunto. Não faço isso, pois ainda não abordei esse tema.😞

Imagine o seguinte: uma pedra cai na água de uma calma lagoa (LAFORE, ROBERT). Quando a pedra entra em contato com a água, ela cria ondas que se espalham de forma igual por toda a superfície criando assim um fenômeno homogêneo. Tal característica se repete nas buscas em largura, ou seja, os nós são percorridos de uma forma igual em relação às suas adjacências. Isto significa que todos os nós que estão a uma aresta de distância do ponto inicial são encontrados primeiro, então todos os nós que estão a duas arestas de distância são encontrados em seguida, e etc. Tal característica será útil se você estiver tentando encontrar o caminho mais curto do nó inicial até um determinado nó (LAFORE, ROBERT).

Para uma execução organizada e procedural, três regras foram criadas. São elas:

Regra 1
Visite o próximo nó não visitado, se existir, que seja adjacente ao nó atual, marque-o e insira-o na fila (LAFORE, ROBERT).

Lembre que nosso ponto de partida é o nó A, já temos conhecimento sobre ele, logo nenhum processamento a mais é necessário. Tal fato nos permite a executar a regra 1, o que nos leva ao nó B. Após isso, devemos verificar se A não possui nenhum outro nó adjacente não visitado ainda, e então descobrimos C, D e E. Para estes três últimos nós, a regra 1 deve ser aplicada. Agora na fila temos: B C D E.

Após executar a regra 1 para todos os nós adjacentes à A, não teremos mais nós adjacentes não visitados. Então, o que fazer ? Para esta necessidade surge a regra 2.

Regra 2
Se você não puder executar a Regra 1 porque não há mais nó não visitado, remova um nó da fila e torne-o o nó atual (LAFORE, ROBERT).

Removendo um nó da fila teremos B, mas porque não E ? Isto acontece devido ao tipo de fila que estamos utilizando. A sigla FIFO significa first-in-first-out, ou seja, o primeiro que entra é o primeiro que sai, assim como na fila de um banco. Logo, filas que usem esse tipo de esquema de organização de itens terão este comportamento, e este é o nosso caso.

Voltando à nossa linha de raciocínio, remover um nó da fila resultará no nó B, e este é o nosso nó atual. Uma nova execução da regra 2 se faz necessária, mas agora é possível executar a regra 1 pois o nó atual possui nós adjacentes não visitados. Isto fará com que F entre na fila.

C sai da fila, não possui adjacências. Devemos remover o próximo pois a regra 1 não consegue ser satisfeita, logo removemos D da fila. A partir deste, enfileiramos G e concluímos que assim como C, o nó E sai da fila e não possui adjacências.

A interação entre a regra 1 e a regra 2 recria o fenômeno de onda citado anteriormente, pois as adjacências de F e G só serão exploradas totalmente quando todos os nós que estão no mesmo “nível” de seus pais forem exploradas primeiro.

A regra 2 é executada em F, menos um na fila e em seguida H é enfileirado pela regra 1. O mesmo acontece para I quando G é desenfileirado. Execuções contínuas da regra 2 em conjunto da 1 resultarão em uma fila vazia, o que nos leva à regra 3.

Regra 3
Se não puder executar a Regra 2 é porque a fila está vazia, terminou (LAFORE, ROBERT).

Visto que houveram muitas movimentações na fila durante a execução das regras, a Tabela 1 mostra de forma detalhada o passo a passo de todas as operações realizadas.

Evento	Fila
Vá para A
Vá para B	B
Vá para C	BC
Vá para D	BCD
Vá para E	BCDE
Remova B	CDE
Vá para F	CDEF
Remova C	DEF
Remova D	EF
Vá para G	EFG
Remova E	FG
Remova F	G
Vá para H	GH
Remova G	H
Vá para I	HI
Remova H	I
Remova I
Terminado

Se você leu o post anterior sobre busca em profundidade notará que as diferenças são grandes. Compare como as duas abordagens funcionam e deixe sua opinião nos comentários.👍

Visto que já conhecemos toda a teoria necessária para entender e executar uma busca em largura, podemos a partir daí transcrever este algoritmo para um programa Java.

Este método executa as três regras descritas acima de uma forma bem simples. Ele inicia adicionando o primeiro nó do grafo, o ponto de partida, na fila, e partir daí verifica repetidamente se a fila não está vazia. Caso negativo a busca chegou ao fim pois não existem mais nós para analisar, mas caso contrário, ainda existem nós não explorados e os processos descritos nas regra 1 e 2 são executados.

É possível notar que um método auxiliar é utilizado para verificar as adjacências de um determinado nó. Por tal motivo, o segundo laço de repetição se faz necessário pois um nó pode ter N adjacências.

O último laço de repetição utilizado tem a finalidade de somente resetar a flag de visitação dos nós para que buscas futuras possam ser executadas sem problemas.

O método getAdjUnvisitedVertex(vertexIndex) é responsável para um determinado nó obter seus nós adjacentes não visitados, conforme citado acima. Sua implementação é simples e tem apoio da matriz de adjacência e da flag de visitação para a recuperação da informação desejada. Caso encontre, retorna a posição deste nó no array de nós, caso contrário, retorna -1 simbolizando que não encontrou nada.

Ambos os métodos fazem parte de uma classe que foi criada em postagens passadas. Logo, os detalhes que já foram incorporados não serão abordados aqui. Para que você tenha uma visão geral de tudo feito até agora, faça o download do projeto usando o link do repositório no fim do post.

A classe acima é somente utilitária. Sua única responsabilidade é criar e montar um grafo para depois executar a busca em largura nele. O resultado esperado de sua execução é o caminho percorrido pelo algoritmo de busca.

Esta postagem é somente mais uma que compõe a grande série de assuntos envolvendo a teoria dos grafos. Em publicações futuras veremos árvores geradoras mínimas, o algoritmo de Warshall e etc.

Até a próxima minha boa gente ! 😘

Leia nossa última postagem sobre grafos: Busca em profundidade - Grafos

Download do código-fonte
Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/Graphs.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004

Busca em profundidade - Grafos

2017-03-01T12:56:00.000-08:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Comecemos esta postagem com a seguinte pergunta: Em um grafo desconhecido, quais nós são possíveis de atingir a partir de um determinado nó ?

A resposta é simples. A partir de um nó inicial é possível atingir qualquer nó que esteja conectado à ele diretamente ou às suas adjacências por arestas. Esta regra é válida para qualquer nó. Contudo, o processo para chegar a essa conclusão não é tão trivial assim, pois os casos em que isto precisa ser determinado são aqueles que o único conhecimento disponível é sobre um nó inicial, ou seja, um ponto de partida.

Caso você tenha chegado a este ponto do texto não entendendo muito do que já foi explicado, recomendo fortemente que você leia nossa primeira postagem sobre a teoria dos grafos. Clique aqui para dar uma conferida.

A construção desse processo consiste em passos sistemáticos que possibilitam a movimentação de um vértice para outro, e assim de pouco em pouco espera se obter o conhecimento completo do grafo. Existem atualmente duas abordagens conhecidas para este tipo de processo: busca em profundidade (DFS - Depth First Search) e busca em largura (BFS - Breadth First Search). Ambas finalmente alcançarão todos os nós conectados. A primeira busca, alvo do nosso estudo, é implementada com uma pilha, ao passo que a segunda é implementada com uma fila. Esses mecanismos resultarão no grafo sendo percorrido de maneiras diferentes (LAFORE, ROBERT).

A pilha citada no parágrafo acima é uma estrutura que já foi abordada aqui no blog. Caso você a conheça pule este parágrafo, mas caso contrário, clique aqui e dê uma lida antes de continuar nesta postagem.

Descobrir a solução para a pergunta acima assombrou por muito tempo os estudiosos da teoria dos grafos, mas o matemático francês Charles Pierre Trémaux, no século XIX, propôs uma versão da busca em profundidade como estratégia para resolver labirintos.

Figura 1 - O labirinto

Pode parecer complicado comparar labirintos com grafos, mas com um pouco de abstração é possível notar que um pode ser sim representado no outro. Para a entrada do labirinto temos o nó inicial de um grafo, para o término de um caminho ou ramificação temos mais nós, e para os caminhos que interligam todos esses três elementos temos as arestas. Um dos segredos para sair de um labirinto é lembrar o caminho feito e geralmente isso é feito usando um barbante. O herói grego Teseu utilizou desta mesma técnica quando enfrentou o terrível Minotauro em seu imenso labirinto. A busca em profundidade utiliza a mesma idéia, mas ao invés do barbante utilizaremos a pilha, já citada anteriormente.

Figura 2 - O labirinto do Minotauro

O algoritmo que procuramos nos dará certeza que o grafo será complemente escaneado sem que percamos tempo com escolhas erradas, e que após todo o procedimento ter sido feito ele terminará sua execução. Contudo, para realizar tal façanha nenhum pré-planejamento pode ser feito, visto que não temos conhecimento sobre sua estrutura. Então, decisões de direção devem ser tomadas uma após a outra ao longo do trajeto feito (EVEN, SHIMON). Por tais motivos a dúvida apresentada no início da postagem é justificada.

Analisemos a Figura 3 para que possamos tomar conhecimento de como a busca em profundidade funciona.

Figura 3 - Grafo de exemplo

A determinação de um ponto de partida é necessária e já foi citado acima, logo para o grafo da Figura 3 temos o nó A representando esse papel. Neste momento a única informação que temos é que apenas este nó compõe o grafo. Então, precisamos executar três passos essenciais: visitar o nó, colocá-lo na pilha para que possamos lembrar no futuro que já passamos por ali, e marcá-lo como visitado. Tudo isto dá vida à Regra 1.

Regra 1
Se possível, visite um nó adjacente não visitado, marque-o e coloque-o na pilha.

Executando esta regra, partimos de A em direção ao nó B. Em B executamos a regra 1 novamente e partimos em direção à F. O processo novamente se repete e vamos de F para H. O nó H não possui adjacências, e logo estamos parados. Então, o que fazer agora? Neste momento surge a regra 2.

Antes de abordarmos a regra 2 note que a denominação “profundidade” vem do efeito que a regra 1 causa no ato da movimentação do grafo. Note que exploramos toda uma ramificação de nós e arestas para assim depois decidir o que fazer. Essa característica será drasticamente modificada quando abordarmos as buscas por larguras.

OBSERVAÇÃO: O nó inicial também entra nesta regra mesmo não sendo adjacente.

Regra 2
Se você não puder seguir a Regra 1, então se possível, retire um nó da pilha.

Seguindo esta regra, desempilhamos H e voltamos para F, logo em seguida para B e finalmente para A. Executamos todo esse caminho de volta porque não foi possível executar a Regra 1, visto que todo este caminho já tinha sido explorado. Note que o uso da pilha tem imensa importância, pois ele age como se fosse o barbante de Teseu, ele mostra o caminho de volta. Quando chegamos em A, a Regra 1 se torna disponível mais uma vez pois este possui vários filhos. Então de A vamos para C e de C voltamos para A. A partir deste, o próximo destino é D.

O nó D por sua vez possui adjacências e a partir dele vamos para G e depois para I. Após chegar neste ponto, voltamos novamente para A, para finalmente ir para E e finalizar em A pela última vez.

Agora não temos mais o que fazer, já percorremos o grafo inteiro saindo de um ponto inicial e terminando o trajeto nele. Eis que surge a Regra 3.

Regra 3
Se você não puder seguir a Regra 1 ou a 2, então terminou.

A tabela abaixo mostra todas as operações realizadas na pilha enquanto o passo-a-passo, descrito acima, foi sendo feito.

Evento	Pilha
Vá para A	A
Vá para B	AB
Vá para F	ABF
Vá para H	ABFH
Volte para F	ABF
Volte para B	AB
Volte para A	A
Vá para C	AC
Volta para A	A
Vá para D	AD
Vá para G	ADG
Vá para I	ADGI
Volte para G	ADG
Volte para D	AD
Volte para A	A
Vá para E	AE
Volte para A	A
Desempilhe A
Terminado

Visto que já conhecemos todos os passos necessários para executar a busca em profundidade, podemos agora ver sua implementação em Java. Repito novamente, que utilizo esta linguagem de programação por uma questão de afinidade, e nada impede que você implemente este mesmo algoritmo em uma outra linguagem de seu gosto.

A implementação se torna bem simples quando temos as regras em mente. O primeiro bloco, linhas 2 à 4, executam a regra 1 para o nó ponto de partida. Não necessariamente o seu nó de partida deve ser o primeiro item do array. Isto foi feito com a finalidade de facilitar a implementação do algoritmo.

O loop que segue da linha 7 até 16 perpetua a regra 1 e insere a regra 2 no programa. O próximo nó adjacente não visitado é obtido através de uma função específica que retorna a posição deste no array de nós. Caso o nó não exista, a regra 2 entra em ação. Caso contrário, o processo continua conforme descrito na regra 1. A implementação desta função não foi incorporada na função de busca porque havia o receio do código ficar muito extenso e isso atrapalhar a análise do algoritmo.

O último laço reseta a flag de visitação de todos os nós para que a busca possa ser executada posteriormente.

O método getAdjUnvisitedVertex(vertexIndex) é responsável para um determinado nó obter seus nós adjacentes não visitados, conforme citado acima. Sua implementação é simples e tem apoio da matriz de adjacência e da flag de visitação para a recuperação da informação desejada. Caso encontre, retorna a posição deste nó no array de nós.

Ambos os métodos fazem parte de uma classe que foi criada em postagens passadas. Logo, os detalhes que já foram incorporados não serão abordados aqui. Para que você tenha uma visão geral de tudo feito até agora, faça o download do projeto usando o link no fim do post.

A classe acima é somente utilitária. Sua única responsabilidade é criar e montar um grafo para depois executar a busca em profundidade nele. O resultado esperado de sua execução é o caminho percorrido pelo algoritmo de busca.

Nas referências é possível encontrar um excelente trabalho feito pela Universidade Federal da Paraíba, onde é proposto a criação de um labirinto aleatório através da aplicação de um algoritmo de busca em profundidade. Para fornecer as outras respostas do labirinto, como a saída e o menor caminho, outros algoritmos são utilizados. Vale a pena a leitura.

Até a próxima minha boa gente ! 😘

Leia nossa última postagem sobre grafos: Matrizes de adjacência e grafos

Download do trabalho da UFPB: https://drive.google.com/file/d/0BzDmhBY6luU6dktwUXhydTIxcms/view?usp=sharing

Download do código-fonte
Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/Graphs.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004

EVEN, SHIMON; Graph Algorithms; 2012

MENEZES, RÔMULO; MACHADO, LILIANE; MEDEIROS, ÁLVARO; Aplicação de Algoritmos de Grafos para Gerar e Percorrer Jogos de Labirintos Aleatórios; Universidade Federal da Paraíba

Matrizes de adjacência e grafos

2017-02-13T04:53:00.002-08:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Na nossa penúltima postagem tivemos uma introdução sobre a teoria dos grafos, onde vimos sua história, áreas de aplicação, definições e exemplos. Você pode dar uma conferida nele clicando aqui. Hoje entenderemos como podemos representar as conexões de um grafo, ou seja, suas arestas.

Adiante veremos que é possível realizar buscas em grafos e que para executar essas tarefas precisaremos de um tipo de registro das conexões do grafo. Esse registro consiste em uma forma de mapear todas as adjacências de um grafo. Um nó é qualificado como adjacente a outro nó quando a distância entre eles é de apenas 1 aresta. Esse mapeamento pode ser representado através de duas estruturas de dados: matrizes e listas encadeadas. Abordaremos aqui as duas formas, suas implementações, vantagens e desvantagens.

Já vimos aqui no blog o que é uma lista encadeada e como ela funciona. Caso você não se lembre, clique aqui e dê uma relembrada. Uma matriz é uma estrutura baseada em linhas e colunas, igual a uma tabela. Enquanto os vetores ou arrays são estruturas unidimensionais, as matrizes podem ser multidimensionais. No nosso caso, nossas matrizes terão apenas duas dimensões onde ambas serão os vértices do grafo. Logo, se um grafo G possuir N vértices, sua matriz de adjacência terá N x N células. Mas o que significa N x N células? Isso significa que um determinado vértice pode estabelecer conexões com todos os outros vértices do grafo, incluindo ele mesmo.

Figura 1 - Grafo de exemplo

Para o grafo da Figura 1, sua matriz de adjacência é mostrada pela Tabela 1.

Tabela 1 - Matriz de adjacência

Note que para todas as células que possuem o número 1 existe uma aresta conectando os vértices mostrados pela linha e coluna. Então, através da matriz é possível concluir que existe uma aresta que parte de A e vai para B. Por convenção, é determinado que a origem de uma aresta é ditada pela linha da matriz, e o destino a coluna. Isto terá mais sentido para grafos orientados. Como o grafo acima não é orientado, precisamos representar suas arestas de forma bidirecional, ou seja, se existe uma ligação de A para B, então existe uma ligação de B para A. Para todas as células da matriz que possuem o número 0 significa que ali não existe uma aresta conectando dois vértices. Como dito acima, a matriz somente mapeia as conexões adjacentes entre vértices.

Ao contrário de uma matriz, uma lista de adjacência não possui zeros e uns para representar as conexões dos vértices de um grafo, eles formam uma versão mais compacta através do uso de uma lista encadeada, onde em cada posição desta lista existe uma outra lista encadeada. Cada lista individual mostra a quais nós um dado nó é adjacente. Lembre-se disso pois frequentemente essa estrutura causa confusão. Ela dá a impressão que a lista individual inteira forma um caminho, sendo que isso não é verdade. A lista de adjacências mostra quais nós são adjacentes, não caminho de nó a nó (LAFORE, ROBERT). Esta situação ficará mais clara com o exemplo da Figura 2.

Figura 2 - Lista de adjacências

Viu como é fácil se confundir ? Em uma olhada rápida é possível afirmar que existe um caminho que começa no vértice B, passa por A e C, e termina em D embora não seja essa a verdade.

As amostras de código abaixo mostram a implementação dessas duas estruturas em Java, mas como eu sempre digo, nada impede que você construa sua implementação em uma outra linguagem de seu gosto.

Matriz de adjacência
Lista de adjacência

Caso você execute algum desses programas, terá como resultado as conexões do grafo, conforme citado anteriormente. Mas, das duas implementações apresentadas qual utilizar ?

Independentemente dos motivos que irei apresentar aqui, tenha algo sempre em mente. A lista de adjacência é uma versão resumida da matriz de adjacência. Logo, em aplicações que necessitamos mais agilidade para avaliar a adjacência entre vértices, inserindo ou removendo conexões, a lista é mais indicada, mas caso você precise de algo mais completo, a matriz é uma boa escolha pois ela mostra quais nós são adjacentes e quais não são. Como sempre digo, e se você acompanha o blog vai saber, não existem balas de prata na computação. Não existem soluções perfeitas.

Um bom exemplo de como a matriz é superior a lista é em uma busca por profundidade. Através dela o algoritmo de busca é capaz de encontrar os nós que não foram visitados e adjacentes a um nó especificado (LAFORE, ROBERT). Contudo, na eliminação de nós o uso da lista é superior, pois para cada eliminação é necessário o translado de todas as linhas e colunas para cima e para a esquerda, ou para baixo e direita. Este processo é custoso, logo uma abordagem baseada em lista encadeada seria melhor pois somente as referências corretas precisariam ser removidas.

É isso amigos, chegamos ao fim de mais uma postagem sobre a teoria dos grafos. Espero que você tenha gostado. Em postagens futuras abordaremos assuntos mais elaborados como buscas, grafos orientados, ponderados e algoritmos da área.

Até a próxima ! 😘

Leia nossa próxima postagem sobre grafos: Busca em profundidade - Grafos
Leia nossa última postagem sobre grafos: Grafos - O início

Download do código-fonte

Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/Graphs.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou, deixa uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004

A história do blog

2017-01-30T05:43:00.001-08:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Nunca fiz um post sobre a história do blog. As pessoas que me seguem aqui não tem idéia de como isso tudo começou e quais foram os desafios. Então, acho que é minha obrigação trazer essa história a vocês.

Tudo começou no 2011, já era Dezembro, e eu estava com um grande problema para resolver no trabalho. Precisava validar o tamanho de anexos na submissão de um formulário web, mas o real problema é que o formulário era dinâmico, ou seja, em uma execução ele poderia ter 20 campos, mas em outras 45 campos.

Pensei que uma possível solução era tentar validar todos os anexos a partir do momento que a requisição chegasse no servidor, mas cheguei a conclusão de não era possível porque não teria onde armazenar os N arrays de bytes que poderiam chegar. Já que não era possível validar via Java, pensei em validar os dados via Javascript, visto que os anexos ainda estavam na página.

Com muita pesquisa consegui chegar a uma solução que na época não foi tão fácil assim (eu era apenas um júnior, pegue leve comigo 😋) e pensei que seria legal ter um repositório para todas essas soluções desses problemas bizarros. Conversei isso com um colega da época, e ele me deu a ideia de uma wiki mas eu lembrava que já tinha feito um blog muito tempo atrás, só não usava.

Uma vez motivado a criar meu próprio conteúdo para internet, reativei o blog que eu tinha criado num cursinho grátis que eu participei sobre a plataforma de blog do Google, o Blogger. Dei uma mexida no layout e nas cores dele, adicionei umas imagens, montei o post e fiz sua primeira publicação. Nasceu o Preciso Estudar Sempre. Me lembro que a excitação foi imensa, achei que em uma semana meu blog iria bombar de acessos e que ficaria mega conhecido entre as pessoas. O resultado não foi o esperado. Nos primeiros meses eu tinha no máximo um único acesso, o qual eu duvidava que tinha sido feito por alguém humano e não um programa robô. Mesmo assim não desanimei e continuei postando conteúdo nele quando tinha a oportunidade seguindo a mesma linha de pensamento.

Fui nessa mesma batida até 2013 quando notei que se eu não mudasse um pouco os temas que abordava não iria conseguir muita atenção dos leitores, visto que eram assuntos muito específicos. Então decidi abordar temas de diversas dificuldades através de dicas rápidas, manuais, tutoriais e etc. A quantidade de leitores aumentou mas não foi algo absurdo, mas mesmo assim continuei persistindo.

Já em 2014 troquei ideias com outro colega de trabalho que me sugeriu que deveria manter uma certa frequência de postagem pois isso iria me ajudar a atrair mais leitores e que eu divulgasse as postagens em redes sociais. Segui essas dicas e os leitores começaram a aumentar. Inicialmente pensava em uma postagem por semana, mas cheguei a conclusão de que ficava muito corrido porque eu não queria por qualquer conteúdo porcaria. Queria fazer algo com esmero para entregar ao público. Então adotei a meta de duas postagens por mês. Dessa forma conseguia manter uma frequência e entregar postagens boas para vocês. Criei uma página do blog no Facebook e entrei em alguns grupos de T.I. em geral para divulgar as minhas postagens. Fazendo isso os leitores aumentaram mais ainda.

Em 2016, o blog ganhou um logotipo, um mascote e um canal no Youtube foi criado. Para este ano, 2017, a previsão é continuar alimentando o blog com postagens de diversas categorias e a página do Facebook com as postagens publicadas aqui e com notícias sobre estudo em geral. Você verá o mascote em um vídeo sem previsão de lançamento.

Visto que já vimos praticamente a história do blog, um desabafo se torna necessário. Quando conto para as pessoas que tenho o blog e faço postagens frequentemente geralmente escuto muitos elogios e frases como: "não sei se conseguiria fazer isso", "eu nunca arranjo tempo para me dedicar com algo assim", "já tentei uma vez mas depois larguei". Quando paro para refletir sobre essas frases, me pergunto uma coisa: será que as pessoas não acham que eu já pensei em desistir várias vezes ?

A resposta é clara. Sim, eu já pensei em largar o blog muitas vezes e quando falo "muitas" não estou exagerando. Foram incontáveis as vezes que mesmo cansado eu fui procurar algum conteúdo para montar uma postagem ou que fui dormir tarde porque estava terminando a revisão de um post. E aí eu te pergunto: porque ou para que tanto sacrifício? Porque não deixar para lá ? O que eu vou ganhar no fim de tudo isso ? A resposta é clara também. Eu queria reconhecimento pelo meu blog, este era e ainda é o meu sonho, então se eu não correr atrás desse sonho como ele vai se tornar realidade ? É impossível que ele se torne conhecido se eu cruzar meus braços e deixar me derrotar por cansaço ou preguiça. O que vou ganhar no fim disso tudo, ou seja, quando eu estiver bem velho é saber que eu sempre fiz o melhor para tentar fazer com que as pessoas aprendessem algo novo. Esta é a minha recompensa.

Faço esse desabafo motivacional porque a quantidade de pessoas que eu vejo que se deixam abalar é imensa. São muitos os que se deixam levar pela rotina e não conseguem mudar consequentemente não atingindo seus sonhos. E a pior parte é que essas mesmas pessoas reclamam do mundo, como se ele fosse responsável por isso. A resposta é óbvia, ele não é, eles que são. Como eles querem atingir o sonho deles se não começam a se mover ? Reclamações e pragas não são e nunca serão a solução para problemas. Contudo, existe uma parte engraçada nesta história. Essas pessoas quando são questionadas sobre o motivo de não conseguirem atingir seus sonhos, elas sempre tem uma resposta na ponta da língua. O trabalho está sempre complicado, sempre existe aquele chefe que pega demais no pé, eles tem a vida mais difícil do mundo. Motivos são fáceis de encontrar quando queremos, mas assumir o verdadeiro motivo pelo qual não atingimos nossos sonhos ainda, este é o verdadeiro desafio. Se olhar no espelho e assumir que você não conseguiu ainda chegar lá é difícil. Não são todos os que conseguem.

Então, no fim das contas, o que quero dizer é: não tenha medo de perseguir seus sonhos. Se você está infeliz no seu emprego atual e sempre quis ir para outra área, vá! Se você sempre quis abrir seu próprio negócio, vá! Se você sempre quis começar o seu blog ou estudar aquele assunto, não perca mais tempo, vá! Não tenha medo. Ao invés de medo, ponha na balança os prós e contras e avalie se este é o momento correto, mas nunca tenha medo de mudar. Aceitar mudanças faz parte da vida.

Se você chegou a este ponto da leitura, devo te parabenizar por chegar tão longe, mas se o que você leu aqui causou alguma diferença na sua vida, eu te agradeço por tal. Não esqueça de fazer por alguém que precise o mesmo que fiz por você agora.

Até a próxima ! 😘

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou, deixa uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Grafos - O início

2017-01-18T05:28:00.003-08:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Falar sobre a teoria dos grafos aqui no blog é falar sobre um tema que já estudamos várias vezes. Então por abordar novamente? Acho que uma postagem dedicada é válida, pois até o momento só olhamos os grafos por uma determinada ótica, da forma computacional, mas existem várias outras que ainda não exploramos. Logo, minha expectativa é que aqui possa ser um ponto de partida para vários outros assuntos.

Um dos pontos que ainda não foi explorado é a aplicação real da teoria dos grafos na nossa realidade, ou seja, no nosso dia a dia. Se você se vê obrigado a ter de estudar este assunto por causa de obrigações acadêmicas, pode acabar se perguntando: para que serve isso ? onde é usado ?

A resposta pode parecer assustadora, mas você usa a teoria dos grafos frequentemente e não se dá conta disso. Diversas são as aplicações para este ramo da matemática:

Geolocalização: GoogleMaps e Waze
Compactação de arquivos
Estruturas de dados
Ponte área entre cidades
Planejamento de uma viagem em família
Grade das suas matérias na faculdade

Note que alguns dos exemplos citados envolvem nosso cotidiano e outros não. Não existe um limite definido de onde ou quando aplicar a teoria dos grafos, basta somente existir uma associação ou correspondência entre os elementos do problema (NETTO, PAULO OSWALDO). Alguns destes exemplos já foram inclusive discutidos aqui no blog. Como visto no post sobre o Algoritmo de Huffman (você pode dar uma conferida nele clicando aqui) é possível compactar arquivos utilizando uma árvore, e árvores são um dos tipos de grafos.

Quando você está no aeroporto e olha a escala de vôos pode acabar se perguntando: como é possível determinar se um avião que sai de São Paulo pode ou não passar por Fortaleza ? Mais uma vez, a teoria dos grafos está aí. Baseado nesta mesma idéia, o GoogleMaps e Waze funcionam da mesma forma. Como é possível determinar um trajeto de um ponto a outro em um mapa, e ainda respeitando ou não o sentido de ruas ? O sistema operacional que você usa utiliza árvores B para organizar/trazer grandes blocos de informações em disco, como ele faz isso ? Acredito que nesta altura a resposta para todas essas perguntas já esteja clara.

Embora essa teoria parece ser algo dos últimos 40 ou 50 anos, na verdade ela é bem mais antiga que isso. Sua origem data do ano de 1736, onde o grande físico e matemático Leonhard Euler resolveu o problema das Sete Pontes de Königsberg com a construção de um grafo, o qual mostrava que o boato popular de percorrer todas as pontes passando uma única vez era impossível, pois a disposição existentes dos elementos não possibilitava tal (NETTO, PAULO OSWALDO). No problema estudado, os pontos correspondiam a margens do rio, e as arestas, as pontes.

Este grafo deu origem a esse novo campo da matemática e se tornou o primeiro grafo desenhado conhecido.

Figura 1 - O grafo-solução do problema das Sete Pontes de Königsberg

-----------------------------------------------------------------------------------------------------------------------
Nota: Você sabia que a palavra Königsberg vem da língua germânica e significa "montanha do rei" ?
-----------------------------------------------------------------------------------------------------------------------

Tá, tudo bem mas o que é um grafo ?! 😕

Matematicamente um grafo é um conjunto. Essa representação gráfica usada com bolinhas e linhas, conhecidas respectivamente como nós ou vértices e arestas, é para facilitar a visão sobre um problema. Então, é possível concluir que um grafo é um conjunto de vértices e arestas. Aplicando este conceito no grafo mostrado na Figura 1, teríamos:

G = {V,A}

Onde G é o grafo e, V e A são conjuntos. V é o conjunto de vértices do grafo. Entenda um vértice como um ponto de interseção entre arestas. Logo paga G temos:

V = {A,B,C,D}

O conjunto de arestas, representado por A, é composto de:

A = {AB,AD,AC,BA,BD,CA,CD}

Note que as arestas são formadas pelos vértices que a compõem, logo AB significa que existe uma aresta que sai do vértice A e vai para o vértice B. Mas nada impede que você nomeie cada uma e tenha no final algo assim:

A = {a,b,c,d,e,f,g}

O grafo mostrado na Figura 1 é bem básico, e como dito anteriormente, essa postagem será o ponto de partida para vários outros conceitos que ainda estão por vir, como: buscas, matrizes, atribuição de direções ou pesos para as arestas, árvores, árvores geradoras, etc. Todas esses novos conceitos serão abordados em postagens futuras.

Note que esta postagem não segue o padrão de postagens do blog. Não introduzimos nenhum algoritmo ou código-fonte. Optei por esse modelo para que o assunto pudesse ser apresentado de uma forma leve ao leitor.

Terminamos !!! 😆👍

Até a próxima ! 😘

Leia nossa próxima postagem: Matrizes de adjacência e grafos

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou, deixa uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

NETTO, PAULO OSWALDO; Teoria e Modelos de Grafos; 1979

Minha participação em artigo publicado no site EcoDebate

2017-01-06T07:30:00.000-08:00

Olá amantes do estudo, meu nome é João Paulo Maida e é com muito prazer que digo que amo estudar.

Estou muito feliz, pois hoje venho trazer a vocês um artigo publicado recentemente o qual possui minha participação. Embora tal não seja específico da minha área, atuei na revisão e entendimento total do texto.

O autor principal, Fernando Maida, possui uma ampla experiência no assunto com atuação de mais 20 anos neste campo através de atuação profissional, aulas, cursos e palestras ministrados. O perfil completo de todos envolvidos é disponibilizado no final do artigo e o sobrenome não é uma mera coincidência.

O artigo aborda os impactos ambientais e sociais envolvidos na atividade da exploração mineral com produção desenfreada, sem qualquer escrúpulo e controle. São mostrados exemplos recentes desta atividade, onde estes servem de apoio para todo o desenvolvimento do trabalho.

Mesmo que você não seja desta área, assim como eu, vale a pena a leitura, pois o trabalho agrega com uma nova visão sobre a sociedade e as atividades exploratórias no meio ambiente. Clique aqui para ler o trabalho no site EcoDebate.

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou, deixa uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Questões de Concurso - Prova 304 - DataPrev Analista de Negócios 2016

2016-12-27T03:26:00.001-08:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Se você chegou aqui agora e não está entendendo sobre o que é essa postagem, recomendo que você dê uma lida primeiro neste post aqui, e depois volte para continuar lendo. Para você que já sabe do que estou falando, vamos começar.

A prova que vamos analisar é a 304 - DataPrev Analista de Negócios 2016. Consegui selecionar três questões para debatermos, são elas:

Questão 43 - Fácil 😝


Figura 1 - Questão 43 da prova 304 DataPrev Analista de Negócios

Pare sua leitura por aqui, tome o seu tempo, leia calmamente a questão e tente encontrar a resposta. Conseguiu achar ?

Questão 43 - Resposta

Figura 2 - Questão 43 respondida da prova 304 DataPrev Analista de Negócios

Entendamos a questão ! Se concentre nela !

A resposta correta é a opção E. Mas porque esta opção e não a opção D, por exemplo ? A questão fala sobre um dos benefícios da programação orientada a objetos, a abstração de classes e objetos. Isto é importante, pois ele será o delimitador para que não escolhamos a opção errada. Consequentemente a opção D se desqualifica, pois ela engloba a afirmação 3, onde esta cita a utilização de vários padrões conceituais durante todo o processo de criação de software e isto não está relacionado diretamente com a abstração de classes e objetos. Este momento é muito inicial no desenvolvimento de um sistema e esta afirmação cita de algo muito mais à frente.

A opção A também se desqualifica, pois engloba a afirmação 3, e a opção B também está errada, mesmo não incluindo a afirmação 3, mas deixando de incluir uma afirmação que está correta, a 2. Esta está correta pois de fato a orientação a objetos traz essa característica. A possibilidade de modelar dados através de classes e objetos eleva o programador a um outro nível de desenvolvimento de software, permitindo que ele desenvolva um código mais limpo e fácil para manutenção e reuso.

A opção C deixa de lado a afirmação 1 o que a torna também errada. Através da orientação a objetos é possível criar estruturas de classes e interfaces conectadas entre si que tornem a reutilização de código maior. Polimorfismo e herança são ótimos exemplos deste caso.

Questão 44 - Médio 😑

Figura 3 - Questão 44 da prova 304 DataPrev Analista de Negócios

Mais uma vez tome o seu tempo e leia cuidadosamente a questão. Essa aí está moleza!

Sobre o que o enunciado se refere ? Simples ! Ele narra a situação onde existe uma classe abstrata e todas as classes que a estendem, se tornando assim filhas, são concretas.

Figura 4 - Diagrama de classes de exemplo

A Figura 4 exemplifica a situação que a questão narra. A classe Montadora é abstrata, logo ela não pode sofrer instanciação direta através do operador new. Então seus filhos entram em ação sendo representações concretas de um pai abstrato, onde em cada um é definido um comportamento particular, e eles sim podem ser instanciados. Tal comportamento é exemplificado pelo método montar().

Imagine o seguinte cenário: surgiu a necessidade de se trabalhar com dados reais, ou seja, centenas de montadoras, onde cada uma monta seus carros de formas completamente diferentes. Como representar isso? Uma única classe Montadora com todos as formas possíveis de se montar um carro não seria uma boa escolha, pois vc acabaria com uma classe com alguns milhares de linhas. Talvez modificações em uma parte do código poderiam criar bugs em outras, afetando assim a linha de montagem de outros automóveis.

Da forma mostrada pela Figura 4 é possível especializar a montagem de carros em classes diferentes e adicionar novas montadores sem mexer nas que já existem. Mas porque especializar ? Especializar é importante pois assim cada uma conhece sua forma de montar carros e não precisa conhecer o método empregado pelas outras ou de características gerais a todas montadoras. Tudo o que for comum a todas as montadoras pode ser posto na classe abstrata, e assim a classe especialista (concreta) se preocupa unicamente com sua responsabilidade no momento, montar carros.

Questão 44 - Resposta

Figura 5 - Questão 44 respondida da prova 304 DataPrev Analista de Negócios

A questão pergunta qual é o conceito obtido quando se obtém novos exemplares a partir de uma representação abstrata. Este processo já foi citado nesta explicação, é a instanciação. Logo, a resposta correta é a opção B.

Questão 45 - Fácil 😝

Figura 6 - Questão 45 da prova 304 DataPrev Analista de Negócios

Respire fundo e tome o seu tempo.

Para responder esta pergunta precisaremos relembrar um conceito inicial da orientação a objetos, o encapsulamento. Muitas vezes é necessário restringir a visibilidade de características (atributos) e comportamentos (métodos) de uma classe, para que recursos externos não utilizem eles de forma indevida. A falta dessa atividade pode tornar o seu projeto de software fraco contra ataques de softwares maliciosos, pois estes podem ocasionar erros propositalmente levando assim a um travamento total do software. Segundo CHESS, BRIAN; WEST, JACOB o que torna o seu software fraco não são problemas de ambiente, como antivírus, firewall, etc.; mas sim erros arquiteturais como este.

Um ótimo exemplo desta situação é uma classe de acesso a banco de dados. Seus únicos comportamentos são: conectar e desconectar; e seus únicos atributos são: login, senha e o driver do banco. Reflita sobre a seguinte questão: qual seria a necessidade de tornar o login e senha do banco de dados visível para qualquer classe do sistema ? A resposta é simples: nenhuma. Neste momento o encapsulamento entra em ação.

É possível criar métodos que encapsulem estas informações. Para o atributo login, por exemplo, não é interessante fornecer uma forma que uma classe usuária possa obter qual login sendo utilizado no momento, mas talvez seria bom fornecer uma forma de se atribuir um login novo caso o default não funcione. Com o encapsulamento os métodos de acesso se tornam os únicos responsáveis pelos recursos que manipulam, sendo eles atributos ou métodos, formando assim um canal de acesso único.

Espero que com a explicação dada a resposta da questão se torne clara.

Questão 45 - Resposta

Figura 7 - Questão 45 respondida da prova 304 DataPrev Analista de Negócios

As opções A, B, D e E são totalmente relacionadas ao encapsulamento, como já citado acima. A única que não é relacionada é a opção C, sendo ela a resposta final.

Com isso terminamos as questões da prova 304 - DataPrev Analista de Negócios. Espero que vocês tenham gostado desse novo formato, e se quiser sugiram provas e questões. 😁

Até a próxima ! 😘

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou, deixa uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

CHESS, BRIAN; WEST, JACOB; Secure Programming with Static Analysis; 2007

Questões de Concurso - O início

2016-12-27T02:59:00.003-08:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Este é o primeiro post de uma nova série de postagens aqui no blog. Sempre que você ver um post com o título começando com Questões de Concurso, já pode esperar algumas belas questões, suas respostas e explicações.

Mas que tipo de questão você vai trazer João ? Sempre trarei questões relacionados à programação, orientação a objetos, estruturas de dados e algoritmos. Todos esses assuntos já estamos discutindo aqui a um certo tempo, logo você tem um grande repositório de material para tirar suas dúvidas. 😊

Minha motivação para começar essa nova série foi trazer uma nova forma de conteúdo pro blog e agregar mais para a comunidade que é ou está focada em concursos públicos.

Este post, especificamente, será o catálogo de todas as postagens dessa nova série. Caso você queira fazer uma pesquisa em todas as provas já comentadas, pode dar uma olhada aqui.

Posts da série Questões de Concurso:

Prova 304 - DataPrev Analista de Negócios 2016

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

WriteYourOwnGraph v2.0

2016-12-19T05:24:00.001-08:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Estou muito feliz 😄 em dizer que através de muito esforço e trabalho, consegui concluir uma versão 2.0 da ferramenta WriteYourOwnGraph. Nesta versão foram adicionadas novas características, como:

Adição de arestas curvas através da curva cúbica de Bezier
Adição de títulos aos nós
Aperfeiçoamento da seleção de arestas
Adição do painel de propriedades
Adição do botão Reset na barra de ferramentas
Fix de alguns bugs

Figura 1 - Versão 2.0 da ferramenta WriteYourOwnGraph

Com o painel de propriedades é possível customizar os nós e arestas de seu grafo, adicionando títulos aos nós ou alternando entre arestas curvas e retas. O painel de camadas não teve seu funcionamento alterado, e a nova ferramenta adicionada no painel de ferramentas possibilita que o usuário possa reiniciar seu trabalho de forma ágil, limpando toda a área de trabalho.

É importante citar que houveram mudanças arquiteturais na ferramenta, pois agora é necessário o uso de um servidor de aplicações para que a WriteYourOwnGraph funcione. Isto se dá pelo fato do painel de propriedades ser carregado via AJAX. Realizei essa escolha visando o reuso e facilidade de manutenção das telas. Eu utilizei o Tomcat, mas sinta-se livre para utilizar qualquer servidor de sua vontade. Novas características e funcionalidades ainda estão por vir. Se você quiser acompanhar, entre no repositório GitHub da ferramenta (o link está no fim do post) e dê uma olhada na aba de Issues.

Figura 2 - Grafo com arestas curvas

A Figura 2 mostra um grafo de três nós e duas arestas sendo essas duas curvas, onde a selecionada tem suas propriedades mostradas no painel.

Faça um teste em casa, me conte aqui nos comentários o resultado, e antes de tudo te desejo um feliz natal com muita felicidade para você e toda sua família. 😉 🎅🎄

Download do código-fonte

Release WriteYourOwnGraph v2.0: https://github.com/PrecisoEstudarSempre/WriteYourOwnGraph/releases/tag/2.0

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

O código de Huffman

2016-11-29T10:23:00.001-08:00

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Você já parou para pensar como os programas de compressão de dados, como WinZip, WinRar, GZIP, entre outros conseguem diminuir o tamanho de um arquivo ? Como será possível diminuir um arquivo de 1Gb para 600 Mb sem perder a informação contida ali ?

Em 1952, David A. Huffman criou o código de Huffman [1] com o intuito de construir um código binário de redundância mínima mais eficiente do que de seu professor, Roberto M. Fano [2]. Através de sua criação se tornou possível a realização de compressões utilizando combinações mínimas de códigos binários não redundantes, ou seja, que não se repetem.

Figura 1 - David Albert Huffman

Mas porque comprimir dados é algo tão importante ?

Pense na seguinte situação: você tem que enviar alguns dados via internet, mas sua conexão é instável, cai toda hora e você não pode enviar pacotes muito grandes, pois podem haver problemas de falta de informação. Então, o que você faz ? Não envia os dados ? Neste tipo de situação a compressão de dados pode ser uma bela mão na roda.

Para que possamos realizar a compressão dos dados utilizando o código de Huffman, devemos primeiro montar uma tabela com duas colunas. A primeira coluna contém os caracteres usados no texto enviado, e a segunda os códigos binários que representam cada caractere. Contudo, você lembra no início do post que eu citei que o código de Huffman é redundância mínima ? Essa redução de redundância significa que cada caractere se transforma em um código binário único.

Para fins de exemplo em todo o post utilizaremos o seguinte texto como exemplo:

"o rato roeu a roupa do rei de roma"

Para cada caractere utilizado um código binário único é associado a ele, ou seja, a letra "o" poderia ser 00, o "b" 10, ou o "a" 11. Porém, é importante ressaltar que nenhum código pode conter outro, por exemplo: se a letra "b" é 10, a letra "r" não pode ser 1000, pois se fosse haveria um problema grande no momento de descompressão. O que seria "r" e o que seria "b" ? Nenhum código pode ser unicamente 0 ou 1 também, pois isso eliminaria toda a gama de combinações binárias possíveis que começam com estes dois números.

Mas uma pergunta permanece: onde está a compressão nisso tudo ? Em modelos como ASCII ou o Unicode, todos os caracteres mapeados por tais possuem, respectivamente, 1 e 2 bytes. Então o nosso texto codificado em um desses modelos seria uma sequência de 0 e 1.

1 byte = 8 bits

2 bytes = 16 bits

A resposta se tornou clara. Se no melhor dos cenários, o modelo ASCII, mapeia cada caractere como 8 bits e conseguimos diminuir essa quantidade para 2 bits, está aí a compressão.

A tabela citada no parágrafo acima é o resultado final do algoritmo do código de Huffman, ela acaba atuando como uma cifra, pois através da mesma é possível comprimir e descomprimir qualquer caractere do texto enviado. Então, tais tarefas que pareciam ser extremamente complicadas acabam se tornando algo simples pois, somente precisamos ler cada caractere e achar seu correspondente binário para comprimir, e para o processo reverso, analisar cada binário e ver sua correspondência em caractere.

Mas como construir a tabela ? A resposta reside em uma árvore binária completa, onde nas folhas ficam os caracteres do nosso texto. Se você nunca leu nada sobre árvores binárias, clique aqui ou dê uma olhada na postagem feita aqui no blog sobre árvores binárias. O link estará no fim desse post.

Para montar a árvore é necessário analisar o texto a ser processado. Note que algumas letras se repetem como o "o", "i", "e", "b", entre outras. O primeiro passo que devemos tomar é montar uma relação de todas as letras usadas, onde cada uma deve vir acompanhada com a quantidade de vezes que se repete. A Tabela 1 mostra a relação montada para o texto de exemplo.

Tabela 1 - Mapa de caracteres com suas quantidades

Note que a relação está ordenada de forma ascendente pela quantidade de cada letra e isso é importante porque como veremos adiante está ordem é determinante para a execução do algoritmo. É de alta importância ressaltar que o caractere whitespace também é contabilizado na nossa análise, pois quando o texto for descomprimido queremos que o texto de saída seja igual ao de entrada. Com a relação pronta podemos montar a árvore binária, seguindo os passos abaixo.

Passo 1: Utilizando a Tabela 1, transforme todas as letras e suas respectivas quantidades em raízes de árvores binárias. Por uma questão de simplicidade de representação iremos utilizar essa bolinhas para representar os nós da árvore e o número abaixo de cada uma é a quantidade de repetição de cada letra.

Figura 2 - Passo 1 da construção da árvore binária de Huffman

Passo 2: Pegue os dois primeiros nós, e transforme eles em filhos de um novo nó, onde a quantidade de repetição desse novo nó é a soma das quantidades de seus filhos. Como este novo pai não possui caractere, seu conteúdo será em branco. Lembre-se de como as árvores binárias funcionam, menores à esquerda e maiores à direita.

Figura 3 - Passo 2 da construção da árvore binária de Huffman

Passo 3: Reordene os nós pela quantidade de repetição de forma ascendente.

Figura 4 - Passo 3 da construção da árvore binária de Huffman

Passo 4 até 10: Repita os passos 2 e 3 até que sobre somente um único nó.

Figura 5 - Passo 4 da construção da árvore binária de Huffman

Figura 6 - Passo 5 da construção da árvore binária de Huffman

Figura 7 - Passo 6 da construção da árvore binária de Huffman

Figura 8 - Passo 7 da construção da árvore binária de Huffman

Figura 9 - Passo 8 da construção da árvore binária de Huffman

Figura 10 - Passo 9 da construção da árvore binária de Huffman

Figura 11 - Passo 10 da construção da árvore binária de Huffman

Não há muito o que explicar aqui, pois as imagens já fazem esse trabalho. Note que o processo de criação da árvore de Huffman é algo bem simples e como resultado todos os caracteres acabam virando nós folha. Lembre-se deste fato, pois ele será de extrema importância na montagem da implementação em Java do nosso algoritmo.

Visto que já abordamos o processo de criação da árvore, podemos começar a abordar o processo de criação da sequência binária. É bem simples de fato. Para cada caminho à esquerda tomado é acumulado 0 ao resultado final, e para cada caminho à direita é acumulado 1. Então, utilizando a Figura 11 podemos concluir que o caractere 'e' é igual à 000, o 'a' 001, o 'p' 10101 e assim segue até o último. Faça o teste, gere todos os códigos de todos os caracteres e conclua que o que foi dito no início do post é de fato verdade. Nenhum código consegue ser contido em outro, por isso é importante que os caracteres sejam as folhas desta árvore.

Como já disse em outras postagens, utilizo Java para a implementação do que estou abordando por uma questão de afinidade, mas nada impede que você recrie a mesma situação na linguagem de sua preferência. Vamos analisar o código parte por parte.

A classe HuffmanNode dispensa comentários complexos. Ela é uma simples classe com alguns atributos e getters e setters. Dentre estes atributos os que merecem mais atenção são: isLeaf e frequency. O primeiro representa um booleano que determina se um nó é folha ou não, criado para tornar a leitura do código melhor. O segundo é a frequência de repetição já citada anteriormente. Os demais atributos são os que tornam a classe um nó de uma árvore binária, ou seja, uma referência para um possível filho à esquerda ou à direita e um valor inteiro para o conteúdo.

Note que eu disse "valor inteiro" e não "caractere". Porque isto acontece se nossa árvore contém letras nas extremidades ? Em Java, e acredito também que em outras linguagens, é possível transformar valores inteiros em caracteres e vice-versa. Isto se dá pelo fato de todo caractere ser internamente um número na tabela ASCII ou no modelo Unicode. Deixarei na seção Outros links o link para a tabela ASCII, onde é possível ver todos os códigos numéricos de todos os caracteres. Faça o teste em casa. 😀

Preferi utilizar esta abordagem por uma questão de conforto, pelo fato de que é difícil identificar onde está o nó space, e também é uma forma de "marcar" os nós sem conteúdo. Veremos este ponto adiante.

Abaixo, a classe que representa a árvore.

Se concentre nos seguintes tópicos listados abaixo:

O atributo root - Representa a raiz da nossa árvore. É através dela que começamos qualquer busca. É a única referência existente a um nó.
Método getCharFrequency - Monta a relação de caracteres e suas respectivas quantidades de repetição, assim como a Tabela 1 também mostra. Esta relação serve de entrada para a montagem da árvore.
Método createBinaryMap - Monta uma relação de caracteres e suas respectivas sequências binárias, onde as sequências somente serão alimentadas após o processamento da árvore. Esta relação é o resultado do processamento feito pela árvore.
Método initializeTree - Cria a lista de raízes.
Método createTree - Executa todo o procedimento explicado pelas Figuras 2 até 11. Seu parâmetro de entrada é a lista gerada pelo método initializeTree.
Método crypt(String nonCryptedText) - Representa a interface pública para a compressão de dados. Sua responsabilidade é receber um texto não comprimido, realizar a compressão e retornar sua versão compactada.
Método crypt(HuffmanNode root, String currentBinary, Map binaryMap) - Versão sobrecarrega do método crypt. Realiza a busca recursiva na árvore, começando da raiz e indo até as folhas. Os três parâmetros são necessários, pois como é baseado em recursividade, o parâmetro root é atualizado constantemente, a atual sequência binária também é atualizada de acordo com o caminho tomado, e o mapa é utilizado para armazenar a sequência a partir do momento que uma folha é atingida. Note que este método não procura somente um único caractere, e sim todos. A árvore é vasculhada completamente.
Método decrypt - Sua responsabilidade é receber um texto comprimido e retornar sua versão descompactada. Tal é realizado utilizando a tabela resultado montada no processo de compressão.

Como utilizar ?

Note que a utilização é bem simples. Caso você queira comparar resultados de tamanho de arquivo antes e depois da compactação, siga as seguintes instruções:

Visite o site http://br.lipsum.com/
Gere um texto com 1000 palavras
Guarde esse texto um novo arquivo txt
Gere o código binário a partir do texto através de algum conversor online. Guarde o resultado em um novo arquivo txt
Inicie o programa de compactação passando como entrada o texto gerado
Aguarde pelo resultado, copie o código binário compactado gerado e cole em um novo arquivo txt
Analise o tamanho dos dois arquivos, a versão binária não compactada e a compactada, e veja a diferença de tamanho entre eles. Caso você fique com dúvidas sobre a integridade do conteúdo compactado, realize a descompressão e compare os resultados. O texto descompactado deve ser igual ao gerado pelo site da etapa 1.

Seguindo estas instruções, obtive o resultado mostrado pela Figura 12.

Figura 12 - Comparação de tamanho de arquivos

Terminamos !!! 😆👍

Baixe o código nos links abaixo e deixe aí sua opinião.

Download do código-fonte

Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/HuffmanCode.git

Link do GoogleDrive: https://drive.google.com/file/d/0BzDmhBY6luU6Vi1pb3BDenRvVEk/view?usp=sharing

Link do Dropbox: https://www.dropbox.com/s/30i7zvwgp29caxi/HuffmanCode.zip?dl=0

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Outros links

ASCII Table and Description - http://www.asciitable.com/

Post sobre árvores binárias - http://precisoestudarsempre.blogspot.com.br/2015/01/arvore-binaria-implementacao-em-java.html

Referências

[1] LAFORE, ROBERT; Estruturas de dados e algoritmos em Java; 2004

[2] Codificação de Huffman - https://pt.wikipedia.org/wiki/Codifica%C3%A7%C3%A3o_de_Huffman