O Desafio ANPMat é uma nova ação que a ANPMat está desenvolvendo com o intuito de aumentar sua interação com outros professores de matemática da educação básica. Nela, periodicamente, serão propostos desafios e discussões sobre temas matemáticos com potencial para instigar a curiosidade de professores e alunos, além de propor reflexões relacionadas ao ensino e à aprendizagem dos temas abordados. Será também uma oportunidade para os professores, alunos e demais amantes da Matemática participarem ativamente das atividades da ANPMat, por meio do compartilhamento de seus conhecimentos e experiências.
Desafio 3: Desfragmentação
Desafio 2: Lei de Benford
Desafio 1: Xadrez 960
Você já ouviu falar em desfragmentação de disco?
Se você usou computadores na década de 1990, muito provavelmente se lembra da necessidade de deixar o seu computador desfragmentando o disco rígido noite a fora de vez em quando.
Essa ação era necessária porque a velocidade de acesso a um disco fragmentado era muito inferior a de um disco desfragmentado e o funcionamento de sistemas operacionais como o Windows inevitavelmente faziam com que os discos ficassem fragmentados.
Mas o que isso significa? Ao salvarmos informações em um disco rígido, pedaços de um mesmo arquivo podem acabar sendo gravados em regiões distantes ou mesmo fora de ordem. Isso é esperado, já que podemos iniciar um arquivo, gravá-lo no disco, iniciarmos um segundo arquivo, que vai acabar sendo gravado no espaço adjacente ao primeiro, e depois voltarmos ao primeiro acrescentando mais conteúdo. Isso faz com que o primeiro arquivo fique dividido em dois pedaços separados pelo segundo arquivo, como na Figura 1.
Mais ainda, se apagamos um arquivo antigo, teremos um espaço livre no disco que pode acabar sendo preenchido com uma nova parte de um outro arquivo, bagunçando ainda mais a ordem das coisas.
Desfragmentar o disco significa justamente reordenar o conteúdo dos pedaços de memória de modo a agrupar e ordenar os pedaços de um mesmo arquivo, fazendo com que a leitura do disco seja mais rápida.
Porém, desfragmentar um disco pode exigir muitas ações! Por exemplo, a Figura 2 mostra um disco fragmentado com 3 arquivos (laranja com 3 trechos, verde com 2 trechos e bege com 2 trechos) e três espaços em branco.
Gostaríamos que ele ficasse como mostrado na Figura 3: pedaços de um mesmo arquivo juntos e em ordem e, além disso, com todos os espaços livres no final. Note que a ordem entre os arquivos não é importante, ou seja, também seria considerada desfragmentada uma configuração que começasse com o arquivo verde.
Mas para desfragmentar um disco, a única ação permitida é mover o conteúdo de um espaço de memória para um espaço livre.
Por exemplo, partindo da situação mostrada na Figura 2, podemos fazer o movimento 4→7, obtendo o disco mostrado na Figura 4, mas não poderíamos fazer a troca 3→6 diretamente, pois isso significaria perder o conteúdo do espaço 6 da memória.
A desfragmentação de discos é um processo necessário até hoje em alguns dispositivos e ainda não se conhece um algoritmo capaz de realizá-la sempre com o menor número de movimentos possível, o que economizaria processamento e energia. Esse é o seu desafio!
Nos links abaixo, você pode interagir com alguns discos fragmentados e tentar desfragmentá-los com o mínimo de movimentos.
Disco 1 Disco 2 Disco 3 Disco 4
Dessa vez, o desafio da ANPMat não vai receber vídeos com as soluções, mas vai convidar estudantes e professores a compartilharem suas soluções para cada um dos discos no nosso perfil do Instagram.
Boa desfragmentação!