Atividade 22: Jogo da Desfragmentação

Apresentação

Esta atividade simula o processo de desfragmentação de um disco rígido, uma operação que ocorre nos bastidores de todo computador moderno, que é computacionalmente desafiadora e que, meesmo assim, pode ser entendida por crianças de todas as idades.

Disciplinas e conteúdos relacionados

Habilidades

Nível de Ensino

Material

O Jogo da desfragmentação

Introdução

O objetivo desse jogo é agrupar as fichas do mesmo tipo de modo que, dentro de cada grupo, elas estejam em ordem com o menor número de movimentos possível.

Para realizar o jogo, a memória do computador é representada por uma sequencia de quadradinhos que podem estar vazio (em branco) ou ocupados por uma ficha preenchida por uma letra e uma cor. Fichas da mesma cor representam partes de uma mesmo arquivo. As letras dentro de um grupo de fichas da mesma cor representam a ordem em que as partes daquele arquivo devem ser posicionadas.

Exemplo

No cenário abaixo, a memória tem 14 espaços. O grupo PQRS já está junto e na ordem, o grupo ABCD está junto mas não em ordem e, por fim, o grupo XYZ não está junto. Além disso, note que os dois primeiros espaços estão disponíveis, assim como o último.

Uma possível solução para esse cenário pode ser obtido movendo a ficha Z para a última posição. Depois, seria necessário inverter as fichas C e D, mas não podemos fazer isso diretamente, precisamos mover a ficha C para um espaço vazio (o primeiro, por exemplo) aí sim movemos a ficha D para onde estava a C e terminamos movendo a ficha C para o espaço após a ficha B (que antes era ocupado por D).

O resultado é esse:

Para poder mostrar a sua solução, é necessário registrar os movimentos feitos usando a letra que identifica cada ficha e o número da posição para onde cada uma foi movida:

Z → 14, C → 1, D → 11, C → 10

Nesse exemplo, foram necessários 4 movimentos. Note que essa não é a única solução possível e que não tem problema deixar espaço em branco entre os blocos, a menos que você opte pela regra adicional que será apresentada a seguir. Também não é necessário respeitar nenhuma ordem entre os diferentes blocos.

Jogando

Para jogar, os alunos deverão recortas as fichas e usar a folha de atividades para posicionar as fichas na "memórias para testes" começando com a "situação inicial" e registrar os movimentos realizados logo abaixo.

A folha de atividades traz duas situações iniciais diferentes para seus estudantes, mas é possível criar novas situações iniciais com algumas variações que serão explicadas abaixo.

Variações e extensões

As variações simples que podem ser adotadas pelo professor para criar mais desafios para seus estudantes são: aumentar ou diminuir o tamanho da memória; aumenar ou diminuir o número de espaços vazios na memória, aumentar ou diminuir a quantidade de arquivos (isso demanda novas fichas e novas cores para identificar os diferentes arquivos) e aumentar ou diminuir o tamanho dos arquivos (isso também demanda novas fichas).

Além dessas variações, sugerimos uma regra adicional que pode ser usada para tornar o desafio mais difícil. Pessoalmente, sugiro que essa regra seja usada com estudanets dos Anos Finais do Ensino Fundamental,c aso contrário o jogo pode parecer simples demais. A regra é:

Regra adicional: todos os espaços vazios devem ficar acumulados no final da memória.

Essa regra aumenta substancialmente o número de movimentos necessários e, assim, deve aumentar a intensidade da busca por soluções cada vez melhores.

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?

Cada cartão colorido representa um bloco de informação a ser alocado em um disco rígido, e cartões da mesma cor representam blocos que compõem um mesmo arquivo. O computador funcionará melhor se os blocos de um mesmo arquivo estiverem todos em sequência e em ordem. Também é desejável ter grandes lacunas de espaço vazio, em vez de muitos espaços pequenos no disco, pois isso evita desperdiçar os blocos não utilizados ou ter que dividir os arquivos entre os blocos vazios dispersos.

O disco fica fragmentado, ou seja, com blocos de informação fora de ordem e com blocos vazios espalhados, quando os arquivos são excluídos ou têm seu tamanho alterado. Isso ocorre naturalmente com o uso de um computador. Por exemplo, suponha que você esteja trabalhando em dois documentos de texto ao longo de um período de algumas semanas. Toda vez que um dos documentos fica significativamente maior, outro bloco será alocado para ele no disco rígido. Mas então, o outro documento pode ficar mais longo e ser alocado no próximo bloco. Assim, você acaba com blocos para os dois documentos misturados um com o outro! Então, se um dos documentos for excluído, haverá espaços vazios no disco alternados com blocos do arquivo que não foi apagado. Isso pode ficar bastante confuso!

Em alguns sistemas operacionais, de tempos em tempos, o usuário precisa "desfragmentar" explicitamente o disco para melhorar o desempenho, e isso pode levar várias horas. Outros sistemas tentam ser mais inteligentes sobre como alocam os blocos, diminuindo a necessidade de desfragmentações explícitas. Esse problema se torna ainda mais complexo em "Máquinas Virtuais" (usadas para "Computação em Nuvem"), que não fornecem acesso direto a um disco, mas simulam um computador e, portanto, simulam o acesso ao disco também.

Os cientistas da computação têm que trabalhar muito para minimizar a necessidade de fragmentação e para desenvolver métodos eficientes para desfragmentar discos fragmentados sem usar muito tempo de processamento para isso. A atividade proposta simula uma desfragmentação e o objteivo de realizá-la com o menor número de movimentos tenta simular a busca por métodos eficientes.

Versão plugada

O tema desta atividade foi usado no Desafio 03 da ANPMat e, por isso, foram desenvolvidas páginas interativas onde o usuário pode fazer os movimentos para desfrag,mentar alguns discos dados.

Na lista abaixo, você pode acessar os quatro discos disponíveis e tentar desfragmentá-los com o menor número de movimentos possível.

Importante: para essa versão plugada, a desfragmentação só é considerada completa se todos os espaços em branco estiverem no final do disco.