complejidad computacional
Páginas: 5 (1138 palabras)
Publicado: 30 de noviembre de 2014
Universidad Autónoma de
Nuevo León
Facultad de Ingeniería Mecánica y Eléctrica
Estructura de datos
Complejidad computacional
Cd. Universitaria a 9 de Marzo del 2012.
Índice:
Introducción…………………………………………………………………………………………3Desarrollo…………………………………………………………………………………………….4
Optimización y decisión…………………………………………………………………………5
Problemas P y NP………………………………………………………………………………….5
Problema de satisfactibilidad………………………………………………………………….6
Introducción:
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 por parte de Euclides, al uso de la complejidad asintótica y la deducibilidad por parte de losbabilónicos.
La ciencia de la Computación se sustenta en dos áreas básicas: los conceptos fundamentales subyacentes 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 basadas en técnicas de diseño de algoritmos: algoritmos voraces (divide y vencerás),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 los procesos computacionales constituye también una limitación de lascapacidades de la computadora.
Evaluar la eficiencia de los algoritmos tiene mucho que ver con 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, sin esperar el veredicto del sistema computacional.
El tema de lacomputabilidad tiene mucho que ver con la búsqueda de las estructuras que se requieren en un lenguaje de programación, de tal forma que se asegure que un programa expresado en dicho lenguaje pueda resolver cualquier problema que tenga una solución algorítmica.
Desarrollo:
La Teoría de la Complejidad Computacional es la parte de la teoría de la computación que estudia los recursosrequeridos durante el cálculo para resolver un problema. Un cálculo resulta complejo si es difícil de realizar.
Podemos definir la complejidad de cálculo como la cantidad de recursos necesarios para efectuar un cálculo. Así, un cálculo difícil requerirá más recursos que uno de menor dificultad. Los recursos comúnmente estudiados son el tiempo (número de pasos de ejecución de un algoritmo pararesolver un problema) y el espacio (cantidad de memoria utilizada para resolver un problema).
Un algoritmo que resuelve un problema pero que tarda mucho en hacerlo, difícilmente será de utilidad. Igualmente un algoritmo que necesite un gigabyte de memoria no será probablemente utilizado. A estos recursos se les puede añadir otros, tales como el número de procesadores necesarios para resolver elproblema en paralelo. Si un cálculo requiere más tiempo que otro decimos que es más complejo y lo llamamos complejidad temporal. Por otro lado, si un cálculo requiere más espacio de almacenamiento que otro decimos que es más complejo, en este caso hablamos de una complejidad espacial. Es claro que el tiempo que se requiere para efectuar un cálculo en un computador moderno es menor que el requeridopara hacer el mismo cálculo con las máquinas de las década pasadas, y seguramente que el tiempo en una máquina de la próxima generación será mucho menor.
El estudio de los procesos computacionales, conduce a una clasificación de los problemas en dos grandes clases: los problemas con solución y los problemas sin solución.
Los...
Universidad Autónoma de
Nuevo León
Facultad de Ingeniería Mecánica y Eléctrica
Estructura de datos
Complejidad computacional
Cd. Universitaria a 9 de Marzo del 2012.
Índice:
Introducción…………………………………………………………………………………………3Desarrollo…………………………………………………………………………………………….4
Optimización y decisión…………………………………………………………………………5
Problemas P y NP………………………………………………………………………………….5
Problema de satisfactibilidad………………………………………………………………….6
Introducción:
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 por parte de Euclides, al uso de la complejidad asintótica y la deducibilidad por parte de losbabilónicos.
La ciencia de la Computación se sustenta en dos áreas básicas: los conceptos fundamentales subyacentes 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 basadas en técnicas de diseño de algoritmos: algoritmos voraces (divide y vencerás),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 los procesos computacionales constituye también una limitación de lascapacidades de la computadora.
Evaluar la eficiencia de los algoritmos tiene mucho que ver con 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, sin esperar el veredicto del sistema computacional.
El tema de lacomputabilidad tiene mucho que ver con la búsqueda de las estructuras que se requieren en un lenguaje de programación, de tal forma que se asegure que un programa expresado en dicho lenguaje pueda resolver cualquier problema que tenga una solución algorítmica.
Desarrollo:
La Teoría de la Complejidad Computacional es la parte de la teoría de la computación que estudia los recursosrequeridos durante el cálculo para resolver un problema. Un cálculo resulta complejo si es difícil de realizar.
Podemos definir la complejidad de cálculo como la cantidad de recursos necesarios para efectuar un cálculo. Así, un cálculo difícil requerirá más recursos que uno de menor dificultad. Los recursos comúnmente estudiados son el tiempo (número de pasos de ejecución de un algoritmo pararesolver un problema) y el espacio (cantidad de memoria utilizada para resolver un problema).
Un algoritmo que resuelve un problema pero que tarda mucho en hacerlo, difícilmente será de utilidad. Igualmente un algoritmo que necesite un gigabyte de memoria no será probablemente utilizado. A estos recursos se les puede añadir otros, tales como el número de procesadores necesarios para resolver elproblema en paralelo. Si un cálculo requiere más tiempo que otro decimos que es más complejo y lo llamamos complejidad temporal. Por otro lado, si un cálculo requiere más espacio de almacenamiento que otro decimos que es más complejo, en este caso hablamos de una complejidad espacial. Es claro que el tiempo que se requiere para efectuar un cálculo en un computador moderno es menor que el requeridopara hacer el mismo cálculo con las máquinas de las década pasadas, y seguramente que el tiempo en una máquina de la próxima generación será mucho menor.
El estudio de los procesos computacionales, conduce a una clasificación de los problemas en dos grandes clases: los problemas con solución y los problemas sin solución.
Los...
Leer documento completo
Regístrate para leer el documento completo.