DE CERVEZAS y otras cosas: Cosas que SÍ se dan en Informática

Ya sabemos que Aitor es informático. Lo explicábamos en este post, donde también vimos qué cosas no hace un informático. Entre lo que aprende un informático y lo que la gente espera que sepa un informático hay enorme vacío, que sólo se puede llenar con muchos fascículos "La informática es fácil" y revistas "MAXimiza TODO TU PC".

Hay informáticos, compañeros de carera, que a la pregunta: qué ordenador tienes responden, uno blanco. Hay informáticos que se quejan de que escriben su contraseña y sólo aparecen asteriscos. Hay doctores que no saben qué es UNIX y dan clases de seguridad en UNIX (de estos hay al menos uno).

Si no nos enseñan a formatear un disco duro, ni a configurar una tarjeta de video ni a hacer páginas web... ¿qué nos enseñan en la carrera?.

Con este post iniciamos una apasionante a la par que didáctica serie:

Cosas que SÍ se dan en Informática

Capítulo 1. Ordenando longanizas.

Aitor me sugiere un problema clásico de la algoritmia para comenzar. Algoritmia es, para nosotros, el arte de resolver problemas paso a paso. El problema, que se estudia en primero de carrera, consiste en ordenar un vector. Un vector no es más que una longaniza de números, que se sitúan consecutivamente en memoria. En inglés se llaman arrays y en Sudamérica lo apañan y los llaman arreglos. He aquí una gloriosa representación de un vector: 4 7 2 43 14 1. Y éste es el mismo vector ordenado: 1 2 4 7 14 43. No parece difícil hacerlo y, de hecho, no lo es. Ahora veamos cómo le decimos a un computador que lo haga.

Un computador dispone de una serie de operaciones -instrucciones-. Entre éstas, saber si un número es mayor que otro, sumar, restar... y poco más, al fin y al cabo. Y una restricción que me invento yo: no puede conocer el valor de más de dos posiciones del vector en la misma operación, es decir, en el mismo instante. Si los computadores tuviesen una instrucción para comparar hasta un millón de números, ordenar vectores sería más sencillo. Pero como no la hay, restringimos a dos los números a comparar y nos las ingeniamos, que la tecnología es cara y los ingenieros baratos.

Veamos cómo lo hacemos. Cogemos los dos primeros números y los comparamos. Si el segundo es menor que el primero, los intercambiamos. En nuestro caso no sería necesario pues 4 es menor que 7. Damos un pasito y realizamos la misma operación. Ahora sí que se cumple nuestra condición e intercambiamos el 7 con el 2. Por tanto, en el siguiente paso compararemos otra vez el 7 con el 43. No cambiamos, damos un pasito, e intercambiamos 43 y 14. Un pasito e intercambiamos 43 con 1. De este modo hemos llegado al final del vector (hemos iterado sobre el vector una vez) y tenemos una cosa como ésta: 4 2 7 14 1 43. Y, como no hemos acabado... ¡empezamos otra vez!

Pero ahora... ¿hace falta llegar al final?. Pues no, porque con este método nos hemos asegurado de arrastrar al elemento más grande hasta el final. Así que cada vez que hagamos una iteración podemos acabar un elemento antes. Tras la segunda iteración, nuestro vector será así: 2 4 7 1 14 43. El 14 ya esta en su lugar. Luego 2 4 1 7 14 43 -> 2 1 4 7 14 43 -> 1 2 4 7 14 43. Hemos hecho tantas iteraciones como elementos del vector menos uno.

Algo tan tonto tenía que tener nombre. Este sistema se llama Bubble Sort. Me dijeron que se llamaba así porque veías cómo los elementos más grandes (burbujas) subían rápidamente hacia arriba. A lo largo de esta fascinante serie veremos cómo los informáticos tenemos mala pata para poner nombre a las cosas.

Un momento... ¿hemos acabado?. Hombre, pues, sí, el vector está ordenado. Pero un informático no sería un ingeniero si se contentase con esto, no señor, ni mucho menos. Vale, tenemos un método para ordenar vectores, pero... ¿es el mejor método posible sobre el mundo mundial para ordenar siempre toda clase de vectores?.

Lo mejor varía según quien considere el problema. Los informáticos atendemos a dos variables para evaluar lo buena que es una solución algorítmica: el tiempo que lleve completarla y el espacio que necesitemos en memoria para resolver el problema (costes temporal y espacial). Un empresario también evalúa en función del tiempo y coste: el tiempo en que tiene que tener listo el producto (o urgencia) y lo que le cueste el informático.

Los costes se determinan, normalmente, en función de la entrada. Los costes constantes no se suelen considerar. Si un algoritmo requiere siempre trescientos segundos para resolver cualquier problema (independientemente de la complejidad del problema), es posible que nos parezca lento para decirnos la hora... pero es que no lo dedicaremos a decir horas. Le pediremos que nos haga la quiniela.

En nuestro caso, necesitamos n-1 iteraciones para resolver el problema (donde n es el número de datos de entrada), pero ese -1 es irrelevante para un n grande. Decimos entonces que la complejidad temporal depende de n. ¿Hasta qué punto?. Pues, en general, cada vez que empezamos una iteración tenemos que recorrer el vector, primero hasta el final, luego hasta el final - 1 posición, luego - 2... como los informáticos no atendemos estas disquisiciones matemáticas, decimos que el coste temporal es de n*n, es decir, de n². No contentos con decirlo lo notamos así: O(n²). Esto significa que, en el peor caso, los datos de entrada al cuadrado serán una cota máxima a la complejidad temporal de la solución. Por otro lado, la complejidad espacial de este algoritmo es "nula": no requerimos más espacio que el propio vector durante el proceso.

¿Qué es el peor caso?. Pues depende. En nuestra solución, que el vector esté ordenado, pero al revés. ¿Existe un mejor caso para nuestra solución?. Sí, que ya esté ordenado. Si tras la primera iteración no hemos hecho ningún cambio, sería idiota continuar el proceso. El coste sería O(n). También existe el concepto de caso medio, pero por hoy ya hemos tenido bastante.

Así que tenemos un algoritmo de coste temporal cuadrático para ordenar un vector... ahora bien: ¿existe algún otro método para ordenar longanizas de números que sea mejor?.

La respuesta en el siguiente capítulo.

Pista: sí.

Posts relacionados