O problema do teste de Singapura

De repente, não se fala de outra coisa...
Num exame para miúdos de 14 anos, em Singapura, saiu o seguinte problema:

Albert e Bernard ficaram amigos de Cheryl, e querem saber a data do seu aniversário. A Cheryl faz uma lista de 10 datas possíveis

Maio: 15, 16, 19
Junho: 17, 18
Julho: 14, 16
Agosto: 14, 15, 17

e diz, separadamente, a Albert o mês do seu aniversário e a Bernard o dia.
Albert diz: não sei qual é o dia, mas sei que o Bernard também não sabe.
Bernard diz: inicialmente, não sabia, mas agora já sei.
Albert conclui: então também sei!
Qual é a data de aniversário de Cheryl?

(solução segue dentro de momentos...)

Vamos então a isso!
Albert diz: não sei qual é o dia, mas sei que o Bernard também não sabe.
Albert sabe o mês. Se o mês fosse Maio ou Junho, não podia ser peremptório relativamente ao facto de Bernard também não saber, pois em Maio há o dia 19 e em Junho o dia 18, que só ocorrem nesses meses. Então o mês é Julho ou Agosto.
Bernard diz: inicialmente, não sabia, mas agora já sei.
Bernard sabe o dia. Se fosse 14, não podia saber a data, pois podia ser em Julho ou Agosto. Assim, é 16 de Julho ou 15 ou 17 de Agosto.
Albert conclui: então também sei!
Albert sabe o mês! Então o dia é 16 de Julho, pois se fosse um dia de Agosto ainda restariam duas possibilidades para a data!

Torre de Hanói

Um problema que muitas vezes se usa para ilustrar o poder da recursividade é o da torre de Hanói.
Segundo a lenda, numa cidade no centro do mundo, um monge realiza a tarefa de mover 64 discos de um pilar para outro, usando apenas um pilar auxiliar, e de acordo com duas regras simples: só pode mover um disco de cada vez e nunca pode colocar um disco sobre outro de menor diâmetro. Quando terminar a tarefa, será o fim do mundo...

Este problema pode ser analisado sob o prisma da recursividade. Realmente, se soubermos resolver o problema para n-1 discos, sabemos facilmente resolvê-lo para n discos!
Como? Aplicando a solução para os n-1 discos duas vezes: primeiro, movendo todos os discos menos o de maior diâmetro para o pilar auxiliar, em seguinda movendo o disco de maior diâmetro para o pilar de destino, e finalmente movendo os n-1 discos que estão no pilar auxiliar para  o pilar de destino...
E já está? Estaria se soubéssemos efectivamente mover os n-1 discos. E se não soubermos? Segundo a mesma lógica, bastaria saber mover n-2 discos, etc.
Repetindo o raciocínio, devemos chegar ao ponto em que basta saber mover 2 discos, e isso sabemos facilmente, com 3 movimentos: mover o disco de menor diâmetro para o pilar auxiliar, mover o disco de maior diâmetro para o pilar de destino, e finalmente mover disco de menor diâmetro do pilar auxiliar para o pilar de destino.
E quantos movimentos serão necessários para mover os 64 discos? Se representarmos por mov(n) o número de movimentos necessários para transportar n discos, ter-se-á:

mov(2) = 3
mov(3) = mov(2) + 1 + mov(2) = 3 + 1 + 3 = 7
mov(4) = mov(3) + 1 + mov(3) = 7 + 1 + 7 = 15 = 2^4 - 1
mov(5) = mov(4) + 1 + mov(4) = 15 + 1 + 15 = 31 = 2^5 - 1
...
mov(64) = 2^64 -1

o que dá exactamente 18 446 744 073 709 551 615 movimentos! Se o monge conseguisse realizar um movimento por segundo, demoraria aproximadamente 5849 milhões de séculos para concluir a tarefa...

Ora aqui está outro belo tema para uma página Web a desenvolver por alunos do 7º ano do nosso ensino secundário.

PACC

O selecionador nacional convocou 17 jogadores para o próximo jogo de futebol. Destes 17 jogadores, 6 ficarão no banco como suplentes. Supondo que o selecionador pode escolher os seis suplentes sem qualquer critério que restrinja a sua escolha, poderemos afirmar que o número de grupos diferentes de jogadores suplentes (A) não se relaciona com o número de grupos diferentes de jogadores efetivos. (B) é superior ao número de grupos diferentes de jogadores efetivos. (C) é igual ao número de grupos diferentes de jogadores efetivos. (D) é inferior ao número de grupos diferentes de jogadores efetivos.
Aqui está um exemplo de uma pergunta mal escolhida e mal formulada.

Imagem retirada de aqui.

Na cabeça do autor da pergunta está aquela ideia simples de que C(n, m) = C(n, n - m), isto é, de que o número de combinações possíveis de m elementos retirados de um conjunto de n é exactamente igual ao número de combinações dos n - m não retirados: C(17, 6) = C(17, 11). Qualquer treinador de futebol sabe: retirados os suplentes, ficam os efectivos.
O problema é que no futebol os jogadores ocupam posições no campo, isto é, com 11 jogadores é possível fazer mais que uma equipa, trocando-os de posição. Não se trata de combinações, mas de arranjos! E na verdade A(17, 11) é maior que A(17, 6), pelo que, nesta óptica, a resposta certa seria a resposta (D), e não a resposta (C) como o IAVE propõe.
Ao perguntar o número de grupos, fica a dúvida. Grupo, é uma palavra dúbia, neste contexto. A sugestão de que se trata de futebol, e não corta-mato, por exemplo, sugere que a posição conta.
E isto não pode acontecer. E não é exemplo de pensamento computacional.
Tivesse eu realizado a prova e respondido (D), não me calava...

Miguel Zapata-Ros

Miguel Zapata-Ros, professor, educador, mestre, dos MOOC, e do pensamento computacional, está a publicar no seu blogue Pensamiento computacional y alfabetización digital / Computational thinking and computer literacy uma série de artigos sobre as dimensões do pensamento computacional absolutamente incontornável para quem se interessa por estes problemas.

Os primeiros artigos versam os tópicos

1. Porquê
2. Problema
3. Definição
4. Domínio teórico
5. Recursividade
6. Iteração
7. Tentativa-erro,

e a sua leitura é obrigatória, pelos conteúdos, pelo alinhamento de tópicos, pelas referências bibliográficas, pelos contributos que incorpora.
Daqui saúdo o Professor Miguel Zapata-Ros pelo seu trabalho notável.

A hora do código

A Khan Academy desafia os estudantes, os Pais e os professores a aprender a programar, seja a desenhar, através de páginas Web, ou da criação de bases de dados.

Desenho e páginas Web para os miúdos de 8 anos, bases de dados para os miúdos de 12 anos.
Criar espaço para o pensamento computacional, sem confundir com processamento de texto, folhas de cálculo, ou apresentações, ferramentas informáticas transversais, da vida corrente, presentes em todos os computadores, é absolutamente fundamental.
Apesar dos pequenos passos que têm sido dados, enquanto não se trabalhar a sério na formação de professores capazes de motivar os nossos miúdos para a descoberta do computador como ferramenta ao seu serviço, como máquina que podem programar para a execução de tarefas repetitivas ou complexas, ou para a realização de experiências de simulação, por exemplo, continuaremos a divergir do que está a acontecer em tantos outros países.

CodeWeek

De 11 a 17 de Outubro de 2014 decorre em toda a Europa a CodeWeek, um conjunto de eventos onde novos e velhos, aprendizes e mestres, vão experimentar formas de ensinar e aprender a usar computadores no seu dia a dia.
No âmbito desta iniciativa, estamos a organizar na Católica Braga um evento a que chamamos "Programar sem computadores", em que vamos brincar à programação com os mais novos, através de um conjunto de acividades divertidas em que todos poderão desempenhar os papéis de programador ou de computador, isto é, daquele que escreve os programas ou daquele que os executa.
O nosso espaço, o nosso dispositivo de entrada saída, o nosso écrã, será todo o campus da FaCiS,

onde os participantes se movimentarão na execução ou na criação de "programas" que proponham movimentos ou interacções com outros objectos existentes.
Estamos na fase de preparação do projecto, e aceitamos todas as sugestões que nos queiram fazer no sentido de valorizar o evento.
Falem-nos!

Pós-graduação

É oficial.
Estão abertas as pré-inscrições para a primeira edição da pós-graduação em Pensamento Computacional e Ensino de Informática, na Católica Braga

O desafio está lançado.
Venham aprender conosco!

Pensamento computacional e ensino de Informática

Muitos professores de Informática não tiveram a formação necessária para trabalhar, e muito menos para ensinar a trabalhar, com as ferramentas informáticas do mundo de hoje, para compreender o mundo da Informática em toda a sua extensão, para perceber o papel da Informática na economia, para despertar nos jovens o gosto pelas questões informáticas.
Esta transformação de mentalidades é muito complexa, não se consegue com um simples clique, exige um enorme esforço de "desaprender", de ver a realidade de uma forma diferente, com um certo distanciamento, como algo com que temos de interagir todos os dias, e de que a tecnologia é apenas uma parte.
Basta olharmos para o modo intuitivo como jovens interagem com os telemóveis, com os jogos, com as bilheteiras automáticas, com uma quantidade de dispositivos à nossa volta, para o percebermos.
Por onde começar, então?
Não é fácil elaborar uma proposta segura. Pode ver-se o que outros fazem, pode olhar-se para as aplicações informáticas que nascem todos os dias, pode partir-se da nossa própria experiência, mas haverá sempre alguma incerteza.
Na Inglaterra, a iniciativa Computing at School tem vindo a dar muitas pistas, a Universidade de Manchester tem uma oferta de cursos para professores nesta área, e muitos outros existem, de que já falamos ou iremos falar.
Na minha opinião, um curso desta natureza poderia ser constituído por quatro módulos básicos,

• Python (programação sem enfeites),
• Informação, Computação e Redes (do bit à nuvem),
• Visualização e Análise de Dados e Redes,
• Projecto (Raspberry Pi/Android/iOS/Gephi),

ao longo de um semestre, que, uma vez concluídos com sucesso,  dariam a cada um uma base sólida para olhar para a Informática de uma outra forma e para abraçar novos desafios.
É só uma ideia. Alguém quer experimentar?
Reacções são bem vindas...