Busca em largura - Grafos

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

Leia Mais ››

Busca em profundidade - Grafos

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

Leia Mais ››

Matrizes de adjacência e grafos

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

Leia Mais ››

A história do blog

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

Leia Mais ››

Grafos - O início

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

Leia Mais ››

Minha participação em artigo publicado no site EcoDebate

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

Leia Mais ››

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

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

Leia Mais ››