TRABAJO DE INVESTIGACIÓN DE LA TEORIA DE LA COMPLEJIDAD COMPUTACIONAL
Enviado por sdasdassdasdasdd • 7 de Octubre de 2022 • Informes • 4.883 Palabras (20 Páginas) • 35 Visitas
INSTITUTO DE EDUCACIÓN TEGNOLOGICO PRIVADO
“GUILLERMO ALMENARA MARTINS”
ESCUELA DE TECNICA DE ENFERMERIA
TRABAJO DE INVESTIGACIÓN DE LA TEORIA DE LA COMPLEJIDAD COMPUTACIONAL [pic 1]
PRESENTADO POR:
CURSO:
DOCENTE:
CICLO:
DEDICATORIA
A mis padres
A nuestros padres por facilitarnos las herramientas necesarias para poder seguir aprendiendo e investigando como estudiantes en esta carrera técnica
Agradecimiento
A nuestro docente Nilo Henry Calderón Copaja
Por todos los conocimientos brindados en esta unidad , además de su dedicación y esmero para compartir con sus alumnos los saberes necesarios
INDICE
1 HISTORIA 2
2 PROBLEMAS, ALGORITMOS Y COMPLEJIDAD 3
2.1 Problema computacional 3
2.2 Problemas de decisión 4
2.3 Algoritmos 4
2.4 Algoritmos de tiempo polinómico y problemas intratables 5
3 CLASES DE COMPLEJIDAD 6
3.1 Definiendo clases de complejidad 6
3.2 Máquinas de Turing deterministas y la clase P 6
3.3 Computación no determinista y la clase NP 7
3.4 Clases de complejidad importantes 8
4 LA PREGUNTA P=NP 9
5 NP-COMPLETITUD 10
5.1 Reducción Polinomial 10
5.2 Problemas NP-completos 11
5.3 Importancia de la NP-Completitud 11
6 HACIENDO FRENTE A PROBLEMAS NP 12
7 VÉASE TAMBIÉN 13
7.1 Reducción (complejidad) 13
7.2 Teorema de Cook 13
7.3 Lista de 21 problemas NP-completos de Karp 14
7.4 Complejidad de Kolmogórov 15
INTRODUCIÓN
La Teoría de la Complejidad Computacional es precisamente la rama de las Matemáticas Computacionales que se dedica al estudio y clasificación de los problemas según su dificultad. Ahora bien, ¿qué entendemos por dificultad? Es evidente que necesitamos una definición formal si queremos trabajar desde un punto de vista matemático, y esta definición debe ser lo más satisfactoria posible, en el sentido de que debe respetar nuestra intuición: si en la realidad tenemos un problema que la mayoría de nosotros diríamos que es más difícil que otro, entonces también debe serlo según la definición formal.
Analicemos entonces lo que entendemos por un problema difícil. Si olvidamos el indeterminismo y asumimos que para todos los problemas existe un algoritmo que los resuelve , tenemos que ver cuál es la diferencia entre un “buen” algoritmo y un algoritmo irrealizable, pues ya hemos dicho que marcarán la dificultad de los respectivos problemas, el algoritmo consistente en generar todas las posibles cadenas de símbolos de un alfabeto de forma progresiva (es decir, comenzamos con todas las posibles cadenas de longitud 1, luego construimos a partir de estas las de longitud 2 y así sucesivamente) y comprobar en cada paso si es la demostración de un teorema es irrealizable principalmente por un motivo: el número de posibles cadenas aumenta exponencialmente con su longitud.
HISTORIA
Antes de cualquier estudio de Complejidad Computacional, varios investigadores establecieron la base de esta teoría. Una de las contribuciones más influyentes fue la definición de 1936 de la máquina de Turing, un concepto poderoso y versátil de la computadora. Cuando se desarrollaron las computadoras en las décadas de 1940 y 1950, las máquinas de Turing se convirtieron en el modelo teórico exacto para la computación.
Sin embargo, pronto se descubrió que el modelo básico de la máquina de Turing no lograba determinar el tiempo y la memoria requeridos por las computadoras, lo cual es un problema grave hoy y más. La idea de medir el tiempo y el espacio en función de la longitud de entrada se originó a principios de la década de 1960 por Hartmanis y Stearns, y así nació la teoría de la complejidad computacional. Inicialmente, los investigadores intentaron comprender las nuevas medidas de complejidad y su relación entre sí. En 1965, Edmonds definió un "buen" algoritmo como un algoritmo con un tiempo de ejecución polinomial finito, es decir, con un tiempo de ejecución polinomial. Esto da lugar a uno de los conceptos más importantes en la teoría de la complejidad computacional: la integridad de NP y su pregunta fundamental, si P = NP. El campo comenzó a desarrollarse cuando los investigadores estadounidenses independientes Stephen Cook y Leonid Levin de la Unión Soviética demostraron que había problemas involucrados que todavía estaban llenos de NP. En 1972, Richard Karp llevó esta idea un paso más allá, mostrando que 21 problemas de combinatoria y teoría de grafos, que se caracterizan por la imposibilidad, son NP completos. Comprender los diferentes modelos computacionales que ya existen. En la década de 1980 hubo una proliferación de modelos finitos, que analizan el proceso computacional de una manera inherente diferente. Ha surgido un nuevo enfoque de problemas como P = NP, y aunque estos modelos tienen limitaciones para separar categorías complejas, este enfoque ha introducido técnicas combinatorias que permiten una mejor comprensión de las limitaciones de estos modelos.
Ya en la década de 1990, se estudiaron nuevos modelos de computadora, como las computadoras cuánticas, donde la misma tarea puede tener una complejidad diferente en la computación clásica y cuántica. Sin embargo, existen algunas limitaciones, incluido el desarrollo de hardware para este modelo y el hecho de que se requiere una cantidad significativa de espacio para los cálculos.
Figura
[pic 2]
Imagen Nº1 MÁQUINA DE TURING
Interpretación : Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador.
...