Fascinación por la vida

Divagaciones mentales de Alberto Gimeno

Algorítmica cotidiana

Como ya sabéis me dedico a programar aplicaciones informáticas. Una parte muy importante de estas aplicaciones es la algorítmica. Un algoritmo es un conjunto de operaciones que permite hallar la solución a un problema. Pensar en operaciones es algo muy abstracto. A veces me gusta comprobar que algunos algoritmos existen en la la vida cotidiana.

Una tarea tremendamente habitual en un programa es tener que manejar colecciones de cosas. En este tema hay varias estructuras y algoritmos archiconocidos que son perfectamente aplicables a la vida cotidiana.

  • La cola. Seguramente todo el mundo habrá oído hablar de la “cola de impresión” (bromas a parte :P) o la “cola de procesos”. Una cola es una estructura muy sencilla: lo primero que entra es lo primero que sale. Es como la cola del cine, o cualquier cola de espera: el que primero llega es el primero en ser atendido, y el último que llega es el último en ser atendido. Las “cosas” se añaden al final de la cola y se van “sacando” del principio de la cola.
  • La pila también es una estructura muy común. Es usual tener una pila de libros, una pila de apuntes o una pila de camisetas limpias. En una pila las cosas se añaden por arriba y se sacan también por arriba. El último en llegar es el primero en salir.

Tanto la pila como la cola son estructuras de acceso secuencial, esto es, si queremos llegar al último elemento tenemos que “despachar” todos los anteriores. No podemos acceder a un elemento concreto, tenemos que acceder a ellos de forma secuencial, uno detrás de otro, hasta llegar al que nos interesa. Un ejemplo cotidiano evidente es una cinta de cassette: si queremos escuchar la quinta canción tenemos que pasar las cuatro primeras, no hay un mecanismo inmediato que nos lleve hasta la canción que queremos escuchar. Lo opuesto a las colecciones de acceso secuencial son las colecciones de acceso aleatorio. Un ejemplo común es el de un CD de audio. En un CD podemos ir a la canción que queramos de forma inmediata. O los libros de una estantería: mientras que en una pila para coger un libro tenemos que levantar los que tiene encima, si los libros están en vertical podemos acceder a cualquiera sin tener que tocar el resto.

A veces nos interesa tener las cosas ordenadas. Queremos acceder por ejemplo a un libro por su título y no por la posición que ocupa. No queremos “el tercer libro”, queremos el libro titulado “Veinte mil leguas de viaje submarino“. Pero claro, no sabemos dónde está exactamente. Si no tenemos los libros ordenados tendremos que ir mirando uno a uno. Si tenemos la colección de libros ordenada la búsqueda será más rápida. Pero voy a cambiar de ejemplo, voy a usar como ejemplo la guía telefónica. Supongamos que estamos buscando a alguien con el apellido “Gimeno”. Abrimos la guía y en la página que estamos los apellidos empiezan por “D” por lo que deducimos que tenemos que avanzar en la guía. Saltamos aleatoriamente unas cuantas páginas de vez y llegamos a una página donde los apellidos empiezan por “I”. Nos hemos pasado. Tenemos que ir hacia atrás, pero no tan atrás como la primera vez… Repetimos estas acciones hasta que llegamos a la página y encontramos el teléfono deseado. Sin darnos mucha cuenta acabamos de usar el algoritmo de búsqueda dicotómica. Este algoritmo también está presente en el típico juego de adivinar un número. Alguien piensa un número y otro intenta adivinarlo. Quien ha pensado el número sólo le dirá a la otra persona si el número es mayor o menor que los que va diciendo. Ejemplo: un número entre cero y cien: 50. Menor. 25. Mayor. 37. Menor….

En una colección ordenada obviamente es mucho más rápido encontrar un dato. Si la guía de teléfono no estuviera ordenada tendríamos que buscar los teléfonos recorriendo todas las personas que hay en la guía hasta encontrar el que nos interesa. La búsqueda dicotómica es útil en tal caso. Sin embargo la búsqueda dicotómica aún es poco óptima. Existe una forma más rápida de buscar datos: las tablas de dispersión.

Un ejemplo quizá demasiado trivial de una tabla de dispersión son los números de habitación en un hotel. En un hotel si te dan la llave 215, sabes que tu habitación está en la segunda planta porque el número de habitación empieza por 2. Bien, pues imaginemos que no es así, que visitamos un hotel en el que las habitaciones están ordenadas (1, 2, 3,… 120, 121) pero no hay una correlación entre el número de habitación y el piso donde se encuentra, y además cada piso tiene más o menos habitaciones que los otros pisos. En tal caso deberíamos hacer como en la guía telefónica: una búsqueda dicotómica. Supongamos que nos dan la habitación 34. Cogemos el ascensor y subimos a la planta quinta y vemos que allí la habitación con el número más bajo es la habitación 61. Cogemos de nuevo el ascensor y bajamos un par de pisos, hasta la planta tercera, y vemos que allí la habitación con el número más alto es la habitación 27. Bien, pues sabemos que nuestra habitación está en la cuarta planta. Con esto vemos que la búsqueda dicotómica no es suficientemente eficiente: en este hotel los huéspedes tienen que hacer varios viajes en el ascensor hasta encontrar su habitación. Con la estructura de “tabla de dispersión” sabemos a partir del número de habitación en qué planta se sitúa la misma; no tenemos que buscar, el dato está ahí, sólo tenemos que desplazarnos hasta esa planta.

Otro ejemplo de tabla de dispersión. En una biblioteca los libros suelen estar ordenados por temas y luego por título. Supongamos una biblioteca que tiene los libros organizados por título alfabéticamente. Un ejemplo de aplicación de la estructura de tabla de dispersión sería tener un armario para cada letra y dentro de cada armario una estantería para cada letra también. Si nuestro libro es “Veinte mil leguas de viaje submarino” lo encontraríamos en el armario “V” (primera letra del título) en la estantería “E” (segunda letra del título). Vemos que este mecanismo es inmediato, que no tenemos que buscar porque a partir del título ya sabemos la localización del libro. El nombre “tabla de dispersión” viene de que las cosas se encuentran dispersas. En un pila las cosas se ponen unas encima de otras sin dejar huecos. En una tabla de dispersión no, en una tabla de dispersión hay huecos. Si no hay ningún libro que empiece por “Ad…” la estantería “D” del armario “A” queda vacía a la espera de que algún libro cuyo título empiece por “Ad…” sea adquirido por la biblioteca. Por lo tanto la tabla de dispersión nos da acceso rapidísimo a las cosas con la desventaja de tener que usar más recursos.

El lector avispado se habrá dado cuenta de que puede haber muchos libros que empiezan por las dos mismas letras. Es decir, en una misma estantería dentro de un armario habrá varios libros, y dentro de ellos habrá que hacer una búsqueda. Efectivamente, esto se llaman “sinónimos”. En nuestro ejemplo “Veinte mil leguas de viaje submarino” y el libro titulado “Verde” serían dos “sinónimos” porque en nuestro mecanismo ocupan el mismo lugar. Existen diversas formas para gestionar esto, pero ya es profundizar demasiado.

Ahora voy a hablar de un par de tipos de algoritmos criptográficos: algoritmos de clave simétrica y algoritmos de clave asimétrica. Los algoritmos de cifrado de clave simétrica son aquellos en los que hay una clave. La misma clave sirve para cifrar y para descifrar. Es como una llave de una puerta, la misma llave que abre es la que cierra. Si tenemos un mensaje y lo ciframos con una clave, con la misma clave se podrá descifrar. Es por lo tanto conveniente que esta clave la tenga sólo la gente imprescindible. Al igual que también es conveniente que nuestra llave de casa sólo la tenga gente de confianza que la necesite. En los algoritmos de clave asimétrica hay dos claves: la clave pública y la privada. Estas claves están íntimamente relacionadas: lo que una cifra la otra lo descifra. Lo que se hace es mantener una clave en secreto (clave privada) y la otra ofrecerla a cualquier persona (clave pública). Yo me imagino esto como un cofre un poco especial. Es un cofre que sirve para depositar y enviar mensajes. Un cofre que para abrirlo hay que usar la clave opuesta a la que se usó para cerrarlo. Si cierro con una llave, se abre con la otra. Si cierro con la pública se abre con la privada y viceversa. Supongamos que yo quiero enviar un mensaje a una persona y quiero que esa persona tenga la certeza de que he sido yo el emisor del mensaje. Lo que hago es depositar el mensaje y lo cierro con mi clave privada. El receptor, como todo el mundo, posee la clave pública y puede abrir el cofre. El receptor está seguro de que he escrito yo el mensaje porque el cofre se ha abierto con la calve pública, lo que quiere decir que fue cerrado con la clave privada que sólo yo tengo. Esto a grosso modo es lo que se llama firma electrónica. Con este mecanismo aseguramos la autenticidad del mensaje, como si hubiera sido firmado. Con esto no hemos asegurado la privacidad del mensaje (todo el mundo tiene la clave pública, todo el mundo podría haber abierto el cofre y leído el mensaje), sólo aseguramos la autenticidad del receptor. Veamos como asegurar la privacidad. Supongamos que ahora alguien quiere mandarme a mí un mensaje sin que nadie más lo pueda leer. Lo que hará esa persona es depositar el mensaje en el cofre y cerrarlo con la clave pública. El cofre llega a mí y sólo yo puedo abrirlo porque sólo yo tengo mi clave privada.

Dejemos la criptografía. Veamos un mecanismo muy obvio: la multitarea. La multitarea es la capacidad de hacer varias cosas a la vez. En un ordenador es evidente que podemos tener varios programas funcionando al vez. Eso es multitarea. En la vida cotidiana la multitarea está presente en todas partes. Podemos leer una revista mientras dejamos el agua a hervir, vemos la televisión mientras se descarga un CD… Alguna vez extremo estas posibilidades y por ejemplo cuando tengo prisa y salgo de casa dejo la puerta abierta, llamo al ascensor y mientras llega el ascensor cierro la puerta de mi casa con llave.

Alguno llegado a este punto se preguntará el porqué de estas paranoias mentales jaja. La respuesta es fácil. Imaginarse aplicaciones cotidianas de los algoritmos permite comprobar fácilmente si son o no son óptimos. Y aquí pongo el ejemplo de Shlemiel el pintor.

Shlemiel consiguió un trabajo como pintor de calles, pintando la línea discontinua de las carreteras. El primer día cogió su cubo de pintura y acabó 300 yardas de carretera. “¡Eso está realmente bien!” le dijo su jefe. “Eres un trabajador muy rápido” y le dio una moneda.

El día siguiente, sólo consiguió hacer 150 yardas. “Bueno, no ha estado tan bien como ayer pero todavía eres un trabajador rápido. 150 yardas es una cantidad muy respetable”. Y le da una pequeña moneda.

Al día siguiente, Shlemiel completó 30 yardas de carretera. “¡Sólo 30 yardas!” le gritó su jefe. “¡Esto es inaceptable!. El primer día hiciste 10 veces más distancia ¿Qué está pasando aquí?”

“No puedo hacerlo mejor”, dijo Shlemiel, “cada día estoy más y más lejos del bote de pintura.”

Esto que aparentemente no es más que una chorrada es lo que hacen muchos programas. Y en el artículo que enlazo está estupendamente explicado para cualquier programador. El algoritmo del pintor consiste en que algo que debería tener un comportamiento lineal realmente tiene un comportamiento exponencial. Un ejemplo es el siguiente: “Para ver este efecto, intenta abrir la Papelera de Reciclaje de Windows cuando está a rebosar — te llevará horas que se abra, lo que tiene claramente un rendimiento no lineal al número de archivos que contiene. Ahí seguro que está el algoritmo de “Shlemiel el Pintor” por algún lado“. Con el doble de archivos la papelera de reciclaje no va el doble de lenta sino cuatro veces más lenta. Ahí está el algoritmo de “Shlemiel el Pintor”.

Y bueno, para terminar este largo artículo, los punteros. Esto que voy a contar es sólo apto para personas que sepan programar. Los punteros son “unas cosas” que sirven para apuntar a direcciones de memoria dentro del ordenador. Sirven para localizar información. Supongamos el siguiente programa en pseudocódigo.

saludo1 = “hola”
saludo2 = saludo1
saludo3 = saludo2

En este programa tenemos tres punteros (saludo1, saludo2, saludo3). Los tres punteros apuntan a un dato. Ese dato es “hola”. Yo me lo imagino como pinzas y prendas de ropa en una cuerda de tender. Los punteros son pinzas, y “hola” es por ejemplo una camiseta. Tras la ejecución de esas tres líneas de código habría tres pinzas (saludo1, saludo2, saludo3) sujetando la camiseta (“hola”). Si ejecutamos lo siguiente…

saludo2 = “adios”
saludo3 = “hasta luego”

Ahora tendremos una pinza (puntero) sujetando cada camiseta (dato). En el momento que ninguna pinza sujeta una prenda de ropa (ningún puntero apunta a un dato), la prenda se cae y esa prenda ya deja de ser útil. En programación ese trozo de memoria quedaría libre, habría que liberarla a mano o en otros lenguajes el garbage collector se encargaría de ella.

Written by gimenete

Martes, mayo 22, 2007 a 1:24 pm

Publicado en opinión

3 comentarios

Subscribe to comments with RSS.

  1. La prenda se cae… Tío, deja la cafeína…

    GoLo

    Martes, mayo 22, 2007 at 1:35 pm

  2. […] Gimeno, Alberto. “Algorítmica cotidiana”, https://gimenete.wordpress.com/2007/05/22/algoritmica-cotidiana/ […]

    Actividad « Fundamentos de Algoritmos

    Domingo, abril 15, 2012 at 7:04 pm

  3. ostia tio pongan el algoritmo

    kevin

    Martes, abril 24, 2012 at 10:39 pm


Los comentarios están cerrados.

A %d blogueros les gusta esto: