Aula xx — Definição de Algoritmo

1. Identificar o que caracteriza um algoritmo.
2. Reconhecer a entrada, os passos e a saída de um algoritmo.
3. Distinguir uma instrução precisa de uma instrução ambígua.
4. Reconhecer que nem todo problema computacional pode ser resolvido por um algoritmo.

A definição é necessária para compreender os algoritmos que serão apresentados, desenvolvidos e analisados nas próximas aulas.

Não diretamente. Nenhuma prova anterior pediu a definição de algoritmo como questão. O que cai é a aplicação: você precisa do conceito para ler o enunciado, identificar entrada e saída e saber o que está sendo pedido.

Algoritmo é uma sequência de passos bem definidos, isto é, sem ambiguidades, utilizada para resolver um problema computacional ou transformar uma entrada em uma saída.

Cormen (3 ed., BR, p. 17) apresenta a definição informal a seguir:

"Informalmente, um algoritmo é qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz algum valor ou conjunto de valores como saída. Portanto, um algoritmo é uma sequência de etapas computacionais que transformam a entrada na saída."

Em termos simples: entrada, passos bem definidos, saída.

Os passos precisam ser claros e não podem permitir interpretações diferentes. "Some os dois números" é uma instrução precisa. "Junte os números de um jeito razoável" não é: duas pessoas executariam de formas diferentes e chegariam a resultados diferentes.

Um problema computacional é uma tarefa na qual podem ser definidos claramente os dados de entrada e o resultado esperado. Ordenar uma lista de números, calcular a média de notas e encontrar o menor caminho entre dois locais são exemplos.

Pense em uma máquina: os dados são colocados na entrada, os passos são executados e um resultado definido deve sair ao final.

Uma pergunta vaga ou subjetiva não constitui, na forma apresentada, um problema computacional. Exemplos: “Qual é o livro mais bonito?” ou “Como fazer alguém feliz?”. Não existe uma única saída correta nem critérios objetivos suficientes. Essas perguntas podem ser transformadas em problemas computacionais quando os critérios são definidos, como: “Qual livro recebeu a maior nota média dos leitores?”.

Definir bem o problema também não garante que exista solução. Há problemas computacionais bem formulados para os quais está provado que nenhum algoritmo consegue dar a resposta em todos os casos. O exemplo clássico é decidir, olhando apenas o código de um programa e sua entrada, se ele vai parar ou rodar para sempre. O problema é preciso, a saída seria sim ou não, e ainda assim não existe algoritmo que resolva.

Nem todo problema tem algoritmo. Saber em qual caso você está depende de prova. Provar que tem: escrever o algoritmo e mostrar que ele sempre termina e sempre dá a resposta certa. Provar que não tem: mostrar que nenhum algoritmo daria conta, como no exemplo do programa que para ou não para. Enquanto ninguém provou nem uma coisa nem outra, o problema fica em aberto e a resposta honesta é que não se sabe.

Algoritmo é uma sequência de passos bem definidos que recebe uma entrada e produz uma saída para resolver um problema computacional.

1. O que significa dizer que os passos de um algoritmo são bem definidos?

Ver gabarito

Significa que os passos são claros e não apresentam ambiguidades: qualquer pessoa que os execute chega ao mesmo resultado.

2. Por que "Qual é o livro mais bonito?" não é um problema computacional, e o que seria preciso mudar para que virasse um?

Ver gabarito

Porque não há critério objetivo nem saída única correta. Definindo o critério, a pergunta passa a ter entrada e saída claras, como em "Qual livro recebeu a maior nota média dos leitores?".