Redes de ordenação / Seja o mais rápido!

Ensinando Ciência da Computação sem o uso do computador

Conteúdo: Redes de Ordenação

Pag. 71 à 75

Seja o mais rápido!

Instruções para as crianças
            Esta atividade lhe mostrará como os computadores colocam números aleatórios em ordem, utilizando o que se chama de rede de ordenação.

1. Organizem-se em grupos de seis. Apenas uma equipe de cada vez pode utilizar a rede.

2. Cada membro da equipe pega um cartão numerado.

3. Cada membro fica em um quadrado no lado esquerdo (Entrada) da rede. Seus números
devem estar embaralhados.

4. Você se move ao longo das linhas marcadas e, ao chegar em um círculo, você deve
esperar outra pessoa chegar.

5. Quando outro membro da equipe chegar ao círculo no qual você está, vocês comparam
suas cartas. A pessoa com o menor número segue o caminho da esquerda. Se você tiver o
maior número na sua carta, tome o caminho à direita.

6. Você estará na ordem correta quando chegar ao outro extremo da rede.

Se uma equipe cometer um erro, as crianças devem recomeçar. Verifique se você
compreendeu o funcionamento de um nó (círculo) da rede, no qual o menor valor vai para
a esquerda e o outro valor vai para a direita. Por exemplo:

Variações

1. Quando as crianças estiverem familiarizadas com a atividade, use um cronômetro para
determinar quanto tempo cada equipe leva para chegar ao final da rede.

2. Use cartões com números maiores (por exemplo, os cartões de três dígitos da fotocópiamestre).

3. Elabore cartões com números maiores, os quais necessitarão de maior esforço para serem comparados, ou use palavras e as compare por ordem alfabética.

Atividades de Extensão

1. O que acontece se o menor for para a direita ao invés de ir para a esquerda e vice-versa? (Os números são ordenados em ordem inversa).

Será que a rede funciona se for utilizada ao contrário ? (Ela não funcionará

necessariamente e as crianças devem ser capazes de encontrar um exemplo de uma

entrada que saia na ordem errada.)

2. Tente desenhar redes maiores ou menores. Por exemplo, aqui está uma rede que ordena
apenas três números. As crianças devem tentar chegar a esta rede por conta própria.

3. Abaixo estão duas redes diferentes que ordenam quatro entradas. Qual é a mais rápida ? 

A segunda. Porque a primeira exige que todas as comparações sejam realizadas,

uma após a outra. A segunda tem algumas comparações sendo realizadas ao mesmo

tempo. A primeira rede é um exemplo de processamento em série enquanto que a segunda

utiliza processamento paralelo para executar mais rápido.

4. Tente fazer uma rede de ordenação maior.

5. As redes também podem ser usadas para encontrar o valor mínimo ou máximo das entradas. Por exemplo, aqui está uma rede com oito entradas e a única saída conterá o menor dos fatores da entrada (Os outros valores serão bloqueados na rede).

6. Quais procedimentos do cotidiano podem ou não ser acelerados utilizando paralelismo ? Por exemplo,cozinhar uma refeição seria muito mais lento utilizando apenas uma panela para cozinhar porque os itens teriam de ser cozidos um após o outro. Quais tarefas podem ser completadas mais rapidamente empregando mais pessoas? Quais
tarefas não podem ?

De que se trata tudo isso?

            Quanto mais usamos os computadores, queremos que estes processem as informações o mais rápido possível. Um jeito de aumentar a velocidade de um computador é escrever programas que usam menos passos de computação (como mostrado nas Atividades 6 e 7).
            Outra maneira de resolver problemas mais rapidamente é ter alguns computadores
trabalhando em diferentes partes de uma mesma tarefa ao mesmo tempo. Por exemplo, na
rede de ordenação de seis números, apesar de haver um total de 12 comparações para ordenar os números, até 3 comparações são feitas simultaneamente. Isso significa que o tempo requerido será o mesmo necessário para apenas 5 passos de comparação. Esta rede paralela ordena a lista mais que duas vezes mais rápido do que um sistema que realiza apenas uma comparação por vez.
            Nem todas as tarefas podem ser completadas mais rapidamente utilizando computação paralela. Fazendo uma analogia, imagine uma pessoa cavando uma vala de 10 metros de comprimento. Se 10 pessoas cavarem um metro da vala cada uma, a tarefa seria completada muito mais rapidamente. Por outro lado, a mesma estratégia não poderia ser utilizada para um buraco de 10 metros de profundidade - o segundo metro não é acessível até que o primeiro metro tenha sido cavado. Os cientistas da computação continuam ativamente tentando encontrar os melhores métodos para dividir problemas de forma que estes possam ser resolvidos por computadores trabalhando em paralelo.

Computer Science Unplugged