Complejidad Computacional
Es la rama de las ciencias de la computación que estudia, de manera teórica, la optimización de recursos requeridos durante la ejecución de un algoritmo para resolver un problema
El análisis se basa en dos aspectos:
El tiempo: Periodo transcurrido entre el inicio y la finalización del algoritmo.
El espacio: La cantidad de memoria (la medida varia según la maquina) que necesita el algoritmo para su ejecución.
La complejidad computacional considera globalmente todos los posibles algoritmos para resolver un problema dado. Estamos en la distinción que existe entre los problemas que pueden ser resueltos por un algoritmo en tiempo polinomico (Es el tiempo ideal, cuando el tiempo de ejecución de un algoritmo es menor que un cierto valor calculado, obviamente usando una formula polinomial como por ejemplo logarítmicas, lineales, cuadráticas o cubicas, se dice que dicho problema se puede resolver en un tiempo polinomico) y los problemas para los cuales no conocemos ningún algoritmo polinomico, es decir el mejor no es polinomico. Los problemas matemáticos los podemos dividir en dos grupos:
Problemas indecidibles: Aquellos que no se pueden resolver mediante un algoritmo
Problemas decidibles: Aquellos que cuentan al menos con un algoritmo para su cómputo.
Sin embargo, un problema decidible puede no ser solucionado por un computador, porque el algoritmo requiere un número elevado de operaciones para resolverlo. Esto nos permite separar en dos los problemas decidibles.
Problemas Tratables: Son los problemas que cuentan con al menos una solución polinomial. Ejemplo: todos los algoritmos a los que se le ha podido estableces su tiempo de ejecución.
Problemas Intratables: Es intratable si no se puede ser resuelto por algún algoritmo eficiente, un problemas puede ser intratable por diferentes motivos.
• El problema requiere de una respuesta de longitud exponencial.
• El problema es decidible pero no se conocen algoritmo polinomiales que lo resuelvan
Esquema
Clasificación por su complejidad:
Problemas de menor a mayor complejidad:
Clase P: Los algoritmo de complejidad polinomica se dice que son tratables en el sentido de que suelen ser abordables en la práctica. Los problemas para los que se conocen algoritmos con esa complejidad se dice que forman la clase P
Ejemplo: Se utiliza en algoritmos matemáticos como logaritmos lineales, cuadráticos o cúbicos
Clase NP: La clase NP(N de no-determinista y P de polinomicos) son un conjunto de problemas que pueden ser resuelto en un tiempo polinomico por una maquina de turing no determinista
Ejemplo: Este tipo de complejidad esta presente en algoritmos como las torres de Hanoi o en el método de ordenamiento Shell.
Clase NP-Completo: Son problemas NP y son los peores problemas posibles de la clase NP, son de enorme complejidad. Se caracterizan por ser todos iguales. La clase NP-Completo se basa en el concepto de transformación lineal.
Ejemplo: El problema del viajero, ciclo hamiltoniano, sudoku.
El análisis se basa en dos aspectos:
El tiempo: Periodo transcurrido entre el inicio y la finalización del algoritmo.
El espacio: La cantidad de memoria (la medida varia según la maquina) que necesita el algoritmo para su ejecución.
La complejidad computacional considera globalmente todos los posibles algoritmos para resolver un problema dado. Estamos en la distinción que existe entre los problemas que pueden ser resueltos por un algoritmo en tiempo polinomico (Es el tiempo ideal, cuando el tiempo de ejecución de un algoritmo es menor que un cierto valor calculado, obviamente usando una formula polinomial como por ejemplo logarítmicas, lineales, cuadráticas o cubicas, se dice que dicho problema se puede resolver en un tiempo polinomico) y los problemas para los cuales no conocemos ningún algoritmo polinomico, es decir el mejor no es polinomico. Los problemas matemáticos los podemos dividir en dos grupos:
Problemas indecidibles: Aquellos que no se pueden resolver mediante un algoritmo
Problemas decidibles: Aquellos que cuentan al menos con un algoritmo para su cómputo.
Sin embargo, un problema decidible puede no ser solucionado por un computador, porque el algoritmo requiere un número elevado de operaciones para resolverlo. Esto nos permite separar en dos los problemas decidibles.
Problemas Tratables: Son los problemas que cuentan con al menos una solución polinomial. Ejemplo: todos los algoritmos a los que se le ha podido estableces su tiempo de ejecución.
Problemas Intratables: Es intratable si no se puede ser resuelto por algún algoritmo eficiente, un problemas puede ser intratable por diferentes motivos.
• El problema requiere de una respuesta de longitud exponencial.
• El problema es decidible pero no se conocen algoritmo polinomiales que lo resuelvan
Esquema
Clasificación por su complejidad:
Problemas de menor a mayor complejidad:
Clase P: Los algoritmo de complejidad polinomica se dice que son tratables en el sentido de que suelen ser abordables en la práctica. Los problemas para los que se conocen algoritmos con esa complejidad se dice que forman la clase P
Ejemplo: Se utiliza en algoritmos matemáticos como logaritmos lineales, cuadráticos o cúbicos
Clase NP: La clase NP(N de no-determinista y P de polinomicos) son un conjunto de problemas que pueden ser resuelto en un tiempo polinomico por una maquina de turing no determinista
Ejemplo: Este tipo de complejidad esta presente en algoritmos como las torres de Hanoi o en el método de ordenamiento Shell.
Clase NP-Completo: Son problemas NP y son los peores problemas posibles de la clase NP, son de enorme complejidad. Se caracterizan por ser todos iguales. La clase NP-Completo se basa en el concepto de transformación lineal.
Ejemplo: El problema del viajero, ciclo hamiltoniano, sudoku.
Comentarios
Publicar un comentario