Atividade 11: Caça ao Tesouro — Autômatos de Estados Finitos
Apresentação
Frequentemente programas de computador precisam processar uma sequência de símbolos como letras ou palavras em um documento, ou até mesmo o texto de outro programa. Cientistas da computação frequentemente usam autômatos de estados finitos para isso. Um Autômato de Estados Finitos (AEF) segue um conjunto de instruções para verificar se o computador reconhecerá a palavra ou conjunto de símbolos. Trabalharemos com algo equivalente a um AEF: mapas do tesouro!
Disciplinas e conteúdos relacionados
- Computação: introdução a programação de computadores.
Habilidades
(EF07MA05) Resolver um mesmo problema utilizando diferentes algoritmos.
(EF07MA07) Representar por meio de um fluxograma os passos utilizados para resolver um grupo de problemas.
(EM13MA315) Investigar e registrar, por meio de um fluxograma,quando possível, um algoritmo que resolve um problema.
Nível de Ensino
- Anos Iniciais e Finais do Ensino Fundamental.
Material
Você precisará de:
Um conjunto de Cartas para Demonstração;
Um conjunto de Cartas da Ilha.
Faça uma cópia de cada um dos conjuntos de cartas e recorte-as. Dobre na linha pontilhada e cole, de modo que, a frente das cartas tenha o nome da ilha, e o fundo tenha as instruções. As instruções devem ficar escondidas de quem estiver tentando desenhar o mapa!
Cada criança precisará de:
Existem atividades opcionais de extensão para as quais as crianças precisarão de:
Ilha do Tesouro
Introdução
Seu objetivo é encontrar a Ilha do Tesouro. Navios piratas amigos navegam por um conjunto fixo de rotas entre as ilhas em uma parte do mundo, oferecendo carona aos viajantes. Cada ilha possui dois navios de partida, A e B, que você pode escolher para viajar. Você precisa encontrar o melhor caminho para a Ilha do Tesouro. Em cada ilha na qual chegar, você pode escolher um dos navios A ou B (não ambos). A pessoa na ilha lhe dirá para onde vai o navio, mas os piratas não têm um mapa de todas as ilhas disponíveis. Use seu mapa para saber onde você está indo e em quais navios você já viajou.
Demonstração
Nota: A atividade usará um mapa diferente.
Use um projetor ou desenhe no quadro o diagrama das três ilhas como abaixo:
Faça uma cópia das cartas e dê uma carta a cada criança. Note que as rotas nessas cartas são diferentes daquelas na atividade principal.
Começando da Ilha dos Piratas, escolha o navio A. A criança deve direcioná-lo para a Baía do Naufrágio. Anote a rota no mapa. Na Baía do Naufrágio, escolha o navio A novamente. Você voltará a Ilha dos Piratas. Anote isso no mapa. Agora escolha o navio B. Anote isso no mapa. Essa rota vai para a Ilha dos Mortos, onde você ficará preso!
Seu mapa final deverá estar assim:
Atividade
Escolha sete crianças para serem as “ilhas”. As crianças segurarão as cartas identificando suas ilhas, com as instruções secretas no verso. Posicione-as aleatoriamente pela sala. O restante das crianças ficará com mapas em branco e terão que navegar da Ilha dos Piratas para a Ilha do Tesouro, marcando isso cuidadosamente em seus mapas. (Uma boa prática é enviar uma criança por vez para que elas não consigam ouvir as rotas de antemão.)
Os primeiros a terminar devem tentar encontrar mais de uma rota.
O mapa completo é o seguinte:
Discussão
Qual é a rota mais rápida? Qual seria uma rota muito lenta? Algumas rotas podem ter laços (loops). Você pode encontrar um exemplo disso? (Por exemplo, BBBABAB e BBBABBABAB, ambos chegam a Ilha do Tesouro.)
Autômatos de Estados Finitos
Outra maneira de desenhar um mapa seria:
As ilhas são representadas por círculos numerados, e a ilha final (com o tesouro) tem dois círculos. Quais rotas podemos usar para chegar a última ilha?
Nota: o 1º mapa termina no círculo duplo (ilha 2) somente se a sequência tem um numero ímpar de As (por exemplo, AB, BABAA, ou AAABABA).
O 2º mapa só alcança o círculo duplo com uma sequência alternada de As e Bs (AB, ABAB, ABABAB, …).
O 3º mapa requer que a sequência contenha no mínimo um B (as únicas sequências que não servem são A, AA, AAA, AAAA, …).
Folhas de Atividades e Materiais Adicionais
Você também pode baixar todas as folhas de atividade e materiais adicionais em formato editável aqui.
Do que se trata tudo isso?
Autômatos de estados finitos são usados na Ciência da Computação para ajudar um computador a processar uma sequência de caracteres ou de eventos.
Um exemplo simples é quando você liga para algum lugar e escuta a mensagem “Tecle 1 para isso… Tecle 2 para aquilo… Tecle 3 para falar com um dos atendentes.” As teclas pressionadas são entradas para um autômato de estados finitos do outro lado do telefone. O diálogo pode ser bem simples ou muito complicado. Algumas vezes, você fica andando em círculos porque existe um laço específico no autômato. Se isso ocorre, então é um erro no projeto do sistema — e isso pode ser extremamente frustrante para quem liga!
Outro exemplo é quando você saca dinheiro no caixa eletrônico do banco. O programa no computador do caixa guia você através de uma sequência de eventos. Dentro do programa, todas as possíveis sequências estão guardadas como um autômato de estados finitos. Toda tecla pressionada leva o autômato a um novo estado. Alguns dos estados têm instruções para o computador como “libere R$100,00 em dinheiro” ou “Imprima um extrato” ou “Ejete o cartão”.
Alguns programas de computador lidam realmente com frases em português usando mapas como os da página 97. Eles podem tanto gerar quanto processar frases digitadas pelos usuários. Nos anos sessenta, um cientista da computação escreveu um programa famoso chamado “Eliza” (em referência à Eliza Dolittle) que conversava com pessoas. O programa fingia ser um psicoterapeuta e fazia perguntas do tipo: “Fale sobre a sua família” e “Prossiga”. Embora o programa não “entendesse” nada, era suficientemente convincente—e seus usuários humanos eram suficientemente ingênuos—para que certas pessoas acreditassem estar conversando com um psicoterapeuta humano.
Embora os computadores não entendam muito bem a linguagem natural, eles podem rapidamente processar linguagens artificiais. Um tipo importante de linguagem artificial é a linguagem de programação. Os computadores usam autômatos de estados finitos para ler programas e traduzi-los para a forma elementar de instruções do computador, as quais podem ser “executadas” diretamente pelo computador.
Para saber mais
O site computacional.com.br traz uma atividade que aborda o mesmo tema, mas com os personagens da Turma da Mônica.
Soluções e dicas
O Misterioso Jogo da Moeda (pág. 98)
O misterioso jogo da moeda usa o seguinte mapa para jogar as moedas:
Se você seguir esse mapa, verá que as duas primeiras de cada três moedas jogadas produzem o mesmo resultado.