4. Análisis asintótico de algoritmos

INTRODUCCIÓN

Algoritmo:

Conjunto de reglas para resolver un problema. Su ejecución requiere unos recursos.

Un algoritmo es mejor cuantos menos recursos consuma, su facilidad de programarlo, corto, fácil de entender, robusto, etc.

Eficiencia: Relación entre los recursos consumidos y los productos conseguidos.

Recursos consumidos:

• Tiempo de ejecución.
• Memoria principal.
• Entradas/salidas a disco. 
• Comunicaciones, procesadores, etc.

Lo que se consigue:

• Resolver un problema de forma exacta, forma aproximada o algunos casos.

Ejemplo: Calcular la media de una matriz de NxM.

Contenido de los datos de entrada.

• Mejor caso. El contenido favorece una rápida ejecución.
• Peor caso. La ejecución más lenta posible.
• Caso promedio. Media de todos los posibles contenidos.

Los factores externos no aportan información sobre el algoritmo.

• Conclusión: Estudiar la variación del tiempo y la memoria necesitada por un algoritmo respecto al tamaño de la entrada y a los posibles casos, de forma aproximada (y parametrizada) no aportan información sobre el algoritmo.

El rendimiento o complejidad está ligado únicamente al algoritmo. En ningún momento con la velocidad del computador o con las facilidades de eficiencia que presenta un lenguaje de programación, ni con el estilo hábil del programador.

Para calcular este rendimiento se tiene en cuenta dos pasos principales:

1. Caracterizar las operaciones básicas del algoritmo. Operaciones básicas constituyen el trabajo realizado para resolver el problema.

2. Debe considerarse sobre quien va a recaer la operación. Se considera entonces los datos (tamaño y configuración).

El análisis computacional de un problema requiere:

         a) Una medida de esfuerzo (operaciones básicas)

         b) Una medida del tamaño (sobre quién va a recaer el esfuerzo)

En base a esto, se pueden clasificar los problemas que se someten al computador para ser solucionados desde el punto de vista del tamaño y del esfuerzo.

Clasificación según el tamaño:

     a. búsqueda, hallar un valor X en una entrada, tal que X satisface la condición Y;

     b. Estructuración, transformar la entrada para que satisfaga la propiedad Y;

     c. Construcción, construir X para que satisfaga la propiedad Y;

     d. optimización, encontrar XC que satisfaga la mejor propiedad Y;

     e. Decisión, decidir si la entrada satisface la propiedad Y;

     f. Adaptativos, mantener la propiedad Y a través del tiempo.

Clasificación según el esfuerzo:

    a. Conceptualmente difíciles, no hay algoritmo asociado por que no se comprende el problema cabalmente;

    b. Analíticamente difíciles, existe algoritmo para resolver el problema pero no se sabe analizar cuanto tiempo tomará solucionar cada instancia;

    c. Computacionalmente difíciles, hay algoritmos y se sabe analizar, pero el análisis indica que instancia relativamente pequeñas tomarán millones de años resolverla;

    d. Computacionalmente imposible, se ha demostrado que no existe algoritmo alguno para hallar la solución del problema.

Análisis de Algoritmos

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.

Intento de caracterizar el algoritmo en términos de la cantidad de computación y memoria que se necesita para resolver un problema.

La moneda tiene dos caras: La dificultad del problema y la eficiencia del algoritmo en resolverlo.

Algoritmos y problemas

• Cada algoritmo resuelve a un problema particular.
• Hay varias maneras de resolver un problema.
• Algunas maneras son buenas y otras son malas.
• El propósito del análisis de algoritmos es identificar los algoritmos buenos.

Calidad de algoritmos

Tiempo total de computación

• Número de operaciones realizadas por el algoritmo.
• Número de transiciones tomadas por la máquina turingque ejecuta el algoritmo.

Cantidad de memoria utilizada

• Número y tamaño de las variables
• Posición extrema a la derecha que se llega a visitar en la cinta de la Máquina Turingdurante la ejecución.

Operaciones básicas

Cuando el algoritmo está expresado en pseudocódigo, no lo vamos a convertir en una máquina Turing.

Buscamos contar la cantidad de las operaciones básicas que contiene el algoritmo.

• Aritmética simple
• Lógica simple
• Comparaciones simples
• Asignaciones simples
• Saltos

Fuente:

• http://es.wikipedia.org/wiki/Algoritmo
• Presentacion en PowerPoint "2.-FUNDAMENTOS DE LA COMPLEJIDAD COMPUTACIONAL", Autor: M.C. Blanca Idalia Martinez Cavazos 
• http://es.wikipedia.org/wiki/An%C3%A1lisis_de_algoritmos