1 · 5W4H do algoritmo
2 · O que é e qual problema resolve?
Algoritmo é uma descrição finita e precisa de um procedimento computacional, constituído por passos que transformam entradas em resultados. Para um algoritmo determinístico convencional, cada passo deve ter significado suficientemente definido para permitir sua execução.
Problema
Temos uma coleção de números e precisamos determinar se um valor está presente.
Solução
Examinar elementos, compará-los com o alvo e encerrar ao encontrar ou esgotar a coleção.
Critérios
Correção, terminação, clareza, consumo de tempo e memória, adequação ao contexto.
Quando usar?
Sempre que uma tarefa precisar de um procedimento reproduzível: busca, ordenação, cálculo, validação, roteamento, automação, decisão ou processamento de informações. Nem todo problema exige escrever um algoritmo novo: frequentemente convém reutilizar bibliotecas e algoritmos já verificados.
O algoritmo descreve o método; um programa é sua expressão em uma linguagem executável, combinada com dados e ambiente de execução.
3 · Pseudolinguagem: léxico, sintaxe e semântica
Pseudolinguagem é uma notação intermediária, voltada à comunicação e ao raciocínio sobre algoritmos, sem depender da sintaxe específica de uma linguagem de programação. Não existe uma pseudolinguagem universal: cada convenção precisa definir seus elementos.
Léxico
Conjunto de símbolos e unidades reconhecidas: identificadores, números, operadores (←, =), palavras-chave (SE, PARA).
Sintaxe
Regras de formação das instruções: como escrever atribuições, condições, repetições e blocos válidos.
Semântica
Significado operacional das instruções: x ← 3 atribui 3 a x; SE seleciona uma ação conforme uma condição.
Pragmática
Uso adequado da notação: clareza, legibilidade, verificabilidade e facilidade de transformação em código.
Exemplo: busca linear
ALGORITMO BuscaLinear(dados, alvo)
PARA i ← 0 ATÉ tamanho(dados) - 1 FAÇA
SE dados[i] = alvo ENTÃO
RETORNE i
FIM_SE
FIM_PARA
RETORNE -1
FIM_ALGORITMOContrato: recebe uma sequência e um alvo; devolve o índice da primeira ocorrência, ou −1 quando não encontra. Aqui os índices começam em zero. Semântica de controle: RETORNE encerra imediatamente a execução.
Distinção: um algoritmo não é uma linguagem. A pseudolinguagem é uma forma de representar algoritmos; uma linguagem de programação permite implementá-los sob regras mais rigorosas.
4 · Laboratório interativo: execute a busca linear
Altere os dados e o alvo; avance uma comparação por vez para observar o comportamento do algoritmo.
Custo da busca linear: melhor caso O(1); pior caso O(n); memória auxiliar O(1). A quantidade de comparações efetivas aparece no laboratório.
5 · Relação entre algoritmo e estrutura de dados
estrutura de dados
algoritmo
Uma estrutura de dados organiza os elementos e suas relações. Um algoritmo estabelece os passos para operar sobre eles. A escolha conjunta afeta desempenho, correção e manutenção. A estrutura pode oferecer operações que o algoritmo utiliza; o algoritmo pode também construir ou modificar a estrutura.
Comparação de estratégias de busca
| Organização | Algoritmo | Pré-condição | Busca (pior caso) |
|---|---|---|---|
| Vetor não ordenado | Busca linear | Nenhuma ordenação | O(n) |
| Vetor ordenado | Busca binária | Ordenação e acesso por índice | O(log n) |
| Árvore binária de busca balanceada | Busca na árvore | Invariante de ordem e balanceamento | O(log n) |
| Tabela hash | Busca por chave | Função hash e tratamento de colisões | O(n), embora O(1) seja esperado em condições usuais |
| Grafo com lista de adjacência | Busca em largura (BFS) | Vértices e arestas definidos | O(V + E) |
Exemplos de aplicação
Catálogo do LAC
Tabela hash para localizar um knowgrama por identificador; algoritmo de consulta por chave.
Percurso de aprendizagem
Grafo para representar pré-requisitos; algoritmo de busca para descobrir caminhos possíveis.
Histórico de navegação
Pilha para guardar estados; operações empilhar e desempilhar para retornar.
Orquestração
Fila para tarefas pendentes; algoritmo de escalonamento para decidir a próxima execução.
Prosseguir para o laboratório de Estruturas de Dados → (link relativo: mantenha os dois arquivos na mesma pasta)
6 · Verificação da aprendizagem
Pergunta: Para procurar um número em um vetor não ordenado, qual alternativa está correta?
Modelo mental esperado
Problema → requisitos → representação dos dados + procedimento → execução → resultado → avaliação. O algoritmo especifica o procedimento; a estrutura de dados sustenta a organização sobre a qual ele opera.
Referências para aprofundamento
- Cormen, Leiserson, Rivest e Stein — Introduction to Algorithms.
- Knuth — The Art of Computer Programming.
- Wirth — Algorithms + Data Structures = Programs.