Atividade 6: Batalha Naval — Algoritmos de Busca

Apresentação

Computadores são frequentemente requisitados a encontrar informação em grandes coleções de dados. Estes precisam desenvolver métodos rápidos e eficientes de fazer isso. Essa atividade demonstra três diferentes métodos de pesquisa: busca linear, busca binária e busca por dispersão/espalhamento (“hashing”).

Disciplinas e conteúdos relacionados

Habilidades

Nível de Ensino

Material

Os jogos 1A e 1B, 2A e 2B e 3A e 3B são para os jogos 1, 2 e 3 respectivamente. As folhas de jogos suplementares 1A’, 1B’, 2A’, 2B’, 3A’ e 3B’ são extras para crianças que gostariam de jogar mais vezes ou que “inadvertidamente” viram a folha do seu parceiro.

Atividade introdutória

Instruções

  1. Escolha em torno de 15 crianças para formar uma fileira na frente da classe. Dê a cada criança um cartão com um número (em ordem aleatória). Mantenha os números escondidos do resto da classe.

  2. Dê a outra criança quatro ou cinco doces. O trabalho dela é descobrir um determinado número. Ela pode “pagar” para olhar um cartão específico. Se encontrar o número correto antes de usar todos os seus doces, ela fica com o restante dos doces.

  3. Repita a atividade, se quiser.

  4. Agora embaralhe as cartas e as distribua novamente. Desta vez, as crianças devem se organizar em ordem crescente. Repita o processo de busca.

Se os números estão ordenados, uma estratégia sensata é usar somente um “pagamento“ para eliminar metade das crianças, escolhendo a criança do meio para revelar o seu cartão. Repetindo esse procedimento, é possível encontrar o número usando somente três doces. O ganho de eficiência será óbvio.

Atividade

As crianças podem ter uma ideia de como um computador faz pesquisas brincando com os jogos de Batalha Naval adaptados que seguem logo abaixo. A utilização do jogo faz com que elas pensem acerca das estratégias que estão usando para localizar os navios.

Batalha Naval — Um jogo de busca linear

Leia as seguintes instruções para as crianças

  1. Formem duplas. Um de vocês pega a folha 1A, e o outro a folha 1B. Não mostrem sua folha para o seu parceiro!

  1. Ambos circulam um navio de guerra na linha superior da folha do jogo e informam o número do navio ao seu parceiro.

  2. Agora, revezem-se para adivinhar onde está o navio do seu parceiro. (Você diz a letra de um navio e o seu parceiro lhe diz o navio correspondente a essa letra).

  3. Quantos tiros são necessários para localizar o navio do seu parceiro? Essa é a sua pontuação no jogo.

(As folhas 1A’ e 1B’ são extras para crianças que gostariam de jogar mais vezes ou que “inadvertidamente” viram a folha do seu parceiro. As folhas 2A’, 2B’ e 3A’, 3B’ são para os jogos seguintes).

Discussão

  1. Quais foram as pontuações?

  2. Quais seriam as pontuações máxima e mínima possíveis? (São 1 e 26, respectivamente, assumindo que as crianças não atiram no mesmo navio duas vezes. Esse método é chamado de ‘busca linear’ porque envolve passar por todas as posições, uma a uma).

Batalha Naval — Um jogo de busca binária

Instruções:

As instruções para essa versão do jogo são as mesmas do jogo anterior, mas os números dos navios estão em ordem crescente. Explique isso às crianças antes de começarem.

  1. Formem duplas. Um de vocês pega a folha 2A, o outro a folha 2B. Não mostrem sua folha ao seu parceiro!

  1. Ambos circulam um navio da linha superior de sua folha de jogo e dizem o número do navio ao seu parceiro.

  2. Agora, revezem-se para adivinhar onde está o navio do seu parceiro. (Você diz a letra de um navio e o seu parceiro lhe diz o navio correspondente a essa letra).

  3. Quantos tiros são necessários para localizar o navio do seu parceiro? Essa é a sua pontuação no jogo.

Discussão

  1. Quais foram as pontuações?

  2. Qual foi a estratégia usada pelos jogadores que tiveram baixa pontuação?

  3. Qual o navio você deveria escolher primeiro? (O navio do meio lhe informa em qual metade da linha o navio escolhido deve estar). Qual posição você deve escolher em seguida? (Novamente, a melhor estratégia é escolher sempre o navio que está na metade da seção que deve conter o navio escolhido.)

  4. Se esta estratégia é aplicada, quantos tiros são necessários para encontrar um navio? (Cinco, no máximo).

Esse método é chamado de ‘busca binária’ porque divide o problema em duas partes.

Batalha Naval — Um jogo de busca usando Hashing

Instruções:

  1. Cada criança escolhe uma folha, como no jogo anterior, e diz ao seu parceiro o número do navio escolhido.

  1. Nesse jogo você pode descobrir em qual coluna (0 a 9) o navio está. Basta somar os dígitos do número do navio. O último dígito da soma é a coluna em que o navio está. Por exemplo, para localizar o navio de número 2345, some os dígitos 2+3+4+5, totalizando 14. O último dígito da soma é 4. Portanto, o navio tem que estar na coluna 4. Ao conhecer a coluna, você deve adivinhar qual dos navios naquela coluna é o desejado. Essa técnica é chamada “hashing” porque os dígitos são “espremidos” (do inglês, “hashed”) uns contra os outros.

  2. Agora jogue usando esta nova estratégia de busca. Você pode jogar mais de um jogo usando a mesma folha – basta escolher colunas diferentes.

(Note que, diferentemente de outros jogos, as folhas reservas 3A’ e 3B’ devem ser usadas em pares, porque o padrão dos navios nas colunas deve ser correspondente).

Discussão

  1. Colete e discuta as pontuações como antes.

  2. Quais navios foram achados mais rapidamente? (Aqueles que estão sós em suas colunas). Quais foram mais difíceis de serem encontrados? (Aqueles em colunas que continham muitos outros navios.)

  3. Qual dos três algoritmos de busca é o mais rápido? Por quê?

Quais são as vantagens de cada um dos três diferentes modos de busca? (A segunda estratégia é mais rápida do que a primeira, mas a primeira não requer que os navios estejam ordenados. A terceira estratégia é geralmente mais rápida que as demais, mas, é possível que seja bastante lenta em algumas situações. (No pior caso, se todos os navios estiverem na mesma coluna, esta será tão lenta quanto a primeira estratégia.))

Atividades de Extensão

  1. Faça com que as crianças construam seus próprios jogos usando os três formatos. Para o segundo jogo, elas devem colocar os números em ordem crescente. Pergunte como elas dificultariam ainda mais o jogo de busca baseado em hashing. (O jogo torna-se mais difícil quando todos os navios estão na mesma coluna.) Como você faria para torná-lo o mais fácil possível? (Você deve tentar colocar o mesmo número de navios em cada coluna.)

  2. O que aconteceria se o navio procurado não existisse? (No jogo de busca linear seriam necessários 26 tiros para mostrar isso. Com a busca binária seriam necessários 5 tiros. Quando se utiliza o sistema de hashing, isso depende de quantos navios presentes na coluna em questão.)

  3. Usando a estratégia de busca binária, quantos tiros seriam necessários se houvessem cem posições (cerca de 6 tiros), mil posições (cerca de 9 tiros), ou um milhão (cerca de 19 tiros)? (Note que o número de tiros aumenta muito lentamente se comparado ao número de navios. Um tiro extra é necessário cada vez que o número de navios dobra. Assim, diz-se que o número de tiros é proporcional ao logaritmo do número de navios.)

Folhas de Atividades e Materiais Adicionais

Você também pode baixar todas as folhas de atividade e materiais adicionais em formato editável aqui.

De que se trata tudo isso?

Computadores armazenam grandes quantidades de informação e precisam ser capazes de vasculhar essas informações rapidamente. Um dos maiores problemas de busca do mundo é tratado pelos motores de busca da internet, os quais devem pesquisar bilhões de páginas em uma fração de segundo. O dado informado ao computador para a pesquisa, tal como uma palavra, um número de código de barras ou o nome de um autor, é chamado de chave de busca.

Computadores podem processar informações muito rapidamente e você poderia pensar que para encontrar algo eles deveriam simplesmente começar no início de onde os dados estão armazenados e procurar até a informação desejada ser encontrada. Isto é o que fizemos no jogo de busca linear. Entretanto, esse método é muito lento – até mesmo para os computadores. Por exemplo, suponha um supermercado que tenha 10 mil produtos diferentes em suas prateleiras. Quando um código de barras é lido numa compra, o computador deve procurar entre 10 mil números para encontrar o nome e o preço do produto. Mesmo que leve apenas um milésimo de segundo para checar cada código, seriam necessários 10 segundos para vasculhar toda a lista. Imagine a demora para processar as compras de uma família!

Uma estratégia melhor é a busca binária. Nesse método, os números estão ordenados. Verificando o item do meio da lista identificará em qual metade a chave de busca está. O processo é repetido até o item ser encontrado. Retornando ao exemplo do supermercado, os 10 mil itens podem ser pesquisados em quatorze sondagens, levando em torno de duzentos milissegundos, quase imperceptível.

Uma terceira estratégia para encontrar os dados se chama hashing. Nesta abordagem, a chave é manipulada para indicar exatamente onde encontrar a informação. Por exemplo, se a chave de busca for um número de telefone, você poderia somar todos os dígitos do número e pegar o resto da divisão da soma por 11. Nesse aspecto, uma chave de hash é parecida com os dígitos verificadores discutidos na Atividade 4 - porções de dados cujo valor depende do outro dado sendo processado. Em geral, o computador encontrará o que procura rapidamente. Há uma pequena chance de que diversas chaves levem ao mesmo local e, neste caso, o computador precisará procurar nestes locais até encontrar a informação pesquisada.

Programas de computador geralmente usam alguma variante da estratégia de hashing para a busca, a menos que seja necessário que os dados estejam ordenados ou se não for possível aceitar respostas lentas em algumas circunstâncias.

Para saber mais

O vídeo Que saco!, da coleção Matemática Multimídia, discute um processo análogo ao do jogo de busca binária, só que usando uma balança de braço para descobrir qual saco tem peso diferente dos demais.