Aplicações Informáticas B · 12.º Ano · Algoritmia e Estruturas de Dados · 1o Periodo

Algoritmos de Pesquisa

Os alunos implementam e comparam algoritmos de pesquisa linear e binária, avaliando a sua complexidade e eficiência.

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

Sobre este tópico

Os algoritmos de pesquisa linear e binária são fundamentais para processar eficientemente grandes conjuntos de dados. Na pesquisa linear, percorre-se a lista sequencialmente até localizar o elemento alvo, com complexidade temporal O(n). Já a pesquisa binária, aplicável apenas a listas ordenadas, divide repetidamente o intervalo de procura ao meio, alcançando O(log n), o que a torna muito mais eficiente para dados volumosos. Os alunos do 12.º ano implementam ambos em pseudocódigo ou programação, testam com listas de tamanhos variados e analisam tempos de execução.

Este tópico, integrado na unidade de Algoritmia e Estruturas de Dados, alinha-se com os standards de Pensamento Computacional e Algoritmia do Currículo Nacional. Os alunos comparam eficiência em cenários reais, identificam pré-condições como a ordenação para a binária e avaliam escalabilidade, desenvolvendo competências críticas para programação avançada e análise de sistemas.

A aprendizagem ativa beneficia este tópico porque simulações manuais com cartas ou objetos físicos tornam a comparação de eficiência concreta e visual, enquanto testes colaborativos com código real revelam padrões de desempenho que leituras teóricas não captam, fomentando compreensão profunda e retenção duradoura.

Questões-Chave

1. Compare a eficiência da pesquisa linear e binária em diferentes cenários de dados.
2. Analise as pré-condições necessárias para aplicar um algoritmo de pesquisa binária.
3. Explique como a complexidade temporal de um algoritmo impacta a sua escalabilidade.

Objetivos de Aprendizagem

• Comparar a complexidade temporal e a eficiência dos algoritmos de pesquisa linear e binária em listas de diferentes tamanhos e estados de ordenação.
• Analisar as pré-condições essenciais para a aplicação bem-sucedida da pesquisa binária, nomeadamente a ordenação dos dados.
• Explicar como a notação Big O (complexidade temporal) se relaciona com a escalabilidade de um algoritmo de pesquisa.
• Implementar em pseudocódigo ou linguagem de programação os algoritmos de pesquisa linear e binária, demonstrando o seu funcionamento.
• Avaliar o impacto do tamanho do conjunto de dados no desempenho relativo da pesquisa linear e binária.

Antes de Começar

Introdução à Algoritmia e Pseudocódigo

Porquê: Os alunos precisam de compreender os conceitos básicos de algoritmos e como representá-los em pseudocódigo antes de implementar algoritmos de pesquisa.

Estruturas de Dados Fundamentais (Listas/Arrays)

Porquê: A compreensão de como os dados são organizados em listas ou arrays é essencial para a implementação e análise de algoritmos de pesquisa.

Conceitos Básicos de Complexidade Algorítmica

Porquê: Uma introdução à ideia de que diferentes algoritmos têm diferentes custos computacionais é necessária para apreciar a comparação de eficiência.

Vocabulário-Chave

Pesquisa Linear	Algoritmo que percorre sequencialmente uma lista ou array, elemento a elemento, até encontrar o valor procurado ou esgotar a lista.
Pesquisa Binária	Algoritmo que procura um elemento num conjunto de dados ordenado, dividindo repetidamente o intervalo de procura ao meio.
Complexidade Temporal	Medida que descreve o tempo de execução de um algoritmo em função do tamanho da entrada, geralmente expressa usando a notação Big O.
Notação Big O	Notação matemática utilizada para descrever o limite superior do crescimento do tempo de execução ou do espaço de memória de um algoritmo à medida que o tamanho da entrada aumenta.
Pré-condição	Uma condição que deve ser verdadeira antes da execução de um algoritmo para que este funcione corretamente.

Atenção a estes erros comuns

Erro comum

A pesquisa binária é sempre mais rápida que a linear.

O que ensinar em alternativa

A binária requer lista ordenada, pré-condição ausente em dados desordenados onde a linear é única opção viável. Simulações manuais com cartas mostram que para listas pequenas a linear é comparável ou mais simples. Abordagens ativas como testes empíricos ajudam alunos a confrontar intuições com dados reais.

Erro comum

A complexidade temporal não importa na prática com computadores modernos.

O que ensinar em alternativa

Para milhões de registos, O(n) torna-se impraticável enquanto O(log n) escala bem. Experiências com datasets crescentes demonstram desacelerações exponenciais. Discussões colaborativas em atividades de medição revelam impactos reais, corrigindo visões superficiais.

Erro comum

Ordenar uma lista sempre compensa para usar binária.

O que ensinar em alternativa

Ordenação inicial O(n log n) pode exceder ganhos em procuras únicas. Comparações em estações rotativas mostram cenários onde linear basta. Aprendizagem ativa via debate de casos práticos clarifica trade-offs.

Ideias de aprendizagem ativa

Simulação Manual: Cartas Ordenadas

Distribua baralhos de cartas ordenadas e desordenadas por grupos. Os alunos simulam a pesquisa linear contando passos sequenciais e a binária dividindo pilhas ao meio. Registem o número de comparações para 10 elementos alvo e comparam resultados em tabela coletiva.

30 min·Pequenos grupos

Implementação Código: Testes Temporais

Os alunos codificam ambos os algoritmos numa linguagem como Python. Geram listas aleatórias de 100 a 10000 elementos, cronometram execuções para 50 procuras e registam médias. Discutem gráficos de tempo vs. tamanho em plenário.

45 min·Pares

Estações Rotativas: Cenários Variados

Crie estações com listas pequenas, grandes ordenadas e desordenadas. Grupos rotacionam, aplicam algoritmos adequados, medem eficiência e debatem escolhas. Apresentam conclusões ao final.

40 min·Pequenos grupos

Análise Escalabilidade: Dados Massivos

Forneça ficheiros CSV grandes. Alunos adaptam código para medir tempos reais, preveem com Big O e validam. Partilham previsões vs. resultados reais em discussão guiada.

35 min·Individual

Ligações ao Mundo Real

• Bibliotecas públicas utilizam algoritmos de pesquisa para localizar rapidamente livros no catálogo, sendo a pesquisa binária mais eficiente se o catálogo estiver ordenado por título ou autor.
• Sistemas de gestão de bases de dados, como os utilizados por empresas de comércio eletrónico, empregam variações de pesquisa binária (árvores B, por exemplo) para encontrar produtos ou informações de clientes em milissegundos, mesmo com milhões de registos.
• Motores de busca como o Google utilizam estruturas de dados e algoritmos de pesquisa otimizados para indexar e recuperar páginas web relevantes em resposta a consultas de utilizadores, demonstrando a importância da eficiência em larga escala.

Ideias de Avaliação

Bilhete de Saída

Entregue a cada aluno um pequeno conjunto de dados ordenado e um valor a procurar. Peça para descreverem os passos que seguiriam para encontrar o valor usando pesquisa binária e estimarem o número de comparações necessárias. Em seguida, peçam para fazerem o mesmo com pesquisa linear e compararem os resultados.

Questão para Discussão

Coloque a seguinte questão para discussão em pequenos grupos: 'Em que situações práticas a pesquisa linear pode ser preferível à pesquisa binária, apesar da sua menor eficiência teórica?'. Peça aos grupos para apresentarem as suas conclusões à turma, justificando com exemplos concretos.

Verificação Rápida

Apresente aos alunos um pequeno trecho de código (pseudocódigo ou linguagem conhecida) que implementa um algoritmo de pesquisa. Peça para identificarem se é pesquisa linear ou binária, quais as pré-condições para o seu funcionamento e qual a sua complexidade temporal aproximada (O(n) ou O(log n)).

Perguntas frequentes

Qual a diferença entre pesquisa linear e binária?

A linear examina elementos sequencialmente até encontrar o alvo, ideal para listas pequenas ou desordenadas, com custo O(n). A binária exige ordenação, divide o espaço ao meio repetidamente e atinge O(log n), superior para grandes dados ordenados. Implementações práticas revelam que a escolha depende do contexto, promovendo decisões informadas em programação.

Como medir a eficiência de algoritmos de pesquisa?

Cronometre execuções médias em listas de tamanhos variados, gere gráficos tempo vs. n e compare com notação Big O. Testes com dados aleatórios e ordenados validam previsões teóricas. Esta análise empírica, comum em atividades laboratoriais, ensina alunos a quantificar escalabilidade de forma rigorosa.

Quais pré-condições para pesquisa binária?

Lista deve estar totalmente ordenada para garantir divisões corretas. Sem isso, resultados erram. Alunos verificam esta condição em código e simulações, analisando falhas em dados desordenados. Compreender pré-condições evita erros em aplicações reais como bases de dados.

Como a aprendizagem ativa ajuda a entender algoritmos de pesquisa?

Simulações físicas com objetos tangíveis tornam abstractos conceitos de divisões e comparações visíveis e intuitivos. Testes colaborativos com código real geram dados próprios sobre eficiência, fomentando debate e descoberta. Estas abordagens constroem confiança na previsão de desempenhos e retêm melhor que teoria passiva, alinhando com pensamento computacional.