Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

PROBLEMAS CLASES P, NP Y NP-COMPLETOS

No description

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of PROBLEMAS CLASES P, NP Y NP-COMPLETOS

Muchas Gracias!
Muchos de estos problemas pueden caracterizarse por el hecho de que puede aplicarse a un algoritmo polinómico para ser comprobados sus posibles soluciones, de esta forma se determina si es válida o invalida.
Por medio de esta característica podemos ejecutar un método de resolución no determinista, que consiste en aplicar heurísticos para obtener soluciones hipotéticas que se van desestimando aceptando al ritmo polinómico. Los problemas de esta clase se denominan NP (la N de no-deterministas y la P de polinómicos). Los problemas de la clase P son subconjunto de los de clase NP.
Los algoritmos de complejidad polinómica se dice que son tratables en el sentido de que suelen ser ejecutados en la práctica.

Los problemas que existen para los algoritmos con esta complejidad, se dicen que forman la clase P.

Aquellos problemas para los que la mejor solución que se conoce es de complejidad superior a la polinómica, se determinan que son problemas intratables.
EJEMPLO CASE P: Multiplicación matricial
Dadas dos matrices A y B de tamaño n x n, hallar C, el producto de las dos.

La solución del algoritmo seria:
CLASE NP-COMPLETO
Existen una amplia gama de problemas de tipo NP, de los cuales se destacan algunos de ellos de extrema complejidad.

Gráficamente se puede decir que algunos de estos problemas se
encuentran en la “frontera externa” de la clase NP. Son catalogados los peores problemas posibles de clase NP.
Estos problemas se caracterizan por ser “iguales” en el sentido de que si se descubriera una solución P para alguno de ellos, esta solución sería fácilmente aplicable a todos ellos.
EJEMPLO CLASE P-COMPLETO:
Algovidea - Vendedor Viajero
CLASE P
PROBLEMAS CLASES P, NP Y NP-COMPLETOS
Inteligencia Artificial
CLASE NP
EJEMPLO NP: Problema CLIQUE
Dado un grafo G y un entero k, ¿es posible encontrar un subgrafo de G completo de tamaño k?

¿Porque?

• Claramente CLIQUE pertenece a NP.
• Ahora deberemos hacer una reducción de SAT a NP.
• Supongamos que tenemos una fórmula en (FNC):

Ahora nombramos:
C1 v C2 v. .. v Ck con n variables proposicionales.

Formaremos un grafo G con un nodo por cada literal que aparece en cada cláusula. Cada nodo está etiquetado con el literal que le dio origen.Agregaremos un arco entre un nodo etiquetado con l y un nodo etiquetado con l0 si y solo si:

– l y l0 están en cláusulas distintas.

– l no es el literal complementario de l.
CLASE P
int i,j,k;
int A[n][n],B[n][n],C[n][n];

// Dar valores a A y B.

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
for(k=0;k<n;k++)
C[i][j]+=A[i][k]*B[k][j];
}
}
EJEMPLO CASE P:
Algoritmo Torre de Hanoi 5
EJEMPLO: CLASE NP
Método de Búsqueda Secuencial
By Manuel Fernando Marulanda
Full transcript