Complejidad Computacional

Realice una síntesis de las dos lecturas sobre complejidad computacional y al final redacte una conclusión sobre el tema.

La complejidad computacional estudia la “dificultad” inherente deproblemas 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 cualbá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.

- ¿Qué es un algoritmo?

Una definición informal (no se considera aquí una definición formal, aunque existe): conjunto finito de reglas que dan una secuencia de operaciones para resolver todos los problemas de un tipo dado. De forma más sencilla, podemos decir que un algoritmo es un conjunto de pasos que nos permite obtener un dato.

- Clasificación de algoritmos

* Algoritmo determinista: en cada paso del algoritmo se determina de forma única el siguiente paso.

* Algoritmo no determinista: deben decidir en cada paso de la ejecución entre varias alternativas y agotarlas todas antes de encontrar la solución.

- Notación O-grande

En general, el tiempo de ejecución es proporcional, esto es, multiplica por una constante a alguno de los tiempos de ejecución anteriormente propuestos, además de la suma de algunos términos más pequeños. Así, un algoritmo cuyo tiempo de ejecución sea T = 3N2 + 6N se puede considerar proporcional a N2. En este caso se diría que el algoritmo es del orden de N2, y se escribe O(N2)

Los grafos definidos por matriz de adyacencia ocupan un espacio O(N2), siendo N el número de vértices de éste.

- Clasificación de problemas

Los problemas matemáticos se pueden dividir en primera instancia 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.

...