Parte3 Propriedades 11 16

Algoritmos: o que os caracteriza?

Quatro propriedades básicas
Obviamente, nem todas as receitas podem ser aceitas como descrições de algoritmos. Em particular, as instruções devem ser claras e executáveis de forma simples. Então, quando uma dada receita pode ser encarada como um algoritmo legítimo? Para tal, precisamos nos certificar de que a receita apresenta quatro propriedades básicas:
•

A primeira é óbvia: o texto da receita deve ser finito. Soa estranho, pois como poderia o texto ser infinito? É uma precaução básica para evitar algoritmos
“triviais”. Por exemplo, no caso do MDC, poderíamos ter um “algoritmo” com a seguinte descrição:
1. Se M=1
2. Se M=2
3. Se M=1
4. Se M=3
5. Se M=2
. . . .

e e e e e

N=1,
N=1,
N=2,
N=1,
N=2,

o o o o o

MDC
MDC
MDC
MDC
MDC

é é é é é

1;
1;
1;
1;
2;

páre. páre. páre. páre. páre.

que continuaria indefinidamente, listando todos os pares de possíveis valores para
M e N, junto com o MDC correspondente. É certo que sempre encontraremos o
MDC correto se “executarmos” esse algoritmo, com quaisquer valores dados para
M e N, pois sempre vamos nos deparar com uma condição verdadeira quando atingirmos a linha onde estão listados os valores dados para M e N.
Obviamente, não queremos classificar essa receita infinita como um algoritmo legítimo. Nem conseguiríamos armazená-la num computador, quanto menos executá-la ...
• O texto do algoritmo deve ser composto apenas por instruções elementares. Mas o que seria uma instrução elementar? Aqui, elementar depende muito do contexto. Por exemplo, o “juntar mais dois ovos” pode perfeitamente ser elementar para um cozinheiro. Mas pode não o ser para uma criança de cinco anos. o “substitua o valor de M pelo novo valor (M-N)” é elementar para quem domina aritmética básica e está à vontade com a noção de que “M” nada mais é que um local onde se pode armazenar números inteiros, de alguma forma, isto é, M é uma “variável”. o “se o valor do dólar for subir 10% no próximo mês com certeza, compre
agora