Recursividad

San Nicolás de los Garza, N.L. A 18 de marzo del 2012

INRODUCCIÓN ………………………………………………….…..…………………………………. 2

HISTORIA …………………………………………………………………………………………………. 3

OPTIMIZACIÓN Y DESICIÓN …………………………………………………………………… 4

PROBLEMA DE SATISFACTIBILIDAD …………………………………………………………. 5

ALGORITMOS NO DETERMINISTAS ………………………………………………………..6

PROBLEMAS P Y NP ………………………………………………………………………………… 7

NP COMPLETITUD ………………………………………………………………………………... 8

NP COMPLETITUD PARTE 2 …………………………………………………………………… 9

CONCLUSIONES ……………………………………………………………………………………. 10

BIBLIOGRAFÍA ……………………………………………………………………………………. 11INTRODUCCIÓN

* La complejidad computacional estudia la “dificultad” inherente de problemas de importancia teórica y/o práctica. El esfuerzo necesario para resolver un problema de forma eficiente puede variar enormemente. Un problema muy complejo se denomina “NP-completo”, lo cual básicamente significa que es imposible encontrar un algoritmo eficiente para encontrar una solución óptima.

*Probar que un problema es “NP-completo” es muy importante puesto que permite abandonar un callejón sin salida (encontrar un algoritmo para la solución óptima) para centrarse en objetivos realizables (encontrar algoritmos para obtener soluciones aproximadas). El objetivo fundamental de la teoría de la complejidad computacional es facilitar el avance en aquellas áreas en las que es posible.

* Laciencia de la computación es un cuerpo sistematizado del conocimiento concerniente al cálculo, que se sostiene en dos áreas fundamentales: La Teoría de la Computabilidad, basada en las ideas y los modelos fundamentales subyacentes al cálculo, y las técnicas de la ingeniería para el diseño de algoritmos. La Teoría de la Complejidad computacional estudia los recursos requeridos para resolver unproblema como son el tiempo y el espacio; por su parte la teoría de la computabilidad se interesa en expresar los problemas como algoritmos sin tener en cuenta la información sobre los recursos necesarios para ello.

2
HISTORIA

* La ciencia de la Computación es el cuerpo sistematizado del conocimiento concerniente al cálculo. Sus principios se remontan al diseño de algoritmos porparte de Euclides, al uso de la complejidad asintótica y la reducibilidad por parte de los babilónicos. La ciencia de la Computación se sustenta en dos áreas básicas: los conceptos fundamentales al cálculo que trajo como consecuencia la existencia de funciones probablemente no calculables o computables, y por otra parte, las técnicas de ingeniería para el diseño de sistemas de computación basadasen técnicas de diseño de algoritmos: algoritmos voraces, algoritmos aleatorizados, algoritmos con retroceso, etc.

* Un proceso computacional, también llamado proceso algorítmico o algoritmo, es fundamental para la ciencia de la Computación, puesto que un computador no puede ejecutar un problema que no tenga una solución algorítmica. Así, cualquier limitación de las capacidades de losprocesos computacionales constituye también una limitación de las capacidades de la computadora. Evaluar la eficiencia de los algoritmos tiene mucho que vercon evaluar la complejidad de los mismos.

* Aunque esta labor pueda resultar ardua, compensa el hecho de obtener programas con alta garantía de corrección y la satisfacción intelectual de haberlos construido bien desde el principio, sinesperar el veredicto del sistema computacional. Sin embargo, el tema que nos aborda es establecer si una función es calculable o computable, soslayando las especificaciones de un sistema computacional especifico.

3
Complejidad computacional. Optimización y decisión

* Dentro de la evolución de la teoría de complejidad, se han encontrado problemas con características similares,...