Informática · 10.º Ano · Pensamento Computacional e Algoritmia · 1o Periodo

Eficiência Algorítmica e Complexidade

Os alunos analisam criticamente diferentes abordagens para resolver o mesmo problema, focando na rapidez e nos recursos computacionais necessários.

• Aprendizagens Essenciais
• DGE: Secundário - Pensamento Computacional
• DGE: Secundário - Resolução de Problemas

Sobre este tópico

A eficiência algorítmica e a complexidade centram-se na análise crítica de diferentes abordagens para resolver o mesmo problema, com foco na rapidez de execução e no consumo de recursos computacionais. Os alunos do 10.º ano comparam algoritmos como a ordenação por inserção e por fusão, medindo o tempo de execução para conjuntos de dados crescentes. Esta análise revela como o volume de dados influencia o desempenho e destaca compromissos entre simplicidade do código e velocidade.

No Currículo Nacional, este tema integra o Pensamento Computacional e a Resolução de Problemas, promovendo competências como a avaliação de trade-offs e o raciocínio abstrato. Os alunos justificam escolhas algorítmicas baseadas em notação Big O, compreendendo que um algoritmo O(n²) pode ser inadequado para grandes inputs, enquanto O(n log n) escala melhor. Esta perspetiva prepara-os para programação real e otimização em contextos práticos.

A aprendizagem ativa beneficia particularmente este tema, pois simulações práticas e comparações em grupo tornam conceitos abstratos como complexidade temporal concretos e mensuráveis. Quando os alunos cronometram execuções reais ou simulam com dados físicos, internalizam trade-offs de forma intuitiva e colaborativa.

Questões-Chave

1. Compare diferentes algoritmos para o mesmo problema em termos de eficiência.
2. Avalie como o volume de dados afeta o desempenho de uma solução algorítmica.
3. Justifique os compromissos entre a simplicidade do código e a velocidade de execução.

Objetivos de Aprendizagem

• Comparar a complexidade temporal de dois algoritmos distintos que resolvem o mesmo problema, utilizando a notação Big O.
• Analisar o impacto do aumento do volume de dados (input size) no tempo de execução de algoritmos com diferentes ordens de complexidade.
• Avaliar o compromisso entre a clareza e simplicidade de um código e a sua eficiência computacional.
• Justificar a escolha de um algoritmo sobre outro com base em critérios de eficiência e requisitos do problema.

Antes de Começar

Introdução à Algoritmia e Pseudocódigo

Porquê: Os alunos precisam de compreender como expressar soluções algorítmicas de forma genérica antes de poderem analisar a sua eficiência.

Estruturas de Dados Básicas (Listas, Arrays)

Porquê: A análise de complexidade está intrinsecamente ligada ao modo como os dados são armazenados e acedidos, sendo fundamental o conhecimento destas estruturas.

Vocabulário-Chave

Complexidade Temporal	Mede o tempo de execução de um algoritmo em função do tamanho da entrada, geralmente expresso usando a notação Big O.
Notação Big O	Uma notação matemática usada para descrever o limite superior do crescimento do tempo de execução ou do espaço de memória de um algoritmo.
Algoritmo de Ordenação	Um procedimento passo a passo para organizar elementos de uma lista ou array numa ordem específica (crescente ou decrescente).
Trade-off	Uma situação em que se sacrifica um benefício para obter outro; neste contexto, o compromisso entre simplicidade do código e velocidade de execução.

Atenção a estes erros comuns

Erro comum

Mais linhas de código significam sempre maior lentidão.

O que ensinar em alternativa

A complexidade depende da estrutura, não do comprimento; um algoritmo simples pode ser exponencial. Atividades de comparação prática ajudam os alunos a medir tempos reais, revelando que otimizações lógicas superam reduções superficiais de código.

Erro comum

Todos os algoritmos funcionam bem com grandes dados.

O que ensinar em alternativa

Algoritmos quadráticos degradam com inputs grandes. Simulações em grupo com dados crescentes mostram curvas de desempenho, permitindo que os alunos visualizem e corrijam esta visão através de discussões guiadas.

Erro comum

Eficiência só importa em computadores potentes.

O que ensinar em alternativa

Recursos limitados amplificam diferenças algorítmicas. Experiências hands-on com dispositivos simples destacam trade-offs reais, fomentando raciocínio crítico em contextos variados.

Ideias de aprendizagem ativa

Comparação Direta: Ordenação de Listas

Divida a turma em pares e forneça listas de números para implementar dois algoritmos de ordenação em Python, como bubble sort e merge sort. Cada par cronometra a execução para 100, 1000 e 10000 elementos, registando tempos numa tabela partilhada. Discuta os resultados em plenário.

45 min·Pares

Simulação Física: Procura Linear vs Binária

Use baralhos de cartas ordenadas para simular procura linear e binária em pequenos grupos. Cronometre buscas em pilhas de 20, 50 e 100 cartas, comparando eficiência. Registe dados num gráfico e preveja escalabilidade para grandes volumes.

30 min·Pequenos grupos

Análise de Trade-offs: Código Simples vs Otimizado

Em individual, os alunos reescrevem um algoritmo ineficiente para um problema como soma de subarrays, testando versões em diferentes tamanhos de input. Partilhem métricas de tempo e memória no final, justificando escolhas.

35 min·Individual

Desafio em Rotação: Problemas Escaláveis

Crie estações com problemas como grafos ou buscas; grupos rotacionam, implementando soluções e medindo desempenho. Compile resultados numa apresentação coletiva.

50 min·Pequenos grupos

Ligações ao Mundo Real

• Engenheiros de software em empresas como a Google ou a Microsoft utilizam a análise de complexidade algorítmica para otimizar motores de busca e sistemas operativos, garantindo respostas rápidas mesmo com biliões de dados.
• Cientistas de dados em instituições financeiras, como o Banco de Portugal, aplicam estes conceitos para desenvolver modelos de deteção de fraude eficientes, que precisam de processar grandes volumes de transações em tempo real.

Ideias de Avaliação

Verificação Rápida

Apresentar aos alunos dois pequenos trechos de código que resolvem o mesmo problema (ex: encontrar o maior elemento numa lista) com abordagens diferentes. Pedir-lhes para identificar qual é mais eficiente e justificar a sua resposta usando a notação Big O.

Questão para Discussão

Colocar a seguinte questão para discussão em grupo: 'Imaginem que estão a desenvolver uma aplicação para gerir o inventário de uma pequena loja vs. uma grande cadeia de supermercados. Que tipo de algoritmo de pesquisa escolheriam para cada caso e porquê, considerando a eficiência e a complexidade do código?'

Bilhete de Saída

Pedir aos alunos para escreverem num pequeno papel: 1) Um exemplo de um problema onde a complexidade O(n²) seria aceitável. 2) Um exemplo de um problema onde seria crucial usar um algoritmo com complexidade O(n log n) ou inferior.

Perguntas frequentes

Como comparar eficiência de algoritmos no 10.º ano?

Forneça o mesmo problema, como ordenar listas, e peça implementações múltiplas em Python. Meça tempos com timeit para inputs variados e use gráficos para visualizar Big O. Discuta trade-offs em grupo para reforçar análise crítica.

O que é complexidade temporal e como ensiná-la?

Complexidade temporal descreve crescimento de passos com o input. Ensine com notação Big O através de exemplos práticos: O(1) constante, O(n) linear. Atividades de cronometragem em dados reais ajudam a diferenciar pior caso de médio.

Como a aprendizagem ativa beneficia a eficiência algorítmica?

Atividades hands-on, como simulações físicas ou codificação em pares, tornam abstrato concreto. Alunos cronometram execuções reais, colaboram em análises e internalizam trade-offs. Esta abordagem aumenta engagement e retenção, preparando para problemas autênticos.

Quais trade-offs entre simplicidade e velocidade?

Códigos simples são fáceis de escrever mas lentos para grandes dados; otimizados exigem mais esforço inicial mas escalam. Peça justificações baseadas em medições, equilibrando legibilidade com desempenho para aplicações reais.