Apresentação
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 Disco 5
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!
Encerramento
Sobre o desafio
Este desafio foi inspirado na atividade The Defrag Game, da clássica coleção de atividades CSUnplugged. A proposta da coleção é oferecer atividades desplugadas, ou seja, que podem ser feitas sem o uso de computadores, mas que explorem temas, problemas ou conceitos da Ciência da Computação de forma acessível à Educação Básica e sem depender de conhecimentos técnicos específicos por parte do professor.
Recentemente, a coleção ganhou uma versão completa em português, traduzida e adaptada, com mais de 20 atividades, algumas delas relacionadas à Matemática. Todo o conteúdo pode ser acessado em desplugada.ime.unicamp.br.
Para o desafio, “replugamos” a atividade, oferecendo um ambiente interativo em que era possível mover as peças digitalmente e verificar quantos movimentos foram necessários para desfragmentar alguns discos.
No exemplo acima, o disco 4 foi desfragmentado com exatamente 7 movimentos.
Se você ainda não tentou resolver os 5 discos que criamos, acesse mais.mat.br/defrag/, leia as regras da desfragmentação e resolva cada um dos discos. Se conseguir, poste no nosso Instagram a sua solução e veja se a sua foi a melhor até o momento.
Por que desfragmentar é importante
Esse processo é importante porque alguns discos de armazenamento de dados são lidos mais rapidamente se os dados armazenados estão desfragmentados, ou seja, todos os pedaços que compõem um arquivo estão gravados próximos e em ordem. Isso se traduz em ganho de tempo na execução de rotinas computacionais.
Apesar de relevante até hoje, não se conhece um algoritmo que desfragmente um disco qualquer com o menor número de movimentos possível.
Relações
Na verdade, esse problema se encaixa em uma categoria muito maior de problemas chamada “packing problems” que, em essência, procura por maneiras ótimas de armazenar um conjunto de objetos em contêineres com tamanhos determinados. As variações são quase infinitas: podemos considerar um ou mais contêineres, contêineres e objetos com tamanhos variados, limitações sobre a ordem em que os objetos podem ser armazenados ou até mesmo a forma geométrica dos objetos e contêineres.
Cada uma dessas variações leva a uma nova subcategoria de “packing problem”, podendo ter ou não aplicação prática direta ou ter relações mais próximas com computação ou matemática.
Essa família maior de problemas engloba até mesmo jogos simples como tetris (você já tinha pensado que o tetris consiste em encaixar objetos com formas variadas em um contêiner retangular deixando a menor quantidade de espaço vazio preso entre os objetos?) e jogos do tipo “water sort” em que temos que organizar líquidos em tubos.
Além desses jogos, outras perguntas relacionadas a essa categoria de problemas podem ser discutidas em aulas de Matemática na Educação Básica, como o experimento Empacotamento de latas da coleção Matemática Multimídia.
Neste experimento, a pergunta que o aluno deve investigar é: como devemos arranjar um conjunto de 6 latas de forma que a quantidade de material necessário para embalá-lo seja a menor possível?
Computação na Educação Básica
Nosso objetivo com este desafio era incentivar a discussão de um problema inspirado por uma temática da computação que pode ser discutida em aulas da Educação Básica sem que seja necessário conhecimento técnico específico por parte do professor.
A atividade disponível na coleção Computação Desplugada propõe uma abordagem para usar o jogo da desfragmentação em sala de aula apenas com papel e tesoura, traz algumas folhas de atividade que podem ser usadas pelos alunos e uma discussão final aprofundando um pouco o tema da desfragmentação de discos.
Se você gostou da proposta, navegue pela coleção e conheça essa e outras atividades disponíveis.