O que é um algoritmo?

Tentaremos responder a esta pergunta no contexto de outra pergunta:

O que é Ciência da Computação?

Existe um dizer famoso em Ciência da Computação, frequentemente (e erroneamente) atribuído a Edsger Dijkstra que diz:

Ciência da computação tem tanto a ver com o computador como a Astronomia com o telescópio, a Biologia com o microscópio, ou a Química com os tubos de ensaio. A Ciência não estuda ferramentas, mas o que fazemos e o que descobrimos com elas.

Bom, mas se computadores não são o foco principal da Ciência da Computação, o que seria então o foco dessa ciência?

Para o professor Donald Knuth, Ciência da Computação é o estudo de algoritmos. Um algoritmo é uma sequência de regras, definida de forma precisa, descrevendo como produzir uma dada saída a partir de uma entrada específica em um número finito de passos.

Aspectos Históricos

Apesar de pensarmos que Ciência da Computação é uma ciência recente, algoritmos vêm sendo estudados desde os tempos antigos. Por exemplo, achados arqueológicos das décadas passadas revelaram tábuas dos povos Babilônicos descrevendo algoritmos para a realização de cálculos matemáticos.

Esses povos usavam algoritmos para representar fórmulas matemáticas. Assim, em vez de escrever uma fórmula como fazemos hoje, eles descreviam os passos para o cálculo da fórmula. Um exemplo de algoritmo (procedimento) encontrado nessas tábuas é transcrito abaixo:

Comprimento e largura devem ser iguais à área.
Você deve proceder como a seguir.
Faça duas cópias de um parâmetro.
Subtraia 1.
Tome o recíproco.
Multiplique pelo parâmetro que você copiou.
Isso dá como resultado a largura.

Esse procedimento quer dizer que, se tivermos $x + y = xy$, é possível calcular $y$ pela fórmula (procedimento) $y = {\left( x - 1 \right)}^{-1}x$.

O exemplo acima foi retirado do livro "Selected Papers in Computer Science", escrito por Donald Knuth. Aliás, a maior parte da discussão nesta seção foi retirada desse livro.

Pela discussão acima, vemos que o estudo de algoritmos, e em certa medida Ciência da Computação, não é algo recente, mas um processo bem estabelecido historicamente.

Agora que já vimos o aspecto histórico de algoritmos, daremos uma definição um pouco mais detalhada do que é um algoritmo.

Definição Mais Detalhada

Em poucas palavras, um algoritmo é um procedimento, uma receita, um processo, uma rotina, um método. "Um algoritmo é um conjunto de regras para se obter uma saída específica a partir de uma entrada específica. Cada passo de um algoritmo precisa ser definido de forma precisa o bastante para que ele seja traduzido para uma linguagem de programação e executado por um computador", ainda de acordo com Donald Knuth.

Existem duas condições para que um procedimento possa ser chamado de algoritmo. Primeiro, as regras descritas por ele precisam especificar operações que sejam tão simples e tão bem definidas que elas possam ser executadas por uma máquina. Além disso, um algoritmo precisa sempre terminar depois de um número finito de passos.

Um exemplo de algoritmo é como calcular a nota média dos alunos de uma turma. O procedimento (algoritmo) para isso envolve os seguintes passos:

  • Calcule a soma das notas da turma:

  • Inicialmente, a soma das notas da turma é zero. Vamos chamar essa soma de nota_total.

  • A seguir, veja a nota de cada aluno e some esta nota à nota_total.

  • Calcule a média da turma. Vamos chamar o total de alunos de n:

  • A média da turma será: nota_total / n.

No procedimento acima, temos todos os requisitos de um algoritmo mencionados acima. Nosso procedimento:

  1. é uma sequência de regras, definidas de forma precisa;

  2. e descreve como produzir uma dada saída a partir de uma entrada específica, em um número finito de passos.

Se quisermos ser um pouco mais precisos e evitar descrições em português, que podem ser ambíguas, podemos definir nosso procedimento (nosso algoritmo) de modo mais matemático:

nota_total = 0
Para cada um dos n alunos, faça:
    nota_total = nota_total + nota_do_aluno
media = nota_total / n

O algoritmo acima é bastante parecido com o que seria sua implementação em uma linguagem de programação. Algumas vezes, quando estamos criando um algoritmo, começamos com um procedimento mais "alto nível" como fizemos agora, mas o objetivo final é ir refinando o procedimento até obter algo mais preciso e sem ambiguidades.

Algoritmos versus Programas

Vimos acima que, para serem executados por um computador, algoritmos precisam ser traduzidos para uma linguagem de programação. Quando traduzimos um algoritmo para uma linguagem de programação estamos criando um programa de computador.

Assim, um programa é uma representação de um algoritmo em uma dada linguagem de programação. Podemos interpretar um algoritmo como sendo um método abstrato para cálculo de alguma saída a partir de alguma entrada, enquanto um programa é a implementação de um método computacional em uma linguagem de programação.

Essa distinção entre algoritmos e programas é importante e muitas vezes negligenciada. Algoritmos podem ser estudados e entendidos de modo independete do hardware ou de uma linguagem de programação específica. Por isso, frequentemente, livros-texto de algoritmos trazem o pseudo-código dos algoritmos.

Entretanto, quando tentamos de fato implementar os algoritmos, vemos que existem detalhes não especificados (ou de difícil compreensão) no pseudo-código, o que acaba tornando a implementação em uma linguagem de programação uma tarefa muito difícil.

Neste material, mostramos os algoritmos bem como implementações em Python de todos eles. Com essas implementações, você verá que os detalhes dos algoritmos ficarão mais claros, e se você quiser implementar os mesmos algoritmos em outra linguagem de programação de sua preferência, terá menos dificuldades do que se partisse somente do pseudo-código. Além disso, quando aplicável, explicaremos formas de usar os mesmos algoritmos por meio de bibliotecas da linguagem.

Playground

# Use este espaço para praticar o que você aprendeu nesta seção. # Basta digitar o código no espaço abaixo e clicar 'run'.
Anterior Início Próximo