of 22/22
Projeto e Análise de Algoritmos Tempo polinomial Verificação de tempo polinomial Diane Castonguay [email protected] Instituto de Informática Universidade Federal de Goiás

Projeto e Análise de Algoritmos - inf.ufg.brdiane/PAA/2006/AULA2006/VerificacaoPolinomial.pdf · Projeto e Análise de Algoritmos Tempo polinomial Verificação de tempo polinomial

  • View
    214

  • Download
    0

Embed Size (px)

Text of Projeto e Análise de Algoritmos - inf.ufg.brdiane/PAA/2006/AULA2006/VerificacaoPolinomial.pdf ·...

  • ProjetoeAnlisedeAlgoritmos

    TempopolinomialVerificaodetempopolinomial

    [email protected]

    InstitutodeInformticaUniversidadeFederaldeGois

  • Tempopolinomial

    Umalgoritmoeficienteseeledecomplexidadepolinomial

    notamanhodaentrada.

    Ideiatamanhodaentrada:n

    Complexidadedoalgoritmo:O(na)

  • Algoritmodeprimalidade

    Primo(n)1.m SqrtInteiro(n) //m=sqrt(n)2.parad 2atm faa3. senmodd=04. entoretornannoprimo5. fimse6.fimpara7.retornanprimo

    Paraumasoluomelhor:http://www.educ.fc.ul.pt/icm/icm98/icm12/Algoritmos.htm

  • ComplexidadedoalgoritmoPrimo

    O(n1/2),masoalgoritmoPrimonoeficiente!

    Porque???

    Paraimplementarumnumerointeirousaseobinario,istoquerdizerqueotamanhodaentrada (lgn)enon.

    n1/2=(2lgn)1/2=(2)lgnexponencialemlgn!

  • Algoritmoderaizquadradainteira

    /*m=sqrt(n) ,n>1*/SqrtInteiro(n)1.m 12.enquanto(m+1)*(m+1)nfaa3. m m+14.fimenquanto5.retorna

    Paraumasoluomelhor:http://www2.fundao.pro.br/articles.asp?cod=151

  • Exemplodealgoritmoseficientes

    Vimosvariosexemplosaolongodadisciplina.

    Hproblemaspelosquaisvimosalgoritmosnoficientes

    eassuassolueseficientes.

    Umexemploosproblemasqueresolvemoscomaprogramaodinmica.

  • Problemaversusalgoritmo

    Tendoumproblemaeumalgoritmoqueoresolve,seoalgoritmonoeficiente,istoquerdizerque

    noexisteumalgoritmoeficientequeresolvaoproblema?

    CLAROQUENO!!!

  • Tiposdeproblemas

    DECISOExisteumaestruturaSquesatisfaaumapropriedadeP?

    RESPOSTA:SIMouNO

    LOCALIZAOEncontrarumaestruturaSquesatisfaaumapropriedadeP.

    RESPOSTA:umaestruturaS

    OPTIMIZAOEncontrarumaestruturaSquesatisfaaumapropriedadeP

    equesejamelhorsegundoalgumcritrioCdemedida.RESPOSTA:umaestruturaStalquenohajaoutramelhor

  • DefinitiondeCLIQUE

    SejaG=(V,E)umgrafonoorientado.UmacliqueV'umsubconjuntodevrticesdeG(V' V )

    talqueparacadapardevrticesu,vV'temosumaaretsa(u,v)emG(i.e(u,v) E).

    OtamanhodeumacliqueV'aquantiadevrticesemV'.

  • Tiposdeproblemas:CLIQUE

    DECISODadoumgrafoGnoorientado.

    existeumacliquedetamanhomaiorouigualak?

    LOCALIZAODadoumgrafoGnoorientado.

    Encontreumacliquedetamanhomaiorouigualak.

    OPTIMIZAODadoumgrafoGnoorientado.

    Encontreumacliquedemaoirtamanho.

  • DefiniodoProblemadocaixeiroviajante

    SejaG=(V,E)umgrafoorientadocompeso.

    Umpercursoumciclosimplesquepassaporcadaverticedografo.

    Opesodopercursoasomadospesosdasarestasdociclo.

  • Tipodeproblemasdocaixeiroviajante

    DECISODadoumgrafoGorientadocompeso.

    existeumpercursodepesomenorouigualak?

    LOCALIZAODadoumgrafoGorientadocompeso.

    Encontreumpercursodepesomenorouigualak.

    OPTIMIZAODadoumgrafoGorientadocompeso.Encontreumpercursodemenorpeso.

  • CLASSEP

    UmproblemapertenceaclasseP(polinomial)seexisteumalgoritmoeficientequeoresolva.

    Paramostrarqueumproblemapolinomialprecisaexibirumalgoritmoqueoresolva

    emtempopolinomial(notamanhodaentrada)

    ParamostarqueumproblemaNOpolinomialprecisamostrarquenenhumalgoritmodecomplexidade

    polinomialpossaresolvelo.

  • CERTIFICADOALGORITMODEVERIFICAO

    Vamosnosconcentraremproblemasdedeciso.Muitosproblemasdedecisopodemserresolvidoatravs

    deumcertificado.

    UmcertificadoumaestruturaSquesatisfazapropriedadeP.

    UmalgoritmodeverificaoumalgoritmoqueprovaseumaestruturaSsatisfazapropriedadeP.

  • VerificaodeumcertificadoCLIQUE

    ECLIQUE(G,V')1.parau,v V'faa2. se(u,v) E3. entoretornaFALSE4. fimse5.fimpara6.retornaTRUE

    PodemosimplementarestealgoritmoparasejaO(V2).

  • CLASSENP

    UmproblemadedecisopertenceaclasseNP(nondeterministicpolinomial)searespostasimdoproblema

    temcertificadopolinomial.

    Isto:temumalgoritmodeverificaopolinomialdapropriedadePporumcertificadodadoS.

  • Exemplo

    CLIQUENP

    SATNP

    P NP

  • Exemplo:SAT

    Entrada:umafrmulabooleanaComposio:

    variaveisbooleanasconectivosbooleanos

    (AND), ( OR),(NOT),(implicao), (Seesomentese)

    parnteses

    ProblemasrelacionadosaSATCIRCUITSAT,CNFSAT,3CNFSATFNC=formanormalconjunta: (de )

    3FNC=formanormalconjuntade3: (3de )

  • Problemadedeciso:SAT

    Dadoumafrmulabooleana,elecapazdesatisfao?

  • SATNP

    ParamostrarqueSATpertenceaNPmostramosqueumcertificado

    (i.eumaatribuiosatisfatriaparaaformuladeentrada)podeserverificadoemtempopolinomial.

    Oalgoritmodeverificaosimplesmentesubsituicadavarivel

    nafrmulaporseuvalorcorrespondente,eentoavaliaaexpresso.

    Essatarefarealizvelemtempopolinomial.Seaexpressotemovalor1,

    afrmulacapazdesatisfao.

  • CLASSEcoNP

    UmproblemadedecisopertenceaclassecoNPsearespostanodoproblema

    temcertificadopolinomial.

  • Ograndequestionamento!

    P=NP???