terça-feira, 3 de maio de 2011

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.

6 comentários:

Rafael F. disse...

Nao faltou multiplicar o resultado parcial por 10^(i-1) ou algo assim? Não sei exatamente aonde na verdade, mas me parece faltar algumas multiplicações por 10 aí, pra definir as dezenas, centenas, etc.

Acho que o mais confuso está a definição de posicionamento (i) e (j) na verdade. Talvez ela já esteja resolvendo essa questão dos resultados e eu não vi.

Charles disse...

TLDR

Charles Bosworth disse...

Hahaha, brincadeira. Depois te digo melhor o que eu achei. Mas se pudesse complementar minha pergunta, eu gostaria de saber o que são FISICAMENTE os algorítmos usados na computação, e que forma física dentro de um chip têm as equações. Quer dizer, não sei se essa é uma pergunta que se faça. Mas comento melhpr depois...

Anônimo disse...

FISICAMENTE as instruções são zeros e uns, isto é, presença ou ausência de corrente.

Uma determinada seqüência de zeros e de uns simboliza para o processador que ele deve fazer algo bem específico.

Ozzer Seimsisk disse...

o que é TDLR?

Bom, algoritmos são estruturas lógicas e não físicas. A parte física é bem mais abstrata e tem várias coisas e subcoisas que eu não vou saber explicar direito por muito tempo ainda. Mas tem muita coisa interessante que atribui sentido a essa parte física fundamental, se isso te interessar. Enfim, se você perguntar prum engenheiro da computação, ele tem uma chance bem maior de conseguir aprender essa parte de hardware. Eu só tenho uma idéia vaga.

Diogo disse...

Eu nunca vi, mas parece que esse "Feynman lectures on computation" é um livro para bixos que explica como se controi um computador a partir dessas coisas de ferro, plastico e silício.

Talvez seja legal olhar o cap. 1.