Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 67 vistas

    Clasificacion de Problemas

    Cargado por

    Jonathan Droop Castelo
    Este documento clasifica los problemas computacionales en diferentes categorías según su complejidad. Explica que los problemas indecidibles no tienen algoritmos para resolverlos, mientras que los decidibles se dividen en intratables, que solo admiten algoritmos exponenciales, y tratables, que tienen algoritmos razonables. Luego define los problemas polinomiales (P) como aquellos con algoritmos deterministas polinomiales y los no polinomiales (NP) como aquellos sin tales algoritmos. Finalmente, describe las clases P, NP y NP-completo, y explica que los problemas NP incluyen

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Clasificacion de Problemas

    Cargado por

    Jonathan Droop Castelo
    67 vistas3 páginas
    Este documento clasifica los problemas computacionales en diferentes categorías según su complejidad. Explica que los problemas indecidibles no tienen algoritmos para resolverlos, mientras que los decidibles se dividen en intratables, que solo admiten algoritmos exponenciales, y tratables, que tienen algoritmos razonables. Luego define los problemas polinomiales (P) como aquellos con algoritmos deterministas polinomiales y los no polinomiales (NP) como aquellos sin tales algoritmos. Finalmente, describe las clases P, NP y NP-completo, y explica que los problemas NP incluyen

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento clasifica los problemas computacionales en diferentes categorías según su complejidad. Explica que los problemas indecidibles no tienen algoritmos para resolverlos, mientras que los decidibles se dividen en intratables, que solo admiten algoritmos exponenciales, y tratables, que tienen algoritmos razonables. Luego define los problemas polinomiales (P) como aquellos con algoritmos deterministas polinomiales y los no polinomiales (NP) como aquellos sin tales algoritmos. Finalmente, describe las clases P, NP y NP-completo, y explica que los problemas NP incluyen

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    67 vistas3 páginas

    Clasificacion de Problemas

    Cargado por

    Jonathan Droop Castelo
    Este documento clasifica los problemas computacionales en diferentes categorías según su complejidad. Explica que los problemas indecidibles no tienen algoritmos para resolverlos, mientras que los decidibles se dividen en intratables, que solo admiten algoritmos exponenciales, y tratables, que tienen algoritmos razonables. Luego define los problemas polinomiales (P) como aquellos con algoritmos deterministas polinomiales y los no polinomiales (NP) como aquellos sin tales algoritmos. Finalmente, describe las clases P, NP y NP-completo, y explica que los problemas NP incluyen

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 3

    Universidad Autónoma de Aguascalientes

    Ingeniería en Computación Inteligente

    Centro de ciencias básicas

    Departamento de Ciencias de la Computación

    Materia: Teoría de la Complejidad computacional

    Clasificación de problemas

    Fecha de entrega: 21/04/20

    Alumno:

    Jonathan Edgardo Castelo López


    Clasificación de los problemas
    Problemas indecidibles: Son aquellos problemas que no poseen algoritmos capaces para
    resolverlos.

    Problemas decidibles: Son aquellos problemas que poseen algoritmos capaces para resolverlos.

    Estos problemas decidibles se dividen en dos: intratables y tratables.

    • Intratables: Son los problemas que solamente admiten como solución algoritmos cuya
    complejidad es super-polinómica (exponecial, por ejemplo).
    • Tratables: Son aquellos problemas en los que existe al menos un algoritmo capaz de
    resolverlo en un tiempo razonable.

    Problemas polinomiales y no-polinomiales


    • Un problema es polinomial (P) si existe un algoritmo determinístico polinomial que lo
    resuelva.
    • Un problema es no-polinomial (NP) si no existe un algoritmo determinístico polinomial que
    lo resuelva.

    Clasificación de problemas según su complejidad

    Clase P

    Es el conjunto de los problemas de decisión que son resueltos en una máquina determinística en un
    tiempo polinómico, lo que corresponde intuitivamente a problemas que pueden ser resueltos aún en
    el peor de sus casos.

    Por ejemplo tenemos a los algoritmos matemáticos como logaritmos, lineales, cuadráticos o
    cúbicos.

    Clase NP

    Es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina no
    determinística en un tiempo 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 un subconjunto de los de la clase NP.

    Por ejemplo, este tipo de complejidad está presente en algoritmos como las torres de hanói o en el
    método de ordenamiento shell.

    Clase NP-Completos

    Se puede decir que los problemas de NP-Completo son los problemas más difíciles de NP y muy
    probablemente no formen parte de la clase de complejidad de P. La teoría de NP-Completos se basa
    en el concepto de transformación polinomial.
    Por ejemplo, tenemos a un algoritmo de rompecabezas; se dispone de N (un cuadrado perfecto)
    piezas de un rompecabezas, cada una con figuras en los lados de formas y colores diferentes. Se
    trata de decidir si se pueden colocar las piezas en un cuadrado haciendo coincidir los colores y las
    figuras. Un algoritmo de fuerza bruta necesita probar (n)*n! combinaciones. No se conoce ningún
    algoritmo mejor.

    En conclusión podemos decir que los problemas de clase NP, que son los que se resuelven de forma
    polinómica incluyen como sub-conjunto a los problemas de clase P, a su vez tienen como sub
    conjunto los de clase NP-Completos, los cuales son también subconjunto de los de clase NP-
    complejos. Para visualizarlo de mejor manera, lo explico con un diagrama de Venn.

    También podría gustarte