A versão original de esta história apareceu em Quanta revista.
Os cientistas da computação geralmente lidam com problemas abstratos que são difíceis de compreender, mas um novo e emocionante algoritmo é importante para quem possui livros e pelo menos uma prateleira. O algoritmo aborda algo chamado problema de classificação da biblioteca (mais formalmente, o problema “List Rotinging”). O desafio é criar uma estratégia para organizar livros em algum tipo de ordem classificada – alfabética, por exemplo – que minimiza quanto tempo leva para colocar um novo livro na prateleira.
Imagine, por exemplo, que você mantenha seus livros agrupados, deixando espaço vazio na extrema direita da prateleira. Então, se você adicionar um livro de Isabel Allende à sua coleção, talvez seja necessário mover todos os livros na prateleira para dar espaço a ele. Essa seria uma operação demorada. E se você receber um livro de Douglas Adams, terá que fazer tudo de novo. Um arranjo melhor deixaria os espaços desocupados distribuídos por toda a prateleira – mas como exatamente eles deveriam ser distribuídos?
Este problema foi introduzido em um Artigo de 1981e vai além de simplesmente fornecer a bibliotecários orientação organizacional. Isso ocorre porque o problema também se aplica ao arranjo de arquivos em discos rígidos e em bancos de dados, onde os itens a serem organizados podem numerar os bilhões. Um sistema ineficiente significa tempos de espera significativos e grandes despesas computacionais. Os pesquisadores inventaram alguns métodos eficientes para armazenar itens, mas há muito que desejam determinar a melhor maneira possível.
No ano passado, IN um estudo Isso foi apresentado nas fundações da Conferência de Ciência da Computação em Chicago, uma equipe de sete pesquisadores descreveu uma maneira de organizar itens que chegam a tentativa ao ideal teórico. A nova abordagem combina um pouco de conhecimento do conteúdo passado da estante com o surpreendente poder da aleatoriedade.
“É um problema muito importante”, disse Seth Pettieum cientista da computação da Universidade de Michigan, porque muitas das estruturas de dados em que confiamos hoje armazenam informações sequencialmente. Ele chamou o novo trabalho de “extremamente inspirado (e) facilmente um dos meus três principais papéis favoritos do ano”.
Limites estreitando
Então, como se medem uma estante bem classificada? Uma maneira comum é ver quanto tempo leva para inserir um item individual. Naturalmente, isso depende de quantos itens existem em primeiro lugar, um valor normalmente indicado por n. No exemplo de Isabel Allende, quando todos os livros precisam se mudar para acomodar um novo, o tempo que leva é proporcional a n. Quanto maior o nquanto mais tempo leva. Isso faz disso um “limite superior” ao problema: nunca levará mais tempo do que um tempo proporcional a n Para adicionar um livro à prateleira.
Os autores do artigo de 1981 que inauguravam esse problema queriam saber se era possível projetar um algoritmo com um tempo médio de inserção muito menos do que n. E, de fato, eles provaram que se poderia fazer melhor. Eles criaram um algoritmo que era garantido para alcançar um tempo médio de inserção proporcional a (log n)2. Esse algoritmo tinha duas propriedades: era “determinístico”, o que significa que suas decisões não dependiam de nenhuma aleatoriedade e também era “suave”, o que significa que os livros devem se espalhar uniformemente nas subseções da prateleira onde inserções (ou deleções) são feitos. Os autores deixaram em aberto a questão de saber se o limite superior poderia ser melhorado ainda mais. Por mais de quatro décadas, ninguém conseguiu fazê -lo.
No entanto, os anos seguintes viram melhorias no limite inferior. Enquanto o limite superior especifica o tempo máximo possível para inserir um livro, o limite inferior fornece o tempo de inserção mais rápido possível. Para encontrar uma solução definitiva para um problema, os pesquisadores se esforçam para restringir a lacuna entre os limites superior e inferior, idealmente até coincidirem. Quando isso acontece, o algoritmo é considerado ideal – limitado de cima e abaixo, não deixando espaço para refinamento adicional.
