La versión original de esta historia apareció en la revista Quanta.
Los informáticos a menudo tratan problemas abstractos que son difíciles de comprender, pero un nuevo algoritmo emocionante es importante para cualquier persona que posee libros y al menos un estante. El algoritmo aborda algo llamado problema de clasificación de la biblioteca (más formalmente, el problema de "etiquetado de la lista"). El desafío es idear una estrategia para organizar libros en algún tipo de orden ordenado, por ejemplo, por ejemplo, que minimiza cuánto tiempo lleva colocar un nuevo libro en el estante.
Imagine, por ejemplo, que mantiene sus libros agrupados, dejando el espacio vacío en el extremo derecho del estante. Luego, si agrega un libro de Isabel Allende a su colección, es posible que deba mover cada libro en el estante para dejarlo. Esa sería una operación que requiere mucho tiempo. Y si obtienes un libro de Douglas Adams, tendrás que hacerlo de nuevo. Una mejor disposición dejaría espacios desocupados distribuidos en todo el estante, pero ¿cómo, exactamente, deberían distribuirse?
Este problema se introdujo en un artículo de 1981, y va más allá de simplemente proporcionar a los bibliotecarios orientación organizacional. Esto se debe a que el problema también se aplica a la disposición de archivos en discos duros y en bases de datos, donde los elementos que se organizarán podrían contar en miles de millones. Un sistema ineficiente significa tiempos de espera significativos y grandes gastos computacionales. Los investigadores han inventado algunos métodos eficientes para almacenar elementos, pero durante mucho tiempo han querido determinar la mejor manera posible.
El año pasado, en un estudio que se presentó en los fundamentos de la Conferencia de Ciencias de la Computación en Chicago, un equipo de siete investigadores describió una forma de organizar artículos que se acercan tentadoramente al ideal teórico. El nuevo enfoque combina un poco de conocimiento del contenido pasado de la estantería con el sorprendente poder de la aleatoriedad.
"Es un problema muy importante", dijo Seth Pettie, una científica informática de la Universidad de Michigan, porque muchas de las estructuras de datos en las que confiamos hoy almacenan la información de hoy. Llamó al nuevo trabajo "extremadamente inspirado (y) fácilmente uno de mis tres documentos favoritos del año".
Límites de estrechamiento
Entonces, ¿cómo se mide una estantería bien organizada? Una forma común es ver cuánto tiempo lleva insertar un elemento individual. Naturalmente, eso depende de cuántos elementos hay en primer lugar, un valor típicamente denotado por norte. En el ejemplo de Isabel Allende, cuando todos los libros tienen que mudarse para acomodar uno nuevo, el tiempo que lleva es proporcional a norte. Cuanto más grande es nortecuanto más tiempo lleva. Eso hace que esto sea un "límite superior" al problema: nunca llevará más tiempo que un tiempo proporcional a norte Para agregar un libro al estante.
Los autores del artículo de 1981 que marcó el comienzo de este problema querían saber si era posible diseñar un algoritmo con un tiempo de inserción promedio mucho menos que norte. Y de hecho, demostraron que uno podría hacerlo mejor. Crearon un algoritmo garantizado para lograr un tiempo de inserción promedio proporcional a (log norte)2. Este algoritmo tenía dos propiedades: era "determinista", lo que significa que sus decisiones no dependían de ninguna aleatoriedad, y también era "suave", lo que significa que los libros deben extenderse uniformemente dentro de las subsecciones del estante donde las inserciones (o deleciones) están hechos. Los autores dejaron abiertos la cuestión de si el límite superior podría mejorarse aún más. Durante más de cuatro décadas, nadie logró hacerlo.
Sin embargo, los años intermedios vieron mejoras en el límite inferior. Mientras que el límite superior especifica el tiempo máximo posible necesario para insertar un libro, el límite inferior proporciona el tiempo de inserción más rápido posible. Para encontrar una solución definitiva a un problema, los investigadores se esfuerzan por reducir la brecha entre los límites superior e inferior, idealmente hasta que coinciden. Cuando eso sucede, el algoritmo se considera óptimo, inicialmente limitado desde arriba y abajo, sin dejar espacio para un mayor refinamiento.
