Vamos falar de Computação - Algoritmos

Sexta passada o Charles me perguntou o que eu fazia, e como funcionava o que eu fazia, e eu me atrapalhei muito na resposta porque não é exatamente fácil de explicar, e porque no fundo eu não sei todos os princípios que regem a computação (eu não sei como funciona a máquina de turing!), e também porque eu aprendi umas coisinhas lá no design, outras ali no ime, outras conversando com a galera (especialmente o chalom), outras aqui na netpoint, e isso tudo me deu uma visão mais ou menos global, mais ou menos intuitiva de como é a computação, como funcionam os computadores, como essa coisa toda se amarra e se articula e no final das contas funcionam (ou não, mas isso é outra história).

O Charles me fez duas perguntas, uma bem complicada, e outra formalmente complicada mas informalmente simples de responder.
- Então você escreve um texto e aí ele faz aparecer aquelas coisas na tela? Como?
e
- O que as pessoas querem dizer quando falam em "algoritmo"?

Foi bem ele ter perguntado isso, porque algoritmos são a base do trabalho de um programador. Bom, pelo menos de um que faça qualquer coisa de interessante.

Essencialmente, um algoritmo é um método, ou uma máquina, que recebe alguma coisa como entrada (input), processa essa coisa e devolve uma determinada saída (output). Imagine por exemplo um moedor de carne como um algoritmo que recebe carne e devolve carne moída. Ou, muito mais apropriadamente, o 'modo de fazer' de uma receita de bolo como um algoritmo que recebe determinados ingredientes e devolve um bolo. Na verdade algoritmos se parecem muito com receitas de bolo porque eles são receitas para se conseguir uma coisa a partir de outra. A diferença básica é que os algoritmos foram definidos por matemáticos, o que significa que neles não há nenhuma abertura para "a gosto" ou "até parecer bom". Se um algoritmo é bom e correto, você pode provar formalmente que ele funciona, e mais uma porção de coisas a respeito dele.

Vou dar uns exemplos, só porque entender o que é um algoritmo é útil de modo geral pra entender como qualquer programa funciona. Imagine, por exemplo, que eu quero pegar vários números e elevá-los ao quadrado. Então, eu vou executar, para cada um deles, um algoritmo que recebe um número n e devolve n^2. Eu vou escrever esse algoritmo assim:

quadrado(numero n) {
   devolve n*n;
}

(o padrão da computação é que * represente multiplicação)
Esse é um exemplo meio idiota, mas imagine que em vez disso eu quero executar uma função f(x) para vários valores de x. Imagine que eu estou, por exemplo, querendo desenhar um gráfico. Digamos que eu queira um gráfico para a função f(x) = 2x^2 + 4x +5. Então posso escrevê-la assim:

f(numero x) {
   devolve (2*x*x) + (4*x) + 5;
}

E escrever um algoritmo que usa essa função para obter os valores de f(x) a partir de uma lista de valores de x:

valores(função f, lista X) {
   nova lista Y;
   para cada Xi em X
      Yi recebe o valor de f(Xi);
  
   devolve Y;
}

Ou outro que recebe essas lista e desenha um gráfico:

gráfico(função f, lista X) {
   para cada x em X
      desenha no gráfico ponto (x,f(x));
  
}

Eu não sei o quão claro isso soa para pessoas que não estão acostumadas com essa linguagem. Existem várias formas de dizer a mesma coisa, vários níveis de rigor e tal. Na matemática, estamos muito acostumados a usar diversos algoritmos. Por exemplo, todo mundo aprendeu a usar o algoritmo de arme-e-efetue de, por exemplo, multiplicação. Eu poderia escrever ele no meu pseudo-código aqui, e acho que vocês reconheceriam:

multiplica(número x, número y) {
   novo número resultado;
   para cada algarismo x(i) de x (com i de 0 a log(x)
      novo número resultado_parcial(i);
      para cada algarismo y(j) de y
         soma (x(i)*y(j)) em resultado_parcial(i);
      soma (10^i)*resultado_parcial(i) em resultado;
   devolve resultado;
}

Esses algoritmos estão ficando muito esqusitos. Talves eu devesse escrevê-los mais assim:

multiplica(número x, número y){
   denote cada algarismo de x por x(i), com i variando de 0 a log(x)-1, de acordo com a posição da direita para a esquerda;
   denote cada algarismo de y por y(j), com j variando de 0 a log(j)-1, de acordo com a posição da direita para a esquerda;
   tome i = 0 e o algarismo da unidade de x (x(0)) como x(i);
   LOOP1:
      tome j = 0 e o algarismo da unidade de y (y(0)) como y(i);
      LOOP2:
         multiplique x(i) por y(j) por 10^i e some ao resultado parcial(i);
         acresça j de um e tome por y(j) o próximo algarismo de y e repita a partir de LOOP2;
      acresça i de um e tome por x(i) o próximo algarismo de x e repita a partir de LOOP1;
   some todos os resultados parciais em um Resultado Final;
   devolva o Resultado Final;
}

(esta versão ficou muito parecida com uma função em Assembly, pra quem se interessa)

Observem como o arme-e-efetue da multiplicação faz exatamente isso, com apenas uns detalhes irrelevantes de ordem de diferença! Dá pra fazer o mesmo com o algoritmo da divisão, da soma, da subtração, da potenciação, do fatorial, de resolver algumas equações e também com aqueles métodos dos gregos (em especial Euclides e Pitágoras) para descobrir se um número é primo, para encontrar máximo divisor comum, etc.

Enfim, me dêem um feedback (quem é das humanas, vai) se isso fez algum sentido pra vocês. Vou parar por aqui antes de me afundar mais.