312
Análise de algoritmos Sílvia Mara da Costa Campos Victer

Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

  • Upload
    others

  • View
    16

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de algoritmos

Sílvia Mara da Costa Campos Victer

Page 2: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de Algoritmos

• Critérios de análise, correção e eficiência.

• Análise de algoritmos: tempo de processamento e número de operações elementares, complexidade de pior caso e caso médio.

• Técnicas de construção de algoritmos: Divisão e conquista (recursão), algoritmos gulosos, programação dinâmica e modelagem em grafos.

• Teoria da Complexidade: problemas de decisão, transformações polinomiais, classes P, NP, Co-NP e NP-completo.

Page 3: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Tópicos • Critérios de análise, correção e eficiência. • Análise de algoritmos • Técnicas de construção de algoritmos:

– Divisão e conquista (recursão) – Programação dinâmica – Algoritmos gulosos – Modelagem em grafos

• Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Page 4: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Critérios de análise, correção e eficiência. Algoritmo:conjunto de instruções que definem passos para a resolução de um

problema.

Critérios para avaliar um algoritmo: Simplicidade: - Um algoritmo é simples se puder ser facilmente entendido, implementado e

mantido. - Não se conhece técnicas formais para isto!

Correção: – Um algoritmo está correto se para toda entrada específica a saída correta é

produzida. Analisa se o algoritmo resolve o problema sem erros. – “Testes servem apenas para provar que um algoritmo tem erros, nunca para

provar que está correto” (Dijkstra) Eficiência: - Considera se a solução que ele propõe utiliza os recursos computacionais,

especialmente memória e tempo de processamento, de maneira adequada e econômica.

Page 5: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Critérios de análise, correção e eficiência. Como medir a eficiência

1- Método experimental (empírico) – Realizar várias implementações completas; – executar um grande número de vezes; – Análise (estatística) dos resultados; • Técnica é utilizada em último caso 2- Método analítico A idéia é construir um modelo matemático do

algoritmo. A comparação de eficiência dos algoritmos se dá a partir da comparação desses modelos.

Page 6: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Critérios de análise, correção e eficiência. Análise empírica:

Esse tipo de avaliação enfrenta grandes desafios, pois se

baseia no desenvolvimento de uma implementação correta e completa do algoritmo e depende não apenas da natureza dos dados de entrada utilizados durante a experimentação, mas também de outros fatores que têm influência no experimento.

Por exemplo, ao comparar algoritmos empiricamente é

necessário levar em conta o ambiente de execução utilizado, considerando as máquinas, os compiladores e os sistemas utilizados durante os experimentos. Portanto, um dos possíveis problemas da análise empírica é que uma implementação pode ter sido realizada com mais cuidado (otimizada) do que a outra, levando a comparações equivocadas.

Page 7: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise matemática - A qualidade de um programa de computador depende da

eficiência de seu algoritmo para resolver o problema ao qual ele propõe solução.

- Do ponto de vista do usuário de um programa, a qualidade pode ser medida em termos de diversos fatores, como interface, robustez, compatibilidade, desempenho, consumo de recursos, entre outros.

- Do ponto de vista do programador, a qualidade de um programa pode estar relacionada a critérios como portabilidade, clareza e reuso.

- Por outro lado, a análise matemática de algoritmos baseia-se em critérios mais gerais para medir a qualidade de um algoritmo.

Page 8: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise matemática • O custo exigido pela maioria dos algoritmos geralmente pode ser

definido matematicamente em função de seu principal dado de entrada, ao qual chamaremos de parâmetro primário do algoritmo.

O tamanho do parâmetro primário: - corresponde ao número de elementos. - Se o parâmetro for um vetor de inteiros : o número de elementos desse

vetor. - afeta diretamente o custo de execução do algoritmo, sendo

diretamente proporcional a ele. O objetivo da análise matemática é expressar a necessidade de recursos de um programa (tempo de execução e/ou espaço de memória) em termos desse parâmetro primário .

• Quando comparada à análise empírica, que é uma análise baseada na experimentação e na observação da execução do programa que implementa um algoritmo, a análise matemática de algoritmos faz uma avaliação mais informativa e mais barata, pois é uma análise independente da máquina, compilador ou sistema e não exige a criação e execução de um programa correspondente.

Page 9: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Crescimento de funções

• Vantagens de associar a eficiência de um algoritmo a funções matemáticas:

- é mais fácil entender como seu custo varia em relação ao tamanho do parâmetro primário do algoritmo.

- permite comparar os custos de diferentes algoritmos com facilidade.

Funções matemáticas normalmente utilizadas na análise matemática do custo:

Page 10: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Crescimento de funções

Funções matemáticas normalmente utilizadas na análise matemática do custo:

Page 11: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Crescimento de funções

Funções matemáticas normalmente utilizadas na análise matemática do custo:

Page 12: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Crescimento de funções Funções de custo tradicionais: O(f): curva da função de custo f. quanto maior o tamanho do parâmetro

primário N, maior será o custo computacional do algoritmo. Ex: se o algoritmo tem uma função de custo exponencial, um pequeno

aumento no tamanho de N tem grande impacto no tempo consumido pelo algoritmo.

Page 13: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Custo de um algoritmo As SIMPLIFICAÇÕES das expressões matemáticas são necessárias para facilitar o

processo de análise de custos e comparação entre algoritmos. Principais simplificações aplicadas na análise matemática do custo de um algoritmo:

1- Considere a execução do algoritmo quando aplicado a quantidades de

dados suficientemente grandes. Em outras palavras, assuma que o parâmetro primário N tende a infinito;

2- Ignore constantes aditivas ou multiplicativas na fórmula matemática correspondente ao custo. Essas constantes não interferem no comportamento geral da função matemática associada;

3- Analise o algoritmo dividindo-o em etapas ou passos elementares, sendo que

cada passo envolve um número fixo de operações básicas cujos tempos de execução são assumidos constantes. Operações básicas: operações muito simples e que não podem ser subdivididas em outros passos, como uma atribuição ou um teste lógico;

4- O número de passos do algoritmo é dado pelo número de passos da operação

básica de maior frequência, comumente chamada de operação dominante.

Page 14: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Custo de um algoritmo Exemplo 1: Algoritmo de Complexidade Constante: Tempo de execução T: depende dos valores de i e n

(parâmetro primário):

Page 15: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Custo de um algoritmo Exemplo 2: Algoritmo de Complexidade Linear: T(n): Obs: k2: constante que depende das características do sistema onde o

algoritmo será executado.

Page 16: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Custo de um algoritmo Exemplo 3: Algoritmo de Complexidade Quadrática:

Page 17: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de algoritmos Área da computação que visa determinar a complexidade (custo) de um

algoritmo: o que torna possível: comparar algoritmos e determinar se um algoritmo é

“ótimo”. 1) Analisar um algoritmo:

– prever os recursos de que o algoritmo necessitará. – Ex: memória, largura de banda de comunicação ou hardware. – Tempo de execução (tempo de computação):(COMPLEXIDADE TEMPORAL) é o que queremos medir com frequência!! Custo: tempo (número de passos) e espaço (memória: complexidade espacial)

2) Suposição de um modelo de computação genérico com um só processador: – RAM: Random Access Machine – máquina de acesso aleatório (como a

tecnologia de implementação) – Instruções executadas sequencialmente

Page 18: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de algoritmos Modelo de Computação: • Ao invés de escolher uma máquina particular, em relação a

qual a eficiência dos algoritmos seria avaliada, é certamente mais conveniente utilizar-se de um modelo matemático de um computador.

• Modelo adotado: (modelo RAM) 1. As operações são todas executadas sequencialmente; 2.a execução de toda e qualquer operação toma uma unidade

de tempo; 3.a memória é infinita.

Page 19: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de algoritmos

- Significa, também, estimar o grau de dificuldade dos problemas. O que é visto em análise de algoritmos:

Ferramentas matemáticas utilizadas:

– Análise Combinatória;

– Teoria das probabilidades;

– Destreza matemática:

• Indução Matemática;

• Séries e Produtórios;

• Potências e Logaritmos, etc.

Page 20: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de algoritmos

Quando é utilizada? - para projetar algoritmos mais eficientes;

- para saber se suas implementações são viáveis do

ponto de vista prático;

- para saber qual é o melhor algoritmo para a resolução de um problema.

- para saber o “grau” de dificuldade de um problema (Teoria da Complexidade).

Page 21: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de algoritmos Qual o método mais eficiente? A complexidade de um algoritmo é medida segundo um modelo

matemático que supõe que este vai trabalhar sobre uma entrada (massa de dados) de tamanho N.

O processo de execução de um algoritmo pode ser dividido em etapas

elementares denominadas passos (número fixo de operações básicas, tempo constante, operação de maior freqüência chamada dominante). O número de passos de um algoritmo é considerado como o número de execuções da operação dominante em função das entradas, desprezando-se constantes aditivas ou multiplicativas.

Definimos a expressão matemática de avaliação do tempo de execução

de um algoritmo como sendo uma função que fornece o número de passos efetuados pelo algoritmo a partir de uma certa entrada.

Page 22: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de algoritmos Ex. 1: Soma de vetores para I de 1 até N faça S[I] ← X[I] + Y[I] Fim para Número de passos = número de somas (N) Ex. 2: Soma de matrizes Para I de 1 até N faça Para J de1 até N faça C[I,J] ←A[I,j] + B[I,J] Fim para Fim para Número de passos = número de somas (N*N)

Page 23: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de algoritmos Ex. 3: Produto de matrizes Para I de 1 até N faça Para J de 1 até N faça P[I,J] ←0 Para K de 1 até N faça P[I,J] ← P[I,J] + A[I,K] * B[K,J] Fim para Fim para Fim para Número de passos = Número de somas e produtos (N*N*N)

Page 24: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de algoritmos

A complexidade pode ser qualificada quanto ao seu comportamento como:

• Polinomial : A medida que N aumenta o fator que estiver sendo analisado (tempo ou espaço) aumenta linearmente.

• Exponencial: A medida que N aumenta o fator que estiver sendo analisado (tempo ou espaço) aumenta exponencialmente.

Algoritmo com complexidade exponencial, não é executável para valores de N muito grandes.

Page 25: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de algoritmos Definição das instruções e seus custos: Análise do PIOR CASO -> - tempo de execução mais longo para qualquer entrada de

tamanho n. - limite superior!!

Tempo de execução: número de operações primitivas ou ‘etapas executadas’

Em geral, um algoritmo é mais eficiente que outro se o tempo de

execução do seu pior caso apresenta uma ordem (taxa) de crescimento mais baixa, para entradas suficientemente grandes!

Exemplo: um algoritmo θ(n2) será executado mais rapidamente no pior caso que um algoritmo θ(n3)

Page 26: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise de algoritmos

Algoritmos ótimos:

- Seja P um problema. Um limite inferior para P é uma função l, tal que a complexidade de pior caso de qualquer algoritmo que resolva P é Ω(l). Isto é, todo algoritmo que resolve P efetua, pelo menos, Ω(l) passos. Se existir um algoritmo A, cuja complexidade seja О(l), então A é denominado algoritmo ótimo para P. Ou seja, A apresenta a menor complexidade dentre todos os algoritmos que resolvem P.

Page 27: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Crescimento de funções A ordem de crescimento do tempo de execução de um algoritmo fornece

uma caracterização simples da eficiência do algoritmo, e também permite comparar o desempenho relativo de algoritmos alternativos.

Eficiência assintótica dos algoritmos: • Quando observamos tamanhos de entrada grandes o suficiente para

tornar relevante apenas a ordem de crescimento do tempo de execução. • Como o tempo de execução de um algoritmo aumenta com o tamanho de

entrada no limite, à medida que o tamanho de entrada aumenta indefinidamente (sem limite)?

• Em geral, um algoritmo assintoticamente mais eficiente será a melhor escolha para todas as entradas, exceto as muito pequenas.

Notação Assintótica: • Descreve o comportamento do algoritmo para n muito grande!! • Mede a eficiência dos algoritmos no limite!!

Page 28: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação θ

LIMITA ASSINTOTICAMENTE UMA FUNÇÃO ACIMA E ABAIXO Θ(g(n))= f(n): existem constantes positivas c1, c2 e n0, tais

que: 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n), para todo n ≥ n0

Conjunto de funções f(n) ∈ Θ(g(n)) membro de g(n): Limite Assintoticamente RESTRITO para f(n)

Page 29: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação θ

Page 30: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação θ Todo membro f(n) ∈ Θ(g(n)) deve ser: - Assintoticamente não negativo sempre que n for suficientemente grande. - Função assintoticamente positiva: função positiva para todo n

suficientemente grande!!

Exemplo 1: f(n)=(1/2)n2 – 3n = Θ(n2) Devemos construir constantes positivas c1, c2 e n0, tais que: Para todo n ≥ n0, a divisão por n2 produz: Exemplo de solução: c1=1/2 , c2=1/14 e n0=7. Certamente existem outras opções para as constantes, mas o fato importante

é que existe alguma opção!

Page 31: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação θ Exemplo 2: 6n3 ≠ Θ(n2) 6n3 ≤ c2n2 ; n ≤ c2/6!! O que não pode ser válido para n

arbitrariamente grande pois c2 é constante !! Exemplo 3: f(n)=an2 + bn + c, a> 0 Descartando os termos de mais baixa ordem e ignorando a

constante, produz-se f(n)=Θ(n2) Exemplo 4: Σ(i=0..d) ain

i, onde ai são constantes e ad>0, tempo p(n)=f(n)=Θ(nd)

Page 32: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação O LIMITE ASSINTÓTICO SUPERIOR (pode ou não ser assintoticamente RESTRITO) (utilizada para expressar comparativamente o crescimento assintótico (velocidade com que tende a infinito) de duas funções.) O(g(n)) = f(n): existem constantes positivas c e n0, tais que: 0 ≤ f(n) ≤ cg(n), para todo n ≥ n0

Conjunto de funções f(n) ∈ O(g(n)) membro de (algum múltiplo contante de g(n) é um limite assintótico superior sobre f(n))

Page 33: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação O

Page 34: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação O f(n) = ϴ(g(n)) f(n) = O(g(n)) an2 + bn + c = ϴ(n2) = O(n2) Qualquer função linear an + b está em O(n2), fazendo-se c=a+|b| e n0=1 - O limite O(n2) no tempo de execução do PIOR CASO da

ordenação por inserção também se aplica a seu tempo de execução sobre toda entrada.

- PORÉM, o limite ϴ(n2) da ordenação por inserção não implica um limite ϴ(n2) no tempo de execução em toda entrada!! Ex: para entrada já ordenada, T(n) = ϴ(n).

- Tempo de execução O(n2) (pior caso) existe uma função f(n) que é O(n2) para todo n (não importando que entrada específica de tamanho n), o T(n) sobre essa entrada tem um limite superior determinado pelo valor f(n)!!

Page 35: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação Ω LIMITE ASSINTÓTICO INFERIOR Ω(g(n)) = f(n): existem constantes positivas c e n0, tais que: 0 ≤ c(n) ≤ f(n), para todo n ≥ n0

Conjunto de funções f(n) ∈ Ω(g(n)) membro de Para 2 funções: f(n) e g(n): f(n) = ϴ(g(n)) sse f(n) = O(g(n)) e f(n) = Ω(g(n)) Exemplo: an2+bn+c = ϴ(n2) Ω(n2) e O(n2), para qualquer cte a, b e c, e a > 0

Page 36: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação Ω

Dizer que o tempo de execução T(n) de um algoritmo é Ω(lg(n)):

Significa que, independentemente da entrada específica de tamanho n escolhida para cada valor

de n, o T(n) sobre essa entrada é, no mínimo,

uma constante * g(n)

para um valor de n suficientemente grande!!

Page 37: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação assintótica em equações e desigualdades

n = O(n2) n ∈ O(n2)

2n2 + 3n + 1 = 2n2 + ϴ(n) = ϴ(n2)

f(n) -> alguma função no conjunto ϴ(n), nesse caso: f(n)=3n + 1

f(n) ∈ ϴ(n), para todo n!!

• ∑(i=1 a n) O(i) ≠ O(1) + O(2) + ... O(n)

Page 38: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação o

Limite superior NÃO assintoticamente restrito O limite superior fornecido pela notação O pode ser ou não

assintoticamente restrito!! Ex: 2n2 = O(n2): limite superior assintoticamente restrito 2n = O(n2): limite superior NÃO assintoticamente restrito!!

o(g(n)) = f(n): para qualquer constante positiva c>0, existe

uma constante n0 > 0, tal que: 0 ≤ f(n) < cg(n), para todo n ≥ n0 Exemplo: 2n = o(n2), mas 2n2 ≠ o(n2)

Page 39: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação o

f(n) = O(g(n)): o limite 0 ≤ f(n) ≤ cg(n) é válido para ALGUMA constante c > 0

f(n) = o(g(n)): o limite 0 ≤ f(n) < cg(n) é válido para TODAS as constantes c > 0

lim f(n) = 0

n ∞ g(n)

A função f(n) se torna insignificante em relação a g(n) à medida que n se aproxima do ∞ !!!

Page 40: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação ω

Limite inferior NÃO assintoticamente restrito

o(g(n)) = f(n): para qualquer constante positiva c>0, existe uma constante n0 > 0, tal que:

0 ≤ cg(n) < f(n), para todo n ≥ n0

f(n) ϵ ω(g(n)) sse g(n) ϵ o(f(n))

Exemplo:

n2/2 = ω(n) MAS

n2/2 ≠ ω(n2)

Page 41: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Notação ω

f(n)=ω(g(n)) implica que

lim f(n) = ∞, se o limite existe

n ∞ g(n)

A função f(n) se torna arbitrariamente grande

em relação a g(n) à medida que

n se aproxima do ∞ !!!

Page 42: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Comparação de funções

Transitividade:

Reflexividade: Simetria:

Page 43: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Comparação de funções

Simetria de transposição:

• f(n) é assintoticamente menor que g(n) sse f(n) = o(g(n)),

• f(n) é assintoticamente maior que g(n) sse f(n) = ω(g(n))

Page 44: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Comparação de funções

Page 45: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Divisão e Conquista Algoritmo recursivo:

• chamam a si mesmos recursivamente uma ou mais vezes para lidar com subproblemas intimamente relacionados

- Dividir o problema em um determinado número de subproblemas (semelhantes ao problema original, mas menores em tamanho).

- Conquistar os subproblemas, resolvendo-os recursivamente.

- Combinar as soluções dos subproblemas para formar a solução do problema original.

Page 46: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

MergeSort Algoritmo de ordenação por intercalação Dividir - a sequência de n elementos em 2 subsequências de n/2

elementos cada uma.

Conquistar - classifica as duas subsequências recursivamente, usando a

ordenação por intercalação.

Combinar (ou intercalar) - intercala as 2 subsequências ordenadas, para produzir a resposta

ordenada.

• MERGE (A,p,q,r), p ≤q < r • intercala A[p..q] e A[q+1..r] A[p..r]

Page 47: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Mergesort • Combinação (Intercalação)

MERGE (A,p,q,r) 1. n1 q-p+1 ϴ(1) 2. n2 r–q ϴ(1) 3. > Criar arranjos L[1..n1+1] e R[1..n2+1] 4. for i 1 to n1 5. do L[i] A[p+i-1] ϴ(n1) 6. for j 1 to n2 7. do R[j] A[q+j] ϴ(n2) 8. L[n1+1] ∞ sentinelas 9. R[n2+1] ∞ cont.

Page 48: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

• Combinação (Intercalação)

10. I 1 11. j 1 12. for k p to r 13. do if L[i] ≤ R[j] 14. then A[k] L[i] 15. i i + 1 16. else A[k] R[j] 17. j j + 1 Obs: l.12 a 17: n iterações!! Cada uma com um tempo constante. ϴ(n), para n=r-p+1 (número de elementos intercalados)

Mergesort Algoritmo de ordenação por intercalação

Page 49: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

• Procedimento MERGE

MERGE (A,9,12,16)

Mergesort Algoritmo de ordenação por intercalação

Page 50: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

• Procedimento MERGE

Mergesort Algoritmo de ordenação por intercalação

Page 51: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Mergesort Algoritmo de ordenação por intercalação

• Ordena os elementos do subarranjo A[p..r]:

MERGE-SORT(A, p, r)

1. if (p<r)

2. then q (p+r)/2 Divisão: ϴ(1)

3. MERGE-SORT (A,p,q) T(n/2) 2T(n/2)

4. MERGE-SORT (A,q+1,r) T(n/2)

5. MERGE (A,p,q,r) Intercalação: ϴ(n)

• l. 3. e 4. Conquista

• l. 5. Intercalação (combinação) de 2 vetores ordenados

Page 52: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Mergesort Algoritmo de ordenação por intercalação

Ex: arranjo A=<5,2,4,7,1,3,2,6> (obs: n potência de 2)

MERGE-SORT(A,1,comprimento[A])

Page 53: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Mergesort Algoritmo de ordenação por intercalação

Equação de recorrência

T(n) = θ(1), se n ≤ c

aT(n/b) + D(n) + C(n), cc.

θ(1): tamanho do problema muito pequeno

Conquista: aT(n/b)

- Supor problema subdividido em a subproblemas: cada um com 1/b do tamanho do programa original. 2T(n/2)

-Divisão: D(n)

- Dividir o problema em subproblemas. θ(1)

Combinação:C(n)

- Combinar as soluções dadas aos subproblemas. θ(n)

Page 54: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Análise da ordenação por intercalação

Dividir: • calcula o ponto médio do subarranjo, que demora um

tempo constante. • D(n) = θ(1)

Conquistar: • Resolve recursivamente 2 subproblemas, cada um com

tamanho n/2 e contribui com 2T(n/2) para o tempo de execução.

Combinar: • MERGE • C(n) = θ(n)

Page 55: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Equação de Recorrência

Page 56: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Árvore de Recursão

Page 57: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Árvore de Recursão

Page 58: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Recorrências Recorrência: equação ou desigualdade que descreve uma

função em termos de seu valor em entradas menores.

MERGE-SORT: T(n) = ϴ(1), se n=1 2T(n/2) + ϴ(n), se n > 1 Solução: T(n) = ϴ(n lg n) Três métodos: 1. Método da substituição (supõe um limite hipotético e usa

a indução matemática para provar que a suposição era correta!!)

2. Método da árvore de recursão (recorrência árvore) 3. Método mestre (T(n) = a T(n/b) + f(n), a≥1,b>1)

Page 59: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1. Método da Substituição 1. Pressupor a forma da solução 2. Usar a indução matemática para encontrar as constantes e

mostrar que a solução funciona.

(Aplicado em casos fáceis de pressupor a forma da resposta) Exemplo 1: Determinar um limite superior sobre a recorrência: T(n) = 2 T

(n/2) + n

1. Supor que a solução é T(n) = O(n lg n) Provar que T(n) ≤ c n lg n, para uma constante c > 0

Supor limite válido para n/2: T (n/2) ≤ c n/2 lg n/2

Substituição na recorrência: (para c>=1)

Page 60: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1. Método da Substituição 2. Indução Matemática Mostrar que esta solução se mantém válida para as condições

limites. (mostrando que as condições limite são adequadas para casos básicos da prova indutiva).

Devemos mostrar que podemos escolher uma constante c

grande o suficiente para que o limite T(n) ≤ c n lg n também funcione para as condições limite.

Supor que T(1)=1 seja a única condição limite da recorrência.

Para n=1, o limite T(n) ≤ c n lg n = 0, mas T(1) = 1!! o caso básico da prova indutiva deixa de ser válido.

• A notação assintótica só exige demonstrar T(n) ≤ c n lg n para n≥ n0, onde n0 é uma constante escolhida.

IDÉIA:.....

Page 61: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1. Método da Substituição Idéia: remover a condição limite T(1) = 1. para n>3, a recorrência não depende diretamente de T(1). Logo, substituir T(1) por T(2) e T(3) como os casos básicos na

prova indutiva, deixando n0=2. - Caso básico da recorrência: n=1 - Caso básico da prova indutiva: (n=2 e n=3) Da recorrência: T(2)=4 e T(3)=5 • A prova indutiva de que T(n) ≤ c n lg n para alguma constante c

≥ 1: escolhe-se um valor de c grande o bastante para que:

T(2) ≤ c 2 lg 2 qualquer valor de c ≥ 2 é suficiente para que T(3) ≤ c 3 lg 3 os casos básicos de n=2 e n=3 sejam válidos

Page 62: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1. Método da Substituição Exemplo 2: Determinar um limite superior sobre a recorrência: T(n) = 2 T (n/2 + 17) + n

Obs: • o 17 não pode afetar substancialmente a solução

para a recorrência:

Quando n é grande, a diferença entre T (n/2) e T(n/2+17) não é tão grande!! Ambos os termos cortam n quase uniformemente pela metade.

Page 63: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Método da Árvore de Recursão Cada nó representa um custo de um único subproblema. Deve-se: • Obter um conjunto de custos por nível: somar os custos dentro

de cada nível da árvore. • Determinar o custo total de todos os níveis da recursão: somar

todos os custos por nível.

• Particularmente úteis quando a recorrência descreve o tempo de execução de um algoritmo de dividir e conquistar.

Uso: • Gerar uma boa suposição, verificada pelo método de

substituição, ou • Prova direta de uma solução para uma recorrência.

Page 64: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Método da Árvore de Recursão Exemplo 1: fornecer uma boa suposição para a recorrência: T(n) = 3 T (n/4) + ϴ(n2) Devemos encontrar um limite superior para a recursão: criar

uma árvore de recursão para a recorrência:

T(n) = 3 T (n/4) + cn2, c > 0

Page 65: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Método da Árvore de Recursão

Page 66: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Método da Árvore de Recursão Usar agora o método de substituição para verificar que nossa

suposição era correta: T(n) = O(n2) é um limite superior para a recorrência: T(n) = 3 T (n/4) + ϴ(n2)

• Queremos mostrar que T(n) ≤ dn2 para alguma constante d>0:

válido desde que d ≥ (16/3)c

Page 67: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Método da Árvore de Recursão Exemplo 2: T(n) = T(n/3) + T(2n/3) + O(n) T(n) = T(n/3) + T(2n/3) + cn, (c: fator cte no termo O(n))

Page 68: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Método da Árvore de Recursão Usar o método da substituição para verificar que O(n lg n) é

um limite superior para a solução da recorrência.

Mostramos que T(n) ≤ dn lg n, para d positivo

Page 69: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3. Método Mestre Resolve recorrências da forma: T(n) = a T(n/b) + f(n) a ≥ 1, b>1 (ctes) e f(n): custo de dividir o problema e combinar os resultados (D(n) +C(n)) função assintoticamente positiva!!!

T(n) pode ser limitado assintoticamente como:

(Compara-se f(n) com a função (n log

b a))

solução para a recorrência determinada pela maior das 2 funções!!

Page 70: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3. Método Mestre 1º. Caso:

• f(n) deve ser POLINOMIALMENTE MENOR que (n logb

a)

• f(n) deve ser ASSINTOTICAMENTE MENOR que (n logb

a) por um fator nϵ

, para alguma constante ϵ >0.

• 3º. Caso:

• f(n) deve ser POLINOMIALMENTE MAIOR que (n logb

a)

• f(n) deve satisfazer a condição de “regularidade” de que:

af(n/b) ≤ c f(n)

Obs:os 3 casos não abrangem todas as possibilidades para f(n)

Page 71: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3. Método Mestre Casos em que o método mestre NÃO se aplica: 1- Existe uma lacuna entre os casos 1 e 3 quando f(n) é

menor que (n logb

a), MAS não POLINOMIALMENTE MENOR.

2. Existe uma lacuna entre os casos 2 e 3 quando f(n) é

maior que (n logb

a), MAS não POLINOMIALMENTE MAIOR.

Se a função f(n) recair nessas lacunas ou a condição de

regularidade 3 não for válida!!

Page 72: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3. Método Mestre Exemplo1: T(n) = 9T(n/3) + n a=9, b=3, f(n)=n (n log

b a) = n2 = ϴ(n2)

f(n) = O (n log3

9 - ϵ), onde ϵ = 1 CASO 1: Solução: T(n)= ϴ(n2)

Exemplo 2: T(n) = T(2n/3) + 1 a=1, b=3/2, f(n)=1

(n log

b a) = (n log3/2 1) = n0 = 1

f(n) =ϴ (n logb

a - ϵ) = ϴ(1) CASO 2: Solução: T(n)= ϴ(lg n)

Page 73: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3. Método Mestre Exemplo 3: T(n) = 3T(n/4) + n lg n

a=3, b=4, f(n)=n lg n e

(n logb

a) = (n log4

3) = O (n 0,793)

Como f(n) = Ω (n log4

3 + ϵ), onde ϵ ⸗ 0,2

CASO 3:

Mostrar que a condição de regularidade é válida para f(n), para n suficiente grande,

af(n/b) = 3 (n/4) lg (n/4) ≤ (3/4) n lg n = cf(n) para c=3/4

Solução para a recorrência: T(n)= ϴ(n lg n)

Page 74: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Programação dinâmica

• Introdução

• Etapas

• Programação de linha de montagem

• Multiplicação de Cadeias de matrizes

• Elementos de programação dinâmica

– Subestrutura ótima

– Superposição de problemas

Page 75: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Programação dinâmica • Resolve problemas combinando as soluções para

subproblemas.

• Aplicável quando os subproblemas NÃO são independentes quando os subproblemas compartilham subsubproblemas.

• Um algoritmo de programação dinâmica resolve cada subsubproblema uma vez só e então grava sua RESPOSTA em uma TABELA evita o trabalho de recalcular a resposta sempre que o subsubproblema é encontrado!!

• Para problemas de otimização: - muitas soluções, cada uma com um valor encontrar UMA

solução com valor ótimo (mínimo ou máximo)!! - UMA solução ótima e NÃO “A” solução ótima.

Page 76: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Programação dinâmica

4 Etapas:

• 1ª. Caracterizar a estrutura de uma solução ótima

• 2ª. Definir recursivamente o valor de uma solução ótima

• 3ª. Calcular o valor de uma solução ótima em um processo de baixo para cima (bottom-up)

• 4ª. Construir uma solução ótima a partir de informações calculadas.

Page 77: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1.Programação de linha de montagem

Exemplo de programação dinâmica: • problema de encontrar o caminho mais rápido em

uma fábrica.

Quais estações escolher nas linhas 1 e 2

a fim de minimizar o tempo total?

Page 78: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1.Programação de linha de montagem

• Uma instância do problema:

Page 79: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1.Programação de linha de montagem

• Infelizmente, há 2n maneiras possíveis de escolher estações:

Conjunto de estações usadas na linha 1: subconjunto de 1,2,...,n 2n subconjuntos!!

• A determinação do caminho mais rápido pela fábrica enumerando todos os modos possíveis e calculando quanto tempo cada um deles demora exigiria o tempo Ω(2n): INVIÁVEL PARA n GRANDE!!!

• Solução: programação dinâmica!!

Page 80: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1.Programação de linha de montagem

Etapa 1: A estrutura do caminho mais rápido pela fábrica

• Caracterizar a ESTRUTURA de uma SOLUÇÃO ÓTIMA

• Propriedade da subestrutura ótima:

Uma solução ótima para um problema (encontrar o caminho mais rápido passando pela estação Si,j) contém em seu interior uma solução ótima para subproblemas (encontrar a passagem mais rápida por S1,j-1 ou S2,j-1).

Page 81: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1.Programação de linha de montagem

Subestrutura ótima: • Construir uma solução ótima para um problema a partir de

soluções ótimas para subproblemas!!

- O caminho mais rápido pela estação S1,j é: O caminho mais rápido pela estação S1,j-1, e depois

diretamente pela estação S1,j. O caminho mais rápido pela estação S2,j-1, uma

transferência da linha 2 para a linha 1, e depois através da estação S1,j.

(mesmo raciocínio para a estação S2,j )

Page 82: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1.Programação de linha de montagem Etapa 2: Uma solução recursiva: Quais são os Subproblemas? encontrar o caminho mais rápido pela estação j em ambas as

linhas, para j=1,2,...,n. fi[j]: - o tempo mais rápido possível para levar um chassi desde o

ponto de partida até a estação Si,j. - Valores de soluções ótimas para subproblemas. f*: Tempo mais rápido para levar um chassi por todo o

percurso.

Objetivo final: f* = min( f1[n] + x1, f2[n] + x2 )

Page 83: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1.Programação de linha de montagem

Equações recursivas: (j=2,3,...n)

Page 84: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1.Programação de linha de montagem

• Uma instância do problema:

Page 85: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1.Programação de linha de montagem

Etapa 3: Cálculo dos tempos mais rápidos

• Algoritmos recursivos baseados nas equações de f*, f1[j] e f2[j]:

T(n): exponencial em n:ϴ(2n)!

• Alternativa:

Calcula-se os fi[j] valores em uma ordem diferente do modo recursivo: na ordem de números de estações j crescentes, da esquerda para a direita!! TEMPO ϴ(n) – PARA CALCULAR O CAMINHO MAIS RÁPIDO E O TEMPO QUE ELE DEMORA!!

Page 86: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1.Programação de linha de montagem

Para preencher uma entrada fi[j], precisamos dos valores de f1[j-1] e f2[j-1] e, sabendo que já

calculamos e armazenamos esses valores, nós os descobrimos simplesmente observando a tabela.

Page 87: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1.Programação de linha de montagem

Etapa 4: Construção do caminho mais rápido (sequência de estações)

Page 88: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes

Calcular o produto:A1 A2 ... An

• (completamente colocado entre parênteses)

• Multiplicação de matriz: associativa

Ex: <A1,A2,A3,A4>

MESMO RESULTADO

MAS

Cada um com um custo!!

Page 89: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes A:p x q e B: q x r C: p x r

tempo para calcular C: p.q.r

• Exemplo: cadeia <A1,A2,A3>. A1:10x100, A2:100x5, A3: 5x50 1. ((A1A2)A3): 10x100x5 + 10x5x50 = 7500 multiplicações escalares (+ rápido) 2. (A1(A2A3)): 10x100x50+ 100x5x50 = 75000 multiplicações escalares!!

Page 90: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes

Contagem do número de colocações entre parênteses:

• P(n): número de alternativas para colocação dos parênteses de uma sequência de n matrizes.

• Solução para a recorrência: Ω(2n)!!

Aplicar a programação dinâmica!

Page 91: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes Etapa 1: A estrutura de uma colocação ótima dos parênteses

Problema não-trivial: Ai,j, onde i<j: • Qualquer colocação ótima dos parênteses do produto AiAi+1..Aj

deve dividir o produto entre Ak e Ak+1 para algum inteiro k no intervalo i ≤ k < j.

• Para algum valor de k: 1º. Calculamos as matrizes: Ai... Ak e Ak+1..Aj 2º. Multiplicamos os 2 para gerar o produto final Ai..Aj, • Custo da colocação dos parênteses: Custo de calcular a matriz Ai... Ak + custo de calcular a matriz Ak+1..Aj + Custo de multiplicar as 2!!!

Page 92: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes • Construir uma solução ótima para uma instância do

problema de multiplicação de cadeia de matrizes:

dividindo o problema em 2 subproblemas (colocação ótima dos parênteses de Ai...Ak e Ak+1...Aj ):

1-Encontrando soluções ótimas para instâncias de

subproblemas, 2-Combinando essas soluções ótimas de subproblemas.

• Assegurar que: quando procurarmos pelo lugar correto

para dividir o produto, consideraremos todos os lugares possíveis, de forma a garantir ter examinado a opção ótima!!

Page 93: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes

Etapa 2: Uma solução recursiva • Definimos recursivamente o custo de uma solução ótima

em termos das soluções ótimas para subproblemas.

Quais são os subproblemas? Determinar o custo mínimo de uma colocação dos

parênteses de AiAi+1... Aj , para 1 ≤ i ≤ j ≤ n. m[i,j]: número mínimo de multiplicações escalares para

calcular a matriz Ai...Aj. m[1..n]: o custo de um caminho mais econômico para

calcular A1..n, para o problema completo.

Page 94: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes

Etapa 2: Uma solução recursiva

• Definição recursiva:

m[i,j]: custo mínimo para calcular os subprodutos Ai..k e Ai..k+1 + custo de multiplicar essas duas matrizes:

m[i,j] = m[i, k] + m[k+1, j] + pi-1pkpj

Mas.... Quem é k???

Page 95: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes k = i, i+1, ..., j-1

• Verificar todos os valores de k para encontrar o melhor!!

• m[i,j]: fornecem os custos de soluções ótimas para subproblemas!!

• TEMPO EXPONENCIAL !!

• s[i,j] é igual a um valor k tal que

• s[i,j]: valor de k no qual podemos dividir o produto para obter uma colocação ótima dos parênteses.

Page 96: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes Etapa 3: Como calcular os custos ótimos

• Temos relativamente poucos subproblemas: um problema para cada opção de i e j que satisfaz a 1 ≤ i ≤ j ≤ n, ϴ(n2).

• Um algoritmo recursivo pode encontrar cada subproblema muitas vezes em diferentes ramificações dessa árvore de recursão:

Propriedade de SUPERPOR problemas!!

2ª. Indicação de aplicabilidade da programação dinâmica.

(1ª.: subestrutura ótima)

• Calcular os custos ótimos utilizando uma abordagem tabular de baixo para cima

Page 97: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes Etapa 3: Como calcular os custos ótimos

• Abordagem tabular de baixo para cima.

Pseudocódigo a seguir:

- Ai: dimensões pi-1 x pi para i=1,2,...,n

- A entrada é uma sequência p=<p0,p1,...pn>, onde comprimento [p]=n+1.

- Tabela auxiliar: m[1..n,1..n] para armazenar os custos de m[i,j]

- Tabela auxiliar: s[1..n,1..n] para registrar qual índice de k alcançou o custo ótimo no cálculo de m[i,j] – para construir uma solução ótima.

O Algoritmo deve preencher a tabela m de uma forma que corresponda a resolver o problema de colocação dos parênteses

em cadeias de matrizes de comprimento crescente!

Page 98: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes

Page 99: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes

- Cada linha horizontal na tabela contém as entradas para cadeias de matrizes do mesmo comprimento.

- MATRIX-CHAIN-ORDER calcula as linhas desde a parte inferior até a parte superior e da esquerda para a direita dentro de cada linha!

Page 100: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes

Número mínimo de multiplicações escalares para multiplicar as seis matrizes é m[1,6] = 15.125

Page 101: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes

- Tempo de execução: O(n3) e Ω(n3).

- O algoritmo exige o espaço θ(n2) para armazenar as tabelas m e s.

- Muito mais eficiente que o método de tempo exponencial de enumerar todas as possíveis colocações entre parênteses e verificar cada uma delas.

Page 102: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2. Multiplicação de Cadeias de matrizes Etapa 4: A construção de uma solução ótima - MATRIX-CHAIN-ORDER: determina o número ótimo de multiplicações

escalares, MAS não mostra diretamente como multiplicar as matrizes!! - Cada entrada s[i,j] registra o valor de k tal que a colocação ótima dos

parênteses de AiAi+1... Aj divide o produto entre Ak e Ak+1. A multiplicação de matrizes final no cálculo ótimo de A1..n é A1..s[1,n]As[1,n+1]..n.

PRINT-OPTIMAL-PARENS(s,i,j) if i=j then print “A”i else print “(“ PRINT-OPTIMAL-PARENS(s,i,s[i,j]) PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j) print “)“ PRINT-OPTIMAL-PARENS(s,1,6) ((A1(A2A3))((A4A5)A6))

Page 103: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Elementos de programação dinâmica

Ingredientes fundamentais que um problema de otimização deve ter para que a programação dinâmica seja aplicável:

• Subestrutura ótima

• Superposição de problemas.

– Quando o método deve ser aplicar?

Page 104: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Subestrutura ótima Um problema apresenta uma subestrutura ótima se: Uma solução ótima para um problema contém em seu

interior soluções ótimas para subproblemas. • Em programação dinâmica: construímos uma solução ótima

para o problema a partir de soluções ótimas para subproblemas (assegurar que o intervalo de subproblemas considerados inclui aqueles que são usados em uma solução ótima).

• 1ª. Situação: o caminho mais rápido pela estação j de uma ou outra linha continha dentro dele o caminho mais rápido pela estação j-1 em uma linha.

• 2ª. Situação: colocação ótima dos parênteses de AiAi+1...Aj que divide o produto entre AK e AK+1 contém dentro dela soluções ótimas para os problemas de colocação dos parênteses de AiAi+1...AK e AK+1..Aj.

Page 105: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Subestrutura ótima Padrão comum na descoberta: 1. Mostrar que uma solução para o problema consiste em fazer

uma escolha. (ex. escolha de uma estação precedente na linha de montagem OU a escolha de um índice no qual será dividida a cadeia de matrizes)... ESSA ESCOLHA DEIXA UM OU MAIS SUBPROBLEMAS A SEREM RESOLVIDOS.

2. Supor que, para um dado problema, tem-se a escolha que conduz a solução ótima.

3. Dada essa escolha, determinar quais subproblemas resultam dela (e como caracterizar o melhor o espaço de subproblemas resultante).

4. Mostrar que as soluções para os subproblemas usados dentro da solução ótima para o problema devem elas próprias ser ótimas!! (técnica “recortar” (solução não ótima) e “colar” (solução ótima) )

Page 106: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Subestrutura ótima O tempo de execução depende:

Número de subproblemas globais

X

Quantas escolhas observamos para cada subproblema

Programação da linha de montagem:

ϴ(n) Subproblemas globais e 2 escolhas para cada um ϴ(n)

Multiplicação da cadeia de matrizes:

ϴ(n2) Subproblemas globais e no máximo (n-1) escolhas para cada um ϴ(n3)

Page 107: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmos gulosos • Introdução • Etapas para a resolução do problema • 1- Problema de seleção de atividades

– Etapas – Propriedade da escolha gulosa: – Propriedade da subestrutura ótima

• 2- Problema da mochila 0-1 – Estratégia gulosa X programação dinâmica

• 3- Código de Huffman – Código de prefixo – Custo da árvore binária – Correção do algoritmo – Propriedade da subestrutura ótima

Page 108: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Programação dinâmica X algoritmos gulosos

Algoritmos gulosos: - Subestrutura ótima de cima para baixo: Em vez de encontrar soluções ótimas para

subproblemas e depois fazer uma escolha: 1º. Faz uma escolha (a escolha que pareça a melhor

no momento) 2º. Resolvem um subproblema resultante dessa

escolha.

Page 109: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmos gulosos

Um algoritmo guloso sempre faz a

escolha que parece ser a melhor no momento –

ele faz uma escolha ótima para as condições locais, na esperança de que essa escolha leve a uma

solução ótima para a situação global.

Page 110: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Etapas para resolução do problema 1- Solução de programação dinâmica (combinar soluções ótimas

para 2 subproblemas para formar uma solução ótima para o problema original). Considerar diversas escolhas ao determinar quais subproblemas usar em uma solução ótima.

2- Observar que só é preciso considerar uma escolha – a escolha gulosa – e, que, ao optar pela escolha gulosa, um dos subproblemas tem a garantir de ser vazio, e só resta um subproblema não vazio.

3- Desenvolver um algoritmo guloso recursivo para resolver o problema de tempo de atividades.

4- Converter o algoritmo recursivo em um algoritmo interativo.

Essas etapas ilustram o relacionamento entre algoritmos gulosos e programação dinâmica

Page 111: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades Programar um recurso entre diversas atividades concorrentes. • Supor um conjunto S = a1, a2,.., an de n atividades que desejam

utilizar um recurso que pode ser utilizado por uma atividade de cada vez.

• Cada atividade ai tem um tempo de início si e um tempo de término fi, onde: 0 ≤ si < fi < ∞. Se selecionada, a atividade ai ocorre durante o intervalo de tempo meio aberto [si, fi).

• As atividades ai e aj são compatíveis se os intervalos [si, fi) e [sj, fj) não se superpõem (isto é, ai e aj são compatíveis se si ≥ fj ou sj ≥ fi).

• Selecionar um subconjunto de tamanho máximo de atividades mutuamente compatíveis.

• Exemplo: a1, a4, a8, a11, a2, a4, a9, a11

Page 112: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades Etapa 1: A subestrutura ótima do problema Solução de programação dinâmica: 1º. Encontrar a subestrutura ótima. 2º. Usá-la para construir uma solução ótima para o problema a

partir de soluções ótimas para subproblemas. Definição de um espaço de subproblemas: Sij: subconjunto de atividades em S que podem começar após a

atividade ai terminar, e que terminam antes da atividade aj começar.

Sij: todas as atividades compatíveis com ai e aj e que também são compatíveis com todas as atividades que não terminam depois de ai terminar e com todas as atividades que não começam antes de aj começar.

Page 113: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades Para representar o problema inteiro:

• Adicionar atividades fictícias a0 e an+1, e adotar as

convenções de que f0 = 0 e sn+1 = ∞. Então S=S0,n+1, e os intervalos para i e j são dados por: 0 ≤ i, j ≤ n+1.

• Supor atividades dispostas em ordem monotonicamente crescente de tempo de término:

f0 ≤ f1 ≤ f2 ≤.... ≤ fn ≤ fn+1

• Espaço de subproblemas: selecionar um subconjunto de tamanho máximo de atividades mutuamente compatíveis de Sij, para 0 ≤ i < j ≤ n+1, sabendo que todos os outros Sij são vazios.

Page 114: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades Subestrutura ótima do problema: • Considerar algum subproblema não vazio Sij, e supor que uma

solução para Sij inclua alguma atividade ak, de forma que: fi ≤ sk < fk ≤ sj

O uso da atividade atividade ak gera 2 subproblemas: Sij (atividades que começam depois de ai terminar e terminam

antes de ak começar) e Skj (atividades que começam depois de ak terminar e terminam

antes de aj começar) cada uma delas consiste em um subconjunto das atividades em

Sij.

Solução para Sij : união das soluções para Sik e Skj, mais a atividade ak

Page 115: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades Número de atividades: - tamanho da solução para Sik + tamanho da solução para Skj + 1 (para a ak). Subestrutura ótima desse problema: • Supor que uma solução ótima Aij para Sij inclui a atividade ak.

Então, as soluções Aik para Sik e Akj para Skj usadas dentro dessa solução ótima para Sij também devem ser ótimas.

(o argumento de recortar e colar também se aplica). • Qualquer solução para um subproblema não vazio Sij inclui

alguma atividade ak, e qualquer solução ótima contém dentro dela soluções ótimas para instâncias de subproblemas Sik e Skj.

• Subconjunto de tamanho máximo Aij de atividades mutuamente compatíveis:

Page 116: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades

2º passo: Uma solução recursiva (no desenvolvimento de uma solução de pgm dinâmica) - Definir recursivamente o valor de uma solução ótima. - c[i,j]: número de atividades em um subconjunto de tamanho máximo

de atividades mutuamente compatíveis em Sij. - c[i,j] = 0 sempre que Sij = Φ; c[i,j] = 0 para i ≥ j Recorrência:

c[i,j] = c[i,k] + c[k,j] + 1 • Essa eq. recursiva pressupõe que conhecemos o valor de k, o que não

é verdade. Há j-i-1 valores possíveis de k (k = i+1,... j-1).

• Conferimos todos os valores de k para encontrar o melhor.

Page 117: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades

Solução de programação dinâmica solução gulosa: • Teorema - Considerar qualquer subproblema não-vazio Sij, e am a

atividade em Sij com o tempo de término mais antigo. fm = min fk: ak ∈ Sij

1. A atividade am é usada em algum subconjunto de tamanho

máximo de atividades mutuamente compatíveis de Sij. 2. O subproblema Sim é vazio: a escolha de am deixa o subproblema

Smj como o único que pode ser não vazio. • Apenas um subproblema é usado em uma solução ótima (o outro tem a garantia de ser vazio) • Para resolver o subproblema Sij apenas uma escolha – tempo de

término mais antigo em Sij.

• O teorema reduz o número de subproblemas e de escolhas!

Page 118: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades

A subestrutura ótima varia:

- na quantidade de subproblemas usados em uma

solução ótima para o problema original

(2 subproblemas foram usados)

e

- na quantidade de escolhas para se determinar quais subproblemas usar.

(j – i – 1 escolhas ao se resolver o problema Sij)

Page 119: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades

De acordo com o teorema:

- Apenas um subproblema é usado em uma solução

ótima (o outro subproblema tem a garantia de ser vazio) e, quando resolvemos o subproblema Sij, só precisamos considerar uma escolha: a que tem o tempo de término mais antigo em Sij.

O teorema reduz o número de subproblemas e

o número de escolhas!!!

Page 120: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades

De acordo com o teorema: • Método top-down: Cada subproblema pode ser resolvido de

cima para baixo (diferente da programação dinâmica). • Para resolver o subproblema Sij, escolhemos a atividade am de Sij

com o tempo de término mais antigo e adicionamos a essa solução o conjunto de atividades usadas em uma solução ótima para o subproblema Smj

• Para resolver Sij : podemos escolher am como a atividade em Sij com o tempo de término mais antigo, e depois resolver Smj.

• A atividade escolhida é portanto uma escolha “gulosa” intuitivamente ela deixa tanta oportunidade quanto possível para que as atividades restantes sejam programadas.

• A escolha gulosa é a que maximiza a quantidade de tempo restante não programado.

Page 121: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades

Etapa 3: Um algoritmo puramente guloso recursivo: s e f: início e término das atividades i e j: índices iniciais do subproblema Si,j - Supor as n atividades de entrada ordenadas por tempo de término

monoticamente crescente. - Chamada inicial: RECURSIVE-ACTIVITY-SELECTOR(s,f,0,n+1) Retorna um conjunto de tamanho máximo de atividades mutuamente

compatíveis em Si,j. • O loop examina ai+1, ai+2, ... aj-1, até encontrar a 1ª atividade am

compatível com ai.

Tempo de execução: Θ(n)

Page 122: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades

Etapa 4: Um algoritmo guloso Iterativo:

- Supor as n atividades de entrada ordenadas por tempo de término monoticamente crescente.

Tempo de execução: Θ(n)

Page 123: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades

- Supor as n atividades de entrada ordenadas por tempo de término monoticamente crescente.

• Atividade selecionada: • Atividade sendo considerada:

Seta para a esquerda: atividade rejeitada. Seta para a direita e para cima: atividade selecionada

Conjunto de atividades selecionadas: a1, a4, a8, a11

Tempo de execução: Θ(n)

Page 124: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades

Elementos da estratégia gulosa: • Um algoritmo guloso obtém uma solução ótima para um

problema fazendo uma sequência de escolhas Opção que parece melhor no momento.

Etapas seguidas até o momento: 1- Determinar a subestrutura ótima do problema 2- Desenvolver uma solução recursiva 3- Provar que, em qualquer fase da recursão, uma das escolhas

ótimas é a escolha gulosa. 4- Mostrar que todos os subproblemas induzidos por ter sido feita

a escolha gulosa, exceto um, são vazios. 5- Desenvolver um algoritmo recursivo que implemente a

estratégia gulosa. 6- Converter o algoritmo recursivo em um algoritmo iterativo.

Page 125: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades Projeto de algoritmos gulosos: 1. Moldar o problema de otimização como um problema no qual fazemos

uma escolha e ficamos com um único subproblema para resolver. 2. Provar que sempre existe uma solução ótima para o problema original

que torna a escolha gulosa, de modo que a escolha gulosa é sempre segura.

3. Demonstrar que, tendo feito a escolha gulosa, o que resta é um subproblema com a propriedade de que, se combinarmos uma solução ótima para o subproblema com a escolha gulosa que fizemos, chegamos a uma solução ótima para o problema original.

Como saber se um algoritmo guloso resolverá

um determinado problema de otimização? Em geral, não há como saber, mas existem dois ingredientes que são exibidos

pela maioria dos problemas que se prestam a uma estratégia gulosa: a propriedade de escolha gulosa e a subestrutura ótima.

Page 126: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades

Propriedade da escolha gulosa: • Uma solução globalmente ótima pode ser alcançada fazendo-se

uma escolha localmente ótima (gulosa) escolha que parece melhor no momento, sem considerar resultados de subproblemas.

Programação dinâmica: uma escolha em cada passo, mas a

escolha pode depender das soluções para subproblemas. (abordagem bottom-up)

Algoritmo guloso: - a escolha feita pode depender das escolhas até o momento,

mas não pode depender de nenhuma escolha futura ou das soluções para subproblemas.

- abordagem top-down. Faz uma escolha gulosa após outra, reduzindo de modo iterativo cada instância do problema dado a um problema menor.

Page 127: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- Problema de seleção de atividades

Propriedade da subestrutura ótima: - Um problema exibe subestrutura ótima se uma

solução ótima para o problema contém dentro dela soluções ótimas para subproblemas.

- Para avaliar a possibilidade de aplicação da programação dinâmica e algoritmos gulosos.

- Demonstrar que uma solução ótima para o subproblema, combinada com a escolha gulosa já feita, produz uma solução ótima para o problema original.

Page 128: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2- Problema da mochila 0-1

Estratégia gulosa x programação dinâmica (a) O ladrão deve selecionar um subconjunto dos 3 itens cujo peso não pode

exceder 50 Kg. (b) O subconjunto ótimo inclui os itens 2 e 3. Qualquer solução com o item 1

não é ótima, embora tenha o maior valor por kg. (c) Para o problema da mochila fracionária, tomar os itens em ordem de

maior valor/Kg produz uma solução ótima! - Problemas semelhantes, mas o problema da mochila fracionária pode

ser resolvido por uma estratégia gulosa, enquanto o problema 0-1 não pode. Algoritmo guloso executado em O(n lg n).

Page 129: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2- Problema da mochila 0-1

Estratégia gulosa x programação dinâmica - Ambos os problemas de mochilas exibem a propriedade de

subestrutura ótima!

- Para resolver o problema fracionário: ALGORITMO GULOSO primeiro calculamos o valor por quilo vi/wi para cada item.

Obedecendo a uma estratégia gulosa, o ladrão começa levando o máximo do item com o maior valor por quilo. Se o suprimento desse item se esgotar e ele ainda puder levar mais, o ladrão levará tanto quanto possível do item com o próximo maior valor por quilo e assim por diante, até não poder levar mais nada.

ordenando os itens pelo valor por quilo, o algoritmo guloso é executado no tempo O(n lg n).

- Problema da mochila fracionária – tem a propriedade de escolha gulosa!!

Page 130: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2- Problema da mochila 0-1

Estratégia gulosa x programação dinâmica - Problema da mochila 0-1: a estratégia gulosa levaria o item 1 primeiro

(6reais/quilo)!!!– a solução ótima levaria os itens 2 e 3, deixando o item 1.

- Levar o item 1 não funciona porque o ladrão é incapaz de preencher plenamente sua mochila, e o espaço vazio diminui o valor efetivo por quilo de sua carga!!!

- As duas soluções possíveis que envolvem o item 1 não são ótimas!!

Page 131: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2- Problema da mochila 0-1

Estratégia gulosa x programação dinâmica - No problema 0-1: quando consideramos um item para inclusão na mochila,

devemos comparar: a solução para o subproblema no qual o item é incluído com a solução para o subproblema no qual o item é

excluído, antes de fazer a escolha. - O problema formulado desse modo ocasiona muitos

subproblemas superpostos: caso de programação dinâmica!

Page 132: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- Código de Huffman

- Eficiente para comprimir dados - O algoritmo guloso de Huffman usa uma tabela das frequências

de ocorrência dos caracteres para elaborar um modo ótimo de representar cada caractere como uma cadeia binária.

- Ex. de um problema de codificação de caracteres:

100.000 caracteres: a-f

300.000 bits

240.000 bits

código de caracteres ótimo

Page 133: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- Código de Huffman

• Código de prefixo: nenhuma palavra de código é também um prefixo de alguma outra palavra de código compressão de dados ótima simplificam a codificação – a palavra de código que inicia um arquivo codificado não é ambígua.

codificação aabe 0.0.101.1101 decodificação • Processo de decodificação: representação para o código de

prefixo através de uma árvore binária.

Page 134: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- Código de Huffman

Exemplo de árvores para os dois códigos apresentados.

(b)código ótimo:

árvore binária cheia

- Cada folha é identificada com um caractere e sua frequência de ocorrência.

Cada nó interno é identificado com a soma das frequências das folhas em sua subárvore.

(a) Árvore correspondente ao código de comprimento fixo. (b) Árvore correspondente ao código de prefixo ótimo.

Não são árvores de pesquisa binária, pois as folhas não precisam aparecer em sequência ordenada e os nós internos não contêm chaves de caracteres.

Page 135: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- Código de Huffman

Custo da árvore T (árvore binária completa):

- C: alfabeto de onde são obtidos os caracteres.

- Árvore para um código de prefixo ótimo: exatamente |C| folhas (uma para cada letra do alfabeto).

- |C|-1 nós internos.

Para cada caractere c em C:

f(c): frequência de c no arquivo

dT(c): profundidade da folha c na árvore.(comprimento da palavra de código para o caractere c)

Número de bits para codificar um arquivo:

Page 136: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- Código de Huffman Algoritmo guloso que produz código de prefixo ótimo!!

Prova de sua correção: baseado na prop. de escolha gulosa e

subestrutura ótima.

Constrói de baixo para cima a árvore T do código ótimo. Começa com um conjunto de |C| folhas e faz |C|-1 intercalações.

Q: fila de prioridade mínima.

Tempo de execução? Supor Q implementada como um heap binário. Para um conjunto C de n caracteres, a inicialização de Q (l.2) pode ser executada em O(n)(BUILD-MIN-HEAP).

Loop for: (n-1) vezes e cada operação do exige o tempo O(lg n) O(n lgn)

O(n lgn)

Page 137: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- Código de Huffman Exemplo:

Page 138: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- Código de Huffman Correção do algoritmo de Huffman:

Propriedade de escolha gulosa: (lema)

Page 139: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- Código de Huffman Correção do algoritmo de Huffman:

Page 140: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- Código de Huffman

Correção do algoritmo de Huffman:

Por que essa é uma escolha gulosa?

O custo de uma intercalação única é a soma das frequências dos dois itens que estão sendo intercalados.

O custo total da árvore é a soma dos custos de suas intercalações.

De todas as intercalações possíveis em cada passo,

ele escolhe a de menor custo.

Page 141: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- Código de Huffman

Correção do algoritmo de Huffman:

Propriedade de subestrutura ótima: (lema)

Page 142: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Modelagem em Grafos

• Busca em Largura

• Busca em Profundidade

• Árvores espalhadas mínimas

– Kruskal

– Prim

• Caminhos mais curtos de única origem

– Bellman-Ford

– Dikstra

Page 143: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Largura • Dado um grafo G=(V,E) e um vértice de origem distinta s, a

busca em largura explora sistematicamente as arestas de G até “descobrir” cada vértice acessível a partir de s.

• Calcula a distância (menor número de arestas) desde s até todos os vértices acessíveis desse tipo.

• Produz uma “árvore primeiro na extensão” com raiz s que contém todos os vértices acessíveis. Para qualquer vértice v acessível a partir de s, o caminho na árvore primeiro na extensão de s até v corresponde a um “caminho mais curto” de s até v em G, ou seja, um caminho que contém o número mínimo de arestas.

• Funciona sobre grafos orientados e não-orientados.

Page 144: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Largura • Expande a fronteira entre vértices descobertos e não

descobertos uniformemente ao longo da extensão da fronteira, ou seja, o algoritmo descobre todos os vértices à distância k a partir de s, antes de descobrir quaisquer vértices à distância k + 1.

Para controlar o andamento, - pinta cada vértice de branco (não descoberto), cinza ou preto

(descobertos).

- Se (u,v) ϵ E e o vértice u é preto, então o vértice v é cinza ou preto; isto é, todos os vértices adjacentes a vértices pretos foram descobertos.

- Vértices de cor cinza: podem ter alguns vértices adjacentes brancos; representam a fronteira entre vértices descobertos (pretos) e não descobertos (brancos).

Page 145: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Largura • Árvore primeiro na extensão: caminho com número

mínimo de arestas. • Subgrafo predecessor de G: Gπ = (Vπ,Eπ)

Predecessor ou pai, ancestral - Se u está em um caminho na árvore a partir da raiz s até o

vértice v, então u é um ancestral de v, e v é um descendente de u.

• Um vértice tem no máximo um pais pois cada vértice é descoberto no máximo uma vez.

Page 146: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Largura

Page 147: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Largura • O procedimento anterior pressupõe que o grafo de entrada

G=(V,E) é representado com o uso de listas de adjacências.

• Variável cor[u]: cor de cada vértice u ϵ V

• π[v]: predecessor de u • d[u]: distância desde a origem s até o vértice u.

• Fila Q: FIFO para gerenciar o conjunto de vértices de cor

cinza.

• Todos os vértices acessíveis a partir de s devem ser descobertos porque, se não fossem, eles teriam valores d infinitos.

Page 148: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Largura • Análise Agregada

• Operações enfileirar/desenfileirar: O(1) Tempo total de operações de fila: O(V) (cada vértice é colocado e retirado da fila no máximo

uma vez) • Soma dos comprimentos de todas as listas de adj é θ(E) →

tempo máximo O(E) para varrer todas as listas de adj. • Inicialização: O(V) • Tempo de execução total de BFS: O(V+E)

• A pesquisa primeiro na extensão é executada em tempo

linear no tamanho da representação de lista de adj. de G.

Page 149: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Largura • Impressão dos vértices em um caminho mais curto

desde s até v, supondo-se que BFS já tenha sido executado para calcular a árvore do caminho mais curto.

• Executado em tempo linear no número de vértices no caminho impresso, pois cada chamada recursiva é para um caminho um vértice mais curto.

Page 150: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade • Procurar “mais fundo” no grafo

• As arestas são exploradas a partir do vértice v mais recentemente descoberto que ainda tem arestas inexploradas saindo dele. Quando todas as arestas de v são exploradas,a busca regressa para explorar as arestas que deixam o vértice v a partir do qual v foi descoberto.

• Esse processo continua até descobrir todos os vértices acessíveis a partir do vértice de origem inicial.

• Se restarem quaisquer vértices não descobertos, então um deles será selecionado como uma nova origem, e a busca se repetirá.

• O processo é repetido até todos os vértices serem descobertos.

Page 151: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade • Subgrafo predecessor produzido por:

Busca em largura – forma uma árvore

Busca em profundidade – pode ser composto por várias árvores pois a busca pode ser repetida a partir de várias origens.

Gπ = (V, Eπ)

Arestas em E: arestas de árvore

• Forma uma floresta primeiro na profundidade composta por várias árvores primeiro na profundidade.

• Vértices coloridos durante a busca (garante que cada vértice acaba em exatamente uma árvore primeiro na profundidade, de forma que essas árvores sejam disjuntas).

Page 152: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade • Cada vértice identificado com carimbos de

tempo:

- d[v]: v descoberto pela primeira vez (cinza)

- f[v]: término de verificação da lista de adj. de v (preto)

- Inteiros entre 1 e 2|V|, pois existe um evento de descoberta e um evento de término para cada um dos |V| vértices.

d[v] < f[v]

Branco cinza preto

Page 153: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade

Page 154: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade

Page 155: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade

Page 156: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade Tempo de execução (Análise Agregada):

• DFS: Linhas 1-3 e 5-7 = θ(V)

• DFS-VISIT: chamado exatamente uma vez para cada vértice v ϵ V, pois é invocado apenas sobre vértices brancos e a primeira ação é pintar o vértice de cinza. Linhas 4-7: θ(E)

• Total: θ(V + E)

Page 157: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade Propriedades: • 1- Subgrafo predecessor Gπ forma uma floresta de

árvores, pois a estrutura das árvores primeiro na profundidade reflete exatamente a estrutura de chamadas recursivas de DFS-VISIT.

(u = π[v] sse DFS-VISIT(v) foi chamado durante uma

pesquisa da lista de adj. de u. O vértice v é um descendente do vértice u na floresta primeiro na profundidade sse v é descoberto durante o tempo em que u é cinza).

• 2- Estrutura de parênteses para os tempos de descoberta e término.

Page 158: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade (Teorema dos parênteses)

(Teorema do caminho branco) • Em uma floresta primeiro na profundidade de um

grafo (orientado ou não), o vértice v é um descendente do vértice u sse no momento d[u] em que a procura descobre u, o vértice v pode ser alcançado a partir de u ao longo de um caminho que consiste inteiramente em vértices brancos.

Page 159: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade a) Grafo orientado Vértices identificados por carimbos de

tempo Arestas:B(retorno),C(cruzada), F(direta)

b) Tempos de descoberta/término entre parênteses

c) Arestas de árvore e diretas descendo no interior de uma árvore primeiro na profundidade.

Arestas de retorno subindo de um

descendente para um ancestral

Page 160: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade Classificação de arestas Arestas de árvore: arestas na floresta primeiro na

profundidade Gπ. A aresta(u,v) é uma aresta de árvore se v foi descoberto primeiro pela exploração da aresta (u,v).

Arestas de retorno: arestas (u,v) que conectam um vértice u a um ancestral v em uma árvore primeiro na profundidade. Autoloops.

Arestas diretas: arestas (u,v) não de árvore que conectam um vértice u a um descendente v em uma árvore primeiro na profundidade. d[u] < d[v].

Arestas cruzadas: todas as outras. Podem estar entre vértices na mesma árvore primeiro na profundidade, desde que um vértice não seja um ancestral do outro, ou podem estar entre vértices em diferentes árvores primeiro na profundidade.

d[u] > d[v].

Page 161: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade Ordenação Topológica: • Em grafos acíclicos orientados (gaos: usados para indicar

precedências entre eventos). • Um grafo orientado G é acíclico sse uma busca em

profundidade de G não produz nenhuma aresta de retorno. • de um gao G=(V,E) é uma ordenação linear de todos os seus

vértices, tal que se G contém uma aresta (u,v), então u aparece antes de v na ordenação.

• de um grafo: ordenação de seus vértices ao longo de uma linha horizontal, de forma que todas as arestas orientadas sigam da esquerda para a direita.

Θ(V+E) O(1)

Page 162: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade Ordenação topológica

(a) GAO: aresta orientada indica que a peça u deve vir antes da peça v.

(b) Ordenação topológica fornece uma ordem no processo de se vestir. Ordem de tempo de término decrescente. Arestas orientadas da esquerda para a direita.

Page 163: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade

Page 164: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade

Page 165: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Busca em Profundidade

Page 166: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Árvores espalhadas mínimas • Grafo conectado não-orientado G=(V,E)

• w(u,v): custo para conectar u e v

• Encontrar um subconjunto acíclico T ⊆ E que conecte todos os

vértices e cujo peso total:

seja minimizado

• Como T é acíclico e conecta todos os vértices, ele deve formar uma árvore: – Árvore espalhada – pois se “estende” pela amplitude do grafo G –

problema da árvore espalhada mínima (de peso mínimo)

Page 167: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Árvores espalhadas mínimas Exemplo de grafo conectado e sua árvore espalhada mínima:

Peso total da árvore: 37 - Essa árvore de amplitude mínima não é única: a remoção da

aresta (b,c) e a substituição pela aresta (a,h) produz uma árvore de amplitude com mesmo peso.

2 algoritmos gulosos: Kruskal e Prim • Em cada passo de um algoritmo, uma entre diversas opções

possíveis deve ser escolhida – melhor escolha do momento – não oferece a garantia de encontrar soluções globalmente ótimas para problemas.

Page 168: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Árvores espalhadas mínimas Como aumentar uma árvore espalhada mínima? Algoritmo genérico – estratégia gulosa – aumenta a árvore espalhada

mínima uma aresta de cada vez. Administra um conjunto de arestas A, mantendo o loop invariante:

Antes de cada iteração, A é um subconjunto de alguma árvore espalhada mínima

• Em cada etapa, determinar uma aresta (u,v) que pode ser adicionada a A

sem violar esse invariante, tal que A U (u,v) também é um subconjunto de uma árvore espalhada mínima –aresta segura para A– pode ser adicionada com segurança a A, e mantendo o loop invariante.

Page 169: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Árvores espalhadas mínimas Inicialização: Depois da linha 1, o conjunto A satisfaz de forma trivial ao loop

invariante. Manutenção: O loop nas linhas 2 a 4 mantém o invariante, adicionando apenas

arestas seguras. Término: Todas as arestas adicionadas a A estão em uma árvore espalhada mínima,

e então o conjunto A retornado na linha 5 deve ser uma árvore espalhada mínima.

Parte complicada: encontrar uma aresta segura na linha 3. Deve existir uma,

pois quando a linha 3 é executada, o invariante estabelece que existe uma árvore espalhada T tal que A ⊆T. Dentro do while, A deve ser um subconjunto próprio de T, e então deve haver uma aresta (u,v) ∈T tal que (u,v) ∉ A e (u,v) é segura para A.

Page 170: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Árvores espalhadas mínimas Definições: • Um corte (S,V-S) de um grafo não-orientado G=(V,E) é uma

partição de V.

• Uma aresta (u,v) ∈ E cruza o corte (S, V-S) se um de seus pontos extremos está em S e o outro em V-S.

• Um corte respeita o conjunto A de arestas se nenhuma aresta em A cruza o corte.

• Uma aresta é uma aresta leve cruzando um corte se seu peso é o mínimo de qualquer aresta que cruza o corte.

Page 171: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Árvores espalhadas mínimas Grafo: Corte (S,V-S)

(a) Vértices no conjunto S em preto e em V-S em branco. Arestas que cruzam o corte: conectam vértices brancos com vértices pretos. Aresta (d,c): única aresta leve que cruza o corte. Um subconjunto A das arestas está sombreado; o corte (S,V-S) respeita A, pois nenhuma aresta de A cruza o corte.

(b) Vértices no conjunto S à esquerda e os vértices no conjunto V-S à

direita. Uma aresta cruza o corte se ela conecta o vértice à esquerda com um vértice à direita.

Page 172: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmo de Kruskal • Baseado no algoritmo genérico de árvore

espalhada mínima.

• O conjunto A é uma floresta – a aresta segura adicionada a A é sempre uma aresta de peso mínimo no grafo que conecta dois componentes distintos.

• Algoritmo guloso: em cada etapa ele adiciona à floresta uma árvore de peso mínimo possível.

• Implementação: utiliza uma estrutura de dados de conjuntos disjuntos para manter vários conjuntos disjuntos de elementos.

Page 173: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmo de Kruskal MST-KRUSKAL(G,w) 1. A 0 2. for cada vértice v ∈ V[G] 3. do MAKE-SET(v) > cria |V| árvores cada uma

contendo um vértice 4. Ordenar as arestas de E por peso w não decrescente 5.for cada aresta (u,v) ϵ E, em ordem de peso não

decrescente 6. do if FIND-SET(u) ≠ FIND-SET(v) 7. then A A U (u,v) 8. UNION(u,v) 9. Return A

Page 174: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmo de Kruskal

Page 175: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmo de Kruskal

Page 176: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmo de Kruskal Tempo de execução: • Depende da implementação da estrutura de dados de conjuntos

disjuntos. • Supor a implementação da floresta de conjuntos disjuntos com as

heurísticas de união por ordenação e compressão de caminho: implementação assintoticamente mais rápida. 1. O(1) 4. O(E lg E)

2-3: |V| + 5-8: O(E): FIND-SET e UNION

O((V+E)α(V)): α: f. de crescimento muito lenta

Como G é supostamente conectado: |E| ≥ |V|- 1. O(Eα(V)) O(E lg E). O(E lg V)

Page 177: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmo de Prim • Baseado no algoritmo genérico de árvore espalhada mínima. • Semelhante ao algoritmo de Dijkstra para localizar caminhos

mais curtos em um grafo.

• Propriedade: as arestas no conjunto A sempre formam uma árvore única. – A árvore começa a partir de um vértice de raiz arbitrária r e aumenta

até a árvore alcançar todos os vértices em V. – Em cada etapa, é adicionada à árvore A uma aresta leve que conecta

A a um vértice isolado de G = (V,A) – adicionando apenas arestas que são seguras para A: quando o algoritmo termina, as arestas em A formam uma árvore espalhada mínima.

• Estratégia gulosa: a árvore é aumentada em cada etapa com uma aresta que contribui com a quantidade mínima possível para o peso da árvore.

Page 178: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmo de Prim Durante a execução do algoritmo: • Os vértices que não estão na árvore residem em uma fila

de prioridade mínima Q baseada em um campo chave.

• Para cada vértice v, chave[v] é o peso mínimo de qualquer aresta que conecta v a um vértice na árvore; chave[v] = ∞ se não existe nenhuma aresta desse tipo.

• Durante o algoritmo, o conjunto A de GENERIC-MST é mantido implicitamente como:

• Quando o algoritmo termina, a fila de prioridades Q está vazia:

Page 179: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmo de Prim

Vértice da raiz: a Arestas sombreadas estão na árvore que está sendo aumentada. Em cada

etapa, os vértices na árvore determinam um corte no grafo, e uma aresta leve cruzando o corte é acrescentada à árvore.

Em (b), pode-se adicionar aresta (b,c) ou (a,h) à árvore, desde que sejam arestas leves cruzando o corte.

Page 180: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmo de Prim

Page 181: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Algoritmo de Prim Desempenho: Depende de como se implementa a fila de prioridades Q – se for

como um heap mínimo binário: usar BUILD-MIN-HEAP para inicializar as linhas 1 a 5 no tempo O(V).

l. 1 a 5: O(V) l. 6 a 11: |V| vezes l.7: O (lg V) Todas as chamadas a EXTRACT-MIN: O (V lg V) Loop for: O(E) vezes l.11: op. Implícita de DECREASE-KEY sobre o heap mínimo – O (lg V) Tempo total: O(V lg V + E lg V)O(E lg V) assintoticament igual ao Kruskal • Pode ser melhorado com heaps de Fibonacci – se |V| elementos estão

organizados em um heap de Fibonacci – operação EXTRACT-MIN em tempo amortizado O(lg V) e DECREASE-KEY no tempo amortizado O(1). Se usar o heap de Fib. para implementar a fila de prioridade mínima Q, o tempo de execução melhora até: O(E + V lg V).

Page 182: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem • Resolve problemas do tipo: como encontrar a rota mais curta do

Rio a São Paulo? Problemas de caminhos mais curtos: • Grafo orientado ponderado G = (V,E), com função peso w: E R

mapeando arestas para pesos de valores reais. O peso do caminho p=<v0,v1,..., vk> é o somatório dos pesos de suas arestas constituintes:

• Peso do caminho mais curto desde u até v:

• Um caminho mais curto desde o vértice u até o vértice: qualquer caminho p com peso w(p) = δ(u,v)

Page 183: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem

• Os pesos das arestas podem ser interpretados como medidas, em vez de distâncias. Qualquer quantidade que se acumule linearmente ao longo de um caminho que se deseje minimizar.

• O algoritmo de busca em largura é um algoritmo de caminhos mais curtos que funciona sobre grafos não ponderados – grafos em que cada aresta tem peso unitário.

• Dado um grafo G=(V,E), encontrar um caminho mais curto desde um determinado vértice de origem s ϵ V até todo vértice v ϵ V.

Page 184: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem

Variantes:

Page 185: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem Subestrutura ótima de um caminho mais curto • Em geral, os algoritmos de caminhos mais curtos se

baseiam na propriedade de que um caminho mais curto entre dois vértices contém outros caminhos mais curtos em seu interior:

propriedade da subestrutura ótima: característica da aplicabilidade de programação dinâmica e do método guloso.

Algoritmo de Dijkstra: algoritmo guloso Algoritmo de Floyd-Warshall (encontra caminhos mais

curtos entre todos os pares de vértices): algoritmo de programação dinâmica)

Page 186: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem Arestas de peso negativo: • Se o gravo G=(V,E) não contém nenhum ciclo de peso negativo

acessível a partir da origem s, então para todo v ϵ V, o peso do caminho mais curto δ(s,v) permanece bem definido, mesmo tendo um valor negativo.

• Se existe um ciclo de peso negativo acessível a partir de s, os pesos de caminhos mais curtos NÃO são bem definidos.

• Se existe um ciclo de peso negativo em algum caminho desde s até v, δ(s,v) = -∞

• Nenhum caminho desde s até um vértice no ciclo pode ser um caminho mais curto – sempre é possível encontrar um caminho de peso menor que segue o caminho “mais curto” proposto e depois atravessa o ciclo de peso negativo.

Page 187: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem Pesos de arestas negativos em um grafo orientado:

• Dentro de cada vértice, o peso de seu caminho mais curto a partir da origem s.

• Como os vértices e e f formam um ciclo de peso negativo acessível a partir de s, eles têm pesos de caminhos mais curtos iguais a -∞. Como o vértice g é acessível a partir de um vértice cujo peso de caminho mais curto é -∞, ele também tem um peso de caminho mais curto igual a -∞.

• Vértices como h,i,j NÃO são acessíveis a partir de s, e assim os pesos de seus caminho mais curtos são iguais a ∞, embora eles residam em um ciclo de peso negativo.

Page 188: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem Representação de caminhos mais curtos:

• Calcular não apenas os pesos de caminhos mais curtos, mas também os vértices nos caminhos mais curtos.

• Dado um grafo G=(V,E), mantemos cada vértice v ϵ V um predecessor π[v] que é outro vértice ou NIL.

• Dado um vértice v para o qual π[v] ≠ NIL, PRINT-PATH(G,s,v) pode ser usado para imprimir um caminho mais curto desde s até v.

Page 189: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem • Durante a execução de um algoritmo de caminhos mais

curtos, os π valores não precisam indicar caminhos mais curtos.

• Como a busca em largura, estamos interessados no subgrafo predecessor Gπ=(Vπ, Eπ) induzido pelos valores de π. Conjunto de vértices:

• Conjunto de arestas orientadas Eπ: o conjunto de arestas induzidas pelos π valores correspondentes aos vértices em Vπ:

Page 190: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem • Caminhos mais curtos não são necessariamente únicos, e

nem árvores de caminhos mais curtos. • Exemplo de um grafo orientado ponderado e duas árvores

de caminhos mais curtos com a mesma raiz:

Page 191: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem Relaxamento: • Para cada vértice v ϵ V, um atributo d[v]: limite superior sobre o peso de

um caminho mais curto desde a origem s até v. • d[v]: estimativa de caminho mais curto. • Inicialização: Θ(V)

• O processo de relaxar uma aresta (u,v) consiste em testar se podemos melhorar o caminho mais curto para v encontrado até agora pela passagem através de u, e atualizar d[v] e π[v]. Uma etapa de relaxamento pode diminuir o valor da estimativa de caminho mais curto d[v] e atualizar o campo predecessor de v, π[v].

• Único meio de se alterar estimativas de caminhos mais curtos e predecessores.

Page 192: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem Exemplo: Relaxamento de uma aresta (u,v) com peso w(u,v)=2.

Estimativa de caminhos mais curtos de cada vértice é mostrada

dentro do vértice. (a) d[v] > d[u] + w(u,v) antes do relaxamento e depois o valor de

d[v] diminui. A estimativa de caminhos mais curtos diminui. (b) d[v] ≤ d[u] + w(u,v) antes da etapa de relaxamento. d[v] não é

alterada pelo relaxamento. Nenhuma estimativa se altera.

Page 193: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem Propriedades de caminhos mais curtos e relaxamento: 1- Desigualdade de triângulos. Para qualquer aresta (u,v) ϵ E: δ(s,v) ≤ δ(s,u) + w(u,v)

2- Limite superior. Sempre temos d[v] ≥ δ(s,v) para todos os vértices v ∈

V e, uma vez que d[v] alcança o valor δ(s,v), ele nunca muda.

3- Nenhum caminho. Se não existe nenhum caminho de s para v, então sempre temos: d[v] = δ(s,v) = ∞

4- Convergência. Se é um caminho mais curto em G para algum u, v ϵ V, e se d[u]=δ(s,u) em qualquer instante antes de se relaxar a aresta (u,v), então d[v]= δ(s,v) em todos os momentos posteriores.

5- Relaxamento de caminho. Se p=<v0, v1, ..., vk> é um caminho mais curto de e as arestas de p são relaxadas na ordem:

6- Subgrafo predecessor. Uma vez que d[v]= δ(s,v) para todo v ϵ V, o subgrafo predecessor é uma árvore de caminhos mais curtos com raiz em s.

Page 194: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem Algoritmo de Bellman-Ford: • Resolve o problema de caminhos mais curtos de única origem no caso

mais geral, no qual os pesos das arestas podem ser negativos

• Retorna um valor booleano indicando se existe ou não um ciclo de peso negativo acessível a partir da origem. Se existe tal ciclo, o algoritmo indica que não existe nenhuma solução. Se não existe tal ciclo, o algoritmo produz os caminhos mais curtos e seus pesos.

• Usa o relaxamento, diminuindo progressivamente uma estimativa d[v] no peso de um caminho mais curto da origem s até cada vértice v ϵ V, até alcançar o peso real de caminho mais curto.

• Retorna TRUE sse o grafo não contém nenhum ciclo de peso negativo acessível a partir da origem.

Page 195: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem

θ(V)

θ(E)

O(E)

• Tempo de execução: O(VE)

Page 196: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem • Execução do Algoritmo de Bellman-Ford

Page 197: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem • Em grafos acíclicos não orientados (GAO)

Page 198: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem

Page 199: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem

Page 200: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem Algoritmo de Dijkstra:

• Resolve o problema em um grafo orientado ponderado G=(V,E) quando todos os pesos de arestas são não negativos.

• Supor w(u,v) ≥ 0 para cada aresta (u,v) ∈ E • Mantém um conjunto S de vértices cujos pesos finais de

caminhos mais curtos desde a origem s já foram determinados. (vértices pretos)

• Seleciona repetidamente o vértice u ≥ V-S com a estimativa mínima de caminhos mais curtos, adiciona u a S e relaxa todas as arestas que saem de u.

• Mantém uma fila de prioridade mínima Q de vértices, tendo como chaves seus valores de d. (vértices brancos). Q=V-S.

• Utiliza uma estratégia gulosa sempre escolhe o vértice “mais leve” ou “mais próximo” em V-S para adicionar ao conjunto S.

Page 201: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caminhos mais curtos de única origem A execução do algoritmo

Page 202: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Problemas NP-Completos • Introdução

• Caráter NP-completo e as classes P e NP

• Técnicas para mostrar que um problema é NP-completo

• Classe de complexidade P – Problema abstrato

– Codificação

– Estrutura de linguagem formal

• Classe de complexidade NP – Verificação de tempo polinomial

– Ciclos hamiltonianos.

– Algoritmo de verificação

– A classe de complexidade NP

Page 203: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Problemas NP-Completos • Caráter NP-Completo e redutibilidade

– Redutibilidade

– Problemas NP-Completos

– Satisfabilidade de circuitos

• Provas do caráter NP-completo...

Page 204: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Introdução • Algoritmos de tempo polinomial – tempo de execução do pior

caso: O(nk), sobre entradas de tamanho n e para alguma constante k.

• Nem todos os podem ser resolvidos em tempo polinomial!! Ex: ‘problema de parada’ (Turing).

• Existem problemas que podem ser resolvidos, mas NÃO em

O(nk), para qualquer constante k.

• Problemas que podem ser resolvidos por algoritmo de tempo polinomial. TRATÁVEIS.

• Problemas que exigem tempo superpolinomial – INTRATÁVEIS ou DIFÍCEIS!

Page 205: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Introdução

• Ainda não foi descoberto nenhum algoritmo de tempo polinomial para um problema NP-completo, mas ninguém ainda foi capaz de provar que NÃO pode existir nenhum algoritmo de tempo polinomial para qualquer deles!!

P ≠NP

Page 206: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Introdução Exemplos:

Caminho simples mais curtos – tempo polinomial

É possível encontrar caminhos mais curtos a partir de uma única origem em um grafo orientado G=(V,E) no tempo O(VE)

Caminho simples mais longo – NP-completo

(entre dois vértices)

Obs: independente dos pesos das arestas!!

Page 207: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Introdução Exemplos: Viagem de Euler – tempo polinomial de um grafo orientado conectado G=(V,E) é um ciclo que

percorre cada aresta de G exatamente uma vez, embora possa visitar um vértice mais de uma vez. Podemos determinar se um grafo tem uma viagem de Euler somente no tempo O(E) – podemos encontrar as arestas no tempo O(E).

Ciclo hamiltoniano – NP-completo

É um ciclo simples de um grafo orientado G=(V,E) que contém cada vértice em V. Determinar se G tem um ciclo hamiltoniano é NP-completo!!

Page 208: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Introdução Exemplos: Satisfabilidade 2-CNF – tempo polinomial Satisfabilidade 3-CNF – NP-completo Uma fórmula booleana: - é capaz de satisfação se existe alguma atribuição dos

valores 0 e 1 para suas variáveis que faça com que ela seja avaliada como 1;

- está em forma normal k-conjuntiva, ou k-CNF, se for o AND de cláusulas de OR de exatamente k variáveis ou suas negações.

- Exemplo: (x1 v¬x2) ^ (¬x1 v x3) ^ (¬x2 v ¬x3) (Ela tem atribuição satisfatória x1 =1, x2 =0, x3 =1)

Page 209: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caráter NP-completo e as classes P e NP

Classe P:

- Problemas que podem ser resolvidos em tempo polinomial O(nk)

Classe NP:

- Problemas verificáveis em tempo polinomial – se tivéssemos de algum modo um “certificado” de uma solução, podemos verificar se o certificado é correto em tempo polinomial no tamanho da entrada para o problema.

Page 210: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caráter NP-completo e as classes P e NP Classe NP: Exemplo 1: Problema do ciclo hamiltoniano - Dado um grafo orientado G=(V,E), um certificado

seria uma sequência <v1,v2,v3,...,v|v|> de |V| vértices. É fácil verificar em tempo polinomial que (vi, vi+1) ∈ E para i=1,2,3,..., |V|-1 e também que (v|V|, v1) ∈ E.

Exemplo 2: Satisfabilidade 3-CNF - Um certificado seria uma atribuição de valores a

variáveis. É fácil verificar em tempo polinomial que essa atribuição satisfaz à fórmula booleana.

Page 211: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caráter NP-completo e as classes P e NP

- Qualquer problema em P também está em NP. (Se um problema está em P então podemos resolvê-lo em tempo polinomial sem sequer receber um certificado)

- P ⊆NP

- P é ou não um subconjunto próprio de NP ?

Page 212: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caráter NP-completo e as classes P e NP

- Um problema está na classe NPC – problema NP-completo – se ele está em NP e é tão “difícil” quanto qualquer problema NP.

- Declaração:

Se qualquer problema NP-completo pode ser resolvido em tempo polinomial, então todo problema NP-completo tem um algoritmo de tempo polinomial!!

Page 213: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caráter NP-completo e as classes P e NP

- Problemas NP-completos intratáveis:

Dada a ampla faixa de problemas NP-completos estudados até hoje, sem qualquer progresso em direção a uma solução de tempo polinomial, seria verdadeiramente espantoso se todos eles pudessem ser resolvidos em tempo polinomial!!

MAS Não se pode eliminar a possibilidade de que os problemas NP-completos possam de fato ser resolvidos em tempo polinomial!!

Page 214: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Técnicas para mostrar que um problema é NP-completo

- Ao mostrar que um problema é NP-completo, estamos fazendo uma declaração sobre a dificuldade para resolver esse problema (ou, pelo menos o quanto o consideramos difícil), não sobre o quanto ele é fácil.

- Não estamos tentando provar a existência de um algoritmo eficiente, mas sim que provavelmente não existe nenhum algoritmo eficiente!

Page 215: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Técnicas para mostrar que um problema é NP-completo

1- Problemas de decisão X problemas de otimização

Problemas de otimização: cada solução possível (i.e. válida) tem um valor associado, e desejamos encontrar a solução possível com o melhor valor.

Problemas de decisão: a resposta é simplesmente “sim” ou “não” (“1” ou “0”).

2- Reduções

Page 216: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Técnicas para mostrar que um problema é NP-completo

1- Problemas de decisão X problemas de otimização

Exemplo:

SHORTEST-PATH:

temos um grafo não orientado G e vértices u e v, e desejamos encontrar o caminho de u até v que utiliza o menor número de arestas

Ou seja, problema de caminho mais curto de um único par em um grafo não orientado e não ponderado.

Porém, O caráter NP-completo não se aplica diretamente a problemas de otimização, mas a problemas de decisão!!

Page 217: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Técnicas para mostrar que um problema é NP-completo

1- Problemas de decisão X problemas de otimização Existe um relacionamento conveniente entre problemas de

otimização e problemas de decisão. Normalmente, podemos formular um determinado problema de

otimização como um problema de decisão relacionado impondo um limite sobre o valor a ser otimizado.

Exemplo: SHORTEST-PATH: Problema de decisão relacionado: PATH. Dado um grafo orientado G, vértices u e v, e um inteiro k, existe

um caminho de u até v consistindo em no máximo k arestas.

Page 218: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Técnicas para mostrar que um problema é NP-completo

1- Problemas de decisão X problemas de otimização Exemplo: 1- Resolver PATH resolvendo SHORTEST-PATH 2- Comparar o número de arestas no caminho mais curto encontrado ao

valor do parâmetro de problema de decisão k. Se um problema de otimização é fácil, seu problema de decisão relacionado

também é fácil!! Caráter NP-completo: se pudermos fornecer evidências de que um problema de decisão é difícil,

também forneceremos evidências de que seu problema de otimização relacionado é difícil!!

Embora restrinja a atenção a problemas de decisão, a teoria de problemas

NP-completos frequentemente também tem implicações para problemas de otimização!!

Page 219: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Técnicas para mostrar que um problema é NP-completo

2- Reduções Exemplo: - Problema de decisão A: problema a ser resolvido em

tempo polinomial. - Problema de decisão B: já sabemos como resolver

em tempo polinomial!!! Entrada para um determinado problema instância

desse problema (em PATH, uma instância seria um dado grafo G, vértices específicos u e v de G, e um certo inteiro k).

Page 220: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Técnicas para mostrar que um problema é NP-completo

2- Reduções Algoritmo de redução Procedimento que transforma qualquer instância α

de A em alguma instância β de B com as características:

a- A transformação demora tempo polinomial. b- As respostas são as mesmas – a resposta para α é

“sim” sse a resposta para β também é “sim”.

Page 221: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Técnicas para mostrar que um problema é NP-completo

2- Reduções Algoritmo de redução Oferece um meio para resolver o problema A em tempo polinomial: 1. Dada uma instância α do problema A, use um algoritmo de redução de

tempo polinomial para transformá-la em uma instância β do problema B.

2. Execute o algoritmo de decisão de tempo polinomial para B sobre a instância β.

3. Use a resposta de β como resposta para α.

Como cada uma das etapas demora tempo polinomial, as 3 juntas também. – modo de decisão sobre α em tempo polinomial. “reduzindo” a solução do problema A à solução do problema B, usamos a “facilidade” de B para provar a “facilidade” de A.

Page 222: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Técnicas para mostrar que um problema é NP-completo

2- Reduções Algoritmo de tempo polinomial para decidir A

Em tempo polinomial: - transformamos uma instância α de A em uma instância β de B,

- resolvemos B em tempo polinomial e - usamos a resposta de β como a resposta para α.

Page 223: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Classe de Complexidade P - Problemas que podem ser resolvidos em tempo

polinomial.

• Problemas “tratáveis”:

1º. Existem poucos problemas práticos que exigem tempo na ordem de um polinômio de altíssimo grau (ex:θ(n100) – intratável).

Uma vez que um algoritmo de tempo polinomial para um problema é descoberto, algoritmos mais eficientes frequentemente o seguem.

Page 224: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Classe de Complexidade P • Problemas “tratáveis”: 2º. Para muitos modelos razoáveis de computação, um

problema que pode ser resolvido em tempo polinomial (tp) em um modelo pode ser resolvido em tempo polinomial em outro modelo.

Ex: a classe de problemas (cp) que podem ser

resolvidos em tp pela máquina de acesso aleatório serial é igual a cp que podem ser resolvidos em tp em máquinas abstratas de Turing. E também igual a cp que podem ser resolvidos em tp em um computador paralelo, quando o número de processadores cresce polinomialmente com o tamanho da entrada.

Page 225: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Classe de Complexidade P • Problemas “tratáveis”:

3º. A classe de problemas de tempo polinomial que podem ser resolvidos tem propriedades de fechamento interessantes, pois os polinômios são fechados sob a adição, a multiplicação e a composição.

Ex: Se a saída de um algoritmo de tempo polinomial é alimentada na entrada de outro, o algoritmo composto é polinomial.

Se o algoritmo de tempo polinomial faz um número constante de chamadas a sub-rotinas de tempo polinomial, o tempo de execução do algoritmo composto é polinomial.

Page 226: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Classe de Complexidade P Problemas abstratos Q

Relação binária sobre um conjunto I de instâncias de

problemas e um conjunto S de soluções de problemas. Ex: uma instância de SHORTEST-PATH é uma tripla que

consiste em um grafo e dois vértices. Uma solução é uma sequência de vértices no grafo, talvez com a sequência vazia denotando que não existe nenhum caminho.

Problema SHORTEST-PATH: relação que associa cada instância de um grafo e 2 vértices com um caminho mais curto no grafo que conecta os 2 vértices.

Caminhos mais curtos NÃO são necessariamente únicos uma dada instância de problema pode ter mais de uma solução!!

Page 227: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Classe de Complexidade P Problemas abstratos Q

A teoria de problemas NP-completos restringe a atenção a

problemas de decisão solução sim/não. Problema de decisão abstrato: função que mapeia o conjunto

de instâncias I para o conjunto solução 0,1. Problema de decisão relacionado a SHORTEST-PATH: problema

PATH. Se i=G,u,v, k é uma instância de PATH, então PATH(i) = 1 (sim) se um caminho mais curto de u até v tem no máximo k arestas, e PATH(i)=0 (não) em caso contrário.

Muitos problemas abstratos não são problemas de decisão, e sim problemas de otimização: algum valor deve ser minimizado ou maximizado. Como visto, é simples reformular um problema de otimização como um problema de decisão não mais fácil que o primeiro!!!

Page 228: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Classe de Complexidade P Codificações

Para um computador resolver um problema abstrato, as instâncias de

problemas devem ser representadas de modo que o programa reconheça!!

Uma codificação de um conjunto S de objetos abstratos é um mapeamento e de S para o conjunto de cadeiras binárias!!

Ex: codificação dos números naturais N=0,1,2,3,... como as cadeias 0,1,10,11,.... e(17)= 10001.

Um algoritmo de computador que “resolve” algum problema de decisão abstrato: toma uma codificação de uma instância de problema como entrada.

Problema concreto: problema cujo conjunto de instâncias é o conjunto de cadeias binárias.

Um problema concreto pode ser resolvido em tempo polinomial se existe um algoritmo para resolvê-lo no tempo O(nk) para alguma constante k.

Page 229: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Classe de Complexidade P Conjunto de problemas de decisão concretos que podem ser

resolvidos em tempo polinomial. Codificações

Mapeiam problemas abstratos em problemas concretos. Dado um problema de decisão abstrato Q que mapeia um conjunto de

instâncias I para 0,1, uma codificação e: I 0,1* pode ser usada para induzir um problema de decisão concreto relacionado, denotado por e(Q).

Se a solução para uma instância de problema abstrato i ∈ I é Q(i) ∈ 0,1, então a solução para a instância de problema concreto e(i) ∈ 0,1* também é Q(i).

Podem existir algumas cadeias binárias que não representam nenhuma instância significativa de problema abstrato (supor cadeias mapeadas arbitrariamente como 0) o problema concreto produz as mesmas soluções que o problema abstrato sobre instâncias de cadeias binárias que representam as codificações de instância do problema abstrato.

Page 230: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Classe de Complexidade P Codificações

A eficiência da solução de um problema não deve depender do modo

como o problema está codificado. Infelizmente, ela depende bastante disso.

Dependendo da codificação, o algoritmo será executado em tempo polinomial ou superpolinomial.

A codificação de um problema abstrato é muito importante para

compreensão do tempo polinomial. Não se pode falar sobre a resolução de um problema abstrato sem primeiro especificar uma codificação!!

MAS se eliminarmos codificações “dispendiosas”, a codificação real de um

problema fará pouca diferença na hora de decidir se o problema pode ser resolvido em tempo polinomial. Por exemplo: a representação de inteiros na base 3 em vez de binário um inteiro representado na base 3 pode ser convertido em um inteiro representado na base 2 em tempo polinomial!!

Page 231: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Classe de Complexidade P Codificações

Uma função f: 0,1* 0,1* é calculável em tempo polinomial

se existe um algoritmo de tempo polinomial A que, dada qualquer entrada x ∈ 0,1*, produz como saída f(x).

Para algum conjunto I de instâncias de problemas, duas codificações e1 e e2 são polinomialmente relacionadas se existem duas funções calculáveis em tempo polinomial f12 e f21 tais que, para qualquer i ∈ I, tempo f12(e1(i))=e2(i) e f21(e2(i))=e1(i).

“A codificação e2(i) pode ser calculada a partir da codificação e1(i) por um algoritmo de tempo polinomial, e vice-versa”.

Se duas codificações e1 e e1 de um problema abstrato são polinomialmente relacionadas, o fato de um problema poder ou não ser resolvido em tempo polinomial é independente da codificação que usamos. e1(Q) ∈ P sse e2(Q) ∈ P.

Page 232: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

P – teoria de linguagem formal

Alfabeto Σ: conjunto finito de símbolos.

Linguagem L sobre Σ: qualquer conjunto de cadeias formadas por símbolos de Σ.

Ex: se Σ = 0,1, o conjunto L = 10,11,101,1011,... é a linguagem de representações binárias de números primos.

ε: cadeia vazia

Ф: linguagem vazia

Σ*: linguagem de todas as cadeias sobre Σ.

Ex: se Σ = 0,1, então Σ* = ε,0,1,00,01,10,11,000,... é o conjunto de todas as cadeias binárias.

Toda linguagem L sobre Σ é um subconjunto de Σ*.

Page 233: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

P – teoria de linguagem formal

Existe uma variedade de operações sobre linguagens.

Operações da teoria de conjuntos, como união e interseção, decorrem diretamente das definições da teoria dos conjuntos.

Complemento de L: L = Σ* - L.

Concatenação de duas linguagens L1 e L2:

L = x1x2 | x1∈ L1 e x2∈ L2

Page 234: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

P – teoria de linguagem formal Fechamento ou estrela de Kleene de uma linguagem L: L* =

ε U L U L2 U L3 U ..., onde Lk é a linguagem obtida pela concatenação de L com ela própria k vezes.

O conjunto de instâncias para qualquer problema de decisão Q é simplesmente o conjunto Σ*, onde Σ=0,1.

Como Q é completamente caracterizado pelas instâncias de problema que produzem uma resposta 1 (sim), podemos ver Q como uma linguagem L sobre Σ=0,1, onde:

L = x ∈ Σ* : Q(x) = 1

Page 235: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

P – teoria de linguagem formal Problema de decisão PATH Linguagem correspondente: PATH = <G,u,v,k>: G=(V,E) é um grafo não

orientado, u, v ∈ V, k >= 0 é um inteiro, e existe um caminho de u até v em G que consiste em no máximo k arestas Obs: <G>: codificação padrão de um grafo G

Page 236: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

P – teoria de linguagem formal A estrutura da linguagem formal permite que se

expresse a relação entre problemas de decisão e algoritmos que os resolvem de forma concisa.

Um algoritmo A aceita uma cadeia x ∈ 0,1* se, dada a entrada x, a saída do algoritmo A(x) é 1.

A linguagem aceita por um algoritmo A é o conjunto L = x ∈ 0,1* : A(x)=1, isto é, o conjunto de cadeias que o algoritmo aceita.

Um algoritmo A rejeita uma cadeia x se A(x)=0.

Page 237: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

P – teoria de linguagem formal Ainda que a linguagem L seja aceita por um algoritmo A, o algoritmo não

rejeitará necessariamente uma cadeia x ∉ L. Ex: o algoritmo pode entrar

em loop infinito.

Uma linguagem L é decidida por um algoritmo A, se toda cadeia binária em L é aceita por A e toda cadeia binária não pertencente a L é rejeitada por A.

Uma linguagem L é aceita em tempo polinomial por um algoritmo A se ela é aceita por A e se, além disso, existe uma constante k tal que, para qualquer cadeia de comprimento n, x∈ L, o algoritmo A aceita x no

tempo O(nk).

Uma linguagem L é decidida em tempo polinomial por um algoritmo A se existe uma constante k tal que, para qualquer cadeia de comprimento n, x∈ 0,1*, o algoritmo decide corretamente se x ∈ L no tempo O(nk).

Para aceitar uma linguagem, um algoritmo só precisa se preocupar com as cadeias em L MAS, para decidir uma linguagem, ele deve aceitar ou

rejeitar corretamente toda cadeia em 0,1*.

Page 238: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

P – teoria de linguagem formal A linguagem PATH pode ser aceita em tempo polinomial.

Algoritmo de aceitação em tempo polinomial:

1º. Verifica se G codifica um grafo não orientado, 2º. Verifica se u e v são vértices em G. 3º. Usa a busca em largura para calcular o caminho mais curto de

u até v em G, 4º. Compara o número de arestas no caminho mais curto obtido

com k. Se G codifica um grafo não orientado e o caminho de u até v tem

no máximo k arestas, o algoritmo dá saída a 1 e para. Senão, ele continua a ser executado para sempre. Porém, não decide PATH, pois ele não dá saída a 0 explicitamente para instâncias em que o caminho mais curto tem mais de k arestas!!

Page 239: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

P – teoria de linguagem formal Um algoritmo de decisão para PATH deve rejeitar

explicitamente cadeias binárias que não pertençam a PATH!

Algoritmo PATH: Em vez de executar para sempre quando não há um caminho de u até v com no máximo k arestas, ele dá saída a 0 e para.

Problema de parada de Turing: existe um algoritmo de aceitação, mas nenhum algoritmo de decisão!!

Page 240: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

P – teoria de linguagem formal Classe de complexidade: conjunto de linguagens, cuja pertinência

é determinada por uma medida de complexidade (ex: tempo de execução) de um algoritmo que determina se uma dada

cadeia x pertence à linguagem L. Definição alternativa da classe de complexidade P: P=L ⊆ 0,1*: existe um algoritmo A que decide L em tempo

polinomial. P também é a classe de linguagens que podem ser aceitas em

tempo polinomial: P=L : L é aceita por um algoritmo de tempo polinomial

Page 241: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

NP – Verificação de tempo polinomial - Algoritmos que “verificam” a pertinência em linguagens.

- Supor que, para uma dada instância <G,u,v,k> do problema

de decisão PATH, também recebemos um caminho p de u até v. Podemos verificar rapidamente se o comprimento de p é no máximo k e, se for, podemos visualizar p como um “certificado” de que a instância de fato pertence a PATH.

- Para PATH, esse certificado não parece importar muito. Afinal PATH pertence a P – pode ser resolvido em tempo linear – e assim, a verificação da pertinência de um dado certificado demora tanto tempo quanto a resolução do problema desde o início.

Page 242: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

NP – Verificação de tempo polinomial Ciclos hamiltonianos

- Um ciclo hamiltoniano de um grafo não orientado G=(V,E) é um ciclo simples que contém cada vértice em V.

- Problema de encontrar um ciclo hamiltoniano em um grafo não orientado – ainda não se sabe de nenhum algoritmo de decisão de tempo polinomial; dado um certificado, a verificação é fácil!!

Page 243: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

NP – Verificação de tempo polinomial Ciclos hamiltonianos

(a) Um grafo representando os vértices, as arestas e as faces de um dodecaedro, com um ciclo hamiltoniano mostrado por arestas sombreadas.

(b) Um grafo bipartido com um número ímpar de vértices. Qualquer grafo desse tipo é não hamiltoniano.

Page 244: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

NP – Verificação de tempo polinomial Ciclos hamiltonianos Problema do ciclo hamiltoniano: “Um grafo G tem um ciclo

hamiltoniano?” Definição através de uma linguagem formal: HAM-CYCLE = <G>: G é um grafo hamiltoniano. Como poderia um algoritmo decidir a linguagem HAM-CYCLE?

Dada uma instância de problema <G>, um algoritmo de decisão possível lista todas as permutações possíveis dos vértices de G, e depois verifica cada permutação para ver se ela é um caminho hamiltoniano.

- Não é executado em tempo polinomial – problema NP-COMPLETO!!

Page 245: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

NP – Verificação de tempo polinomial Algoritmo de Verificação

Algoritmo de dois argumentos A:

- Cadeia de entrada comum x

- Cadeia binária y chamada certificado

Verifica uma cadeia de entrada x se existe um certificado y tal que A(x,y)=1.

A linguagem verificada por um algoritmo de verificação:

L = x ∈ 0,1*: existem y ∈ 0,1* tal que A(x,y)=1

Page 246: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

NP – Verificação de tempo polinomial Algoritmo de Verificação

Intuitivamente, um algoritmo A verifica uma linguagem L se, para qualquer cadeia x∈L, existe um certificado y que A pode utilizar para provar que x∈L. Além disso, para qualquer cadeia x∉L, não deve haver nenhum certificado digital provando que x∈L.

Problema do ciclo hamiltoniano: o certificado é a lista de vértices no ciclo hamiltoniano.

O algoritmo de verificação examina cuidadosamente

o “ciclo” proposto para ter certeza!!!

Page 247: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

A classe de complexidade NP Classe de linguagens que podem ser verificadas por um

algoritmo de tempo polinomial. NP: nondeterministic polynomial time

- Uma linguagem L pertence a NP sse existe um algoritmo

de tempo polinomial de duas entradas A e uma constante c tal que:

L = x ∈ 0,1*: existe um certificado y com |y| = O(|x|c) tal que A(x,y)=1.

“A verifica a linguagem L em tempo polinomial.”

Page 248: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

A classe de complexidade NP Verificação em tempo polinomial! HAM-CYCLE ∈ NP. Se L ∈ P, então L ∈NP pois, se existe um algoritmo de

tempo polinomial para decidir L, o algoritmo pode ser facilmente convertido em um

algoritmo de verificação de dois argumentos que simplesmente ignore qualquer certificado e aceita exatamente as cadeias de entrada que ele determina para estar em L.

Logo, L ⊆ NP.

Page 249: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

A classe de complexidade NP Classes de complexidade:

P: problemas que podem ser resolvidos com rapidez.

- Fechada sob o complemento.

NP: problemas para os quais uma solução pode ser verificada rapidamente.

- Inclui linguagens que não estão em P.

- Fechada sob o complemento ? (L ∈ NPL ∈ NP ?)

co-NP: conjunto de linguagens L tais que L ∈ NP.

Page 250: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

A classe de complexidade NP Possibilidades de relacionamentos entre classes de complexidade P P=NP ∩ co-NP P

(a) Mais improvável!! (b) NP é fechada sob o complemento. (c) NP não é fechada sob o complemento. (d) Mais provável

Page 251: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caráter NP-completo e redutibilidade Classes de problemas “NP-completos”

P ≠NP?

Propriedade: se qualquer problema NP-completo pode ser resolvido em tempo polinomial, então todo problema em NP tem uma solução em tempo polinomial, isto é, P=NP.

MAS nenhum algoritmo de tempo polinomial jamais foi descoberto por qualquer problema NP-completo!!

Page 252: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Caráter NP-completo e redutibilidade Linguagem HAM-CYCLE: problema NP-completo. Se pudéssemos decidir HAM-CYCLE em tempo

polinomial, então poderíamos resolver todo problema em NP em tempo polinomial.

Se NP – P fosse não vazia HAM-CYCLE ∈ NP – P Linguagens NP-completas: linguagens “mais difíceis” em NP. REDUTIBILIDADE em tempo polinomial!! comparar a “dificuldade” relativa de linguagens

Page 253: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Redutibilidade Um problema Q pode ser reduzido a outro problema Q’ se

qualquer instância de Q pode ser “facilmente reformulada” como uma instância de Q’, cuja solução fornece uma solução para a instância de Q.

- Exemplo: problema de resolver equações lineares em um x indeterminado se reduz ao problema de resolver equações quadráticas.

Dada uma instância ax+b=0, transformamos essa instância em 0x2 + ax+b=0, cuja solução fornece uma solução para ax+b=0.

Se um problema Q se reduz a outro problema Q’, então Q não é, em certo sentido, “mais difícil de resolver” que Q’.

Page 254: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Redutibilidade Estrutura de linguagem formal para problemas de decisão: Uma linguagem L1 é redutível em tempo polinomial a uma

linguagem L2, L1 ≤p L2 se existe uma função calculável de tempo polinomial

f:0,1* 0,1* tal que, para todo x∈0,1*, x ∈ L1 sse f(x) ∈ L2 função de redução f Algoritmo de redução F: algoritmo de tempo polinomial que

calcula f.

Page 255: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Redutibilidade Redução de tempo polinomial de uma linguagem L1 a uma

linguagem L2 por meio de uma função de redução f. Cada linguagem é um subconjunto de 0,1*.

Para qualquer entrada x ∈ 0,1*, a questão de saber se x∈ L1

tem a mesma resposta que a questão de saber se f(x)∈ L2. A função de redução mapeia qualquer instância x do problema de

decisão representado pela linguagem L1 para uma instância f(x) do problema representado por L2.

Page 256: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Redutibilidade Reduções de tempo polinomial: poderosa ferramenta para provar que diversas linguagens pertencem a P. sim, x ∈ L1 x não, x ∉ L1 F: algoritmo de redução que calcula a função de redução f de L1 a L2 em

tempo polinomial. A2: algoritmo de tempo polinomial que decide L2. A1: algoritmo que decide se x∈ L1 usando F para transformar qualquer

entrada x em f(x) e então usando A2 para decidir se f(x) ∈ L2. A saída de A2 é o valor fornecido como a saída de A1. Algoritmo executado

em tempo polinomial, pois F e A2 são executados em tempo polinomial.

sim, f(x)∈ L2

f(x) não, f(x)∉ L2

A1

F A2

Page 257: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Problemas NP-completos Reduções de tempo polinomial: meio formal de mostrar que um

problema é pelo menos tão difícil quanto outro, até dentro de um fator de tempo polinomial. Se L1 ≤pL2, então L1 não é mais que um fator polinomial mais difícil que L2.

Conj. de linguagens NP-completas: problemas mais difíceis em NP. Um linguagem L∈ 0,1* é NP-completa se: 1. L ∈ NP e 2. L’ ≤p L para todo L’ ∈ NP.

- Se uma linguagem L satisfaz à propriedade 2, mas não

necessariamente à propriedade 1, dizemos que L é NP-difícil. - Classe NPC: classe de linguagens NP-completas. - Caráter NP-completo: ponto crucial de se determinar se P é de

fato igual a NP.

Page 258: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Problemas NP-completos Teorema: Se qualquer problema NP-completo pode ser resolvido em

tempo polinomial, então P=NP. - Supor que L ∈ P e também que L ∈ NPC. Para qualquer L’

∈ NP, temos L’ ≤p L (prop.2). Também temos que L’ ∈ NP:

Se qualquer problema em NP não pode ser resolvido em

tempo polinomial, então nenhum problema NP-completo pode ser resolvido em tempo polinomial.

- Prova: Contrapositivo do primeiro.

Page 259: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Problemas NP-completos A questão P≠NP ? se concentra em torno dos problemas NP-

completos. Modo como a maioria dos cientistas da computação teórica vê os

relacionamentos entre P, NP e NPC. Tanto P quanto NPC estão inteiramente contidas dentro de NP, e P ∩ NPC = Ф:

Como ainda não foi descoberto nenhum algoritmo de tempo

polinomial para qualquer problema NP-completo, uma prova de que um problema é NP-completo fornece uma excelente evidência para a impossibilidade de seu tratamento.

NP NPC

P

Page 260: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos

Depois que provarmos que pelo menos um problema é NP-completo, poderemos usar a

redutibilidade de tempo polinomial

como uma ferramenta para provar

o caráter NP-completo de outros problemas.

Problema da satisfabilidade de circuitos:

Problema NP-completo

Page 261: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos Problema: dado um circuito combinacional booleano composto de portas

AND, OR e NOT, ele é capaz de satisfação?

Tamanho de um circuito combinacional booleano: número de elementos combinacionais somado ao número de fios no circuito.

Codificação padrão para circuitos.

É possível criar uma codificação semelhante à de grafos que mapeie qualquer circuito C dado em uma cadeia binária <C> cujo comprimento seja polinomial no tamanho do próprio circuito.

Como uma linguagem formal, pode-se definir:

CIRCUIT-SAT =

<C>: C é um circuito combinacional booleano capaz de satisfação

Page 262: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos Duas instâncias do problema de satisfabilidade de circuitos:

(a) A atribuição <x1=1, x2=1, x3=0> (atribuição verdade) para as

entradas desse circuito faz a saída do circuito se tornar 1. O circuito é então CAPAZ DE SATISFAÇÃO – tem uma atribuição satisfatória.

(b) Nenhuma atribuição para as entradas desse circuito pode fazer a saída do circuito se tornar 1. O circuito é então INCAPAZ DE SATISFAÇÃO.

Page 263: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos - Dado um circuito C, podemos determinar se ele é capaz de

satisfação apenas verificando todas as atribuições possíveis para as entradas.

Infelizmente, se existem k entradas, existem 2k atribuições possíveis.

- Quando o tamanho de C é polinomial em k, a verificação de cada uma demora o tempo Ω(2k), que é superpolinomial no tamanho do circuito.

- Há uma forte evidência de que não existe nenhum algoritmo de tempo polinomial que resolva o problema da satisfabilidade de circuitos, porque a satisfabilidade de circuitos é NP-completa.

Page 264: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos O problema da satisfabilidade de circuitos pertence à classe NP. Prova (1ª. Parte) Forneceremos um algoritmo de tempo polinomial A de duas entradas que

pode verificar CIRCUIT-SAT:

Uma entrada para A é (uma codificação padrão de) um circuito combinacional booleano C.

A outra entrada é um certificado que corresponde a uma atribuição de valores booleanos aos fios em C.

1- Para cada porta lógica no circuito, ele verifica se o valor fornecido no fio

de saída é corretamente calculado como uma função dos valores nos fios de entrada.

2- Em seguida, se a saída do circuito inteiro é 1, o algoritmo fornece a

saída 1, pois os valores atribuídos às entradas de C fornecem um atribuição satisfatória. Cc, A fornece a saída 0.

Page 265: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos O problema da satisfabilidade de circuitos pertence à classe NP. Prova (cont) Sempre que um circuito capaz de satisfação C é dado como

entrada para o algoritmo A, existe um certificado cujo comprimento é polinomial no tamanho de C e que faz A fornecer a saída 1.

Sempre que um circuito incapaz de satisfação é dado como

entrada, nenhum certificado pode fazer A acreditar que o circuito é capaz de satisfação.

O algoritmo A é executado em tempo polinomial CIRCUIT-SAT

pode ser verificado em tempo polinomial, e CIRCUIT-SAT ∈ NP.

Page 266: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos O problema da satisfabilidade de circuitos é NP difícil. Prova (2ª. Parte) L: qualquer linguagem em NP. F: algoritmo de tempo polinomial que calcula uma função de

redução f que mapeia toda cadeia binária x para um circuito C=f(x) tal que

x ∈ L sse f(x) ∈ CIRCUIT-SAT Como L ∈ NP, deve existir um algoritmo A que verifique L em

tempo polinomial. O algoritmo F usará o algoritmo A de duas entradas para calcular a função de redução f.

Page 267: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos O problema da satisfabilidade de circuitos é NP difícil.

Seja:

T(n): tempo de execução pior caso do algoritmo A sobre cadeias de entrada de comprimento n

k>=1 uma cte tal que

T(n)=O(nk) e o comprimento do certificado seja O(nk).

O tempo de execução de A é na realidade um polinômio no tamanho total da entrada, o que inclui tanto uma cadeia de entrada quanto um certificado; contudo, como o comprimento do certificado é polinomial no comprimento n da cadeia, o tempo de execução é polinomial em n!!

Page 268: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos O problema da satisfabilidade de circuitos é NP difícil. Prova Representar a computação de A como uma sequência de configurações (qq

estado particular da memória do computador) Cada configuração dividida em: programa para A, o contador de programa e

estado da máquina auxiliar, a entrada x, o certificado y e o espaço de armazenamento de trabalho.

Cada configuração ci é mapeada em uma configuração subsequentes ci+1

pelo circuito combinacional M que implementa a hardware do computador.

A saída do algoritmo A-0 ou 1- é gravada em algum local designado na área de arm. de trabalho quando A termina sua execução e, se supomos que daí em diante A pára, o valor nunca muda. se o algoritmo é executado par ano máximo T(n) passos, a saída permanece como um dos bits em cT(n).

Page 269: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos A sequência de configurações produzidas por um algoritmo A em execução sobre uma entrada x e um

certificado y. Cada configuração representa o estado do computador para uma passo da computação, e, além de A, x e y, inclui o contador de pgm (PC), o estado da máq. aux., e o espaço de armazenamento de trabalho. Exceto por y, a configuração inicial c0 é cte. Cada configuração é mapeada para a configuração seguinte por um circuito combinacional booleano M. A saída é um bit distinto no espaço de armazenamento de trabalho.

Co

C1

.

.

CT(n) Saída 0/1

A PC estado de máquina auxiliar x y armaz.de trabalho

M

A PC estado de máquina auxiliar x y armaz.de trabalho

M

A PC estado de máquina auxiliar x y armaz.de trabalho

M

M

Page 270: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos O algoritmo de redução F constrói um único circuito

combinacional que calcula todas as configurações produzidas por uma dada configuração inicial. A idéia é juntar T(n) cópias do circuito M. A saída do i-ésimo circuito, que produz a configuração ci, é inserida diretamente na entrada do (i+1)-ésimo circuito.

As configurações, em vez de terminarem em um registrador de estado, simplesmente residem como valores nos fios

que conectam cópias de M.

Page 271: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos Algoritmo de redução de tempo polinomial F:

- Dada uma entrada x, ele tem de calcular um circuito C=f(x) que seja capaz de satisfação sse existe um certificado y tal que A(x,y)=1.

- Quando F obtém uma entrada x, primeiro ele calcula n = |x| e constrói um circuito combinacional C’ que consiste em T(n) cópias de M. A entrada para C’ é uma configuração inicial correspondente a uma computação sobre A(x,y), e a saída é a configuração cT(n).

- F é executado em tempo polinomial!!

Page 272: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos

Page 273: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de circuitos A linguagem CIRCUIT-SAT é pelo menos tão difícil quanto

qualquer linguagem em NP e, como pertence a NP, ela é NP-completa!!

O problema da satisfabilidade de circuitos é NP-completo!!!

Page 274: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Provas do caráter NP-completo

1- Satisfabilidade de fórmulas

2- Satisfabilidade de 3-CNF

Page 275: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Provas do caráter NP-completo Vários problemas de satisfabilidade de fórmulas são NP-completos.

Reduzindo a L uma linguagem NP-completa L’ conhecida, reduzimos

implicitamente toda linguagem em NP a L. Método para provar que uma linguagem L é NP-completa: 1. Prove que L ∈NP. 2. Selecione uma linguagem NP-completa conhecida. 3. Descreva um algoritmo que calcule uma função f que mapeie toda

instância x ∈ 0,1* de L’ para uma instância f(x) de L. 4. Prove que a função f satisfaz a x ∈ L’ sse f(x) ∈ L para todo x ∈ 0,1*. 5.Prove que o algoritmo que calcula f é executado em tempo polinomial. Etapas 2 a 5- mostram que L é NP-difícil!!

Page 276: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Provas do caráter NP-completo

Page 277: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de fórmulas • Metodologia de redução dando uma prova do caráter NP-

completo para o problema de determinar se uma fórmula booleana, não um circuito, é capaz de satisfação.

• Primeiro problema a ser apresentado como NP-completo!!

• Problema de satisfabilidade de fórmulas.

Instância de SAT: fórmula booleana Ф composta de:

1. n variáveis booleanas: x1, x2,..., xn.

2. m conectivos booleanos

3. parênteses

Page 278: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de fórmulas • Atribuição verdade para Ф: conjunto de valores para as variáveis de Ф, • Atribuição satisfatória: atribuição verdade que faz com que ela seja

avaliada como 1. • Uma fórmula com um atribuição satisfatória é uma fórmula booleana

capaz de satisfação.

Uma dada fórmula booleana é capaz de satisfação? Em termos de linguagem formal: SAT = <Ф> : Ф é uma fórmula booleana capaz de satisfação Exemplo: Tem a atribuição satisfatória <x1=0, x2=0 , x3=1, x4=1> Assim, essa fórmula Ф pertence a SAT.

Page 279: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de fórmulas • O algoritmo simples para determinar se uma

fórmula booleana arbitrária é capaz de satisfação não é executado em tempo polinomial. Existem 2n atribuições possíveis em uma fórmula Ф com n variáveis.

• Se o comprimento de <Ф> é polinomial em n, então a verificação de cada atribuição exige o tempo Ω(2n), que é superpolinomial no comprimento de <Ф>. É improvável que exista um algoritmo de tempo polinomial.

Page 280: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de fórmulas • Redução da satisfabilidade de circuito à

satisfabilidade de fórmula. A fórmula produzida pelo algoritmo de redução tem uma variável para cada fio no circuito.

Page 281: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de fórmulas É NP-completa??

Provas:

Prova 1: SAT ∈ NP? (item 1)

Prova 2: SAT é NP-difícil? (itens 2 a 5)

(mostrando que CIRCUIT-SAT ≤pSAT)

Page 282: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de fórmulas Prova 1: SAT ∈ NP? (1) - Mostrar que um certificado que consiste em uma

atribuição satisfatória para uma fórmula de entrada Ф pode ser verificado em tempo polinomial.

- O algoritmo de verificação simplesmente substitui cada variável na fórmula por seu valor correspondente, e então avalia a expressão. (tarefa de tempo polinomial)

- Se a expressão tem o valor 1, a fórmula é capaz de satisfação.

Page 283: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de fórmulas Prova 2: SAT é NP-difícil? (2-5) (2) CIRCUIT-SAT ≤pSAT? (CIRCUIT-SAT : NP-completa conhecida) - Qualquer instância de satisfabilidade de circuito pode ser

reduzida em tempo polinomial a uma instância de satisfabilidade de fórmula.

- A indução pode ser usada para expressar qualquer circuito combinacional booleano como uma fórmula booleana: observamos a porta que produz a saída do circuito e expressamos indutivamente cada uma das entradas da porta como fórmulas:

- a fórmula do circuito é obtida, escrevendo-se uma expressão que aplica a função da porta a fórmulas de suas entradas!! ESSE MÉTODO NÃO CONSTITUI UMA REDUÇÃO DE TEMPO POLINOMIAL!!!

Page 284: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de fórmulas Prova 2: SAT é NP-difícil?

CIRCUIT-SAT ≤pSAT?

(3) Para cada fio xi no circuito C, a fórmula Ф tem uma variável xi. A operação apropriada de uma porta expressa como uma fórmula envolvendo as variáveis de seus fios incidentes. A operação da porta AND de saída: x10 ↔(x7 ^ x8 ^ x9).

Page 285: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de fórmulas Prova 2: SAT é NP-difícil?

CIRCUIT-SAT ≤pSAT?

(3) Fórmula Ф produzida pelo algoritmo de redução:

Tempo polinomial!!

Page 286: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de fórmulas Prova 2: SAT é NP-difícil? CIRCUIT-SAT ≤pSAT? (4 e 5) Por que o circuito C é capaz de satisfação exatamente

quando a fórmula Ф é capaz de satisfação? - se C tem atribuição satisfatória, cada fio do circuito tem

um valor bem definido, e a saída do circuito é 1. - a atribuição de valores de fios a variáveis em Ф faz cada

cláusula de Ф apresentar o valor 1, e assim a conjunção de todos eles tem o valor 1.

- reciprocamente, se existe uma atribuição que faz Ф apresentar o valor 1, o circuito C é capaz de satisfação!!

CIRCUIT-SAT ≤pSAT!!

Page 287: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de 3-CNF Linguagem 3-CNF ou 3-CNF-SAT. - Literal em uma fórmula booleana: ocorrência de uma variável ou

sua negação. - Uma fórmula booleana está em forma normal conjuntiva, ou

CNF, se é expressa como um grupo AND de cláusulas, cada uma das quais é o OR de um ou mais literais.

- Uma fórmula booleana está em 3-forma normal conjuntiva, ou 3-CNF, se cada cláusula tem exatamente três literais distintos.

- Ex: Uma dada fórmula booleana Ф em 3-CNF é capaz de satisfação ??

(improvável existir um algoritmo de tempo polinomial!!)

Page 288: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de 3-CNF

É NP-completa??

Provas:

Prova 1: 3-CNF-SAT ∈ NP? (item 1)

Prova 2: 3-CNF-SAT é NP-difícil? (itens 2 a 5)

(mostrando que SAT ≤p 3-CNF-SAT)

Page 289: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de 3-CNF Algoritmo de redução: 3 passos: cada passo transforma progressivamente a fórmula de

entrada Ф, deixando-a mais próxima da 3-CNF desejada. 1º. Passo: construir uma árvore binária “de análise” para a fórmula

de entrada Ф, com literais como folhas e conectivos como nós internos.

Árvore de análise para a fórmula:

Page 290: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de 3-CNF - Caso a fórmula de entrada contenha uma cláusula como OR de diversos literais,

a associatividade por ser usada para colocar a expressão totalmente entre parênteses, de forma que cada nó interno na árvore resultante tenha 1 ou 2 filhos.

- A árvore de análise binária pode ser vista como um circuito para calcular a função.

- 1º. Para a saída de cada nó interno, introduz-se uma variável yi. - 2º. Reescrever a fórmula original como o AND da variável de raiz e uma

conjunção de cláusulas descrevendo a operação de cada nó. Expressão resultante Ф’ (construção de Ф’ a partir de Ф preserva a satisfabilidade!!) Máximo de 3 literais, Cada clausula com um OR de literais.

Page 291: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Satisfabilidade de 3-CNF 2º. Passo: Converter cada cláusula para a forma normal

conjuntiva. - Tabela verdade avaliando todas as atribuições

possíveis para suas variáveis.Ex: para a cláusula:

3º. Passo: transformação adicional da fórmula para

cada cláusula ter exatamente 3 literais distintos.

A redução pode ser calculada em tempo polinomial!!

Page 292: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Problemas NP-completos 1- O problema do grupo exclusivo (CLIQUE)

2- O problema de cobertura de vértices (VERTEX-COVER)

3- O problema do ciclo hamiltoniano (HAM-CYCLE)

4- O problema do caixeiro-viajante

(TSP)

5- O problema da soma de subconjuntos

(SUBSET-NUM)

Page 293: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

Problemas NP-completos A Estrutura de provas do caráter NP-completo. Redução do caráter NP-completo de CIRCUIT-SAT

Page 294: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- O problema do grupo exclusivo - Um grupo exclusivo em um grafo não-orientado G=(V,E) é um

subconjunto V’⊆ V de vértices, com cada par conectado por uma aresta em E Subgrafo completo de G.

- Tamanho de um grupo exclusivo: número de vértices que ele contém.

Problema de otimização de encontrar um grupo exclusivo de

tamanho máximo em um grafo. Como um problema de decisão, simplesmente perguntamos se

um grupo exclusivo de um dado tamanho k existe no grafo. Definição formal: CLIQUE=<G,K>: G é um grafo com um grupo exclusivo de

tamanho k.

Page 295: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- O problema do grupo exclusivo Um algoritmo simples para determinar se um grafo

G=(V,E) com |V| vértices tem um grupo exclusivo de tamanho k é listar todos os k subconjuntos de V e conferir cada um para ver se ele forma um grupo exclusivo.

O tempo de execução desse algoritmo é polinomial se

k é uma constante. Porém, em geral k poderia estar próximo de |V|/2, e nesse caso, o algoritmo é executado em tempo superpolinomial.

É improvável que exista um algoritmo eficiente

para o problema do grupo exclusivo!!

Page 296: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- O problema do grupo exclusivo

É NP-completo!!

Provas:

Prova 1: CLIQUE ∈ NP? (item 1)

Prova 2: CLIQUE é NP-difícil? (itens 2 a 5)

(mostrando que 3-CNF-SAT ≤p CLIQUE)

Page 297: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- O problema do grupo exclusivo

Prova 1: CLIQUE ∈ NP?

Usamos o conjunto V’⊆V de vértices no grupo

exclusivo como um certificado para G. A verificação se V’ é um grupo exclusivo pode ser realizada em tempo polinomial verificando se, para todo para u, v ∈ V’, a aresta u,v ∈ E.

Page 298: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- O problema do grupo exclusivo Prova 2: CLIQUE é NP-difícil? mostrar que 3-CNF-SAT ≤p CLIQUE O algoritmo de redução começa com uma instância de 3-CNF-SAT. Seja = C1 ^

C2 ^... Ck uma fórmula booleana em 3-CNF com k cláusulas. Para r=1,2,...,k, cada cláusula Cr tem exatamente três literais distintos l1’, l2’ e l3’.

Construir um grafo G tal que Ф seja capaz de satisfação sse G tem um grupo

exclusivo de tamanho k: Para cada cláusula Cr = (l1’ v l2’ v l3’) em Ф, inserir também uma tripla de

vértices v1’, v2’ e v3’ em V. Inserir uma aresta entre dois vértices vi

r e vjs se ambas as características

se mantêm: .

Page 299: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- O problema do grupo exclusivo Grafo G derivado da fórmula 3-CNF Ф=C1 ^ C2 ^C3, onde C1 = (x1 v

¬x2 v ¬ x3), C2 = (¬x1 v x2 v x3) e C3 = (x1 v x2 v x3) na redução de 3-CNF-SAT a CLIQUE.

Uma atribuição satisfatória da fórmula é x2=0, x3=1 e x1 pode ser 0

ou 1. Essa atribuição satisfaz a C1 com ¬x2 e satisfaz a C2 e C3 com x3, correspondendo ao grupo exclusivo de tamanho k=3 com vértices ligeiramente sombreados (¬x2, x3, x3).

G calculado a partir de Ф em tempo polinomial!!

Page 300: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

1- O problema do grupo exclusivo

Page 301: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2- O problema de cobertura de vértices Encontrar uma cobertura de vértices de tamanho mínimo

em um dado grafo (problema de otimização). Uma cobertura de vértices de um grafo não orientado

G=(V,E) é um subconjunto V’⊆V tal que (u,v) ∈ E, então u ∈ V’ ou v ∈ V’ (ou ambos).

Cada vértice “cobre” suas arestas incidentes, e uma

cobertura de vértices para G é um conjunto de vértices que cobre todas as arestas em E.

O tamanho de um cobertura de vértices é o número de vértices que ela contém.

Page 302: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2- O problema de cobertura de vértices Problema de otimização problema de decisão: - Determinar se um grafo tem uma cobertura de vértices de um

dado tamanho k.

- VERTEX-COVER = <G,k>: grafo G tem uma cobertura de vértices de tamanho k.

Problema NP-completo!! - Prova1: VERTEX-COVER ∈NP.

- Supor um grafo G=(V,E) e um inteiro κ. O certificado é a própria

cobertura de vértices V’⊆V. O algoritmo de verificação: 1- Afirma que |V’|=κ. 2- Verifica, para cada aresta (u,v) ∈ E, que u ∈ V’ ou v ∈ V’. Verificação realizada em tempo polinomial

Page 303: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2- O problema de cobertura de vértices Prova 2- NP-difícil - Mostrar que |V’|=κ - Redução baseada na noção de “complemento” de um grafo. Dado um grafo não

orientado G=(V,E), define-se o complemento de G como G = (V,E), onde E = (u,v):u,v ∈V, u≠v, e (u,v) ∉ E

- G: grafo que contém exatamente as arestas que não estão em G!! - Redução de CLIQUE a VERTEX-COVER:

(a) (b) - (a) Um grafo não orientado G=(V,E) com grupo exclusivo V’=u,v,x,y. - (b) Grafo G produzido pelo alg. de redução com cobert. de vértices V-V’ =w,z de

tamanho 2.

v

y x

w z

v u u

y x

z w

Page 304: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2- O problema de cobertura de vértices

Algoritmo de redução:

1º.Toma como entrada uma instância <G,κ> do problema do grupo exclusivo.

2º. Calcula G (em tempo polinomial)

3º. Saída: instância <G,|V|-κ> do problema de cobertura de vértices.

Essa transformação é uma redução:

- O grafo G tem um grupo exclusivo de tamanho κ sse o grafo G tem uma cobertura de vértices de tamanho |V|-κ.

Page 305: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

2- O problema de cobertura de vértices

G G v

y x

w z

v u u

y x

z w

Page 306: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- O problema de Ciclo Hamiltoniano NP-completo! Prova: 1- HAM-CYCLE ∈NP 2- VERTEX-COVER ≤p HAM-CYCLE 1- HAM-CYCLE ∈NP Dado G=(V,E), certificado: sequência de vértices |V| que forma o

ciclo hamiltoniano. Algoritmo de verificação: confere se essa sequência contém cada

vértice em V exatamente uma vez e se, com o primeiro vértice repetido no final, ela forma um ciclo em G verifica se existe uma aresta entre cada par de vértices consecutivos e entre o primeiro e o último vértice.

Tempo polinomial!

Page 307: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- O problema de Ciclo Hamiltoniano 2- VERTEX-COVER ≤p HAM-CYCLE Dado um grafo não orientado G=(V,E) e um inteiro κ, construímos

um grafo não orientado G’=(V’,E’) que tem um ciclo hamiltoniano sse G tem uma cobertura de vértices de tamanho κ.

Conceitos: Dispositivo: fragmento de um grafo. Para cada aresta (u,v) ∈ E, o grafo G’ que construímos conterá

uma cópia desse dispositivo, denotado por Wuv. Cada vértice em Wuv : [u,v,i] ou [v,u,i], onde 1≤i≤6, de forma que cada dispositivo Wuv contém 12 vértices e 14 arestas.

Em particular, apenas os vértices [u,v,1], [u,v,6], [v,u,1] e [v,u,6] terão arestas incidentes do lado de fora de Wuv.

Page 308: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- O problema de Ciclo Hamiltoniano 2- VERTEX-COVER ≤p HAM-CYCLE Exemplo: o dispositivo usado para reduzir o problema de cobertura de

vértices ao problema de ciclo hamiltoniano. Uma aresta (u,v) do grafo G corresponde ao dispositivo Wuv no grafo G’ criado na redução. (a) O dispositivo, com vértices individuais identificados. (b)-(d) Os caminhos sombreados são os únicos possíveis pelo dispositivo que incluem todos os vértices, supondo que as únicas conexões do dispositivo ao restante de G’ são realizadas pelos vértices [u,v,1], [u,v,6], [v,u,1] e [v,u,6].

Page 309: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- O problema de Ciclo Hamiltoniano 2- VERTEX-COVER ≤p HAM-CYCLE Redução de uma instância do problema de cobertura de vértices a uma

instância do problema de ciclo hamiltoniano. (a) Um grafo não orientado G com uma cobertura de vértices de tamanho 2, consistindo nos vértices levemente sombreados w e y. (b) O grafo não orientado G’ produzido pela redução, com o caminho hamiltoniano correspondendo à cobertura de vértices sombreada. A cobertura de vértices w,y correspondentes às arestas (s1,[w,x,1]) e (s2,[y,x,1]) que aparecem no ciclo hamiltoniano.

Page 310: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- O problema de Ciclo Hamiltoniano 2- VERTEX-COVER ≤p HAM-CYCLE

Os únicos vértices em V’ além daqueles de dispositivos são vértices seletores s1,s2,...,sk. Arestas incidentes em vértices seletores de G’ para selecionar os k vértices da cobertura.

Page 311: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- O problema de Ciclo Hamiltoniano Outros tipos de arestas: 1- para cada vértices u∈V, adiciona arestas para unir

pares de dispositivos, a fim de formar um caminho contendo todos os dispositivos que correspondem a arestas incidentes sobre u em G.

Ordena-se arbitrariamente os vértices adjacentes a cada vértice u∈V como u(1), u(2),..., u(grau(n)), onde (grau(u)) é o número de vértices adjacentes a u.

Cria-se um caminho em G’ passando por todos os dispositivos que correspondem a arestas incidentes em u adicionando as E’ as arestas ([w,x,6],)

Page 312: Análise de algoritmos · –Algoritmos gulosos –Modelagem em grafos •Complexidade: - problemas de decisão, - transformações polinomiais, - classes P, NP, Co-NP e NP-completo

3- O problema de Ciclo Hamiltoniano Outros tipos de arestas:

Continua..