Quanto custa um algoritmo? Tempo, memória, energia e limites

Corrida de algoritmos de busca e ordenação, contagem de passos, o custo em energia de um data center e o que nenhum computador consegue resolver.

Metodologia ativa

Habilidades da BNCC

• EM13CO03Identificar e analisar o custo de algoritmos em tempo de execução, uso de memória e consumo de energia, comparando soluções para um mesmo problema. 📥 Baixar slides (PDF)
• EM13CO05Identificar os limites da Computação, distinguindo o que pode ou não ser automatizado, e os limites da mente humana na resolução de problemas. 📥 Baixar slides (PDF)

Objetivos de aprendizagem

• Comparar algoritmos para o mesmo problema pelo número de passos, pela memória usada e pela energia gasta.
• Explicar por que alguns algoritmos ficam inviáveis quando a entrada cresce.
• Reconhecer problemas que o computador não resolve ou não resolve em tempo útil, e o papel do julgamento humano.

Materiais

• Baralhos ou cartões numerados (1 por grupo)
• Cronômetro do celular
• Computadores para a Esteira da Ordenação e a Estante da Busca Binária
• Planilha para registrar passos

Desenvolvimento

Tempo total previsto: 100 minutos.

1. 10 minQuem acha primeiro?

   Dois voluntários procuram uma carta: um numa pilha embaralhada, outro numa pilha ordenada com busca binária. Contem os passos de cada um.

2. 25 minCorrida de ordenação

   Em grupos, ordenem 8, 16 e 32 cartas com seleção e com intercalação (merge sort), contando comparações. Registrem na planilha e façam um gráfico de passos por tamanho.

3. 15 minNo computador

   Na Esteira da Ordenação, comparem bolha, seleção e inserção com o contador de trocas. Discuta: e com um milhão de itens? Apresente a ideia de crescimento linear, quadrático e logarítmico sem fórmulas pesadas.

4. 15 minMemória e energia

   Mostre que guardar uma cópia ordenada gasta memória e que cada operação gasta energia. Use o recurso Data Center por Dentro para estimar o consumo de servidores e a água de resfriamento.

5. 25 minO que o computador não resolve

   Apresente três situações: o problema do caixeiro-viajante com 30 cidades (explosão de combinações), o problema da parada (nenhum programa decide se qualquer outro programa termina) e uma decisão ética (quem recebe uma vaga). Em grupos, classifiquem: computável e rápido, computável mas inviável, não computável, exige julgamento humano.

6. 10 minFechamento

   Cada grupo escreve uma frase: “Um algoritmo melhor importa quando…”. Retome os limites: velocidade não resolve tudo.

Avaliação

Avalie a planilha com os passos medidos e o gráfico, e a classificação das situações da última etapa com justificativa. Uma boa resposta liga o crescimento da entrada ao custo e diferencia problema difícil de problema impossível.

Acessibilidade e inclusão

Materiais relacionados