No primeiro artigo desta série, o Hélio comentou: ‘Algoritmos’ é um tema pouco valorizado por muitos programadores iniciantes, que querem logo botar a mão na massa.

É a mais pura verdade. Quando eu tive a minha primeira noção do que são algoritmos (no dia 12 de julho de 2004, no Curso de Programação da Olimpíada Brasileira de Informática na UNICAMP), confesso que fiquei decepcionado. Qual a utilidade de algo tão formal pra algo que já sabemos fazer? Eu já programava em C e achei um saco o professor escrevendo no quadro aqueles pseudocódigos de problemas super simples, perdendo tempo com isso ao invés de programar. Porém, hoje percebo que algoritmos são muito mais legais (e importantes) do que eu pensava. Claro que para somar dois inteiros não há necessidade de escrever um pseudocódigo, mas algoritmos são representações essenciais para problemas mais complexos e grandes aplicações.

Acredito que você que já leu os dois primeiros artigos já deve saber, mas não custa lembrar: algoritmo é a relação entre entrada e saída do programa, é o rascunho do programa, o projeto. E um projeto antes de colocar a mão na massa é indispensável. Enquanto a implementação é a função dos pedreiros, o algoritmo é a função dos engenheiros. Se os engenheiros não existissem, acho que os pedreiros não iam conseguir fazer as casas e os prédios que eles constroem hoje em dia!

Não querendo desmerecer alunos de sistemas de informação, mas a maioria deles não passa de pedreiros.

O algoritmo sempre existe, mesmo que apenas no seu pensamento. A primeira coisa que você pensa quando quer fazer uma aplicação (a não ser que você seja louco) é: o que é a aplicação? O que ela vai fazer? E se você sair implementando uma coisa complexa, você vai se decepcionar depois demorando mais do que o tempo de fazer a implementação só para limpar o código! Por isso, representar algoritmos complexos é essencial.

E mais… Mesmo se você tivesse tempo infinito, memória infinita, etc. e tal (não tivesse necessidade de limpar o código), você vai precisar de um algoritmo pra provar que o seu programa funciona, para se organizar e para estudar a sua lógica. Se você não planejar um algoritmo para o caso acima, qualquer funcionalidade que você queira adicionar no meio, por falta de projeto e organização, vai demorar bem mais tempo. Por isso, algoritmo não é uma perda de tempo antes da programação, mas a programação é que se torna uma perda de tempo quando não teve um algoritmo (ou, um projeto). O livro Algoritmos: Teoria e Prática reforça essa interessante idéia na página 7:

Suponha que os computadores fossem infinitamente rápidos e que a memória do computador fosse livre. Você teria alguma razão para estudar algoritmos? A resposta é sim, se não por outra razão, pelo menos porque você ainda gostaria de demonstrar que o método da sua solução termina, e o faz com a resposta certa.

Outra utilidade do algoritmo é compartilhar idéias de problemas complexos. Todo programador entende um pseudocódigo e por isso convém muitas vezes apresentar sua idéia de um programa em forma de um algoritmo, num pseudocódigo, ao invés de passar um programa implementado em C para uma dúzia de programadores de VBScript (e sem dúvidas é muito melhor do que ter que aprender uma linguagem da Microsoft!!!).

Existe uma série de algoritmos comuns que todo programador deve conhecer (projetos prontos para muitas coisas complicadas que precisamos implementar no dia-a-dia) e isso é o que vamos começar a estudar no próximo artigo. :)

No primeiro artigo desta série, expliquei o que é um algoritmo e até citei exemplos do cotidiano, como acordar ou falar com outra pessoa. Talvez você nem tenha se dado conta, mas usando listas numeradas eu representei os algoritmos ali presentes, inclusive destacando a entrada e a saída de cada situação-problema. Porém, não é sempre assim que representamos algoritmos.

Não existe uma regra padrão para a representação de algoritmos. Cada pessoa escreve de forma diferente, mas o importante é ser legível e convencionado. Por exemplo, o livro Algoritmos: Teoria e Prática* traz nas páginas 14 e 15 convenções do pseudocódigo que utiliza no livro inteiro. Já eu, quando vou passar o mesmo algoritmo, utilizaria outro tipo de código, você pode utilizar outro, e por aí vai. Mas todos têm que ter o mesmo foco: legibilidade e fácil implementação para qualquer linguagem.

* A partir deste artigo, sempre que eu falar “Cormen”, “CLRS”, “Introduction to Algorithms” ou “Algoritmos: Teoria e Prática” estarei me referindo a um livro que é referência essencial nessa área. A versão que tenho (de onde tiro o número das páginas) é a tradução da segunda edição americana publicada pela Elsevier em 2002.

Os pseudocódigos costumam parecer um código em linguagem Pascal traduzido para a sua língua. :) Usam quase sempre estruturas que estamos acostumados a usar na programação, como se, enquanto, para, arrays, etc. Eles existem para que o algoritmo seja de fácil leitura para qualquer programador, que programe em qualquer linguagem “normal”. Veja o pseudocódigo do Insertion Sort, um algoritmo de ordenação de vetores bastante simples:

para j $\leftarrow{}$ 2 até comprimento do vetor, faça
 elemento $\leftarrow{}$ vetor[j]
 i $\leftarrow{}$ j - 1
 enquanto i > 0 e vetor[i] > elemento, faça
  vetor[i + 1] $\leftarrow{}$ vetor[i]
  i $\leftarrow{}$ i - 1
 fim-enquanto
 vetor[i + 1] $\leftarrow{}$ elemento
fim-para

(Não se preocupe em entender o que ele faz, AINDA, pois veremos isso mais adiante)

Se você programa em qualquer linguagem, você não terá dificuldade em traduzir esse pseudocódigo para ela. O pseudocódigo é sempre uma maneira bem simples de escrever o código. Veja por exemplo, o mesmo código em C:

for (j=2; vetor[j]!=NULL; j++) {
    elemento = vetor[j];
    for (i = j-1; i > 0 && vetor[i] > elemento; i--) {
        vetor[i+1] = vetor[i];
    }
    vetor[i+1] = elemento;
}

Você deve ter percebido que ao invés de usar três linhas com uma declaração, um condicional e um incremento, eu juntei todos num só for. Mas por isso o algoritmo é bem simples e sempre parte do princípio de que a sua linguagem é simples. Veja só a implementação do código em Pascal e compare-a com a do pseudocódigo:

for j:=2 to comprimento, do begin
    elemento := vetor[j];
    i := j-1;
    while i>0 && vetor[i] > elemento, do begin
        vetor[i+1] := vetor[i];
        i := i-1;
    end;
    vetor[i] := elemento;
end;

Linha por linha ela é exatamente igual! A única diferença é que o pseudocódigo é traduzido… Geralmente os pseudocódigos são parecidos sempre com essa base e suas implementações não são muito diferentes. E vai ser sempre dessa maneira que eu vou representar os algoritmos (usando pseudocódigos e alguns traduzindo para C para mostrar implementações). No entanto, qualquer dúvida sobre essa representação, fique a vontade para perguntar através dos comentários.

Um algoritmo é um procedimento computacional definido que recebe um ou mais valores (entrada) e produz um ou mais valores (saída). O algoritmo é aquela fórmula matemática, aquele pedaço de código, que fica ali no meio da entrada e da saída para transformar o primeiro no segundo.

Vamos supôr por exemplo que temos a função:

A sua entrada é o x e a sua saída é o y (ou f(x), o valor que a função retorna).

O algoritmo aqui seria o seginte:

1. Entrada: Receber o valor X.
2. Elevar X ao quadrado e guardar o número resultante como Z.
3. Dividir Z por 3 e guardar o número resultante como Y.
4. Saída: Imprimir o valor Y.

O algoritmo, portanto, é a lógica do nosso problema matemático, ou, informático. É a seqüência de passos que eu faço na minha cabeça (ou, quando é complexo, no papel) antes de escrever, em C, a função f:

int f(int x) {
   int z, y;
   z = pow(x, 2);
   y = z/3;
   return y;
}

Se formos pensar, veremos que tudo o que fazemos é um algoritmo, é um procedimento que recebe uma entrada e envia uma saída. Não só no computador, mas na vida. Quando eu falo com alguém, eu espero sua entrada (o que a pessoa fala pra mim), então penso e transformo essa entrada numa saída (a resposta que vou dar pra pessoa). E assim é com várias outras coisas. Podemos dizer também que acordar é um algoritmo, por exemplo:

1. Entrada: Meu cérebro disse que eu estou acordado!
2. Percebi que acordei, mas estou com sono. Espero um pouco.
3. Saída: Abrir os olhos.
4. Saída: Se espreguiçar.
5. Saída: Tirar a coberta.
6. Saída: Sentar na cama.
7. Saída: Sair da cama.

Podem existir vários algoritmos diferentes para resolver o mesmo problema. No caso de Acordar, cada um acorda de forma diferente, por exemplo. Foi até um exemplo meio estranho esse aí, mas outro algoritmo poderia dar outra saída, como por exemplo simplesmente abrir os olhos e cair da cama. Ou no caso acima da função matemática, poderíamos ter um algoritmo que fizesse a mesma coisa de maneira diferente também.

O algoritmo que usamos depende principalmente do tempo que ele demora pra ser executado e a memória que ele gasta no computador. Chamamos isso de custo. Quando começarmos a ver os algoritmos de ordenação de vetores (arrays), veremos que cada algoritmo faz uma coisa diferente, mas todos servem para o mesmo propósito: ordenar o vetor. Para uma entrada pequena, um pode ser mais rápido… Para uma maior, outro. Portanto, o algoritmo que queremos usar (o tempo que ele vai demorar pra ser executado e a memória que ele vai gastar no computador) depende principalmente do tamanho da entrada (que chamamos de n e no exemplo da função seria lá em cima seria a variável x).

Na maioria dos casos (e vai ser sempre assim aqui nos meus artigos), a entrada será o teclado (por exemplo, o usuário digita o X para a função) e a saída será a tela (por exemplo, o programa imprime o resultado da função, o Y, para a tela). Essas são a entrada e saída padrão (standard input output do C), que é usada nas olimpíadas e na maioria dos problemas que resolvemos no computador.

Em resumo, portanto, um algoritmo é a lógica de um programa computacional. Nos próximos artigos, isso deverá ser mais esclarecido e começaremos a ver algoritmos “de verdade” ;)

Qualquer dúvida, sugestão ou notificação de erro; poste um comentário ou me envie um e-mail (não só nesse, mas também nos próximos artigos). Espero que gostem.

Impressionante a quantidade de besteiras que todo programador faz… Às vezes, uma semana depois de fazer um programa ou um site, eu já sinto raiva do script que acabei de fazer e me sinto obrigado a refazê-lo. Brincando um pouco nas férias, estou refazendo vários problemas da OBI e cada vez mais percebo a quantidade de lixo que achamos nos nossos scripts. E o pior é perceber o tempo que eu levava pra fazer aqueles problemas que podiam ser resolvidos de maneira tão simples (e eu pensava que tinha uma solução muito boa)… Estou resolvendo a lista de tarefas da modalidade Programação Nível 2, mas apenas os problemas de grafos (todos eles eu já tinha resolvido, mas estou agora programando-os melhor). Confiram as besteiras que eu fiz nos primeiros deles:

Aeroporto

[enunciado]

Um problema de grafos? Não! Mas parece muito. Na verdade, se ele pedisse qualquer coisa mais do que o grau de cada vértice eu precisaria de representar usando grafos, mas a única coisa que ele quer é que eu conte a quantidade de vezes que cada número aparece na entrada.

A primeira solução deste problema, que agora já não está mais entre nós, foi feita no curso de programação básica da OBI 2004, em Campinas, quando começava a aprender grafos. Pra vocês terem uma idéia do drama, eu fiz uma busca em profundidade pra contar o número de arestas que cada vértice tem (pra medir o grau de cada vértice).

Confiram a básica solução que fiz ontem: (e que daqui a algum tempo posso vir a achar ridícula também… hehehe)

#include <stdio.h>
#define AMAX 101

int main() {
	int a, v, x, y, t[AMAX]; // t = tráfego, grau dos vértices
	int i, maior, teste=1;

	while (scanf("%d %d", &a, &v)&&a&&v) {
		maior=0;
		for (i=1; i<=a; i++) {
			t[i]=0;
		}
		for (i=0; i<v; i++) {
			scanf("%d %d", &x, &y);
			t[x]++;
			t[y]++;
			if (t[x]>maior) {
				maior=t[x];
			}
			if (t[y]>maior) {
				maior=t[y];
			}
		}
		printf("Teste %dn", teste++);
		for (i=1; i<=a; i++) {
			if (t[i]==maior) {
				printf("%d ", i);
			}
		}
		printf("bnn");
	}

	return 0;
}

Batuíra

[enunciado]

O objetivo é achar o caminho mínimo de peso de 1 a N. Uma simples busca em profundidade resolve o problema. Agora vejam a busca em profundidade que eu faria em 2004, que ainda não tirei da minha galeria de códigos: batuira.c e comparem com a que eu fiz ontem (e que ainda poderia ser melhorada):

#include <stdio.h>
#include <values.h>
#define NMAX 101

int n, marc[NMAX], g[NMAX][NMAX];
int resultado;

void buscaemprofundidade(int v, int soma) {
	int w;

	if (v==n) {
		if (soma<resultado) {
			resultado=soma;
		}
	} else {
		marc[v]=1;
		for (w=1; w<=n; w++) {
			if (g[v][w]&&!marc[w]) {
				buscaemprofundidade(w, soma+g[v][w]);
			}
		}
	}
}

int main() {
	int x, y, xy;
	int i, j, teste=1;

	while (scanf("%d", &n)&&n) {
		resultado=MAXINT;
		for (i=1; i<=n; i++) {
			marc[i]=0;
			for (j=1; j<=n; j++) {
				g[i][j]=0;
			}
		}
		while (scanf("%d %d %d", &x, &y, &xy)&&x&&y&&xy) {
			g[x][y]=xy;
			g[y][x]=xy;
		}
		buscaemprofundidade(1, 0);
		printf("Teste %dn%dnn", teste++, resultado);
	}

	return 0;
}

Dengue

[enunciado]

Esse foi com certeza meu maior susto. Foi por causa desse problema que eu resolvi escrever este artigo… Dá até vergonha de mostrar a busca em profundidade que usei para resolver o problema anteriormente. O objetivo do problema é descobrir partindo de que vértice do grafo o vértice que se encontra mais longe tem custo menor. Ou seja, é só fazer uma busca em largura com todos os vértices. Mas antigamente eu não simpatizava muito com a busca em largura, então fiz aquela besteira. E imaginem quanto tempo eu não levei pra fazer aquela joça… Bom… Pelo menos deve ter servido pra eu quebrar a cabeça naquela época! Vejam o código novo (sujeito a mudanças, é claro!):

#include <stdio.h>
#include <values.h>
#define NMAX 101

int main() {
	int w, i, j, x, y, teste=1, g[NMAX][NMAX], n, d[NMAX], fim, ini, fila[NMAX], v, a, md[NMAX], c;

	while (scanf("%d", &n)&&n) {
		for (i=1; i<=n; i++) {
			for (j=1; j<=n; j++) {
				g[i][j]=0;
			}
		}
		for (i=1; i<n; i++) {
			scanf("%d %d", &x, &y);
			g[x][y]=1;
			g[y][x]=1;
		}
		c=0;
		md[0]=MAXINT;
		for (v=1; v<=n; v++) {
			for (i=1; i<=n; i++) {
				d[i]=n;
			}
			md[v]=0;
			d[v]=0;
			ini=0;
			fim=0;
			fila[fim++]=v;
			while (ini!=fim) {
				a=fila[ini++];
				if (d[a]>md[v]) {
					md[v]=d[a];
				}
				for (w=1; w<=n; w++) {
					if (g[a][w]&&d[w]==n) {
						d[w]=d[a]+1;
						fila[fim++]=w;
					}
				}
			}
			if (md[v]<md[c]) {
				c=v;
			}
		}
		printf("Teste %dn%dnn", teste++, c);
	}

	return 0;
}

Bom… Simplificando… Se você não é programador, não seja; você vai ficar louco! :lol: Este problema que citei aqui não acontece só com esses problemas de olimpíadas mas também com vários scripts, principalmente os que vamos alterando com o tempo e adicionando novas features. Já recomecei do zero muitos sites para deixá-los decentes e muitos programas também (essa versão do aeroporto.c já é a terceira!) e não só esses de olimpíadas (o meu programa de ouvir música, em Bash, eu já fiz umas 10 vezes).

Quando eu acabar de re-resolver todos os problemas da seção de códigos lógicos eu vou publicar todos juntos. Por enquanto, vou deixar tudo do jeito que tá pra vocês apreciarem meus scripts mal-feitos. ;)

Quem costuma visitar meu blog perceberá que apareceu um ícone lá no canto inferior direito, escrito Bom Demais para o IE. A imagem, posicionada lá embaixo usando um position:fixed; (que o IE não suporta) é de uma campanha muito legal que você pode conhecer clicando no link. Participem e tenham um site “bom demais para o Internet Explorer”! :)

Hoje foi minha última aula desse ano e abertura da OLIS (olimpíada do meu colégio). Começaram extra-oficialmente as férias. Finalmente vou ter um tempinho pra poder estudar informática, matemática e música; aproveitar a praia, viajar, ler… Demorou, hein?

Como toda pessoa organizada (categoria que eu não me enquadro, mas estou tentando), fiz meu “plano” para aproveitar bem essas férias e também para decidir o que eu vou querer no ano que vem. Aqui embaixo está publicado, e sujeito a mudanças (porque meus objetivos sempre podem mudar). Notem também que eu coloquei algumas coisas como “ganhar olimpíada” que seriam conseqüência das outras ações. Além disso, eu coloquei alguns objetivos que podem parecer “sonhos”, mas acho que sempre é bom traçar objetivos difíceis pra tentar ir o mais longe possível.

Informática

Acho que foi a área em que eu menos evoluí nesse ano. É que é incrível que quanto mais eu aprendo, mais percebo que ainda tenho cada vez mais coisa a aprender. Isso não faz sentido matematicamente falando… A informática é desafiante e a gente sempre tem a impressão de que somos ignorantes. É como o Zeh falou num post em seu blog: “O mais legal de ser programador é olhar pra certas coisas que você fez no passado, que achava uma grande idéia, e perceber que aquilo era algo extremamente fedorento.”

Mas vamos lá…

• Dominar os algoritmos mais básicos de grafos, programação dinâmica e geometria (saber implementá-los sem consulta em C).
• Obter medalha de ouro na Olimpíada Brasileira de Informática.
• Participar da Olimpíada Internacional de Informática.
• Dominar o básico da linguagem C (saber gerenciar memória, usar bibliotecas como ncurses, usar sockets, etc.)
• Aprender de vez a programar em C/GTK, para criar interfaces gráficas.
• Dominar conceitos da orientação a objetos (abstração, encapsulamento, herança, poliformismo) e saber implementá-los em Java, C++ e PHP 4 e 5.
• Aprender um JavaScript mais avançado (saber criar aqueles marquees por exemplo, ou como o cara pode arrastar um div pela tela) e exercitar essas linguagens client-side e Ajax dentro dos padrões web.
• Saber diferenciar Unix/Linux/FreeBSD/OpenSolaris. Instalar estes outros sistemas no meu laptop.
• Exorcizar o laptop. Não usar mais nem Flash, abolir o Windows.
• Converter o laboratório de informática do Colégio Salesiano pra Linux (Edubuntu, que eu conheci essa semana e achei muito massa!).
• Programar com frameworks.
• Aprender Awk.
• Aprender alguma coisa de hardware e de baixo nível (Assembler).

Matemática

Nesse ano, fui mal nas duas olimpíadas (brasileira e catarinense) e mesmo ganhando medalha de bronze na Olimpíada de Maio, não fiquei muito contente. De qualquer maneira, sinto que estou evoluindo na matemática graças as aulas do Vavá e mesmo as do Fabiano, que são lerdas mas às vezes trazem uma novidade.

• Obter medalha de ouro na Olimpíada Regional de Matemática.
• Obter medalha na Olimpíada Brasileira de Matemática.
• Dominar geometria básica (decorar fórmulas dos volumes dos objetos, por exemplo).
• Fazer exercícios dos Eureka!s
• Fazer contas mentalmente mais rápido (exemplo: resolver uma Bháskara mentalmente em menos de 15 segundos)
• Trabalhar com matrizes.
• Trabalhar com funções de terceiro grau e superiores.
• Trabalhar com números complexos.
• Gabaritar a prova de matemática do vestibular do ITA no final do ano.
• Prosseguir com treinamento para olimpíadas com o professor Vavá.

Física

Física depois desse ano entrando na minha lista de matérias legais e que eu preciso estudar bastante pra passar no ITA… Vamos à lista…

• Dominar conceitos básicos e conhecer fórmulas básicas (Newton, Kelpler, Galileu, Einstein).
• Revisar meu livro de física desse ano (2005).
• Participar da Olimpíada Brasileira de Física.
• Participar da Olimpíada Brasileira de Astronomia.
• Prosseguir com grupo de estudos físicos com o professor Valdir.
• Acertar 75% da prova de física do vestibular do ITA no final do ano.

Trabalho

Resolvi parar de trabalhar no Colégio, porque o salário era muito baixo (cerca de 200 reais é pouco, mesmo pra trabalhar 10 horas por semana) e o emprego fixo é muito chato (tem dias que eu vou lá e não faço nada, outros dias que tem um monte de coisa pra fazer e eu não consigo acabar nada; fora os alunos que vão lá no Lab. de Informática encher o saco – hehehe). Vou pegar mais freelances e acho que vou lucrar mais me dedicando só a isso e aos estudos, tanto financeiramente quanto nos aprendizados. Mas vou fazer uma proposta ao Colégio que é continuar mantendo o site deles (afinal, eles precisam de alguém pra fazer isso), mas fazer de casa e com isso só perder tempo quando precisar de alguma mudança, em casa!

Compras

Compras prioritárias que estou querendo fazer de livros e acessórios nesse ano… Aceito presentes! :D

• Como programar em C (H. M. Deitel e P. J. Deitel) – e a mesma coisa de Java
• Programando em C para Linux, Unix e Windows (Marcos Laureano)
• Programação Avançada em Linux (Gleicon da Silveira)
• Máquina fotográfica digital
• iPod
• Escaleta
• Piano (não, esse aqui já foi sonhando)

Passeios e Cursos

Viagens [sendo] programadas…

• Campinas – SP: Se tudo der certo, pra visitar meu irmão na UNICAMP e participar do Curso de Programação da OBI
• Porto Alegre – RS: Fórum Internacional do Software Livre
• Rio de Janeiro – RJ: Não tem nenhum evento não, mas eu queria conhecer.
• México: Se tudo der certo, estamos lá na olimpíada internacional!

Música

No ano que vem, quero voltar a fazer aula de piano. Acho que farei com a mãe de uma amiga, que dá aula na ADMITA.

Nesse final de semana fomos pra Curitiba (quem acompanha meu feed viu as fotos no Flickr). Meu irmão Bruno fez vestibular pra música/violão na UNICAMP. Ele não achou a prova muito difícil e falou que acertou uns 80%. Ainda tem mais uma fase de prova de conhecimentos gerais e depois é a prova de aptidão (violão). Acho que ele passa… :)

Alguém tem notícias dos caras da UFSC? Já fizemos a final da Olimpíada Regional Catarinense de Matemática (por que eles não mudam o nome pra quem é de fora saber de onde que é e quem é de dentro não pensar que toda a Região Sul participa da olimpíada?) há dois meses, o ano já vai acabar, e NADA! (nem mesmo o gabarito da prova, mesmo sem o resultado final…)

Sempre que eu escrevo posts grandes, eu me perco no meio. Então se alguma parte ficou difícil de entender ou se tem algum erro de português aí, me avisem! :)