Tras el gran éxito de sus estrenos anteriores, Algoritmos de ordenamiento y Algoritmos de redondeo, teknoPLOF! vuelve al ataque con su tercera entrega Algoritmos de búsqueda básicos para torpes (<- este último metavínculo es recursivo en sí mismo; miedito).

Los programadores informáticos son muy cuadriculados y todo lo tienen que hacer siguiendo unas pautas prefijadas perfectamente determinadas y secuenciadas. Paso 1, paso 2 y paso 3; y fin del asunto. Como suelen utilizar enormes cantidades de datos (yo que sé, como inmensas listas de personas con sus teléfonos, por ejemplo), se les hace necesario poder buscar un elemento en concreto dentro de un grupo de ellos. Y eso, a veces, no es tan sencillo.

Hoy en día existen métodos de búsqueda propios y muy optimizados en los lenguajes de programación más modernos y, también, en los propios gestores de datos. Sin embargo, no viene mal conocer los algoritmos de búsqueda más básicos del mundo mundial por si se nos presenta esa ocasión eventual en la que tenemos cosas que ordenar y no disponemos de herramientas a nuestra disposición.

Y, además, lo vamos a hacer de una manera tan insultantemente sencilla que resulta hasta ofensiva. Pero bueno, allá vamos.

Búsqueda secuencial (lineal)

Es tan fácil como recorrer, secuencialmente, toda la lista de elementos en la que queremos buscar uno en concreto (llamado clave) desde el principio hasta el final. Si lo encontramos, ¡estupendo!, si no lo encontramos es que no está. Tan sencillo como eso.

La búsqueda secuencial se utiliza para listas o matrices de datos que están desordenadas, que no siguen un orden en concreto, como un listado de alumnos de un colegio, por ejemplo, que no está ordenado alfabéticamente.

Dado que, como decimos, el conjunto no tiene un orden prefijado, es probable que el elemento que estamos buscando se encuentre en primera posición, que esté el último o que ande por el medio de la lista (¡o que no esté!). Por ello, este tipo de búsqueda puede ser mu rpdilla o hacerse eteeeeeeeeerna, en función del número de elementos en el grupo. Funciona correctamente en listas cortitas y es muy sencillo de implementar.

Búsqueda binaria (dicotómica)

El algoritmo de búsqueda binaria es mucho más eficaz que el de búsqueda secuencial, pero eso sí, necesita que la lista de datos esté ordenada; por ejemplo, un índice de pueblos organizados numéricamente, de menor a mayor, por su código postal.

Los pasos que se deben seguir son muy sencillos. Se empieza a buscar el dato que necesitamos encontrar por el elemento de en medio de la lista, el del centro. Si no es el que buscamos, comprobamos qué relación tiene con él, es decir, si es mayor o menor. Si es menor, por ejemplo, acotamos la búsqueda a la primera mitad de la lista. Y repetimos: cogemos el elemento central y lo comparamos con el que estamos buscado; si no es, volvemos a acotar la búsqueda en función de si el que buscamos es mayor o menor que el nuevo central.

Un ejemplo facilón para que quede claro. Dada la siguiente lista de valores numéricos ordenados:

2 23 35 38 47 56 57 76 83 85 90 92 95 98 99

Quiero saber si el número 56 se encuentra en la lista. Leo el valor central de la lista: 76. ¿Es el que busco? No. ¿Es mayor o menor que el que busco? Mayor. Por lo tanto me quedo con una lista más pequeña, la que va de 2 a 57. Leo, otra vez, en valor central: 38. ¿Es el que busco? No. ¿Es mayor o menor que el que busco? Menor. Entonces, mi nueva lista para comparar es de 47 a 57. Vuelvo a leer el valor central: 56. ¿Es el que busco? Sí. Finiquitado en tres comparaciones.

En el caso de que, en algún momento, alguna de las listas tenga un número par de elementos, no pasa nada, los programadores son tan listos que ellos se encargan de realizar labores de redondeo a la hora de averiguar la parte media de una relación.

Búsqueda por interpolación

Este último tipo de búsqueda es un poco más puñetero. En principio es muy parecido al anterior, pues es un algoritmo recursivo (se repite continuamente hasta que da con el valor buscado) y también acota las listas en secciones más pequeñas. La diferencia con la búsqueda binaria es que, en lugar de cortar las listas todo el rato por la mitad, éstas se delimitan siempre por medio de los valores resultantes de una interpolación matemática. Más clarito: si durante la búsqueda encontramos un valor que está muy cerca del número clave que buscamos, parece más razonable continuar buscando en esa área, en lugar de cortar y buscar el número central otra vez.

En matemáticas, se denomina interpolación a la obtención de nuevos valores partiendo del conocimiento de un conjunto de otros valores. Fijémonos de nuevo en la lista anterior. Tras la primera comparación apuntando al centro, la nueva lista que nos quedaba iba de 2 a 57. El número que andaba buscando era el 56, que está terriblemente cerquita del final de mi lista; tan cerquita, tan cerquita que casi se tocan. La lógica me dice que voy a andar mejor empezando a buscar por el final que tirando al centro y comparando de nuevo.

Los programadores utilizan esas interpolaciones matemáticas, codificadas en código fuente de un lenguaje de programación, para determinar por dónde andan los valores más cercanos y afinar la búsqueda.

Y hemos llegado al final. Existen otros algoritmos de búsqueda, pero estos son los más simples y los más utilizados. Y no vamos a escribir ni una sola línea de código porque nos hemos prometido hacerlo fácil de entender. Los informáticos que deseen codificar estas explicaciones, no creo yo que tengan ningún problema en hacerlo rápidamente; es extremadamente sencillo.

Se acabó.

No hemos encontrado palabras para definir esto. Puede ser un vídeo, puede ser una imitación, puede ser una voz enlatada, un fake… O, también, puede ser la mejor imitación de voces con la que nos hemos encontrado nunca. Si es así, el mejor de los mejores chapós por ellos; si no, estamos asombrados al cien por cien.

En fin, ¿es esta la mejor imitación jamás contada (y no sólo de voces de cantantes) o es el meme más extremo del que vamos a dar cuenta en esta sección?

La Red proveerá. Pasen y vean.

Y todo era un fake (muy bien hecho y muy bien cantado, claro que sí)

¿Estás cansado de escuchar la misma música mientras te tuestas al sol en la playa? ¡Pues no te preocupes porque aquí estamos con un nuevo podcast para animarte las largas tardes de verano!

Toda la actualidad informativa en nuestra sección ‘Noticias’. Nos acercamos hasta la Euskal Encounter, os traemos las novedades de Google Now y de Windows 9, os alertamos de los fallos de seguridad descubiertos en todos los USB, damos una vuelta por las tiendas de impresión 3D de Amazon y nos ponemos los últimos smartwatch de OnePlus y HP.

Con la ‘App de la Semana’ podrás crear un plano de tu vivienda sin sacar el flexómetro del bolsillo, y es que la realidad aumentada de nuestros dispositivos nos facilita, y mucho, nuestra actividad profesional. MagicPlan es la solución.

Si tú eres de los que piensan que te echaron algo en la copa la última noche, en lugar de pensar que ya no estás para tomarte cinco cubatas seguidos, sacarás mucho partido al ‘Teknoútil’ de esta semana: Personal Drink ID.

‘Se habla de’ la caída de los servidores de Facebook. Drama y morbo a partes iguales entre los usuarios de esta red social.

Nos ponemos serios para ‘El Debate’: el proyecto de ley de la mal llamada Tasa Google, y en ‘Retroclick’ nos trasladamos a los albores de la informática para descubrir los primeros virus.

Tomad asiento, aquí empieza Ready, Set, Click!

El podcast, vía iVoox, en http://www.ivoox.com/rsclick-t01x08-programa-completo-06-08-2014-audios-mp3_rf_3380178_1.html

Atari Bit Byter User Club (ABBUC) es una asociación alemana de usuarios de máquinas retro de Atari. En su web podemos encontrar un montón de información sobre las Atari de ocho bits, así como una revista digital periódica y, también, un punto de encuentro para todos los retrofrikis atarianos. Asimismo, anualmente celebran un concurso de hardware y otro de software (en este último nos centraremos) con suculentos premios en metálico.

En concreto, este 2014, la inscripción para la competición de software termina el próximo 31 de agosto. La reglas varían de un año a otro y, en este caso, los juegos o aplicaciones desarrolladas deben ser completamente funcionales para las versiones PAL de Atari 800XL (de 64 Kb) o de Atari 130XE (de 128 Kb) con unidad de disco Atari 1050. El software debe presentarse en uno o más disquetes de 5,25″ (sin protección de copia) o, en su caso, en imágenes de disco ATR. Además, deben contener la frase «ABBUC software contest 2014» en la pantalla de presentación y, por último, si llevan algún tipo de texto escrito, este deberá estar exclusivamente en inglés o en alemán.

Ganador de 2007

No se permite software comercial, ni juegos previamente lanzados en Internet o revistas, ni programas que ya hayan participado en anteriores concursos de ABBUC. Lo que sí se pueden presentar son desarrollos previos, siempre y cuando cambien bastante con respecto al original o se extiendan mucho sus funcionalidades. También se admiten conversiones de otras plataformas y colecciones de programas, si esos programas guardan entre sí una temática coherente (por ejemplo, un sistema DOS y sus utilidades).

Ganador de 2009

Si nos decidimos a presentar nuestro flamante juego ochobitero, debemos saber que, junto al código correspondiente, tenemos que presentar una descripción corta, o manual, de no más de dos páginas (DIN A5), escrito en un tamaño de fuente normal y con un máximo de tres capturas de pantalla. Además, si la descripción no fuera suficiente para comprender el desarrollo completamente, se puede anexar una documentación detallada, pero de forma separada al manual de usuario anterior. También habremos de precisar nuestra dirección postal y una cuenta bancaria para el ingreso del premio, en el caso de que nos hagamos con una victoria.

Ganador de 2010

Los diseños y sus documentaciones deben ser enviadas por correo ordinario o electrónico no más tarde del 31 de agosto de 2014 a las 22:00 (GMT+1). El primer premio se recompensa con 500 €, el segundo 250 €, el tercero 125 €, el cuarto 75 €, el quinto 50 €, y al sexto y al décimo lugar se les otorga un premio de bajo precio en material.

Ganador de 2011

Todos aquellos interesados todavía disponen de algo menos de un mes para terminar sus joyas retro y enviarlas al concurso. Quién sabe, igual os alzáis con uno de los premios. ¡Suerte!

Hasta ahora la misión Rosetta ha sido un completo éxito. Tras diez años de viaje y 957 días en hibernación, la sonda espacial Rosetta de la Agencia Espacial Europea (ESA) ha llegado a su primer destino hoy mismo, 6 de agosto del año 2014, a las 11:35 (hora española): encontrarse con el cometa 67P/Churyumov-Gerasimenko y ponerse a su lado (a unos 100 kilómetros de distancia) para viajar con él de vuelta hasta la Tierra.

Lanzada el 2 de marzo de 2004, su objetivo principal es investigar la composición y características del 67P, lo que puede dar mucha y muy buena información sobre la formación del sistema solar, pues existe una muy bien fundada suposición que explica que los cometas son los objetos menos modificados del Sistema Solar desde su formación, hace 4.600 millones de años.

Recomiendo encarecidamente perder dos minutos de vida visionando el siguiente vídeo, el cual muestra el viaje completo que ha hecho Rosetta hasta ahora y lo que le queda (hasta diciembre de 2015), marcando etapa a etapa cada momento.

La sonda ha recorrido nada más y nada menos que 6.400 millones de kilómetros a través de un intrincado camino para ganar impulso y dar alcance al cometa. Permaneció, como decíamos al principio, 957 días hibernando y, tras 10 maniobras de corrección, que comenzaron en mayo y han terminado hoy, por fin ha alcanzado su objetivo inicial. El siguiente vídeo de la ESA muestra las maniobras de aproximación.

A partir de ahora, viajará con 67P a una velocidad aproximada de 55.000 km/h, aproximándose al Sol para orbitar a su alrededor y, posteriormente, pasará cerca de la Tierra. 67P/Churiumov-Guerasimenko es un cometa de periodo orbital de 6,6 años descubierto en 1969 por el científico soviético Klim Ivánovich Churiumov, estudiando las fotografías de Svetlana Ivanovna Gerasimenko, también investigadora soviética (de ahí su extenso nombre).

En noviembre de este mismo año, Rosetta aterrizará sobre 67P haciendo uso de uno de sus múltiples módulos (en concreto el llamado Philae) para lanzar dos arpones que la anclen a la superficie del cometa. Esto no se ha hecho nunca (bueno, en el cine sí) y se convertirá en el mayor desafío de la misión.

La sonda, una vez asentada, taladrará el cometa, tomará muestras y analizará su composición. Con estos datos podremos llegar a saber más sobre el origen del universo, así como también acerca de dos de las mayores incógnitas que tiene el ser humano: el origen del agua en la Tierra y el origen de la vida en la Tierra.

«We are at the comet» (estamos en el cometa). Con estas palabras ha celebrado la ESA el éxito de esta parte fundamental de la misión Rosetta. La cuenta de Twitter de la agencia se ha llenado de tuis de saludo al cometa en un montón de idiomas diferentes, muchos de ellos con la imagen de la primera fotografía que Rosetta a tomado de 67P, la que se puede ver al principio de esta entrada.

Este último vídeo de ESA España explica a la perfección y de una manera muy didáctica todo el proyecto.

¡Felicidades, ESA! ¡Hola, cometa!