Olá amigos, bem vindos a segunda parte de nossa jornada em torno das Distâncias entre edições. 

No primeiro artigo, eu parei bem no momento de aplicar ao nosso problema uma estratégia de resolução de problemas chamada de Programação Dinâmica.

A ideia seria já aplicá-la agora neste segundo artigo, porém ao longo de minha análise percebi que um há um conceito que poderia ser um pouco confuso para não-programadores: a navegação através de uma matriz com a utilização de dois índices. 

Por isso, essa segunda parte será uma breve apresentação do conceito de Matrizes e Índices.  Ele é fundamental para conseguirmos entender com clareza todo o algoritmo.

 

Matrizes, Índices e Cartelas de Bingo

Sabe quando você joga Bingo e vai marcando em uma cartela os números que vão sendo sorteados? 

Num dado momento você olha pra cartela, vê que todos os grãos de milho estão posicionados nas casas (eu sempre joguei bingo raiz, sinto muito) e se sente livre para gritar que o jogo terminou e ganhar o dinheiro, correto?

Para um computador realizar tal façanha  (pensando didaticamente de forma ingênua) ele precisaria criar um modelo lógico da cartela e sair marcando e conferindo casa a casa toda vez que um número novo fosse sorteado.

Quando todos estivessem marcados ele anunciaria Bingo!  

Para construir tal modelo, as linguagens de programação dispõem de um mecanismo chamado Matriz e utilizam dispositivos chamados de índices para registrar em qual posição da matriz o processamento do algoritmo se encontra.

 

Verificando na prática

Vamos pensar de forma prática. Imagine uma matriz de nome A com 3 linhas e 3 colunas 

O quadro verde da imagem acima informa que o nosso algoritmo está na posição inicial da matriz, uma vez que ambos os índices estão na posição zero. Essa informação também é  representada como sendo A(0,0).    

Esta segunda imagem mostra o que acontece quando o valor do Índice J é incrementado em uma unidade. O algoritmo sai da posição A(0,0) e vai para a posição A(0,1). Ou seja, começa a navegar horizontalmente na matriz. 

Se ao invés de incrementar o índice J, nós estivéssemos alterado o valor do índice I, a movimentação seria de A(0,0) para A(1,0) e a navegação do nosso algoritmo aconteceria na Vertical. Conforme apresentado na terceira imagem acima.   

E por fim, se fosse necessário caminhar com nosso algoritmo em forma de diagonal, poderíamos incrementar os dois índices ao mesmo tempo. A movimentação aconteceria da posição A(0,0) para a posição A(1,1). 

Ou seja, através da manipulação dos I e J é possível navegar através das células da matriz de forma horizontal, vertical e até em diagonal se preciso. 

 

Conclusão

Toda essa tangente foi necessária, porque um dos pilares da Programação Dinâmica é o de dividir problemas grandes em problemas maiores e em problemas menores.

Depois dessa divisão, os resultados são armazenados numa estrutura paralela. Essa estrutura paralela é representada nos algoritmos através de uma matriz. E é com a utilização de índices que o algoritmo navega entre os resultados armazenados ao longo da execução.

Finalmente temos todas as informações para, no próximo artigo, colocar o Algoritmo de Distancia entre edições do Levensthein para funcionar. 

Obrigado pela leitura e te vejo na parte 3.