Introduccion a los fundamentos de algoritmos

Apuntes Sobre Teoría de Algoritmos 1

CONCEPTOS BASICOS.

Una posible definición de algoritmo es un conjunto de reglas que permiten obtener un resultado determinado a partir de ciertas reglas definidas.

Otra definición sería, algoritmo es una secuencia finita de instrucciones, cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en untiempo finito. Ha de tener las siguientes características: Legible, correcto, modular, eficiente, estructurado, no ambiguo y a ser posible se ha de desarrollar en el menor tiempo posible.

Características de un algoritmo de computador:

Ser algoritmo: Tiene que consistir en una secuencia de instrucciones claras y finitas.

Ser correcto: El algoritmo ha de resolver el problema planteado entodas sus facetas.

Ser legible.

Ser eficiente: Es relativa porque depende de la maquinas en la que lo ejecutemos. Existen ejemplos de algoritmos eficientes que ocupan demasiado espacio para ser aplicados sin almacenamiento secundario lento, lo cual puede anular la eficiencia.

Un algoritmo eficiente pero complicado puede ser inapropiado porque posteriormente puede tener que darlemantenimiento otra persona distinta del escritor.


Eficiencia de los Algoritmos
Cuando tenemos que resolver un problema, es posible que estén disponibles varios algoritmos adecuados. Indudablemente deseamos el mejor, pero entonces ¿como podemos seleccionar el mejor? Si es un problema sencillo, cualquiera tal vez funcionaría sin inconvenientes, pero cuando el problema es más complejo entonces tendremosque solucionar de forma más cuidadosa el algoritmo a utilizar.

El enfoque empírico para seleccionar un algoritmo consiste en programar las técnicas e ir probando hasta obtener el algoritmo adecuado. Otro enfoque consiste en determinar matemáticamente la cantidad de recursos necesarios para cada uno de los algoritmos, como el tiempo de ejecuciones y el espacio de almacenamiento. El que seconsidera mas importantes corresponde al tiempo de computadora y cuando nos refiramos a eficiencia de un algoritmo, estaremos hablando de tiempo de ejecución.
Otros posibles recursos corresponden a (numero de procesadores en caso de que sea una aplicación que corra en paralelo, etc.)
Para medir la eficiencia de un algoritmo se debe tener en cuenta el caso o ejemplar (Un ejemplar corresponde a un datode entrada para el algoritmo, hay infinitos ejemplares y puede haber varios tipos dependiendo del limite o restricciones de la aplicación) que se vaya a suministrar como dato de entrada. El tamaño de un ejemplar se corresponde formalmente con el número de bits que se necesitan para representar el ejemplar en una computadora, utilizando algún esquema de codificación. Sin embargo el tamaño será unnúmero entero que mida el número de componentes de un ejemplar.

Otro enfoque para la selección de un algoritmo, consiste en el matemático. La ventaja de utilizar el enfoque matemático o teórico, consiste en que esta no depende ni del computador que se esté utilizando, ni del lenguaje de programación, ni siquiera de las habilidades del programador, y consiste en la formulación matemática de laeficiencia del algoritmo.

También resulta posible analizar los algoritmos utilizando un enfoque hibrido, en el cual la forma de la función que describe la eficiencia del algoritmo se determina matemáticamente y seguidamente se determinan empíricamente aquellos parámetros numéricos que sean específicos para un cierto programa. Empleando este enfoque se puede predecir el tiempo que necesitará unacierta implementación para resolver un ejemplar o caso mucho mayor de los que se hayan empleado en las pruebas.

Si se desea medir la cantidad de espacio que utiliza un algoritmo en función del tamaño de los ejemplares, está a disposición una unidad natural, EL BIT. Si deseamos medir la eficiencia de un algoritmo en función del tiempo que se necesita para llegar a una respuesta, entonces no...