São Paulo (AUN - USP) - O professor de Teoria Computacional da Universidade Federal do Paraná e doutorando da USP, Renato Carmo, investigou recentemente alguns problemas de busca, delimitando alguns limites atuais da computação. Suas conclusões são de natureza teórica, mas interessantes. Os dois casos que o professor investigou são ‘Busca Ótima em Ordens Parciais’, e ‘Ordem Dinâmica em K-partidas’. Apesar dos nomes, não são conceitos demasiado complexos.

Para entender a busca parcial, é preciso entender o que é uma busca total. Busca total, é quando todos os objetos de busca podem ser comparados entre si. Números, por exemplo, em menor e maior. Palavras podem pela ordem alfabética. Buscas em ambientes parciais, porém, envolvem conceitos que não podem ser comparados: por exemplo, numa mesma lista, palavras e números.

Ao fazer qualquer pesquisa, o computador faz perguntas – cálculos – com as quais responde as perguntas. Por exemplo, vamos imaginar um conjunto com os números (1,2,3), e pedir números pares. Ele fará três perguntas, uma a cada número, e dará a resposta que for compatível – no caso, apenas o 2.

Tudo isso leva um certo tempo da máquina, que é a capacidade de processamento. Ao fazer uma busca em uma ordem parcial, o computador precisa de um tempo ou uma capacidade de processamento maior – o que Renato chama de um custo maior.

Ele chegou a determinar um limite, que é o máximo de perguntas que o computador, de modo a trabalhar do modo mais ótimo, ou seja, ideal, pode fazer em cada busca. Este limite corresponde à fórmula matemática Log N dividido por 2. N é o número de objetos a serem pesquisados.

Ordem Dinâmica em K-partidas, por sua vez, lida com pesquisa em bancos de dados; desde os pessoais até os maiores como o da Receita Federal. Estes bancos de dados, porém, formados apenas por texto em sua grande maioria, não são afetados pelos problemas das Ordens Dinâmicas.

Os problemas de busca neste campo, de modo geral, atingem aqueles dados formados por imagens, áudio e vídeo, que pedem uma capacidade de processamento muito alta. Como exemplo, o professor cita as inúmeras imagens de satélite do INPE (que inclusive, estão disponíveis ao público). Apesar de ser apenas texto, os bancos genéticos, por sua elevada extensão e complexidade, também apresentam custo – ou seja, tempo e processamento – alto.

Apesar do professor ter alcançado um limite para este caso, preferiu não citá-lo, por ser teórico e complexo demais, segundo ele.

Workshop

Renato começou a trabalhar com problemas de busca após um workshop bancado pelo PRONEX – Programa de Apoio a Núcleos de Excelência, um instrumento de estímulo à pesquisa e ao desenvolvimento científicos no País – realizado no ano 2000, entre grupos das Universidades de São Paulo, Campinas, PUC do Rio de Janeiro, e as Federais do Rio de Janeiro, Ceará, Pernambuco e Mato Grosso do Sul.

Neste workshop, ele conheceu Eduardo Laber, docente da PUC-Rio que já estudava algoritmos e soluções de busca. Laber foi, durante todo o processo, seu co-orientador não oficial.

Renato faz questão de mostrar a utilidade destes seminários pagos pelo PRONEX como forma eficiente de transmissão e obtenção de conhecimentos. Ele espera, ainda, que com mais estudos teóricos como estes, as pessoas deixem de fazer o que considera uma associação perigosa, que é a de computação com computador. Em sua própria definição, “é a mesma coisa que achar que o astrônomo estuda telescópios”.