Tipos de busca

Xogar ao escondite, xogar a Afundir a flota ou a outros xogos onde hai que desenvoler unha estratexia para atopar obxectos é un dos retos que nos gustan ás persoas. Pero, como lle explicamos a unha máquina como buscar cousas de maneira eficiente?.  A continuación propoñemos unha serie de xogos que vos axudarán a afondar nestes conceptos.

Primeiro xogo: Adiviña quen ten a carta

 

O xogo trata de adiviñar quen ten unha carta determinada dunha baralla facendo o mínimo número de preguntas. A persoa que debe adiviñar ten 5 chuches que poderá empregar como pago polas respostas. Poderá quedarse cos chuches restantes.

 

baralla española de cartas
CC BY-SA 3.0   Basquetteur

  • Escollemos 15 persoas e asignámoslle unha carta cun número aleatorio a cada unha.

  • Outra persoa debe adiviñar quen ten un número determinado. A esta persoa se lle dan 5 caramelos, que debe empregar como pago por cada pregunta que faga para adiviñar quen ten o número pedido (en canto acerte pode quedar co resto dos caramelos).

  • Repítese o xogo, pero desta vez ordénanse ás persoas de menor a maior carta. Agora a persoa que debe adiviñar pode empregar unha estratexia: dar un caramelo á persoa do medio. Repetindo esta estratexia debería gastar so 3 caramelos.

  • Podemos rematar xogando ao clásico xogo de Afundir a flota,  pensando en cales son as estratexias de busca que empregamos.

 

 

 

 


Segundo xogo: A serpe quere comer

Para realizar este xogo imos dividirnos en tres grupos, de maneira que cada un dos grupos tratará de alimentar á súa serpe buscando os vermes (ou cempés, dependendo do gusto das serpes).Cada grupo empregará diferentes técnicas de busca, que poremos en común cando remato o xogo.

Organizamos cada  grupo en parellas aos que lles repartiremos as tarxetas A e B (coa advertencia de que non ensinen a tarxeta aos seus compañeiros).

O xogo consiste en adiviñar en que letra está posicionado o verme cun número determinado:

  • Empeza o xogador A, sinalando un dos vermes e dicindo en alto o seu número. O xogador B terá que ir tenteando letras ata adiviñar onde estaba o verme indicado. Cada vez que falla a adiviña terá que apuntarse un punto.
  • Tócalle a quenda  ao xogador B, que repite a estratexia do primeiro xogador.
  • Gañará o xogador que teña adiviñado onde están todos os vermes coa mínima puntuación .

A diferenza entre os tres grupos será o tipo de tarxetas que lles repartimos. Todas as tarxetas poderás descargalas nesta ligazón

1º Subgrupo: Tarxetas de busca lineal

A busca lineal consiste en ir tenteando onde está o verme de maneira lineal, un a un, sen ningunha pista. Como este método de busca é o máis lento, en xeral, para equilibrar os tempos con outros subgrupos poderemos limitar a busca ao número de vermes que igualen tempo cos outros subgrupos.

 

2º Subgrupo: Tarxetas de busca binaria

Neste caso hai que advertir aos xogadores que os números están ordenados de menor a maior, por tanto para acertar non deben facer un tenteo ao chou, senón que deberían comezar polo do medio e dividir en dous (binario) as posibilidades e así repetidamente ata atopar a letra.

(Dependendo do tempo que dispoñamos podemos deixar que xoguen unha partida libremente e que reflexionen na estratexia que seguiron).

 

3º Subgrupo: Tarxetas de busca por transformación de claves (hashing)

Neste caso a cuestión  é saber que os vermes están ordenados en diferentes fendas, segundo unha clave. Na ligazón coas tarxetas podedes atopar dúas claves diferentes:

  • As tarxetas de clave SUMA, nas que para saber en que fenda están so hai que sumar todos números do verme e quedarse coa última cifra do resultado.
  • As tarxetas en clave IMPAR, nas que para saber en que fenda están os vermes so hai que sumar os números impares e quedarse coa última cifra.

Posta en común dos tres tipos de procura   

Cada subgrupo expón aos outros subgrupos en que consistía o seu xogo, respondendo ás seguintes preguntas:

  1. Que estratexia empregou a persoa gañadora?

  2. Cales son os barcos máis rápidos de achar? (so haberá diferencia na busca por clave)

  3. Cantos puntos obtivo a persoa gañadora?

  4. Na segunda partida. Aprendiches algo da estratexia da túa parella ou dos teus propios erros?.

  5. Describe detalladamente o proceso de busca seguido.

Unha vez expostos os tres métodos de busca, reflexionamos cal é o máis rápido e  cales son as vantaxes e desvantaxes dos tres métodos (o segundo é máis rápido que o primeiro, pero precisa de ter os vermes ordenados, a terceira estratexia é máis rápida, en xeral, pero pode tocar que haxa moitos vermes na mesma fenda e entón tornase igual que a primeira).

No caso da busca binaria podemos tamén facer ver cal será o máximo número de intentos que hai que facer para localizar un verme, en función do número total de vermes que teñamos (se temos 100 vermes a busca é 7, para 1000  o máximo número é 10 e para 10000 os intentos so aumentan a 14. ( En xeral, para n vermes o máximo número de intentos sería log2n  (lembramos que  n = 2nº intentos ).  Deixamos unha ligazón cunha calculadora para seguir probando e comprobar que o número de intentos non aumenta ao mesmo tempo que o número de vermes senón moito menos.


3º Xogo : Realizar taboleiros para busca con clave.

Neste caso  deberás realizar os teus propios pares de taboleiros, pero sen especificar a clave que vas empregar, de xeito que sexa o propio xogador o que teña que adiviñala primeiro, antes de poñerse a xogar.

modelo da tarxeta de transformación por clave

 

Neste caso primeiro haberá que descifrar un algoritmo, podemos aproveitar para introducir o concepto de Criptografía, no que é habitual empregar o método de busca por clave (hashing).

Basado en: https://classic.csunplugged.org/