Slides de Aula unidade II

Prévia do material em texto

Unidade II
ASPECTOS TEÓRICOS
DA COMPUTAÇÃO
Profa. Miryam de Moraes
Introdução
 Decidibilidade é o estudo das 
propriedades exibidas pelas linguagens 
com o objetivo de determinar a 
existência ou não de um algoritmo
capaz de aceitar ou rejeitar, em tempo 
e espaço finitos uma cadeia qualquere espaço finitos, uma cadeia qualquer 
apresentada para análise.
 Não basta um problema ser decidível.
Há que se considerar os custos 
dessa solução.
 Custos dizem respeito ao tempo total de 
execução e ao volume total de memória 
para se chegar à solução do problema.
Complexidade computacional
 Complexidade: “estudo das propriedades 
exibidas pelas linguagens com o 
objetivo de determinar o custo de seu 
processamento, em termos do tempo e 
espaço finitos” (RAMOS, VEGA e NETO, 2009).
“A complexidade de tempo de uma 
computação mede a quantidade de trabalho 
gasto pela computação” (ROSA, J. L. G.).
Wellington- 10
Realce
Estudo comparativo da
grandeza de algumas funções
n log2(n) n*log2(n) n2 n3 2n
1 0 0 1 1 2
10 3.32 33 100 1000 1024
100 6 64 664 104 106 1 268 x1030100 6.64 664 104 106 1, 268 x1030
1000 9.97 9970 106 109 1, 072 x 10301
Complexidade de tempo
 Seja MT uma Máquina de Turing 
determinística.
 “A complexidade de tempo (tempo de 
execução) é a função f:  tal que 
f(n) é o número máximo de transições 
processadas por uma computação de 
MT quando iniciada com uma cadeia 
de entrada de comprimento n, 
independentemente de MT aceitar 
ou não.” (ROSA, J. L. G.)
 Assume-se que a computação termina 
para toda a cadeia de entrada.
A notação  – grande 
 Sejam f, g R+, diz-se que f(n) = 
O(g(n)), se existirem números inteiros e 
positivos c e n0 tais que:
n, n  n0, f(n) < c. g(n)
 A notação  é utilizada para dar umA notação  é utilizada para dar um 
limite assintótico superior sobre uma 
função, dentro de um fator constante.
A notação  – grande 
 Seja f(n) = n e g(n) = n2. Tem-se que n = 
O(n2). De fato, n2  n e, portanto, f(n) é 
O(n2), com constantes c = 1 e n0  0.
 Seja f(n) = (n + 2)2 f(n) é (n2) com c = 5: Seja f(n) = (n + 2) , f(n) é (n ), com c = 5:
n2 + 4n + 4  5 n2, para n  2
Operações com a notação 
f(n) = O(f(n))
c x f(n), c 
constante
= O(f(n))
O(f(n)) + O(f(n)) = O(f(n))
O(O(f(n)) = O(f(n))
O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
O(f(n)) . O(g(n)) = O(f(n) . g(n))
f(n) . O(g(n)) = O(f(n) . g(n))
Máquina de Turing de k fitas
 Teorema: seja L uma linguagem aceita por 
uma Máquina de Turing determinística de 
k fitas M com complexidade de tempo f(n). 
Então L é aceita por uma Máquina de 
Turing padrão de uma fita com 
complexidade de tempo  (f(n)2)complexidade de tempo  (f(n)2).
 Observe-se que a eliminação de fitas 
adicionais (de k fitas para 1 fita) 
transforma o tempo de execução para 
no máximo uma potência de 2.
Não determinismo
 Definição: seja uma Máquina de Turing 
não determinística. A complexidade de 
tempo de M é a função f :  tal que 
f(n) é o número máximo de transições 
processadas por uma computação de M, 
empregando qualquer escolha deempregando qualquer escolha de 
transições quando iniciada com uma 
cadeia de entrada de comprimento n.
 Deve-se considerar todas as computações 
possíveis para uma cadeia de entrada! 
Wellington- 10
Realce
Algumas considerações
 Cálculos em uma Máquina de Turing
em tempo exponencial são bastante 
ineficientes e, portanto, raramente 
apresentam utilidade.
 Problemas para os quais não existe 
um algoritmo em tempo polinomial 
são ditos intratáveis.
 A teoria da complexidade classifica os 
problemas decidíveis em tratáveis e 
intratáveis.
Wellington- 10
Realce
Wellington- 10
Realce
Wellington- 10
Realce
Interatividade
Assinale a alternativa correta:
a) Todo problema decidível apresenta 
solução (n).
b) Todo problema decidível apresenta 
solução com complexidade computacionalsolução com complexidade computacional 
polinomial.
c) Toda Máquina de Turing com n  1 fitas 
pode ser reduzida a uma Máquina de 
Turing padrão.
d) A eliminação de fitas adicionais de umad) A eliminação de fitas adicionais de uma 
MT não transforma o tempo de execução.
e) Todo problema decidível apresenta 
solução O(n!).
Wellington- 10
Realce
A classe P
 Uma Linguagem L é denominada 
polinomialmente decidível se existe 
uma Máquina de Turing determinística
polinomial que a decide.
 Uma Máquina de Turing (MT) é 
denominada polinomial se a máquina 
sempre para, qualquer que seja a entrada 
x de comprimento n, após p(n) transições. 
 p(n) é uma função polinomial do 
comprimento n da cadeia de entrada.
Wellington- 10
Realce
Wellington- 10
Realce
A classe P
 P é a união de todos os conjuntos de 
linguagens decidíveis por uma Máquina 
de Turing em tempo limitado por um 
polinômio de grau d.
 Todo algoritmo prático/eficiente pode 
ser reduzido a uma Máquina de Turing 
limitada em tempo polinomial.
 São exemplos:
 Caminho de Euler;
 Problema da Satisfabilidade Booleana Problema da Satisfabilidade Booleana 
SAT 2.
Wellington- 10
Realce
Wellington- 10
Realce
Caminho de Euler (Gersting, J.)
 Dado um grafo G, existe algum caminho 
em G que use todas as arestas 
exatamente uma vez?
 Teorema: existe um Caminho de Euler 
em um grafo conexo se, e somente se, 
não existem nós ímpares ou existem 
exatamente dois nós ímpares. No caso 
em que não existem dois nós ímpares, o 
caminho pode iniciar em qualquer nó e 
terminar aí; no caso de dois nós ímpares, 
o caminho precisa começar em um deleso caminho precisa começar em um deles 
e terminar no outro.
 Solução polinomial.
Wellington- 10
Realce
Wellington- 10
Realce
Caminho de Euler (Gersting, J.)
 Inspeciona-se a matriz de adjacência e 
calcula-se para cada linha i o grau do 
nó i, simplesmente, efetuando-se:
grau = grau + A[i, j]. 
 Ao final, verifica-se se o grau daquele
nó (linha) é ímpar. Se for, incrementa-se 
o total de nós ímpares.
 Naturalmente, se o total (de nós ímpares) 
for 0 ou 2, então existe o Caminho 
de Euler.
 Em uma matriz n  n, devem ser 
inspecionadas n linhas. 
 O algoritmo O(n2) é o pior caso.
Wellington- 10
Realce
Satisfabilidade booleana
 Uma fórmula booleana é composta por 
variáveis e operações booleanas.
 Literal: variável booleana ou variável 
booleana negada.
 Cláusula: fórmula booleana compostaCláusula: fórmula booleana composta 
por literais e a operação “OU”.
 Fórmula normal conjuntiva: composta 
por cláusulas conectadas pelo 
operador “E”.
 2SAT: instâncias do problema da 2SAT: instâncias do problema da 
satisfabilidade booleana apresentam 
2 ou menos literais em cada cláusula, 
na sua forma normal conjuntiva.
Satisfabilidade booleana – 2SAT
 Exemplo:
 O problema da satisfabilidade-2 
pertence à classe P.
 Exemplo de solução:
 Atribui se um valor “True” para a Atribui-se um valor “True” para a 
primeira literal da primeira cláusula;
 nas cláusulas que se sucedem, 
sempre que ocorrer esta literal, o 
valor recém-atribuído é substituído;
 após o O(n) etapas, em que n é o 
número de cláusulas, a 
satisfabilidade é decidida.
Wellington- 10
Realce
Alcançabilidade
 Linguagens codificam problemas.
 Um problema é um conjunto de entradas, 
tipicamente infinito e uma questão 
do tipo sim/não arguida para cada 
entrada (propriedade que a entrada
pode ter ou não).
 Problema da alcançabilidade: dado um 
grafo direcionado G  V  V, em que V = 
{v1, v2, ...,vn} é um conjunto finito, e dois 
vértices vi, vjV, existe um caminho vij
para vj em G?
 Solução com desempenho O(n3).
Wellington- 10
Realce
Wellington- 10
Realce
Circuito hamiltoniano Dado um grafo G, existe um circuito que 
passe por todos os nós de G exatamente 
uma vez.
 O único algoritmo conhecido para este 
problema consiste em examinar todas 
as permutações possíveis dos nós e, 
para cada permutação, verificar se 
se trata de um circuito hamiltoniano. 
 Trata-se, portanto, de um problema O(n!).
Wellington- 10
Realce
Problema do caixeiro viajante
 Um caixeiro viajante, partindo de sua 
cidade, deve visitar exatamente uma 
única vez cada cidade de uma dada 
lista de cidades e retornar para casa 
de modo que a distância total percorrida 
seja a menor possívelseja a menor possível. 
 Este problema tem inúmeras aplicações 
práticas, como minimização de rotas de 
veículos, sequenciamento de atividades, 
entre outros.
 Há que se fazer uma pesquisa exaustiva 
sobre o espaço de busca.
 Trata-se de um problema cuja 
solução é O(n!).
Wellington- 10
Realce
Wellington- 10
Realce
Problemas de otimização
“São problemas cujas soluções possuem 
melhor ‘custo’ (determinado por uma 
função de custo) entre um conjunto de 
possíveis soluções” (RAMOS, M. V., 2012).
 Problema do caixeiro viajante: dado um 
inteiro n  2, uma matriz n x n cujos 
elementos dij representam a distância 
entre os nós i e j e seja um inteiro B tal 
que B  0, encontrar uma permutação a 
partir do conjunto  {1, 2, ..., n} tal que:
c( ) = d (1) (2) + d (2) (3) + ... + d (n) (1)
e c()  B
Wellington- 10
Realce
Wellington- 10
Realce
Interatividade 
Assinale a alternativa que apresenta um 
problema cuja solução é polinomial.
a) A rota mais longa para se visitar 
n cidades de uma região.
b) A rota mais curta para se visitarb) A rota mais curta para se visitar 
n cidades de uma região.
c) A pior alocação de processos à memória 
de um sistema computacional.
d) A alocação ótima de processos ao 
microprocessadormicroprocessador. 
e) Cálculo dos zeros de um polinômio 
quadrático.
Wellington- 10
Realce
A classe NP
 NP é o conjunto de todas as linguagens 
que são decidíveis em tempo polinomial 
p(n) em MT não determinísticas.
 Prova-se que: sendo L uma linguagem 
aceita em tempo p(n) por uma Máquina 
de Turing não determinística, então 
existirá uma Máquina de Turing 
determinística que: decide L em tempo 
r (n**d)., com r, d > 0.
 P  NP. 
 Mas... P = NP?
Wellington- 10
Realce
A classe NP (RAMOS, M. V.)
“Um verificador para uma linguagem L é um 
algoritmo V tal que: L = {w | V aceita (w,c) 
para alguma cadeia c}”. 
 Um verificador não encontra uma 
solução, apenas analisa uma possível 
solução gerada a priori e diz se se trata 
realmente de uma solução ou não. 
 Uma linguagem é polinomialmente
verificável se existe para esta um 
verificador de tempo polinomial.
 NP é a classe das linguagens que têm 
verificadores de tempo polinomial.
Wellington- 10
Realce
Wellington- 10
Realce
Aplicações de grafos
 A classe NP contém muitos problemas 
de interesse prático.
 São exemplos de aplicações de grafos:
 o diagrama Entidade – Relacionamento 
é um grafo;é um grafo;
 um mapa de estradas, ruas etc. é um 
grafo;
 rede de computadores é um grafo;
 redes neurais;
 fluxograma;
 circuito digital etc.
Wellington- 10
Realce
Wellington- 10
Realce
Wellington- 10
Realce
Redução
 O Princípio da Redução consiste 
basicamente na construção de um 
algoritmo de mapeamento entre as 
linguagens que traduzem os problemas.
 Se a classe de uma dessas linguagens é 
conhecida, então pode-se estabelecer 
algumas conclusões sobre a linguagem 
que se deseja investigar.
 Os problemas NP apresentados 
anteriormente são NP – completos, pois 
têm a seguinte propriedade de 
completude: todos os problemas em NP 
podem ser reduzidos àqueles via 
reduções polinomiais.
Wellington- 10
Realce
Redução
 Sejam dois problemas A e B e as 
correspondentes linguagens LA e LB.
Uma máquina de Redução R de LA
para LB (sobre um alfabeto A) é tal 
que (w  A):
a) Se w  LA. Então R(w)  LB.
b) Se w  LA. Então R(w)  LB.
 Uma função f: A*  A* é denominada 
função computável em tempo polinomial 
se existe uma MT com limitaçãose existe uma MT com limitação 
polinomial que efetue sua computação. 
Redução polinomial de L1 para L2
 Sejam duas linguagens L1, L2  A*.
 Uma função computável em tempo 
polinomial r: A*  A* é denominada 
redução polinomial de L1 para L2 se 
para cada x  A* for válido: x  L1, 
se e somente se r(x)  L2.
 Se r1 é uma redução polinomial de L1 para 
L2 e r2 é uma redução polinomial de L2
para L3, então sua composição r1 o r2 é 
uma redução polinomial de L1 para L3.
 Lewis e Papadimitriou apresentam o 
seguinte exemplo de redução: 
ciclo hamiltoniano para 
satisfabilidade booleana.
Redução polinomial
 Problema da mochila: dado um conjunto 
S = {a1, a2, ..., an} de números inteiros 
não negativos, representados em binário 
e um inteiro K, existe um subconjunto 
P  S tal que a soma de todos os 
elementos de P resulte igual a K?elementos de P resulte igual a K?
 Problema de escalonamento para duas 
máquinas: sejam duas máquinas que 
têm a mesma velocidade, cada tarefa 
pode ser executada em qualquer 
máquina e não há restrições em ordenarmáquina e não há restrições em ordenar 
as tarefas a serem executadas. Dados os 
tempos de execução a1, a2, ..., an e um 
prazo D. (continua)
Redução polinomial
 Problema de escalonamento para duas 
máquinas (continuação): tem-se ainda 
que todos os valores são codificados 
em binários. Pergunta-se se é possível 
alocar as tarefas às máquinas de forma
a cumprir o prazo Da cumprir o prazo D.
 Lewis e Papadimitriou apresentam a 
redução polinomial de problema da 
mochila para o problema da partição e do 
problema da partição para o 
escalonamento de duas máquinasescalonamento de duas máquinas.
Interatividade
Assinale a alternativa incorreta.
a) Em um problema de decisão, o objetivo 
é decidir a resposta sim ou não a 
uma questão. 
b) Se existe uma máquina de reduçãob) Se existe uma máquina de redução 
de LA para LB (sobre um alfabeto ), 
então LB = LA.
c) Linguagens codificam problemas.
d) É possível reduzir o problema do ciclo 
hamiltoniano para o da satisfabilidadehamiltoniano para o da satisfabilidade
booleana.
e) A classe NP contém muitos problemas 
de interesse prático.
Problemas NP – difíceis 
e NP – completos
Um problema B é NP – difícil se a 
seguinte condição for verificada:
  L  NP – existe uma redução de tempo 
polinomial de L para B. 
 A classe de problemas NP – completosA classe de problemas NP completos 
é um subconjunto de problemas NP
relacionados com a complexidade 
de todos os problemas NP.
 Definição: uma linguagem L  A* 
é denominada NP – completa seé denominada NP completa se 
e somente se L  NP e para toda 
linguagem L’  NP existe uma 
redução polinomial de L’ para L.
Problemas NP – completos
 Teorema de Cook: o problema da 
satisfabilidade é NP – completo.
 Teorema: a satisfabilidade-3 é um 
problema NP – completo.
 Problema MAX SAT: dado um conjunto FProblema MAX SAT: dado um conjunto F 
de cláusulas e um inteiro K, existe uma 
atribuição verdadeira que satisfaça pelo 
menos K, destas cláusulas?
 Teorema: MAX SAT é NP – completo.
 São também problemas NP completos: São também problemas NP – completos:
 clique, ciclo hamiltoniano, ciclo 
hamiltoniano não direcionado, 
problema do caixeiro viajante.
Problemas NP – completos
 São problemas NP – completos: 
 problema dos conjuntos 
independentes;
 problema do clique;
 problema da cobertura dos nós; problema da cobertura dos nós;
 problema da mochila;
 problema da partição;
 problema de escalonamento em duas 
máquinas.q
P= NP?
 Trata-se de um dos maiores problemas 
da Ciência da Computação.
 P  NP, pois toda linguagem que pode 
ser decidida em uma MT determinística, 
pode também ser decidida por uma MT 
não determinística.
 Teorema: seja L uma linguagem NP –
completa. P = NP se e somente se L  P.
 Resta saber se NP  P, ou seja, se:
P = NPP = NP.
Estratégias para lidar com 
problemas NP – completos
 Lewis e Papadimitriou apresentam as 
seguintes estratégias para “enfrentar” 
problemas considerados NP –
completos:
 considerar casos particulares;
 empregar algoritmos de aproximação;
 utilizar backtracking e ramificação 
limitada;
 efetuar melhoras locais.
Algoritmos de aproximação
 Considere-se que P seja um problema de 
otimização NP – completo.
 Seja x a entrada deste problema e opt(x) 
represente a solução ótima.
 Seja A um algoritmo de tempo polinomialSeja A um algoritmo de tempo polinomial 
para P e que A(x) seja uma solução não 
ótima produzida para a entrada x.
 Se A satisfaz a desigualdade abaixo, 
para algum valor de ε, para todas as 
instâncias x do problema.instâncias x do problema.
A: algoritmo de aproximação ε. 
Interatividade 
Assinale a alternativa correta:
a) Verificar se uma dada fórmula booleana 
cujas cláusulas apresentam apenas 2 
literais é “satisfazível”, não é um 
problema NP.
b) É possível demonstrar que P  NP e 
NP  P.
c) Não se sabe se P = NP.
d) Se P é diferente de NP, então existem 
problemas na classe P que são NPproblemas na classe P que são NP –
completos.
e) O algoritmo para a busca em uma árvore 
binária é NP – completo.
ATÉ A PRÓXIMA!