Propriedades dos Algoritmos
Aprenda as cinco propriedades essenciais que definem um algoritmo adequado: entrada, saída, definitude, finitude e eficácia.
Propriedades dos Algoritmos
Nem todo conjunto de instruções se qualifica como um algoritmo. Para que um procedimento seja considerado um verdadeiro algoritmo, ele deve satisfazer cinco propriedades essenciais. Compreender essas propriedades ajuda você a projetar algoritmos melhores e identificar os defeituosos.
As Cinco Propriedades Essenciais
Todo algoritmo válido deve ter estas cinco características:
| Propriedade | Pergunta que Responde | Por que Importa |
|---|---|---|
| Entrada | Com quais dados o algoritmo começa? | Define o escopo e a aplicabilidade |
| Saída | Qual resultado o algoritmo produz? | Define o propósito e os critérios de sucesso |
| Definitude | Cada passo é claro e sem ambiguidade? | Garante execução consistente |
| Finitude | O algoritmo eventualmente para? | Previne loops infinitos |
| Eficácia | Cada passo pode realmente ser executado? | Garante viabilidade prática |
Propriedade 1: Entrada
Um algoritmo deve ter zero ou mais entradas -- valores ou dados fornecidos ao algoritmo antes de iniciar sua execução.
Compreendendo a Entrada
As entradas são as matérias-primas com as quais seu algoritmo trabalha. Elas podem ser:
- Números (ex.: uma lista de temperaturas)
- Texto (ex.: um parágrafo para analisar)
- Objetos (ex.: um baralho para embaralhar)
- Nada (alguns algoritmos geram dados sem entrada)
Exemplos
ALGORITMO: Somar Dois Números
ENTRADA: Dois números, A e B
SAÍDA: A soma de A e B
PASSO 1: Ler o número A
PASSO 2: Ler o número B
PASSO 3: Calcular SOMA = A + B
PASSO 4: Retornar SOMA
FIM ALGORITMO
ALGORITMO: Gerar os Primeiros 10 Números Pares
ENTRADA: Nenhuma
SAÍDA: Lista dos primeiros 10 números pares
PASSO 1: Criar uma lista vazia chamada NUMEROS_PARES
PASSO 2: Definir CONTADOR como 2
PASSO 3: ENQUANTO a lista tiver menos de 10 números FAÇA
Adicionar CONTADOR a NUMEROS_PARES
Definir CONTADOR como CONTADOR + 2
FIM ENQUANTO
PASSO 4: Retornar NUMEROS_PARES
FIM ALGORITMO
Um algoritmo com zero entradas ainda é válido. Por exemplo, um algoritmo que gera a sequência de Fibonacci do zero não precisa de entrada externa.
Propriedade 2: Saída
Um algoritmo deve produzir pelo menos uma saída -- um resultado que tenha uma relação especificada com as entradas.
Por que a Saída Importa
A saída é a razão de existir do algoritmo. Sem saída, o algoritmo não realiza nada. A saída deve ser:
- Previsível: Dada a mesma entrada, o algoritmo deve produzir a mesma saída
- Útil: A saída deve resolver o problema para o qual o algoritmo foi projetado
- Bem definida: Você deve saber exatamente qual forma a saída terá
Exemplos
ALGORITMO: Encontrar o Máximo
ENTRADA: Uma lista de números
SAÍDA: O maior número na lista
PASSO 1: Definir MAX como o primeiro número na lista
PASSO 2: PARA cada número restante na lista FAÇA
SE o número atual for maior que MAX ENTÃO
Definir MAX como o número atual
FIM SE
FIM PARA
PASSO 3: Retornar MAX
FIM ALGORITMO
| Algoritmo | Entrada | Saída |
|---|---|---|
| Ordenar uma lista | [3, 1, 4, 1, 5] | [1, 1, 3, 4, 5] |
| Contar palavras | "Olá mundo hoje" | 3 |
| Verificar primo | 7 | verdadeiro |
| Inverter texto | "ola" | "alo" |
Propriedade 3: Definitude
Cada passo de um algoritmo deve ser precisamente definido -- não deve haver ambiguidade sobre o que fazer em qualquer ponto.
O Problema com Ambiguidade
Considere estas duas instruções:
| Ambíguo (Ruim) | Definido (Bom) |
|---|---|
| "Adicione um pouco de sal" | "Adicione 1 colher de chá de sal" |
| "Caminhe até se sentir cansado" | "Caminhe por 30 minutos" |
| "Escolha um número" | "Escolha o primeiro número na lista" |
| "Faça ficar bonito" | "Alinhe todo o texto à margem esquerda" |
Exemplo: Definido vs. Indefinido
ALGORITMO RUIM: Fazer Café (Indefinido)
PASSO 1: Pegue um pouco de café
PASSO 2: Adicione água
PASSO 3: Aqueça
PASSO 4: Sirva
PASSO 5: Adicione leite se quiser
O algoritmo ruim acima falha na definitude porque: "um pouco de café" é vago, "água" não tem quantidade, "aqueça" não tem temperatura, e "se quiser" torna o comportamento inconsistente.
ALGORITMO BOM: Fazer Café (Definido)
ENTRADA: Pó de café, água, leite (opcional)
SAÍDA: Uma xícara de café
PASSO 1: Medir 2 colheres de sopa de pó de café
PASSO 2: Colocar o pó no filtro
PASSO 3: Medir 250 mililitros de água
PASSO 4: Aquecer a água a 95 graus Celsius
PASSO 5: Despejar água quente sobre o pó
PASSO 6: Aguardar 4 minutos para a infusão
PASSO 7: SE leite for solicitado ENTÃO
Adicionar 30 mililitros de leite
FIM SE
PASSO 8: Servir em uma xícara
FIM ALGORITMO
Propriedade 4: Finitude
Um algoritmo deve terminar após um número finito de passos -- ele não pode rodar para sempre.
Loops Infinitos
A violação mais comum da finitude é o loop infinito -- um loop que nunca termina porque sua condição de terminação nunca é alcançada.
No diagrama acima, X começa em 1 e continua aumentando. Ele NUNCA será igual a 0, então o algoritmo roda para sempre! Isso viola a propriedade de finitude.
Garantindo a Finitude
Para garantir a finitude, todo loop deve ter:
- Uma condição de terminação clara que pode ser avaliada
- Um caminho garantido para alcançar essa condição
- Progresso em direção à condição a cada iteração
BOM: Loop Finito
PASSO 1: Definir CONTADOR como 10
PASSO 2: ENQUANTO CONTADOR for maior que 0 FAÇA
Imprimir CONTADOR
Definir CONTADOR como CONTADOR - 1
FIM ENQUANTO
PASSO 3: Imprimir "Feito!"
RUIM: Loop Potencialmente Infinito
PASSO 1: Definir CONTADOR como 10
PASSO 2: ENQUANTO CONTADOR não for igual a 5 FAÇA
SE CONTADOR for par ENTÃO
Definir CONTADOR como CONTADOR - 2
SENÃO
Definir CONTADOR como CONTADOR + 2
FIM SE
FIM ENQUANTO
Percorra o exemplo ruim com lápis e papel. Começando em 10: 10 -> 8 -> 6 -> 4 -> 2 -> 0 -> -2... Ele nunca chegará a 5!
Propriedade 5: Eficácia
Cada passo de um algoritmo deve ser básico o suficiente para ser executado -- em princípio, por uma pessoa usando apenas lápis e papel em uma quantidade finita de tempo.
O que Torna um Passo Eficaz?
Um passo eficaz é aquele que:
- Pode ser executado exatamente como descrito
- Completa em uma quantidade finita de tempo
- Não requer operações impossíveis ou indefinidas
Passos Eficazes vs. Ineficazes
| Passo Eficaz | Passo Ineficaz | Por que Falha |
|---|---|---|
| "Adicionar 5 a X" | "Somar todos os números do universo" | Impossível de completar |
| "Dividir X por 2" | "Dividir X por 0" | Matematicamente indefinido |
| "Encontrar o maior número nesta lista de 100" | "Encontrar o maior número primo" | Não existe maior primo |
| "Lançar uma moeda" | "Prever os números da loteria de amanhã" | Impossível de determinar |
Exemplo
ALGORITMO: Calcular a Média
ENTRADA: Uma lista de N números
SAÍDA: A média aritmética dos números
PASSO 1: Definir SOMA como 0
PASSO 2: PARA cada número na lista FAÇA
Adicionar o número à SOMA
FIM PARA
PASSO 3: SE N for maior que 0 ENTÃO
Definir MEDIA como SOMA dividida por N
Retornar MEDIA
SENÃO
Retornar "Não é possível calcular: lista vazia"
FIM SE
FIM ALGORITMO
A verificação no Passo 3 (SE N for maior que 0) garante a eficácia prevenindo a divisão por zero, que seria uma operação indefinida.
Exemplo Completo: Verificando Todas as Propriedades
Vamos analisar um algoritmo completo em relação às cinco propriedades:
ALGORITMO: Contar Vogais em uma Palavra
ENTRADA: Uma palavra (sequência de letras)
SAÍDA: O número de vogais na palavra
PASSO 1: Definir CONTAGEM como 0
PASSO 2: Definir VOGAIS como a lista [a, e, i, o, u]
PASSO 3: PARA cada letra na palavra FAÇA
PARA cada vogal em VOGAIS FAÇA
SE a letra for igual à vogal ENTÃO
Adicionar 1 à CONTAGEM
FIM SE
FIM PARA
FIM PARA
PASSO 4: Retornar CONTAGEM
FIM ALGORITMO
Análise das Propriedades
| Propriedade | Satisfeita? | Explicação |
|---|---|---|
| Entrada | Sim | Recebe uma palavra como entrada |
| Saída | Sim | Retorna um número (contagem de vogais) |
| Definitude | Sim | Cada passo é claro e sem ambiguidade |
| Finitude | Sim | A palavra tem letras finitas; os loops terminarão |
| Eficácia | Sim | Cada passo é uma operação básica e realizável |
Exercícios Práticos
Exercício 1: Identificação de Propriedades
Para cada instrução abaixo, identifique qual propriedade (se houver) ela viola:
- "Pense em um número entre 1 e 10, depois continue adicionando 1 até alcançar seu número favorito"
- "Calcule o resultado de dividir 10 por 0"
- "Pegue uma lista de números e retorne o maior"
- "Misture os ingredientes até parecer certo"
- "Comece com 5, subtraia 1 repetidamente até chegar a 10"
Exercício 2: Corrija o Algoritmo
O seguinte algoritmo viola uma ou mais propriedades. Identifique quais e reescreva-o corretamente:
ALGORITMO: Encontrar Temperatura Média
ENTRADA: Lista de temperaturas diárias de um mês
PASSO 1: Somar todas as temperaturas
PASSO 2: Dividir pelo número de dias
PASSO 3: Retornar o resultado
Exercício 3: Lista de Verificação de Propriedades
Escreva um algoritmo para "Encontrar a palavra mais longa em uma frase." Depois, crie uma lista verificando cada uma das cinco propriedades.
Exercício 4: Verdadeiro ou Falso
Determine se cada afirmação é verdadeira ou falsa:
- Um algoritmo deve ter pelo menos uma entrada.
- Um algoritmo pode ter zero entradas.
- Um algoritmo deve produzir exatamente uma saída.
- Se um algoritmo tem um loop, ele deve sempre terminar.
- "Adivinhe a resposta" é um passo eficaz.
Exercício 5: Desafio de Design
Projete um algoritmo que satisfaça todas as cinco propriedades para a seguinte tarefa:
Tarefa: Dada uma lista de notas de alunos, determine se a média da classe é suficiente (60 ou acima).
Inclua:
- Especificação clara de entrada e saída
- Pelo menos uma condicional
- Pelo menos um loop
- Todos os passos devem ser definidos e eficazes
Resumo
Nesta lição, você aprendeu:
- Entrada: Algoritmos precisam de zero ou mais entradas para trabalhar
- Saída: Algoritmos devem produzir pelo menos um resultado
- Definitude: Cada passo deve ser claro e sem ambiguidade
- Finitude: Algoritmos devem terminar após um número finito de passos
- Eficácia: Cada passo deve ser praticamente executável
Essas cinco propriedades formam a base para avaliar qualquer algoritmo. Quando você projetar seus próprios algoritmos, sempre verifique-os contra esta lista para garantir que sejam válidos.
Termos-Chave
| Termo | Definição |
|---|---|
| Entrada | Dados fornecidos a um algoritmo antes da execução começar |
| Saída | O resultado produzido por um algoritmo após a execução |
| Definitude | Cada passo é precisamente definido sem ambiguidade |
| Finitude | O algoritmo termina após um número finito de passos |
| Eficácia | Cada passo pode ser executado em tempo finito |
| Loop Infinito | Um loop que nunca termina, violando a finitude |