Aplicações Informáticas B · 12.º Ano

Ideias de aprendizagem ativa

Introdução à Complexidade Algorítmica

A complexidade algorítmica é um tema abstrato que exige ligação entre teoria e prática, por isso a aprendizagem ativa é essencial. Os alunos precisam de ver, medir e comparar comportamentos de algoritmos para compreenderem que a notação Big O não é apenas simbólica, mas tem impacto real no desempenho. Esta abordagem direta ajuda a internalizar conceitos que, de outra forma, permaneceriam teóricos e difíceis de apreender.

• Aprendizagens Essenciais
• DGE: Secundário - Algoritmia e Programação
• DGE: Secundário - Pensamento Computacional

• 30–45 min
• Pares → Turma inteira
• 4 atividades

Atividade 01

• Análise de Estudo de Caso
• 45 min · Pequenos grupos

Comparação Prática: Bubble Sort vs Insertion Sort

Divida a turma em grupos pequenos. Cada grupo implementa os dois algoritmos em Python para ordenar listas de tamanhos crescentes (10 a 1000 elementos). Cronometre a execução e registe os tempos. Discuta os resultados num gráfico partilhado.

Avalie a importância da notação Big O para prever o comportamento de algoritmos em larga escala.

Sugestão de Facilitação

Durante a comparação entre Bubble Sort e Insertion Sort, peça aos alunos para cronometrem execuções com vetores de tamanhos crescentes, anotando os tempos em tabelas partilhadas para discussão coletiva.

O que observar

Apresente aos alunos um pequeno trecho de código (ex: um ciclo for aninhado). Peça-lhes para identificar a operação dominante e determinar a complexidade Big O do algoritmo, escrevendo a resposta numa folha. Verifique as respostas para identificar dificuldades comuns.

• Analisar
• Avaliar
• Criar
• Tomada de Decisão
• Autogestão

Atividade 02

• Análise de Estudo de Caso
• 30 min · Individual

Gráficos de Big O: Simulação Individual

Os alunos criam funções para O(n) e O(n²) com loops aninhados. Executam com entradas variadas, medem tempos e plotam curvas em Excel ou Google Sheets. Partilham os gráficos na aula.

Analise como diferentes operações básicas contribuem para a complexidade de um algoritmo.

Sugestão de Facilitação

Na simulação individual de gráficos Big O, forneça folhas quadriculadas e peçam aos alunos para desenharem curvas com base em tabelas de valores pré-calculadas, incentivando a interpretação visual da notação.

O que observar

Coloque a seguinte questão para discussão em pequenos grupos: 'Se um algoritmo tem complexidade O(n log n) e outro tem O(n²), qual deles será mais eficiente para um conjunto de dados com 1 milhão de elementos? Justifiquem a vossa resposta com base no comportamento esperado destas ordens de complexidade.'

• Analisar
• Avaliar
• Criar
• Tomada de Decisão
• Autogestão

Atividade 03

• Análise de Estudo de Caso
• 35 min · Pares

Análise em Pares: Otimização de Pesquisa

Em pares, implementem busca linear e binária. Testem com listas ordenadas de 100 a 10 000 elementos, registem complexidades e expliquem diferenças na notação Big O.

Preveja o impacto de um algoritmo ineficiente no desempenho de uma aplicação real.

Sugestão de Facilitação

Na análise em pares de otimização de pesquisa, distribua código com pesquisas sequencial e binária, pedindo aos alunos que contem operações em casos concretos antes de generalizar para a notação.

O que observar

Distribua um cartão a cada aluno com um algoritmo descrito (sem código explícito, apenas a lógica). Peça-lhes para escreverem a ordem de complexidade Big O esperada para o tempo de execução e uma frase explicando porquê. Recolha os cartões à saída da sala.

• Analisar
• Avaliar
• Criar
• Tomada de Decisão
• Autogestão

Atividade 04

• Análise de Estudo de Caso
• 40 min · Turma inteira

Debate Coletivo: Impacto Real

Apresente cenários de aplicações reais. A turma discute em roda o impacto de O(n²) vs O(n log n) em big data, votando em soluções otimizadas.

Avalie a importância da notação Big O para prever o comportamento de algoritmos em larga escala.

Sugestão de Facilitação

No debate coletivo sobre impacto real, peça aos alunos para trazerem exemplos de aplicações do dia a dia (como motores de busca ou jogos) e relacionarem as complexidades discutidas com os seus desempenhos.

O que observar

Apresente aos alunos um pequeno trecho de código (ex: um ciclo for aninhado). Peça-lhes para identificar a operação dominante e determinar a complexidade Big O do algoritmo, escrevendo a resposta numa folha. Verifique as respostas para identificar dificuldades comuns.

• Analisar
• Avaliar
• Criar
• Tomada de Decisão
• Autogestão

Algumas notas sobre lecionar esta unidade

Ensine complexidade algorítmica começando sempre com exemplos concretos e mensuráveis. Evite saltar diretamente para a notação formal; em vez disso, use atividades que permitam aos alunos recolher dados, analisar padrões e só depois formalizar com Big O. Pesquisas mostram que esta abordagem construtivista, baseada em experiências repetidas, reduz a tendência dos alunos para confundirem constantes com termos dominantes na notação.

No final destas atividades, os alunos conseguem classificar algoritmos comuns com a notação Big O correta e explicar como o tamanho da entrada afeta o tempo de execução. Devem também ser capazes de identificar trade-offs entre tempo e espaço de memória, utilizando argumentos baseados em dados empíricos recolhidos durante as experiências práticas.

---

Atenção a estes erros comuns

• Durante a atividade Comparação Prática: Bubble Sort vs Insertion Sort, watch for students who assume that the faster execution time on their machine directly reflects the Big O complexity of the algorithm.

  Use a tabela partilhida onde os alunos registam tempos para vetores de tamanhos 100, 1.000 e 10.000, destacando que as constantes de hardware afetam todos os algoritmos igualmente, mas a diferença de crescimento entre O(n²) e O(n log n) mantém-se visível.

• Durante a atividade Análise em Pares: Otimização de Pesquisa, watch for students who assume that a recursive search is always less efficient than an iterative one due to memory usage.

  Peça aos alunos que comparem o número de operações (comparações) e o espaço de pilha usado, usando vetores de entrada com tamanhos variados e discutindo os trade-offs entre tempo e espaço em grupo.

• Durante a atividade Gráficos de Big O: Simulação Individual, watch for students who believe that a simple algorithm with fewer lines of code is inherently more efficient.

  Peça aos alunos que desenhem gráficos de Bubble Sort (O(n²)) e pesquisa binária (O(log n)) para o mesmo intervalo de valores, destacando que a inclinação das curvas revela a verdadeira eficiência assintótica, independentemente da simplicidade do código.

---

Metodologias usadas neste resumo

• Análise de Estudo de Caso