complejidad computacional

Modelo Funcional y Teoría de Algoritmos

Unidad III: Introducción a la Complejidad Computacional

Objetivos:

Comprender el significado de la complejidad computacional de un algoritmo mediante el estudio de estrategias de análisis de eficiencia y eficacia y la puesta en práctica de las mismas.

Explicar la teoría fundamental de la complejidad algorítmica basándose en definiciones yplanteamientos matemáticos así como en el estudio de notaciones de complejidad y medidas empíricas de rendimiento y comportamiento en algoritmos.

Analizar los conceptos de eficiencia en tiempo y espacio por medio de su aplicación en algoritmos comparativos que resuelvan un mismo problema.

Explicar los conceptos teóricos requeridos para distinguir entre los problemas posibles de resolver pormedios computacionales de aquellos problemas para los cuales no existe solución algorítmica práctica.

Comprender la complejidad de algoritmos recursivos e iterativos mediante la aplicación de técnicas inductivas y deductivas para análisis y diseño de algoritmos recursivos e iterativos.



La Teoría de la complejidad computacional es la parte de la teoría de la computación que estudia losrecursos requeridos durante el cálculo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (número de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (cantidad de memoria utilizada para resolver un problema).


COMPLEJIDAD COMPUTACIONAL: Indica el esfuerzo que hay que realizar para aplicar un algoritmo y lo costoso que éste resulta.




Lateoría de la complejidad defiere de la teoría de la computabilidad en que esta última se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello. Hoy en día las máquinas resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problemay su tiempo de ejecución es polinómica.

Estos son problemas agrupados en el conjunto P. Los problemas con coste factorial o combinatorio están agrupados en NP. Estos problemas no tienen una solución algorítmica, es decir, una máquina no puede resolverlos en un tiempo razonable.

Marco Histórico
Un algoritmo es un conjunto de operaciones y procedimientos que deben seguirse para resolver unproblema. La palabra algoritmo se deriva del nombre latinizado del gran Matemático Árabe Mohamed Al Khowarizmi, el cual escribió sobre los años 800 y 825 su obra “Quitad Al Mugabala”, donde se recogía el sistema de numeración hindú y el concepto del cero. Fue Fibonacci, el que tradujo la obra al latín y el inició con la frase: Algoritmi Dicit. El lenguaje algorítmico es aquel por medio del cual serealiza un análisis previo del problema a resolver para encontrar un método que permita resolverlo. Al conjunto de todas las operaciones a realizar y el orden en que se deben efectuar, se le denomina algoritmo. Es un método para resolver un problema mediante una serie de datos precisos, definidos y finitos.
Generalidades
El programador de computadoras es antes que nada una persona que resuelveproblemas, por lo que para llegar a ser un programador eficaz se necesita aprender a resolver problemas de un modo riguroso y sistemático. A la metodología necesaria para resolver problemas mediante programas se denomina Metodología de la Programación. El eje central de esta metodología es el concepto, ya tratado, de algoritmo.
Un algoritmo es un método para resolver un problema. Aunque lapopularización del término ha llegado con el advenimiento de la era informática, algoritmo proviene de Mohamed Al−Khowarizmi, matemático persa que vivió durante el siglo IX y alcanzo gran reputación por el enunciado de las reglas para sumar, restar, multiplicar y dividir números decimales.
Euclides, el gran matemático griego (del siglo IV antes de Cristo) que inventó un método para encontrar el...