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.

n formas de se atravessar um rio com uma corda

1. Prender uma ponta da corda num galho alto sobre o rio e balançar até o outro lado.
2. Amarrar uma ponta em alguma coisa do outro lado do rio e se puxar para o outro lado
3. Amarrar do outro lado e passar por cima da corda bamba
4. Fazer uma ponte de corda, amarrar do outro lado e atravessar
5. Usar a corda pra fazer uma jangada e navegar até o outro lado
6. Prender a corda em alguma coisa alta deste lado, se balançar e se lançar para o outro lado (é diferente de 1 porque você larga a corda)
7. Prender uma pedra na ponta, usar a corda pra verificar a profundidade e, se for raso, atravessar andando
8. Pescar um peixe muito grande e ir cavalgando-o até a outra margem (estou usando uma ordem mais ou menos cronológica, acho que essa foi a primeira das absurdas)
9. Queimar a corda pra fazer sinal de fumaça e chamar alguém que tenha um barco
10. Usar a corda como cabresto e atravessar a cavalo
11. Amarrar a corda numa pedra no meio do rio e se lançar no rio pra fazer um pêndulo horizontal usando a corrente no lugar da gravidade (essa foi apelidada de "pêndulo relativístico" pq segundo o Chalom seria necessária velocidade próxima de c pra fazer o péndulo subir)
12. Amarrar a corda em alguma coisa na cordenada z da outra margem e se jogar no rio sem nadar, de forma que a correnteza faça um meio-pêndulo horizontal e te leve para a outra margem (uma variação mais possível de 11)
13. Amarrar a corda num objeto voador (pássaro/avião/super-man) e deixar ele te levar para a outra margem
14. Amarrar a corda na Lua e... esperar que ela te leve?
15. Amarrar a corda na ponta de uma árvore alta e puxá-la de forma a derrubar a árvore, formando uma ponte
16. Usar a corda para fazer um estilingue e se lançar sobre a água!
17. Vender a corda e comprar um barco
18. Girar a corda bem rápido para se levantar como um helicóptero (como a Gabi, engenheira aeronáutica do grupo, destacou, seria necessário girar ortogonalmente a outra ponta da corda para controlar o movimento)
19. Construir uma hélice movida a corda (com aquele sistema de enrolar-desenrolar)
20. Se a corda for suficientemente grande, assorear o rio com ela e passar por cima
21. Usar a corda para contruir uma catapulta ou trebuchet
22. Com a corda amarrada numa árvore na mesma margem, correr em semi círculo e esperar que a inércia te leve em MCU até a outra margem
23. Amarrar a corda numa madeira balsa e atravessar nadando
    

Tenho certeza de que discutimos algumas outras, mas não estou lembrando no momento.

"O Boi tem a fazenda inteira dentro dele!"

Situação: Maria (ou qual seja o nome dela) é uma sul-rio-grandense que veio trabalhar como empregada doméstica em São Paulo.

— Maria, vai no açougue e traz um lagarto pra fazer assado.
— Lagarto?! Come-se lagarto aqui em São Paulo?!
— Não, lagarto, a parte do boi, assim-assim-etc...
— Ah, quer dizer tatu!

(história contada pela avó do André)

Dica do quotidiano - vidro embaçado

Aprendi ontem no cursinho uma técnica bastante simples para impedir o vidro de embaçar: basta passar detergente na superfície e limpar a seco, com pano ou de preferência papel absorvente. O vidro é um composto iônico de sílica, sódio e potássio, que atrai fortemente a água. O detergente se liga a ele por sua ponta polar e cria uma camada apolar, ou seja, hidrofóbica. Estou pensando em experimentar usar isso nos vidros dos carros aqui, embora seja um processo um pouco demorado limpar todo o detergente excedente sem usar água (a água dissolve o detergente o remove completamente do vidro).

Aparentemente, um dos alunos do psor de química usou esse recurso para escrever mensagens secretas no espelho do banheiro, que só apareciam quando o espelho embaçava. Ah, a criatividade =)!

Aprendi hoje: alto forno

Hoje (ou ontem, sei lá) tive uma aula sobre obtenção de metais puros e o professor contou a história fantástica de como descobriram como funciona o alto-forno. Para quem não lembra, alto-forno é aquele forno gigantesco usado para transformar minério de ferro (óxido de ferro) em ferro metálico. O protótipo desse forno foi inventado na Idade do Ferro, mas hoje em dia eles são bastante complexos. Enfim, um dia um grupo de pesquisa decidiu descobrir o que acontecia de verdade dentro dele, e teve uma idéia brilhante: dissecação.
Eles desligaram o forno ao mesmo tempo em que derramavam sobre ele uma quantidade colossal de nitrogênio líqüido, congelando tudo o que estava dentro dele mais ou menos no lugar em que estava, e depois fatiaram o forno congelado para estudar cada uma das fases separadamente!