Análisis de algoritmos

Capítulo 1

Análisis de Algoritmos

1.1 Objetivo Educacional

– Comprender el concepto de complejidad de los algoritmos y su aplicación en la selección de los mismos

1.2 Actividades de aprendizaje

– Evaluar la complejidad de algoritmos propuestos
– Determinar el mejor algoritmo en cuanto al tiempo de ejecución
– Determinar la complejidad de un algoritmo considerando complejidaden el espacio

1.3 Introducción

Las estructuras de datos son abstracciones que se usan para manejar grandes cantidades de información y las relaciones entre diferentes piezas de información. También mantienen una relación estrecha con la complejidad algorítmica – seleccionar una estructura de datos apropiada para un trabajo es crucial para escribir buen software.

Debido a que lasestructuras de datos son abstracciones de alto nivel, estas nos presentan operaciones en grupos de datos, tal como agregar un dato a una lista, o buscar el dato de prioridad más alta en una cola. Cuando una estructura de datos provee operaciones, podemos llamar a la estructura un tipo de dato abstracto (algunas veces abreviado como ADT por sus siglas en inglés o TDA en español). Un tipo de dato abstractopuede minimizar dependencias en el código, que es importante cuando el código necesita ser cambiado.

Los lenguajes de programación están equipados con un conjunto de tipos construidos, tales como los números enteros y de punto flotante que permiten trabajar con objetos de datos para los cuales el procesador de la computadora tiene un soporte nativo. Estos tipos construidos son abstracciones queel procesador actualmente provee porque los tipos construidos ocultan detalles acerca de su ejecución y limitaciones.

Por ejemplo, cuando se usa un número de punto flotante se está primeramente conciente de su valor y las operaciones que se pueden aplicar a ellos. Si se considera el cálculo de la longitud de la hipotenusa como:
c = sqrt(a * a + b * b)

Esta línea usa patrones comunes paracalcular los valores y acumular el resultado. De hecho, estos patrones son tan repetitivos que los lenguajes de alto nivel fueron creados para evitar esta redundancia y permitir a los programadores pensar acerca de qué valor fue calculado en lugar de cómo fue calculado.

Aquí están inmersos dos conceptos útiles y relacionados:

La abstracción que es cuando patrones comunes se agrupan juntos bajoun solo nombre y entonces se parametrizan con objeto de obtener un entendimiento de alto nivel de tal patrón. Por ejemplo, la operación de multiplicación requiere dos valores fuente y escribir el producto de esos dos valores en un destino dado. La operación se parametriza por las dos fuentes y el destino.

La encapsulación es un mecanismo para ocultar a los usuarios, los detalles deimplementación de una abstracción. Cuando se multiplican números, por ejemplo, no se necesita conocer la técnica usada por el procesador, sólo se necesitan conocer sus propiedades.

Cada estructura de datos puede ser concebida como una sola unidad que tiene un conjunto de valores y un conjunto de operaciones que pueden ser ejecutadas para acceder o cambiar esos valores.

1.4 Análisis de AlgoritmosPara procesar una gran cantidad de datos se utiliza una computadora y a través de un lenguaje de programación se establece un algoritmo de solución, que es un conjunto de instrucciones mediante las cuales se indica la forma de resolver un determinado problema.

Una vez que se ha determinado que el algoritmo es correcto, es necesario determinar la cantidad de recursos computacionales requeridospara tal efecto, como el tiempo de proceso y el espacio de memoria, además de que éste sea sencillo y claro, y por supuesto, que sea el óptimo, es decir, se necesita realizar un análisis del algoritmo.

Se analizan los algoritmos con la intención de mejorarlos, si es posible y de escoger uno de entre varios con los que se podría resolver un problema, utilizando los criterios mencionados de:...