Otimização - Explorando sistemas de busca

Autor:Thiago Vasconcellos Batalha

Diversos recursos computacionais são inventados todos os dias para facilitar a realização dos mais variados tipos de trabalho. Como por exemplo, um localizador de palavras em um texto. Quando pressionamos as teclas ctrl + F em um computador ou acessamos o recursos "localizar" (geralmente representado por uma lupa) em nossos celulares, o dispositivo realiza uma busca no site que estamos visitando e nos mostra em que local da página aquela palavra está. É um recurso que pode nos poupar bastante tempo! Entretanto, para realizar a busca, o dispositivo precisa comparar as palavras presentes no texto com a palavra desejada de alguma forma. Existem diversas formas diferentes que o dispositivo pode utilizar para buscar uma palavra. Algumas formas são mais rápidas outras são mais demoradas, tudo depende da quantidade de operações que a maquina terá que fazer. Um grande desafio da computação é tentar realizar uma tarefa utilizando a menor quantidade de operações possíveis.

Como utilizar o applet?

O applet abaixo foi desenvolvido para explorar e pensar novas estratégias de busca. Para isso, ao clicar em reiniciar ele irá gerar um número aleatoriamente entre 0 e 99. Após isso, ao clicar em qualquer um dos 100 botões numerados de 00 até 99 ele te informará se o valor selecionado é maior, menor ou igual ao número sorteado. Além disso, ele fornece o número total de tentativas que você fez até encontrar o número.

Para um computador todas as letras e símbolos digitados se tornam números. Dessa forma, considere que uma lista com 100 palavras listadas em ordem alfabética é interpretada pelo computador como os números 0, 1, 2, ..., 99. Sendo 0 a primeira palavra da lista, 1 a segunda palavra e assim por adiante. Assim, localizar uma palavra em ordem alfabética equivale a encontrar um número em ordem crescente (ordenado do menor para o maior) tal como no applet acima. Utilizando esse texto e o applet explore as atividades propostas.

Atividade 1

Marcos descreveu o seguinte procedimento para poder encontrar o número sorteado no applet: Clique no botão correspondente ao primeiro número (00), se o valor for igual pare. Se o valor do botão for menor do que o valor sorteado clique no botão seguinte e repita o procedimento. Exemplo 1: Supondo que o valor sorteado seja 19. Então o botão 00 será testado, depois o botão 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18 e por fim o 19. Momento em que será exibida a mensagem: "Encontrou". Portanto, o valor sorteado será encontrado em 20 operações. Exemplo 2: Supondo que o valor sorteado seja 3. Serão testados os botões 00, 01, 02 e 03. O valor será encontrado em 4 operações Explore o procedimento descrito por Marcos no applet e escreva qual é o número máximo de operações que podem ser necessárias utilizando esse procedimento para encontrar o valor sorteado? Escreva um comentário explicando o motivo da sua resposta. Dica: Para descobrir o maior número de operações que podem ser realizadas pense numa situação em que seguindo o procedimento fielmente o valor sorteado será encontrado quando chegar ao último passo possível.

Atividade 2

Janaína pensou no seguinte procedimento para encontrar o valor: Considerando o botão atual como 00, 1 - testa-se o décimo botão após o atual (ou seja, botão 09); Se for igual pare. Se for maior que o valor sorteado, testa cada um dos 9 botões anteriores em ordem crescente. Se for menor, "salta" dez botões e teste-o (botão 19). 2 - Repita o procedimento (1) até encontrar o valor sorteado. Exemplo 1: Supondo que o valor sorteado seja 30. Será testado primeiramente o botão 09, em seguida o botão 19, após ele o botão 29 e o botão 39. Neste momento o applet informara que o valor testado é maior do que o valor sorteado. Então será testado o botão 30 e o valor sorteado será encontrado em 5 operações. Exemplo 2: Supondo que o valor sorteado seja 13. Serão testados os botões 09 e 19. Nesse momento o applet informará que o valor testado é maior do que o valor sorteado. Então serão testados os botões 10, 11, 12 e 13. Encontrando assim o valor sorteado em 6 operações. Explore o procedimento descrito por Janaína no applet e escreva qual é o número máximo de operações que podem ser necessárias utilizando esse procedimento para encontrar o valor sorteado? Escreva um comentário explicando o motivo da sua resposta.

Atividade 3

R2D2 pensou no seguinte procedimento para encontrar o valor: Considere 02 como o número atual, 1 - testa-se o número primo atual; Se for este o valor sorteado pare, Se for menor, teste o próximo número primo. Se for maior, teste cada um dos valores que estão entre este número primo e o menor número primo mais próximo a ele, em ordem crescente. Exemplo 1: Supondo que o valor sorteado seja 9. Será testado primeiramente o botão 02, em seguida o botão 03, após ele o botão 07 e o botão 11. Neste momento o applet informara que o valor testado é maior do que o valor sorteado. Então serão testados os botões 08 e 09 e o valor sorteado será encontrado em 6 operações. Exemplo 2: Supondo que o valor sorteado seja 97. Serão testados os botões 02, 03, 05, 07, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 e 97. Sendo o valor sorteado encontrado em 25 operações. (Foram utilizados todos os números primos existentes entre 00 e 99) Explore o procedimento descrito por R2D2 no applet e escreva qual é o número máximo de operações que podem ser necessárias utilizando esse procedimento para encontrar o valor sorteado? Escreva um comentário explicando o motivo da sua resposta.

Atividade 4

Qual dos procedimentos descritos anteriormente permite encontrar de forma mais rápida o valor sorteado, considerando em cada um deles o caso em que serão necessários o maior número de operações possível.

Assinale a sua resposta aqui

A
Marcos
B
Janaína
C
R2D2

Verifique minha resposta (3)

Atividade 5

Que tal tentar descrever o seu próprio procedimento para encontrar o valor sorteado? Pense em um procedimento simples e teste-o no applet! Depois, verifique se ele encontra o valor sorteado em menos operações do que os procedimentos descritos por Marcos, Janaína e R2D2. Não esqueça de descrever o seu procedimento como resposta dessa atividade!