Análise de Algoritmos

Ronaldo Cristiano Prati

Bloco A, sala 513-2

ronaldo.prati@ufabc.edu.br

Programação dinâmica

  • Armazena uma tabela com solução de (sub)problemas já resolvidos
    • Essa estratégia é chamada de memorização
  • Usa as soluções da tabela para resolver problemas ainda não resolvidos
  • Ao final, usamos a informação coletada no caminho para resolver o problema completo

Programação dinâmica

  • Duas abordagens
    • Top Down: geralmente a transcrição direta de um algoritmo recursivo

    • Bottom up: inicia pelos problemas menores e usa essa solução para resolver problemas maiores

Programação dinâmica

  • O nome "dinâmica" se refere ao fato que o problema é resolvido em multiplos estágios
  • O nome foi atribuído (junto com a criação da técnica) nos anos de 1950
  • Precisava de um "nome bonito" para conseguir financiamento da força aérea americana:

“It’s impossible to use the word, dynamic, in the pejorative sense...I thought dynamic programming was a good name. It was something not even a Congressman could object to.”

Subsequência Comum

  • A sequência BDFH é uma subsquência de ABCDEFGH

    • Observe que não precisam, necessariamente, serem contínuos
  • Se XX e YY são sequências, uma subsequência comum é uma subsequência de ambas as sequências.

    • BDFH é uma subsequência de ABCDEFGH e ABDFGHI

Subsequência Comum Máxima

  • A maior subsequência comum é uma sequência que é comum e é a mais longa.

    • A maoir subsequência comum entre ABCDEFGH and ABDFGHI é ABDFGH.
  • Problema: Dados duas sequências X={X1,X2,,Xm}X=\{X_1,X_2,\cdots,X_m\} e Y={Y1,Y2,,Yn}Y=\{Y_1,Y_2,\cdots,Y_n\}, encontrar uma subsquência de maior tamanho LCS(X,Y)LCS(X,Y)

Aplicações

  • Bioinformática:
    • Encontrar a semelhança genética entre espécies; Encontrar sequências comuns para uma detarminada característica/doença genética
  • Diferença entre arquivos:
    • Comando diff do do unix
  • Merge em controlo de versões
    • svn, git, etc.
  • Processamento de Língua Natural
    • pareamento de sentenças

Maior Subsequência comum

  • Solução por força bruta:

    • Enumerar todas as possíveis subsequências de XX. Checar se cada uma dessas subsquências também é subsequência de YY, guardando a de maior comprimento.
  • Complexidade?

    • Existem 2m2^m subsequências de XX
    • Tempo linear para verificar se a subsequência de XX está em YY
    • O(n2m)O(n2^m), portanto ineficiente

Programação dinâmica

  1. Identificar subestrutura ótima
  2. Encontrar uma formulação recursiva
  3. Usar programação dinâmica para encontrar o valor da função ótima
  4. Se necessário, armazenar informação adicional de tal maneira que no passo 3 podemos encontrar a solução ótima

Subestrutura ótima

  • Vamos definir um prefixo como uma subsequência que se inicia na primeira, até uma certa posição ii

Subestrutura ótima

  • Seja C[i,j]C[i,j] o tamanho da maior subsquência comum entre XiX_i e YjY_j

C[4,4]=3C[4,4] = 3

Subestrutura ótima

  • Seja C[i,j]C[i,j] o tamanho da maior subsquência comum entre XiX_i e YjY_j

C[2,3]=4C[2,3] = 4

Formulação recursiva

  • Seja XX e YY duas sequências de tamanho ii e jj, nas quais queremos encontrar a maior sequência comum.

  • Vamos tentar escrever C[i,j]C[i,j] em função de problemas menores

    • Seja X[i]X[i] e Y[j]Y[j] os dois últimos caracteres da sequência:

    Ci,j={0se i=0 ou j=01+Ci1,j1se X[i]=Y[j]max(Ci1,j,Ci,j1)se X[i]Y[j]C_{i,j} = \begin{cases} 0 & \text{se } i=0 \text{ ou } j=0\\ 1 + C_{i-1,j-1} &\text{se } X[i] = Y[j] \\ \max(C_{i-1,j},C_{i,j-1}) &\text{se } X[i] \neq Y[j] \\ \end{cases}

Formulação recursiva

  • Se X[i]=Y[j]X[i] = Y[j], então
    Ci,j=1+Ci1,j1C_{i,j} = 1 + C_{i-1,j-1}
    uma vez que as duas últimas posições são iguais (portanto a subsequência máxima entre os dois últimos caracteres é 1),

Formulação recursiva

  • Se i=0i=0 ou j=0j=0, então C[i,j]=0C[i,j] = 0 uma vez que
    • Ou XX ou YY não contém nenhum caracter, e não tem nenhuma subsequência em comum.

Formulação recursiva

  • Se X[i]=Y[j]X[i] = Y[j], então Ci,j=1+Ci1,j1C_{i,j} = 1 + C_{i-1,j-1}
    uma vez que
    • as duas últimas posições são iguais (portanto a subsequência máxima entre os dois últimos caracteres é 1),
    • e devemos continuar verificando o restante da subsquência

Formulação recursiva

  • Se X[i]Y[j]X[i] \neq Y[j], então max(Ci1,j,Ci,j1)\max(C_{i-1,j},C_{i,j-1}) uma vez que
    • A subsequência máxima pode se dar ignorando o último caracter da primera sequência
    • A subsequência máxima pode se dar ignorando o último caracter da segunda sequência

Formulação recursiva

  • Uma LCS(X,Y)LCS(X,Y) pode ser obtida recursivamente da seguinte maneira:

    • Se Xm=YnX_m = Y_n, eles fazem parta de LCSLCS, e deve-se continuar procurando em LCS(Xm1,Yn1)LCS(X_{m-1},Y_{n-1})
    • Se XmYnX_m \neq Y_n, então temos dois subproblemas
      • Encontrar uma LCS(Xm1,Yn)LCS(X_{m-1},Y_{n});
      • Encontrar uma LCS(Xm,Yn1)LCS(X_{m},Y_{n-1});
      • LCS(X,Y)LCS(X,Y) é a maior entre essas duas.
  • A complexidade desse algoritmo é O(2(m+n))O(2^{(m+n)})

Formulação recursiva

  • Observe também que há um overlap entre os subproblemas

Programação Dinâmica

  • Assim com no problema da mochila inteira, vamos usar uma matriz para armazenar os valores de Ci,jC_{i,j} já calculados

Ci,j={0se i=0 ou j=01+Ci1,j1se X[i]=Y[j]max(Ci1,j,Ci,j1)se X[i]Y[j]C_{i,j} = \begin{cases} 0 & \text{se } i=0 \text{ ou } j=0\\ 1 + C_{i-1,j-1} &\text{se } X[i] = Y[j] \\ \max(C_{i-1,j},C_{i,j-1}) &\text{se } X[i] \neq Y[j] \\ \end{cases}

Programação Dinâmica

  • A matriz é criada com uma linha e coluna a mais, inicialmente preenchida com zeros

Programação Dinâmica

  • Preenchemos a matriz de acordo com os três casos possíveis até completar a matiz

Programação Dinâmica

  • O tamanho da maior subsequência comum está na última posição da matriz

Programação Dinâmica

  • Os dois caracteres são diferentes, então o 3 deve ter vindo do 3 de cima

Programação Dinâmica

  • Os dois caracteres são iguais, então o 3 deve ter vindo desta célula

Programação Dinâmica

  • Como a última iteração foi um match, devemos nos mover na diagonal
  • Como os dois elementos são diferentest, o 2 pode ter vindo tanto da esquerda quanto de cima

Programação Dinâmica

  • Digamos que escolhemos a de cima
  • Como os dois caracteres são diferentes, e o valor da célula de cima é menor que o da esquerda, o 2 deve ter vindo da esquerda

Programação Dinâmica

  • Os dois caracteres são iguais, então o 2 deve ter vindo desta célula

Programação Dinâmica

  • Os dois caracteres são iguais, então o 1 deve ter vindo desta célula

Programação Dinâmica

  • Chegamos ao final das duas subsequências, a maior subsequência comum correspondem aquelas em houve um match. Nesse caso, ACG

Algoritmo

Algoritmo

Complexidade

  • É fácil ver que a complexidade do algoritmo é O(mn)O(mn), com um custo adicional de memória de O(mn)O(mn)

Algoritmo Needleman-Wunsch

  • Quando dois caracteres são iguais, temos um match
  • Quando há um buraco, temos um gap
  • Em algumas situações, queremos dar pesos diferentes ao match e ao gap
    • Esse é um requisito comum em análise de DNA, em que queremos evitar buracos muito grandes no aninhamento
  • Eventualmente, podemos também permitir match por similaridade
    • Por exemplo, s e z tem um som parecido

Algoritmo Needleman-Wunsch

  • Seja α(a,b)\alpha(a,b) uma função que retorna o benefício/penalidade de alinhar os caracteres aa e bb (que podem ou não serem iguais)

  • Seja α(gap)\alpha(gap) a penalidade de alinhar um caracter com um gap

  • O Algoritmo de Needleman-Wunsch é similar ao algoritmo de encontrar uma subsequência máxiama, mas com o objetivo é encontrar o alinhamento de pontuação máxima

Algoritmo Needleman-Wunsch

  • Para o algoritmo de Needleman-Wunsch, definimos uma matriz de pontuação em que os pesos são definidos por

Pi,j=max{α(xi,yj)+Pi1,j1α(gap)+Pi1,jα(gap)+Pi,j1P_{i, j}=\max \left\{\begin{array}{l}{\alpha\left(x_{i}, y_{j}\right)+P_{i-1, j-1}} \\ {\alpha(g a p)+P_{i-1, j}} \\ {\alpha(g a p)+P_{i, j-1}}\end{array}\right.

Algoritmo Needleman-Wunsch

Algoritmo Needleman-Wunsch

  • É fácil ver que a complexidade é a mesma do algoritmo que encontra a maior subsquência máxima