1.1 Algoritmo

A noção de um algoritmo é fundamental para toda a programação de computadores, então devemos começar com uma análise cuidadosa desse conceito.

A própria palavra “algoritmo” é bastante interessante; à primeira vista, pode parecer que alguém pretendia escrever “logaritmo”, mas embaralhou as quatro primeiras letras. A palavra não apareceu no Webster’s New World Dictionary até 1957; encontramos apenas a forma mais antiga “algorismo” com seu significado antigo, o processo de fazer aritmética usando numerais arábicos. Durante a Idade Média, os abacistas computavam no ábaco e os algoristas computavam por algorismo. Na época do Renascimento, a origem desta palavra era incerta, e os primeiros linguistas tentaram adivinhar sua derivação fazendo combinações com algiros [doloroso] + arithmos [número]; outros disseram que não, a palavra vem de “Rei Algor de Castela”. Finalmente, os historiadores da matemática encontraram a verdadeira origem da palavra algorismo: vem do nome de um famoso autor de livros didáticos persa, Abū ‘Abd Allāh Muḥammad ibn Mūsā al-Khwārizmī (c. 825)—literalmente, “Pai de Abdullah, Mohammed, filho de Moisés, nativo de Khwārizm.” O Mar de Aral na Ásia Central já foi conhecido como Lago Khwārizm, e a região de Khwārizm está localizada na bacia do rio Amu, ao sul desse mar. Al-Khwārizmī escreveu o célebre texto árabe Kitāb al-jabr wa’l-muqābala (“Regras de restauração e equação”); outra palavra, “álgebra”, deriva do título desse livro, que era um estudo sistemático da solução de equações lineares e quadráticas. [Para notas sobre a vida e obra de al-Khwārizmī, veja H. Zemanek, Lecture Notes in Computer Science 122 (1981), 1–81.]

Gradualmente, a forma e o significado de algorismo foram se corrompendo; conforme explicado pelo Oxford English Dictionary, a palavra “passou por muitas perversões pseudo-etimológicas, incluindo a recente algoritmo, na qual é eruditamente confundida” com a raiz grega da palavra aritmética. Esta mudança de “algorismo” para “algoritmo” não é difícil de entender, dado que as pessoas tinham esquecido a derivação original da palavra. Um dos primeiros dicionários matemáticos alemães, Vollständiges mathematisches Lexicon (Leipzig: 1747), deu a seguinte definição para a palavra Algorithmus: “Sob esta designação estão combinadas as noções dos quatro tipos de cálculos aritméticos, a saber, adição, multiplicação, subtração e divisão.” A frase em latim algorithmus infinitesimalis era na época usada para denotar “modos de cálculo com quantidades infinitamente pequenas, conforme inventado por Leibniz.”

Em 1950, a palavra algoritmo estava mais frequentemente associada ao algoritmo de Euclides, um processo para encontrar o maior divisor comum de dois números que aparece nos Elementos de Euclides (Livro 7, Proposições 1 e 2). Será instrutivo apresentar o algoritmo de Euclides aqui:

---

Algoritmo $E$ (algoritmo de Euclides).

Dado dois números inteiros positivos $m$ e $n$, encontre o maior divisor comum, ou seja, o maior número inteiro positivo que divide ambos $m$ e $n$ sem deixar resto.

$E1$. [Encontrar o resto] Divida $m$ por $n$ e deixe $r$ ser o resto. (Ou seja, 0 ≤ $r$ < $n$.)

$E2$. [É zero?] Se $r$ = 0, o algoritmo termina; $n$ é a resposta (o MDC de $m$ e $n$).

$E3$. [Reduzir] Defina $m$ ← $n$, $n$ ← $r$ e volte para a etapa $E1$. ||

---

Claro, Euclides não apresentou seu algoritmo exatamente dessa forma. O formato acima foi adotado para ilustrar o estilo de apresentação dos algoritmos ao longo deste livro.

Cada algoritmo recebe uma letra identificadora (como o "E" no exemplo anterior), e os passos do algoritmo são numerados, seguindo essa letra ($E1$, $E2$, $E3$). Os capítulos são divididos em seções numeradas e, dentro de uma seção, os algoritmos são designados apenas pela letra. Quando referenciados em seções posteriores, o número da seção correspondente é anexado. Por exemplo, estamos na Seção 1.1; dentro dessa seção, o algoritmo de Euclides é chamado de "Algoritmo $E$", mas em seções futuras será referido como "Algoritmo 1.1E".

Cada passo de um algoritmo, como o $E1$, começa com uma frase resumida entre colchetes, que sintetiza seu conteúdo principal de forma concisa. Essa frase geralmente aparece também em um fluxograma complementar, como mostrado na Figura 1, para facilitar a visualização do algoritmo pelo leitor.

Fig. 1. Fluxograma para o Algoritimo E.

Após a frase de resumo, segue uma descrição, em palavras e símbolos, de uma ação a ser executada ou decisão a ser tomada. Comentários entre parênteses, como o da segunda frase no passo $E1$, também podem ser incluídos. Esses comentários servem como explicações adicionais sobre o passo, frequentemente destacando características invariantes das variáveis ou os objetivos atuais. Eles não especificam ações que fazem parte do algoritmo, mas são destinados ao leitor como auxiliares para uma melhor compreensão.

A seta "←", presente no passo $E3$, representa a operação de substituição, também chamada de atribuição. Por exemplo, "$m$ ← $n$" significa que o valor da variável $m$ será substituído pelo valor atual de $n$. Quando o Algoritmo $E$ começa, $m$ e $n$ possuem valores iniciais predefinidos; ao final do algoritmo, esses valores podem ter mudado. A seta "←" é utilizada para distinguir a substituição da igualdade. Não diríamos "Atribua $m$ = $n$", mas, talvez, perguntaríamos "$m$ = $n$?". O símbolo "=" denota uma condição a ser verificada, enquanto "←" indica uma ação a ser executada. A operação de aumentar $n$ em um é representada por "$n$ ← $n$ + 1" (lido como "$n$ recebe $n$ + 1" ou "$n$ é substituído por $n$ + 1"). Em termos gerais, "variável ← fórmula" significa que a fórmula deve ser calculada com base nos valores atuais das variáveis envolvidas, e o resultado deve substituir o valor anterior da variável à esquerda da seta. Pessoas não familiarizadas com computação podem, às vezes, dizer "$n$ se torna $n$ + 1" ou usar "$n$ → $n$ + 1" para essa operação, mas isso pode causar confusão, pois entra em conflito com as convenções padrões e deve ser evitado. Vale ressaltar que a ordem das ações no passo $E3$ é crucial: "Atribua $m$ ← $n$, $n$ ← $r$" é diferente de "Atribua $n$ ← $r$, $m$ ← $n$", pois a segunda sequência faria com que o valor anterior de $n$ se perdesse antes de ser usado para atribuir $m$. Assim, a segunda sequência equivale a "Atribua $n$ ← $r$, $m$ ← $r$". Quando várias variáveis devem receber o mesmo valor, podemos usar múltiplas setas; por exemplo, "$n$ ← $r$, $m$ ← $r$" pode ser simplificado como "$n$ ← $m$ ← $r$". Para trocar os valores de duas variáveis, usamos "Troque $m$ ↔ $n$", ou alternativamente, podemos usar uma variável temporária t: "Atribua t ← $m$, $m$ ← $n$, $n$ ← t".

Um algoritmo começa pelo passo de menor número, geralmente o passo 1, e segue a execução sequencial dos passos subsequentes, salvo indicação em contrário. No passo $E3$, o comando "volte para o passo $E1$" define claramente a ordem computacional. No passo $E2$, a ação é precedida pela condição "Se $r = 0$"; portanto, se $r ≠ 0$, a parte seguinte dessa sentença não será executada. Para maior clareza, poderíamos adicionar a frase redundante: "Se $r ≠ 0$, vá para o passo $E3$."

A linha vertical pesada || no final do passo $E3$ indica o término do algoritmo e o retorno ao texto. Já discutimos quase todas as convenções notacionais usadas nos algoritmos deste livro, exceto uma notação que denota elementos "subscritos" ou "indexados", ou seja, itens de um vetor ordenado. Suponhamos que tenhamos $n$ quantidades, $v_1$, $v_2$,$...$,$v_n$; em vez de escrever $v_j$ para o $j$-ésimo elemento, frequentemente usamos a notação $v[j]$. Da mesma forma, a notação $a[i, j]$ pode ser preferida em vez de uma notação duplamente subscrita, como $a_{ij}$. Também são usados nomes de variáveis compostos, geralmente em letras maiúsculas; por exemplo, $TEMP$ pode ser o nome de uma variável para armazenar temporariamente um valor calculado, e $PRIME[K]$ pode denotar o $K$-ésimo número primo, entre outros.

Agora que entendemos a estrutura dos algoritmos, vamos executar um. Antes de prosseguir, é importante destacar que um algoritmo não deve ser lido como um romance; tentar fazê-lo tornaria sua compreensão mais difícil. Para realmente entender um algoritmo, é preciso vê-lo em ação. A melhor forma de aprender é experimentando: o leitor deve pegar lápis e papel e resolver um exemplo assim que encontrar um novo algoritmo no texto. Geralmente, um esboço de exemplo será fornecido, mas, caso contrário, é fácil criar um. Esse método simples e eficiente facilita a compreensão, enquanto outras abordagens costumam falhar.

Vamos então trabalhar com um exemplo do Algoritmo $E$. Suponha que temos $m = 119$ e $n = 544$. Começamos pelo passo $E1$. (O leitor deve acompanhar o algoritmo enquanto detalhamos cada etapa.) A divisão de $m$ por $n$ aqui é trivial, pois o quociente é zero e o resto é 119, então $r \leftarrow 119$. No passo $E2$, como $r \neq 0$, seguimos adiante. No passo $E3$, atualizamos os valores: $m \leftarrow 544$ e $n \leftarrow 119$.

Se originalmente tivéssemos $m < n$, o quociente no passo $E1$ seria sempre zero, e o algoritmo prosseguiria com a troca de $m$ e $n$. Para evitar essa redundância, poderíamos adicionar um novo passo inicial:

E0. [Garantir que $m \geq n$.] Se $m < n$, trocar $m \leftrightarrow n$.

Essa modificação não alteraria a essência do algoritmo, mas reduziria seu tempo de execução em aproximadamente metade dos casos, ainda que aumentasse ligeiramente seu comprimento.

Retornando ao passo $E1$, temos: $544 \div 119 = 4 + \frac{68}{119}, \quad \text{portanto, } r \leftarrow 68$. No passo $E2$, como $r \neq 0$, seguimos para o passo $E3$: $m \leftarrow 119$, $n \leftarrow 68$. A próxima iteração nos dá $r \leftarrow 51$, depois $m \leftarrow 68$, $n \leftarrow 51$, em seguida $r \leftarrow 17$, com $m \leftarrow 51$, $n \leftarrow 17$. Finalmente, quando $51$ é dividido por $17$, obtemos $r \leftarrow 0$, encerrando o algoritmo no passo $E2$. Assim, o maior divisor comum de 119 e 544 é 17.

Isso é um algoritmo. O termo moderno se assemelha a conceitos como receita, processo, método, técnica, procedimento ou rotina, mas carrega uma nuance própria. Um algoritmo não é apenas um conjunto finito de regras que define uma sequência de operações para resolver um problema específico. Ele possui cinco características essenciais:

---

1) Finitude

Um algoritmo deve sempre terminar após um número finito de passos. O Algoritmo $E$ satisfaz essa condição porque, após o passo $E1$, o valor de $r$ é menor que $n$. Assim, se $r \neq 0$, o valor de $n$ diminui na próxima execução do passo $E1$. Como uma sequência decrescente de números inteiros positivos deve, inevitavelmente, chegar ao fim, o passo $E1$ é executado apenas um número finito de vezes para qualquer valor inicial de $n$.

No entanto, o número de passos pode se tornar arbitrariamente grande. Algumas escolhas específicas de $m$ e $n$ podem fazer com que o passo $E1$ seja repetido mais de um milhão de vezes.

(Um procedimento que possui todas as características de um algoritmo, exceto a finitude, pode ser chamado de método computacional. Euclides não apenas formulou um algoritmo para encontrar o máximo divisor comum de dois números, mas também propôs uma construção geométrica semelhante para determinar a "maior medida comum" entre dois segmentos de reta. Esse é um método computacional que não termina se os comprimentos forem incomensuráveis. Outro exemplo de método computacional não terminável é um processo reativo, que interage continuamente com seu ambiente.)

---

2) Definitude

Cada passo de um algoritmo deve ser claramente definido, com instruções rigorosas e inequívocas para cada situação possível. Embora os algoritmos deste livro atendam a esse critério, eles estão descritos em inglês, o que pode levar a interpretações ambíguas. Para evitar esse problema, linguagens de programação formais são usadas para especificar algoritmos, garantindo que cada instrução tenha um significado exato. Neste livro, muitos algoritmos serão apresentados tanto em linguagem natural quanto em uma linguagem de programação. Quando um método computacional é expresso em uma linguagem de programação, ele é chamado de programa.

No Algoritmo $E$, a definitude do passo $E1$ exige que o leitor compreenda exatamente o significado da divisão de $m$ por $n$ e do cálculo do resto. No entanto, não há um consenso universal sobre esses conceitos para valores que não sejam inteiros positivos. Por exemplo, qual seria o resto de $-8$ dividido por $-\pi$? Ou de $59/13$ dividido por zero? Portanto, o critério de definitude requer que $m$ e $n$ sejam sempre inteiros positivos ao executar o passo $E1$. Essa condição é garantida inicialmente, e, após o passo E1$F$, r $é um número inteiro não negativo que só pode ser zero no passo$E3$. Assim,$m $e$ n $$ permanecem inteiros positivos, como necessário.

---

3) Entrada

Um algoritmo pode ter nenhuma, uma ou várias entradas, ou seja, valores fornecidos antes ou durante sua execução. No Algoritmo $E$, por exemplo, há duas entradas: $m$ e $n$, ambas pertencentes ao conjunto dos inteiros positivos.

---

4) Saída

Todo algoritmo gera pelo menos uma saída, que está relacionada às suas entradas. No caso do Algoritmo $E$, a saída é o valor de $n$ no passo $E2$, que corresponde ao máximo divisor comum das duas entradas.

(Podemos demonstrar matematicamente que esse valor é, de fato, o máximo divisor comum. Após o passo $E1$, temos $m = qn + r$ para algum inteiro $q$. Se $r = 0$, então $m$ é múltiplo de $n$ e, nesse caso, $n$ é claramente o máximo divisor comum. Se $r \neq 0$, qualquer número que divida $m$ e $n$ também deve dividir $r$, e qualquer número que divida $n$ e $r$ também divide $m$. Assim, o conjunto de divisores comuns de $m$ e $n$ é o mesmo que o conjunto de divisores comuns de $n$ e $r$. Portanto, o passo $E3$ não altera a resposta do problema original.)

---

Aqui está a versão revisada do seu texto, mantendo a precisão técnica e melhorando a fluidez e clareza:

---

5) Efetividade

Um algoritmo deve ser efetivo, ou seja, suas operações devem ser suficientemente básicas para que possam, em princípio, ser executadas exatamente e em um tempo finito por alguém utilizando apenas lápis e papel. O Algoritmo $E$ emprega apenas operações como a divisão de um número inteiro positivo por outro, a verificação de igualdade com zero e a atribuição de valores entre variáveis. Essas operações são consideradas efetivas, pois os números inteiros podem ser representados de forma finita no papel e há um método bem definido para realizar a divisão (o "algoritmo da divisão").

Entretanto, as mesmas operações deixariam de ser efetivas se os valores envolvidos fossem números reais arbitrários, expressos como expansões decimais infinitas, ou se representassem comprimentos físicos de segmentos de reta, que não podem ser especificados exatamente.

Outro exemplo de um passo não efetivo seria a seguinte instrução: “Se 4 for o maior número inteiro $n$ para o qual existe uma solução para a equação $w^n + x^n + y^n = z^n$ em inteiros positivos $w, x, y$ e $z$, então vá para o passo E4.” Essa operação não seria efetiva até que se desenvolvesse um algoritmo capaz de determinar se 4 é de fato o maior número inteiro com essa propriedade.

Podemos ilustrar o conceito de algoritmo comparando-o a uma receita de culinária. Uma receita normalmente possui as qualidades de finitude (embora se diga que uma panela vigiada nunca ferve), entrada (ovos, farinha, etc.) e saída (um prato pronto). No entanto, frequentemente carece de definitude. Instruções como “Adicione uma pitada de sal” podem ser imprecisas — o que exatamente constitui uma "pitada"? Onde o sal deve ser adicionado? Expressões como “misture levemente até a massa ficar granulada” ou “aqueça o conhaque em uma panela pequena” são compreensíveis para um chef treinado, mas um algoritmo deve ser especificado de forma tão precisa que até um computador possa segui-lo sem ambiguidade.

Ainda assim, um programador pode aprender muito estudando um bom livro de receitas. (O autor, de fato, quase chamou este volume de "O Livro de Receitas do Programador". Talvez um dia ele escreva um livro intitulado "Algoritmos para a Cozinha.")

Vale notar que a exigência de finitude, por si só, não é suficiente para tornar um algoritmo prático. Além de possuir um número finito de passos, ele deve ser eficiente, ou seja, o número de etapas deve ser razoável. Por exemplo, existe um algoritmo que determina se as brancas podem sempre vencer no xadrez, assumindo jogo perfeito. Contudo, sua execução demandaria um tempo extraordinariamente grande, tornando-o inviável na prática, mesmo sendo finito. No Capítulo 8, discutimos alguns números finitos que, de tão grandes, ultrapassam nossa compreensão.

Na prática, buscamos não apenas algoritmos, mas algoritmos eficientes e elegantes. Um critério fundamental de qualidade é o tempo de execução, frequentemente expresso pelo número de vezes que cada passo é realizado. Outros fatores incluem adaptabilidade a diferentes arquiteturas computacionais, simplicidade e clareza. Muitas vezes, há vários algoritmos para resolver um mesmo problema, e a análise de algoritmos nos permite determinar qual deles é superior.

Vejamos, por exemplo, o Algoritmo de Euclides sob essa perspectiva. Suponha que conhecemos um valor fixo de $n$ e queremos saber, em média, quantas vezes o passo $E1$ do Algoritmo $E$ será executado para diferentes valores de $m$. Antes de tudo, precisamos verificar se essa média é bem definida, pois estamos lidando com um número infinito de escolhas para $m$. No entanto, observamos que, após a primeira execução do passo $E1$, apenas o resto de $m$ dividido por $n$ importa. Assim, para encontrar $T_n$, basta executar o algoritmo para $m = 1, 2, ..., n$, contar o número total de execuções do passo $E1$ e dividir por $n$.

A grande questão é determinar a ordem de crescimento de $T_n$: será aproximadamente $\frac{1}{3} n$? Ou talvez $\sqrt{n}$? Na verdade, essa questão leva a um problema matemático extremamente complexo e ainda não totalmente resolvido, analisado mais a fundo na Seção 4.5.3. Para valores grandes de $n$, pode-se provar que $T_n$ é aproximadamente $(12 \ln 2 / \pi^2) \ln n$, ou seja, proporcional ao logaritmo natural de $n$, com uma constante de proporcionalidade que talvez não seja intuitiva à primeira vista. A Seção 4.5.2 explora mais detalhadamente o Algoritmo de Euclides e outros métodos para calcular o máximo divisor comum.

A análise de algoritmos busca investigar essas questões quantitativas e, às vezes, avaliar se um algoritmo é ótimo sob determinado critério. A teoria dos algoritmos, por outro lado, trata de questões mais fundamentais, como a existência de algoritmos eficientes para determinados problemas.

Até aqui, nossa abordagem aos algoritmos foi informal, o que pode ser insatisfatório para leitores com inclinação matemática. Para construir uma teoria rigorosa dos algoritmos, encerramos esta seção com uma fundamentação formal baseada na teoria dos conjuntos.

Definimos formalmente um método computacional como sendo um quádruplo $(Q, I,$\Omega $, f)$, no qual $Q$ é um conjunto contendo os subconjuntos $I$ e $\Omega$, e $f$ é uma função de $Q$ em si mesmo. Além disso, $f$ deve deixar $\Omega$ fixo ponto a ponto; ou seja, $f(q)$ deve ser igual a $q$ para todos os elementos $q$ de $\Omega$. As quatro quantidades $Q$, $I$, $\Omega$, $f$ são destinadas a representar, respectivamente, os estados da computação, a entrada, a saída e a regra computacional. Cada entrada $x$ no conjunto $I$ define uma sequência computacional, $x0, x1, x2, ...,$ conforme segue:

Para cada entrada $x$ em $I$, define-se a sequência computacional $x_0, x_1, x_2, ...$ conforme a regra:

$x_0 = x e \quad x_{k+1} = f(x_k), para \quad k \geq 0.$

A sequência termina em $k$ passos se $k$ for o menor inteiro tal que $x_k$ pertence a $\Omega$. Nesse caso, diz-se que a sequência produz a saída $x_k$. Algumas sequências podem nunca terminar, e um algoritmo, por definição, deve sempre terminar em um número finito de passos para todo $x \in I$.

O Algoritmo $E$ pode ser formalizado nesses termos:

• $Q$ é o conjunto de todos os singletons $(n)$, pares $(m, n)$ e quádruplos $(m, n, r, i)$, onde $m, n, r$ são inteiros positivos e $i$ assume valores específicos;
• $I$ é o subconjunto de todos os pares $(m, n)$;
• $\Omega$ é o subconjunto de todos os singletons $(n)$.

Defina f da seguinte forma:

$f(m, n) = (m, n, 0, 1); \quad f(n) = (n);$

$f(m, n, r, 1) = (m, n, \text{resto de} \quad m \quad \text{dividido por} \quad n, 2);$

$f(m, n, r, 2) = (n) \quad \text{se} r = 0,\quad (m, n, r, 3)\quad \text{caso contrário};$

$f(m, n, p, 3) = (n, p, p, 1).$

A correspondência entre essa notação e o Algoritmo $E$ é evidente.

A formulação do conceito de algoritmo apresentada não inclui a restrição de efetividade discutida anteriormente. Por exemplo, $Q$ pode representar sequências infinitas que não são computáveis por métodos manuais, ou $f$ pode envolver operações que não são executáveis por seres humanos. Se desejarmos restringir a noção de algoritmo a operações elementares, podemos impor condições adicionais sobre $Q$, $I$, $\Omega$ e $f$, como exemplificado a seguir:

Seja $A$ um conjunto finito de símbolos, e $A^*$ o conjunto de todas as cadeias de caracteres sobre $A$ (ou seja, o conjunto de todas as sequências ordenadas $x_1x_2 \dots x_n$, com $n \geq 0$ e $x_j \in A$ para $1 \leq j \leq n$). A ideia central é codificar os estados da computação de modo que eles sejam representados por cadeias de $A^*$.

Agora, seja $N$ um número inteiro não negativo, e defina $Q$ como o conjunto de todos os pares $(\sigma, j)$, onde $\sigma$ pertence a $A^*$ e $j$ é um número inteiro tal que $0 \leq j \leq N$. Defina também $I$ como o subconjunto de $Q$ onde $j = 0$, e $\Omega$ como o subconjunto onde $j = N$. Se $\theta$ e $\sigma$ são cadeias de $A^*$, dizemos que $\theta$ ocorre em $\sigma$ se $\sigma$ pode ser decomposto como $\alpha\theta\omega$, onde $\alpha$ e $\omega$ são cadeias em $A^*$.

Para completar a definição, seja $f$ uma função do seguinte tipo, definida pelas cadeias $\theta_j$, $\varphi_j$ e pelos inteiros $a_j$, $b_j$, para $0 \leq j < N$:

$f(\sigma, j) = (\sigma, a_j) \quad \text{se } \theta_j \text{ não ocorre em } \sigma;$

$f(\sigma, j) = (\alpha\varphi_j\omega, b_j) \quad \text{se } \alpha \text{ é a cadeia mais curta tal que } \sigma = \alpha\theta_j\omega;$

$f(\sigma, N) = (\sigma, N).$

Cada passo desse processo computacional é claramente efetivo, e a experiência prática demonstra que regras de correspondência de padrões dessa natureza são suficientemente poderosas para realizar todas as operações que conseguimos executar manualmente. Existem muitas outras formas essencialmente equivalentes de definir um método computacional efetivo, como, por exemplo, utilizando máquinas de Turing. A formulação apresentada aqui é praticamente idêntica à que A. A. Markov propôs em seu livro The Theory of Algorithms [Trudy Mat. Inst. Akad. Nauk 42 (1954), 1–376], que foi posteriormente revisada e expandida por N. M. Nagorny (Moscou: Nauka, 1984; edição em inglês, Dordrecht: Kluwer, 1988).

---