Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Introducción a la NP_Completitud




Enviado por Pablo Turmero



Partes: 1, 2

    Monografias.com

    Ineficiencia e Intratabilidad
    Problemas algorítmicos para los que no existe una solución satisfactoria

    Ejemplos
    Torres de Hanoi
    Puzzle del mono

    Monografias.com

    Torres de Hanoi
    Dadas tres estacas y N anillos, secuencia de movimientos para transferir los anillos de una a otra siguiendo ciertas reglas
    El procedimiento recursivo implica un movimiento de aro y dos llamadas recursivas

    Monografias.com

    ¿Cuántos movimientos son necesarios?
    2N-1
    Si fuéramos capaces de mover un millón de anillos cada segundo, para N=64. ¿cuánto tiempo tardaríamos?
    Medio millón de años
    Torres de Hanoi

    Monografias.com

    El puzzle del mono
    Nos limitamos a problemas de decisión
    N cartas, N=M*M, con orientación fija, ¿existe alguna combinación que forme un cuadrado de M*M en el que todas las mitades estén casadas?

    Monografias.com

    El puzzle del mono
    Con N=25 y un computador capaz de construir y evaluar un millón de posibilidades por segundo. Cuanto tiempo tardaría el algoritmo en el caso peor?
    Para colocar la primera, 25 posibilidades, para la segunda 24, …. 25!, resultaría que nuestro computador tardaría 490 billones de años en calcular todas las posibilidades

    Monografias.com

    El puzzle del mono
    Existen conjuntos de cartas para los que la solución siempre existe, para otros nunca.
    ¿Existe una manera mejor de resolver el problema?
    Probablemente no, pero no estamos seguros

    Monografias.com

    Tiempo razonable/irrazonable
    N
    Función
    Polinomial
    Exponencial
    El número de protones en el universo tiene 79 dígitos. El número de microsegundos desde el “Big Bang” tiene 24 dígitos

    Monografias.com

    Admiten algoritmos razonables
    No admiten algoritmos razonables
    (Gp:) Problemas intratables
    (Gp:) Problemas
    tratables

    Tiempo razonable/irrazonable
    Una función polinomial en N es aquella que esta limitada por Nk, para algún k.
    Un algoritmo cuyo tiempo de ejecución esta acotado por una función polinomial lo consideramos razonable. En otro caso irrazonable.
    En términos de problemas algorítmicos diremos que son problemas tratables o intratables

    Monografias.com

    Problemas NP_Completos
    El problema del puzzle, que hemos visto, es realmente un problema intratable?

    Quizá es cuestión de esperar que lo computadores sean mas rápidos
    Puede ser causa de nuestra incompetencia para idear buenos algoritmos?
    No tiene valor el esfuerzo, este problema es un problema especifico, no es importante.

    Monografias.com

    Problemas NP_Completos
    Existen cerca de 1000 problemas algorítmicos con características parecidas
    Sus limites inferiores son lineales y sus limites superiores exponenciales.
    La clasificación de estos problemas es desconocida no sabemos a que lado de la línea están.
    Vamos a denotar esta clase como NPC, significando NP-completos.

    Monografias.com

    Problemas NP_completos
    Problemas de encontrar caminos
    Problema del viajante de comercio: El viajante tiene que visitar N ciudades, hallar el camino mas corto que conecta todas ellas sin que se visite dos veces la misma ciudad.

    Monografias.com

    Problemas NP_completos
    El problema del ciclo Hamiltoniano: dado un grafo, existe un camino que pase por todos los puntos exactamente una vez?

    Partes: 1, 2

    Página siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter