Bienvenida

Programacion II

Una historia casi real:

Una pequeña empresa de ex-alumnos de Ingeniería Informática de la Uned ha desarrollado un sistema de visión artificial capaz de reconocer el rostro de una persona y determinar si coincide con alguno de los almacenados en una base datos. La máquina ha tenido muy buena aceptación como sistema de control de accesos (cerradura automática) y varias empresas lo han comprado. El algoritmo de comparación de caras se puede ejecutar, en principio, en un ordenador personal de gama baja. El tiempo que el sistema tarda en procesar una imagen depende del número de imágenes n almacenadas en la base de datos

Tras haber vendido varios sistemas a pequeñas empresas, varias medianas empresas y un gran hospital se han interesado por él y lo han comprado. Sin embargo, al poco tiempo se reciben quejas de éstas empresas en relación con el excesivo tiempo que requiere el proceso de reconocimiento.

Ante esas quejas, los desarrolladores realizan unas pruebas de velocidad de reconocimiento para distintos tamaños de base de datos, siempre ejecutando el programa de reconocimiento sobre el ordenador de gama baja mencionado. Los resultados son:

Es indudable que el tiempo de reconocimiento para base de datos de 100 imágenes o más es inaceptable, para un sistema con 200 personas con acceso autorizado cada persona ha de pasar más de seis minutos ante la cámara. Se dedice probar a sustituir el ordenador por uno con procesador Pentium y más memoria en lugar del humilde 386 original. Las pruebas con el nuevo ordenador arrojan los siguientes resultados:

El tiempo se ha reducido, sin embargo es de más de un minuto todavía para empresa de 200 personas, además si se prueba con una de 1000 el tiempo es de 2000 segundos (algo más de media hora), lo cual es claramente inaceptable.

Puesto que se desea poder vender el sistema a grandes organismos y empresas, los nuevos empresarios deciden aplicar los conocimientos aprendidos en Programación II y Programación III y tratar de desarrollar un algoritmo de reconocimiento más eficiente. Las pruebas sobre el ordenador de bajas prestaciones dan ahora el resultado:

Con este nuevo algoritmo el tiempo para 200 puede ser aceptable, todavía algo alto. Probando con el ordenador de gama alta se obtiene:

Los tiempos son ahora muy buenos. Deciden adoptar el nuevo algoritmo e instalar los ordenadores más potentes. Instalan su máquina en grandes empresas, hospitales, ministerios, ...

Moralejas

a) Ante un mal algoritmo el aumento de potencia del procesador no conduce a mejoras importantes, especialmente cuando el problema a tratar crece. El cambio de ordenador no consigue reducir el tiempo a un valor aceptable para n alto.

b) Un algoritmo mejorado produce buenos resultados incluso para procesador poco potente. El segundo algoritmo del ejemplo ha logrado colocar el tiempo en valores casi aceptables incluso para ordenador de poca potencia

c) Un algoritmo mejorado permite aprovechar mejor las ventajas de un procesador más potente de forma que es posible tratar en un tiempo de proceso inferior problemas más complejo. Supóngase que se limita el tiempo aceptable de reconocimiento en 3 segundos. Con el primer algoritmo, ordenador lento se tiene un n máximo aceptable de 17. Al pasar, con ese mismo algoritmo a ordenador rápido se tiene un n máximo de 39. Con el segundo algoritmo y ordenador lento n es 52 y pasa a valer 200 para ordenador rápido. Es decir, en el primer caso al cambiar de procesador se logra aumentar en un factor de poco más de dos el tamaño del problema tratable en un tiempo dado, en el segundo caso en un factor de casi cuatro.

Y ahora las áridas ecuaciones

El ingeniero usa las matemáticas fundamentalmente para comunicarse con los de su especie evitando largas parrafadas como las del apartado anterior. Lo explicado en el ejemplo puede traducirse a:

El primer algoritmo es de orden cuadrático, es decir, si f(n) es la función que determina el tiempo de ejecución en función del tamaño n de la base de datos se tiene que:, en concreto f(n)=0,01n² para el primer ordenador. Para el segundo ordenador f(n)= 0,002n². El segundo algoritmo es de orden n.log n. En concreto para el primer ordenador la función de coste es f(n)=0,01.n.lg n, y para el segundo 0,002.n.lg n.

Cuando se aprende el lenguaje matemático la economía de espacio para una explicación es evidente. Por todo ello se ha de realizar el esfuerzo mínimo necesario para comprender los conceptos matemáticos que permitan expresar ideas de forma simple y precisa. No se ha de caer en el extremo opuesto, es decir, usar las matemáticas de forma extensa, abusiva y aburrida sin que aporten nada especial a la comprensión básica del problema.

¿ Que és orden de complejidad de un algoritmo ?

El orden de complejidad de un algoritmo en cuanto a tiempo de ejecución es una expresión matemática que permite indicar cómo crece el tiempo de ejecución cuando crece el tamaño del problema que resuelve el algoritmo.

Se ha de insistir en dos puntos en esta definición:

• Es una indicación del crecimiento del tiempo de ejecución cuando crece el tamaño del problema. ¿ Qué es "tamaño de problema " ?. Infinidad de algoritmos resuelven problemas en los que el tiempo de resolución varía cuando, sin variar la esencia del propio algoritmo, si varía uno o varios parámetros que determinan el tamaño de los datos de entrada. Por ejemplo, en un algoritmo de ordenación que ordene los registros de una base de datos, o los elementos de un vector etc. el tiempo de ejecución crece cuando crece el número de registros o elementos a ordenar.

• Indica cómo crece el tiempo de ejecución. Cuando se habla de coste asintótico no se trata de expresar una medida absoluta del tiempo de ejecución del algoritmo. Se trata de expresar cómo varía el tiempo de ejecución cuando el tamaño del problema crece. Supóngase, por ejemplo, que un algoritmo de ordenación de vectores es de orden cuadrático. Es decir, que siendo f(n) el tiempo de ejecución necesario para ordenar n elementos del vector, se tiene . A partir de esta información no se puede determinar cuánto tiempo se tardará en ordenar un vector de tamaño dado. Pero sí se se puede decir que, cuando el tamaño n del vector a ordenar crece, el tiempo de ejecución crece cuadráticamente. Así si se nos dice que el tiempo necesario para ordenar un vector de 100 elementos es de 1 segundo se puede concluir que el tiempo necesario para ordenar uno de 1000 elementos será del orden de 100 segundos. Es decir, al multiplicar por 10 el tamaño del problema el tiempo se ejecución se multiplica por 10²

Se han de tener en cuenta otros factores al analizar el coste de ejecución de un algoritmo. El contenido de los datos de entrada influye también en el tiempo de ejecución de muchos algoritmos. Así, por ejemplo, el tiempo de ejecución de un algoritmo de ordenación de vectores puede ser muy distinto según el vector contenga datos ya ordenados, o casi ordenados, o no. En general, cuando se hable de coste asintótico, se refiere al caso de contenido de datos más desfavorable, es decir el caso peor.

En la asignatura se trata casi siempre el coste desde el punto de vista asintótico y para el caso peor. Esto no significa que, para problemas concretos, este tratamiento sea siempre el más adecuado y se ha de razonar con sentido común en casos como esos. Dos ejemplos ilustrarán esto:

1. Se dispone de dos algoritmos que tratan vectores de tamaño variable, determinado por un parámetro n, uno de coste f1(n)=0,001 n² y otro de coste f2(n)=0,1n. Los algoritmos se van a utilizar para tratar vectores de tamaño 50 o menor ¿ Cúal es el más apropiado ?. Desde el punto de vista de coste asintótico es evidente que el mejor algoritmo es el segundo, de coste lineal. Sin embargo para vectores de tamaño 50 se tiene que el coste del primer algoritmo es 2,5 y el del segundo 5. Luego para tamaño 50 o menor es preferible el primer algoritmo aunque su coste asintótico sea peor. En la figura adjunta puede comprobarse que el primer algoritmo es en realidad mejor para tamaño de problema menor de 100.

2. Un algoritmo de ordenación tiene coste cuadrático en el caso peor, sin embargo cuando se aplica sobre vectores ordenados el coste es lineal. Si al aplicarlo sobre un serie larga de vectores la probabilidad de que el vector sobre el que se aplica esté ya ordenado es muy alta, la función de coste asintótico para caso peor deja de ser útil. Es preferible utilizar una función de coste medio basada en la probabilidad de aplicación sobre vector ya ordenado.

Este apartado sólo ha pretendido servir de introducción al estudio de costes de ejecución desde un punto de vista práctico sirviendo de complemento al apartado 1.1 de Peña. En este apartado se exponen las ideas básicas a tener en cuenta en el análisis de coste:

• El análisis detallado (tal y como el realizado en el texto para el algoritmo de ordenación por el método de selección), es demasiado tedioso y costoso en tiempo ( a su vez) como para ser de aplicación práctica normal. Por ello se utiliza el estudio de coste asintótico aproximado.

• Los factores que influyen en el tiempo de ejecución de un algoritmo son: tamaño de los datos, contenido de los datos e implementación concreta del algoritmo (máquina y compilador)

• Se estudia normalmente el coste para caso peor

• Dos implementaciones diferentes del mismo algoritmo sólo diferirán en cuanto a tiempo de ejecución en una constante multiplicativa. En el ejemplo del inicio de esta página las dos implementaciones (sobre dos máquinas distintas) de cada uno de los algoritmos se diferencian en un factor de 5, es decir una máquina es 5 veces más rápida que la otra. Sin embargo esto no cambia el tipo (en cuanto a coste asintótico) de cada uno de los algoritmos.