Aula07

44 %
56 %
Information about Aula07
Education

Published on March 20, 2014

Author: yuripassos58

Source: slideshare.net

Description

Aula sobre intratabilidade

Intratabilidade Yuri tavares dos Passos

MT limitada por tempo ● Dada uma entrada de tamanho n. Uma MT que sempre pára dentro de T(n) movimentos é dita limitada por um tempo T(n). – Esta MT pode possuir múltiplas fitas. – Pode ser não determinística. ● O caso deteminístico e multifita corresponde a uma algoritmo de tempo de execução T(n).

A classe P ● Se uma MT determinística M é limitada por um tempo polinomial T(n), então dizemos que M é limitada por tempo polinomial. – T(n) = O(nk ), para um k constante. ● Assim, L(M) pertence a classe P. ● Quando falamos de P, não estamos falando de um algoritmo que roda em computador ou em uma MT.

Equivalência polinomial de computadores e MT ● Como foi discutido sobre a conversão entre MT multifita e computadores, vimos que uma algoritmo que roda em tempo O(T(n)) em um PC roda em tempo O([T(n)]2 ) em uma MT multifita. ● Se T(n) é um polinômio, [T(n)]2 também é.

Exemplos de problemas em P ● Dado uma sequência de números, ela está ordenada? ● Dado uma palavra w, ela pertence a uma gramática G? – Algoritmo CYK executa em tempo O(n3 ) ● Dado um grafo G, nós x e y, existe uma caminho de x a y? – Algoritmo de Djikstra executa em tempo O(n log n), para n nós.

Tempo de execução entre polinômios. ● O(n log n) não é um polinômio. ● Mas para pertencer a P, basta que seja limitada por um polinômio. ● O(n log n) < O(n2 )

A classe NP ● O tempo de execução de uma MT não-determinística é o número máximo de passos tamados ao longo de qualquer ramo. ● Se este tempo é limitado por um polinômio, então a MT não determinística é dita limitada por um tempo polinomial. ● Sua linguagem/problema é dito estar em uma classe NP.

Definição alternativa de NP ● A classe NP pode ser definida como a classe dos problemas que possuem um verificador que executa em tempo polinomial. ● Um verificador é um algoritmo que verifica se uma entrada w, de tamanho n, possui uma propriedade c. – Formalmente, um verificador V é um algoritmo que aceita <w,c>. – Assim, um problema A pode ser enunciado como: ● A = {w| V aceita <w,c> para alguma cadeia c} – A é NP se V executa em tempo polinomial.

Exemplo 1 ● Saber se um número x é composto, ou seja, existem dois números inteiros positivos maiores que 1, p e q, tais que x=pq. – COMPOSTO = {x| x=pq, para inteiros p,q > 1} ● Verificar se um x pertence a COMPOSTO pode ser feito em tempo polinomial. Basta fornecer x e um de seus divisores (p ou q). – V verificará a entrada <x,p>. ● Contudo, verificar se x pertence a COMPOSTO também pode ser feito em tempo polinomial em uma MT determinística.

Exemplo 2 ● Um caminho hamiltoniano em um grafo direcionado G é um caminho que passa por todos os nós de G somente uma vez. – CAMHAM = {<G,s,t> | G é um grafo direcionado com um caminho hamiltoniano de s para t}

Exemplo 2

Exemplo 2 ● Um verificador V para <G,s,t> seria utilizado junto com um caminho C. Assim a verificação seria apenas comparar se C é um caminho se s a t que passa somente uma vez em cada nó. – V verificaria a entrada <G,s,t,C>. ● CAMHAM é um problema que ainda não sabem se possui uma MT determinística que resolva em tempo polinomial.

P e NP ● Um dos problemas aberto da computação é: – P = NP? ● Há milhares de problemas que estão em NP, mas não parecem estar em P. ● Mas também não há provas de que não estejam em P.

Problemas completos ● Uma maneira de descobrir se P = NP é identificar os problemas completos para NP. ● Um problema é NP-completo se ele tem a propriedade de, caso pertencer a P, todos os problemas em NP também serão P. ● Esta definição é feita formalmente usando uma redução de tempo polinomial.

Problemas completos – intuição ● Um problema completo para uma classe engloba todo problema em uma classe, mesmo se ele não parece englobar. ● Verificar se uma expressão booleana, composta por E, OU e NÃO possui algum resultado verdadeiro engloba qualquer problema a respeito de MT.

Redução de tempo polinomial ● Semelhante as reduções feitas para descobrir a (in)decibilidade dos problemas. ● Mas agora com a restrição de levar um tempo polinomial para fazer as conversões entre cadeias. Conversão em tempo polinomialw x

Redução de tempo polinomial ● Objetivo: encontrar uma maneira de mostrar que o problema L é NP-completo reduzindo todo problema em NP para L de tal forma que se nós tivermos um algoritmo de tempo polinomial para MT determinísticas que decida L, então nós podemos construir um algoritmo de tempo polinomial para qualquer problema em NP.

Redução de tempo polinomial Redução de tempo polinomial NP Um problema NP-completo . . . . . . .. . . Um problema NP

Redução de tempo polinomial ● Precisamos da noção de um tradutor de tempo polinomial, ou seja, uma MT que: – Possui uma entrada de tamanho n. – Opera de modo determinístico em tempo polinomial p(n). – Produz uma saída uma fita separada, denominada fita de saída. ● O tamanho da saída e no máximo p(n).

Tradutor de tempo polinomial estado nentrada Fitas de rascunho Fita de saída < p(n) Lembre-se: requerimento importante é tempo < p(n).

Redução de tempo polinomial ● Considere L e M linguagens. ● Digamos que L seja redutível em tempo polinomial a M se existe um tradutor T tal que para toda entrada w de T, a saída x = T(w) pertence a M se e somente se w pertence a L.

Redução de tempo polinomial T w ∈ L w ∉ L x ∈ M x ∉ M

Problemas NP-completos ● Um problema/linguagem M é dito NP-completo se para toda linguagem L em NP, há uma redução de tempo polinomial de L para M. ● Propriedade fundamental: Se L é redutível a M em tempo polinomial e M possui um algoritmo de tempo polinomial, então L também tem um algoritmo de tempo polinomial.

Problemas NP-completos R S sim não Tradutor x w - Tradutor executa em tempo p(n) (polinômio) - R decide em tempo q(n) (polinômio) - S decide em tempo p(n) + q(n) (polinômio) - M = L(R) - L = L(S)

Problemas NP-completos Redução de tempo polinomial NP Um problema NP-completo . . . . . .. . Um problema NP . .

O plano NP SAT Todos os problemas NP se reduzem em tempo polinomial ao SAT, que é NP-completo 3- SAT SAT se reduz em tempo polinomial ao 3-SAT 3-SAT se reduz em tempo polinomial a muitos problemas que também são NP-completos

Próxima aula ● Veremos o problema SAT e porque ele é NP-completo.

NP-completude e heurísticas ● Na vida prática, quando encontramos problemas que são comprovadamente NP-completos, devemos: – Descobrir ou desenvolver heurísticas. – Reduzir o conjunto de entradas para adequar a realidade do problema real.

Referências ● HOPCROFT, John E.; ULLMAN, Jeffrey D.; MOTWANI, Rajeev. Introdução à teoria de autômatos, linguagens e computação. [Rio de Janeiro]: Campus, c2003. p. 328-352 ● SIPSER, Michael. Introdução à teoria da computação. 2ª Ed. Thomson. São Paulo. 2007. ● Traduzido e adaptado dos slides de Jeffrey D. Ullman.

Add a comment

Related presentations

Related pages

Game Development - # Aula07 - Atari and 2600 - YouTube

Hey folks? Today we begin our introductory course to the development of digital games, here in this course we will know a little history of ...
Read more

Aula07 - YouTube

Aula07 Valber Cunha. Subscribe Subscribed Unsubscribe 7 7. Loading... Loading... Working... Add to. Want to watch this again later?
Read more

Google

Advertising Programmes Business Solutions +Google About Google Google.com © 2016 - Privacy - Terms. Search; Images; Maps; Play; YouTube; News; Gmail ...
Read more

aula07 - MP3 Download, Play, Listen Songs - 4shared

aula07 - download at 4shared. aula07 is hosted at free file sharing service 4shared. Online file sharing and storage - 15 GB free web space. Easy registration.
Read more

Adm Fin Aula07 - administracao-financeira - 2 - Passei Direto

Baixe grátis o arquivo Adm Fin Aula07 enviado para a disciplina de administracao-financeira Categoria: Anotações - 2 - 969883
Read more

aula07 - Download - 4shared

aula07 - download at 4shared. aula07 is hosted at free file sharing service 4shared.
Read more

59925-Aula07 - scribd.com

59925-Aula07 - Download as Powerpoint Presentation (.ppt), PDF File (.pdf), Text File (.txt) or view presentation slides online.
Read more

Aula07 GQ on Vimeo

This is "Aula07 GQ" by on Vimeo, the home for high quality videos and the people who love them.
Read more