Este problema consiste em contar o número de caminhos para chegar iniciando até parte inferior direita em uma matriz MxN realizando no máximo k curvas como mostrado na figura.
O que é uma curva?
Cada movimento que altera a direção é considerado uma curva, isto é,
se nós estávamos nos movendo ao longo da linha e passamos a nos mover ao longo da coluna
ou se estávamos nos movendo ao longo da coluna e agora passamos a mover ao longo da linha.
Podemos resolver este problema em tempo polinomial, utilizando uma matriz multidimensional com 4 dimensões para guardar a quantidade de caminho nas células considerando a quantidade de curvas e mudanças de direção.
O vídeo mostra como implementar a solução deste problema.
O problema da mochila é um problema de otimização combinatória. Isto que dizer que temos que trabalhar com diversas combinações e obter uma combinação que é ótima, ou seja, é a melhor segundo algum critério. O problema da mochila é um dos 21 problemas NP-completos de Richard Karp.
Este tipo de problema queremos preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é preencher a mochila com o maior valor possível, contudo não podemos ultrapassar o peso máximo. Vemos portanto que formulação do problema é extremamente simples, porém sua solução é mais complexa.
No vídeo apresentamos como resolver esta versão da mochila.
Existem diversas variações do problema da mochila. Se você estiver curioso dê uma olhada na wikipedia.
A sequência de Fibonacci é uma sucessão de números que, misteriosamente, aparece em muitos fenômenos da natureza. Ela foi descrita no final do século 12 pelo italiano Leonardo Fibonacci. É uma sequência infinita que começa com 0 e 1 ou 1 e 1 (depende de onde você está lendo a informação). Os números seguintes são sempre a soma dos dois números anteriores. Portanto, depois de 0 e 1, vêm 1, 2, 3, 5, 8, 13, 21, 34…
Logo
F[1] = 1
F[2] = 1
F[n] = F[n-1] + F[n-2], para n > 3
Esta definição mostra claramente como podemos implementar a sequência usando recursividade, isto é, podemos criar uma função e chamá-la recursivamente para obter os valores F[n-1] e F[n-2] até chegar nos casos base que são F[1] e F[2].
Contudo podemos ver na figura abaixo que existe muito trabalho repetido. Podemos usar os recursos da programação dinâmica para melhorar o desempenho deste cálculo.
No vídeo vemos como implementar a sequência de Fibonacci usando recursividade e usando programação dinâmica.
Dado um valor de troco N (um número inteiro no nosso exemplo). Nós temos suprimento infinito de cada tipo de moeda do conjunto S = {S1, S2, .., SM}. Note que temos portanto M tipos de moedas e teoricamente temos infinitas delas. Quantas maneiras podemos combinar as moedas para obter um troco exato? A ordem das moedas não importa.
Por exemplo temos que dar um troco de N = 4 dinheiros.
O conjunto de moedas que temos é S = {1,2,3}.
Podemos ver que existem quatro soluções: {1,1,1,1}, {1,1,2}, {2,2}, {1, 3}.
Assim a resposta do programa deve ser 4.
Este problema pode ser resolvido por DP. Identificamos as duas características:
1) Subestrutura ótima
Para contar soluções, podemos dividir todas as soluções em dois subconjuntos:
a) Todas as soluções que não contêm moeda "i" (ou seja Si).
b) As soluções que contêm pelo menos uma moeda Si.
Desta forma podemos escrever o problema de contagem como
C(S, n) = C(S', n) + C(S, N-Si)
Onde S' = S - {Si}
Desta forma vemos que o problema tem a propriedade subestrutura ótima como o problema pode ser resolvido usando soluções de subproblemas. A equação e as condições abaixa deixam claro também que os problemas são sobrepostos.
Temos que notar que existem algumas condições:
a) C(S,0) = 1, pois se n=0 existe uma solução que não precisa de mais moedas
b) C(S,n) = 0, se n<0, pois n negativo, não há uma solução do problema (subtraiu demais)
c) C(S,n) = 0, se S = {} e n > 0, pois se não temos moedas para dar um troco "n" (já que n é maior que zero), não tem como acharmos uma solução.
O que falta no exemplo acima? Se você falou a memorização dos dados... acertou!
A memorização aumenta bastante a velocidade, uma vez que não precisamos recalcular.
Em computação a programação dinâmica é um método utilizado para a construção de algoritmos capazes de resolver problemas computacionais. Este método é aplicável aos problemas cuja solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada.
A solução anterior é memorizada para evitar recálculo.
Desta forma a programação dinâmica ou DP (Dynamic Programming) resolve um problema a partir de subproblemas que sobrepostos compõem o problema original.
Um problema computacional pode ser resolvido por DP se possuir duas características denominadas (1) subestrutura ótima e (2) superposição de subproblemas. Um problema apresenta uma subestrutura ótima quando uma solução para o problema contém em seu interior soluções para subproblemas - isto é temos a mesma fórmula de recorrência. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes - é aí que entra a memorização.
A DP não é uma forma intuitiva de pensar, portanto temos que ver diversos exemplos para conseguir compreender e assimilar como ela trabalha. Vou criar a partir de agora um conjunto de posts que mostram como solucionar alguns problemas usado DP. Estes posts virão com uma implementação completa em Java para o problema. O primeiro da série busca descobrir de quantas maneiras é possível dar um troco (N) utilizando um determinado conjunto de moedas.
Um versão inicial do livro sobre uso de Padrões em Java está disponível para download no endereço https://goo.gl/smbjtX. Este livro mostra alguns padrões de projeto que eu utilizei com mais frequência neste Blog. O livro está sendo distribuído com a licença Creative Commons.
Um versão inicial do livro Introdução ao Java está disponível para download no endereço https://goo.gl/paqpmv. Neste livro faço um apanhado condensado das informações e vídeos que posto neste Blog sobre a utilização da linguagem Java. O livro está sendo distribuído com a licença Creative Commons.
O material ainda não está completo. Vocês verão dois grandes capítulos ainda não escritos. Este livro também não foi sujeito a revisão, portanto cuidado com os erros de português. Toda sugestão será bem vinda.
Apresentamos em um post antigo denominado Recursividade - Parte 2 ou MergeSort como implementar um algoritmo bastante eficiente de ordenação. Este algoritmo é o mergesort que usa o método de dividir para conquistar. Como o mergesort dividi a lista de elementos que devem ser ordenados em sublistas, podemos melhorar um pouco o desempenho em ambientes de multiprocessamento. Como? Fazendo que as sublistas sejam processadas em paralelo pelos diversos processadores que possuímos.
Vamos ver no vídeo como podemos implementar threads com mergesort para torná-lo mais rápido via paralelismo. Note que não estamos alterando o número de operações, portanto a complexidade do algoritmo é a mesma.
Recentemente precisei de um cronômetro e (para variar) o Windows não tinha. Então resolvi fazer uma classe em Java que implementasse o cronômetro na tela. Precisava somente de um cronômetro simples, que ao clicar em "Iniciar" começasse a contar o tempo (em segundos) e que eu pudesse parar.
A classe que implementa o cronômetro pode ser vista no vídeo. É interessante perceber que é necessário mobilizar um monte de coisas para fazer o cronômetro funcionar:
precisamos criar uma interface gráfica que utiliza JFrame, JPanel, JLabel e JButton para permitir a comunicação com o usuário
para criar os tratadores dos botões, isto é, os procedimentos que devem ser executados quando clicamos nos botões utilizamos uma classe ActionListener anônima na qual alteramos o método actionPerformed
precisamos criar uma thread de timer capaz de ser disparada a cada "x" segundos, ou no nosso caso milissegundos
para o timer funcionar temos que criar outra classe anônima que implementa TimerTask.
No post anterior sobre Redução de Dimensionalidade apresentamos somente os conceitos teóricos para realizar da redução. Neste novo post apresentamos um código em Java que faz SVD (Singular Value Decomposition).
O desenvolvimento deste exemplo foi bastante simplificado ao usarmos o pacote JAMA, desenvolvido pelo NIST, que permite a realização de diversas operações sobre matrizes em Java. Mais informações sobre o pacote veja no site do Jama.
Vimos no post anterior (do capítulo 5) como utilizar vetores, que são arranjos como um conjunto de n valores de um mesmo tipo. Podemos expandir este conceito considerando que estes valores podem ser arranjados em diversas dimensões, sendo a mais comum o arranjo bidimensional ou matriz bidimensional. Uma matriz bidimensional pode ser utilizada por exemplo para representar um conjunto de valores de uma tabela por exemplo.
Como veremos no vídeo, uma matriz é basicamente um vetor onde cada
elemento é por sua vez um vetor, desta forma podemos obter uma matriz retangular como em
int[][] retangular = new int[3][4]; // matriz com 3 linhas e 4 colunas
mas também podemos criar uma matriz irregular como
int[][] retangular = new int[3]; // retangular[0] = new int[5]; retangular[1] = new int[10];
retangular[2] = new int[2];
A primeira linha gera uma matriz com 3 linhas, porém as colunas ainda não estão definidas. As três linhas seguintes geram as colunas de cada linha - na segunda linha de código a primeira linha é configurada para possuir 5 colunas, depois a segunda com 10 e na última linha de código a terceira linha terá 2 elementos.
Um vetor (array) é um objeto que contém um número fixo de valores de um único tipo. O tamanho de um vetor é estabelecido quando o array é criado. Após a criação, este tamanho é fixo e não pode ser mudado. Cada item em um vetor é denominado elemento. Cada elemento pode ser acessado por um índice numérico. A numeração de um vetor começa com 0.
Vamos fazer uma variação deste exemplo para mostrar que é possível criar um array não somente dos tipos primitivos (int, double, char...), mas de qualquer classe de desejarmos. Veja o Exemplo 02-a.
Neste post trataremos de 3 estruturas de repetição em Java. Um problema com estruturas de repetição é o que chamamos de looping infinito, isto ocorre devido ao fato do bloco de programa desta estrutura fica repetindo a mesma sequência de códigos esperando por um resultado que nunca irá acontecer. Por isto devemos garantir que a variável que controla o loop seja alterada.
A primeira estrutura que veremos é for. Esta é a instrução mais comum e tem o formato apresentado abaixo. A expressão de inicialização inicializa o laço for; ele é executado uma vez, antes da primeira execução do bloco de comandos. A expressão de incremento é chamada após cada iteração do loop for. É perfeitamente aceitável esta expressão aumentar ou diminuir a variável de controle. O bloco de comandos será executado enquanto a condição de comparação for verdadeira. Quando a expressão avaliada na comparação for falsa, o loop termina.
for(inicialização; comparação; incremento) { bloco de comandos; }
Outra estrutura de repetição é while. While executa uma comparação com a variável. Se a comparação for verdadeira, ele executa o bloco de instruções ( entre { } ) ou apenas a próxima linha de código logo abaixo (se não houver o bloco entre {} ). O bloco de comandos será executado enquanto a condição de comparação for verdadeira.
while (comparação) { bloco de comandos; }
while (comparação) instrução;
A terceira estrutura é denominado do ... while. É similar ao while, porém a comparação é realizada somente no final, desta forma o bloco será executado pelo menos uma vez. O bloco de comandos será executado enquanto a condição de comparação for verdadeira.
Estruturas condicionais (que veremos neste post) e de repetição (que veremos no próximo) são fundamentais para a maioria das linguagens de programação. Sem estas estruturas, as instruções dos programas seriam executadas sequencialmente sem nenhum tipo de reaproveitamento ou ramificação, como vimos no post do capítulo 2.
Instrução if () ... else ...
A instrução if é uma estrutura condicional de seleção única, uma vez que após a avaliação da expressão condicional será executada apenas uma instrução (ou grupo de instruções) como ilustrado no fluxograma da instrução if. No diagrama podemos ver que o fluxo de execução passa por uma estrutura de decisão. Esta estrutura deve avaliar uma condição e somente se esta condição for verdadeira, as instruções do bloco azul serão executadas como parte do fluxo principal, caso contrário as instruções do bloco vermelho serão executadas.
Instrução switch (variável) case ...
A instrução switch é uma estrutura condicional de seleção múltipla, uma vez que após a avaliação da expressão condicional será executada uma das opções case. O conteúdo da variável em switch é comparado com a constante em cada opção case, se achar um valor igual a instrução ou grupo de instruções seguintes ao case selecionado é executada até chegar uma instrução break. Se não encontrar uma opção case, executará default.
Este problema consiste em contar o número de caminhos para chegar iniciando até parte inferior direita em uma matriz MxN realizando no máximo k curvas como mostrado na figura.
