Archive for the ‘Ciência da Computação’ Category

Coordenadas homogêneas

Saturday, April 24th, 2010

Conheci as coordenadas homogêneas por acaso. Era 2004, ganhei a modalidade iniciação da Olimpíada Brasileira de Informática e passei o inverno estudando C, acho que por dois motivos: interesse pelos problemas da modalidade programação e desejo de aproveitar bem o curso que os medalhistas fazem na UNICAMP; ou talvez fosse apenas falta do que fazer ou curiosidade mesmo. Não importa.

Confundo os cursos de 2004, 2005 e 2006, mas lembro que no primeiro aprendi com um monitor sobre recursão, representação de grafos e busca em profundidade. Lembro também que foi em 2004 que conheci o CLRS (livro que comprei alguns meses depois e tenho na cabeceira até hoje). Esse post, porém, é sobre um acontecimento mais aleatório relacionado a esse curso e, ouso afirmar, digno de figurar n’O Andar do Bêbado do Mlodinow.

O pessoal da modalidade programação ia tirar cópias de um livro do Stolfi e do Rezende, chamado “Fundamentos de Geometria Computacional” (dá pra baixar aqui). Nem sabia do que estavam tirando xerox, mas vi que era barato e que todos os mais velhos estavam querendo, então também pedi.

Folheei o livro, não entendi nada, deixei num canto e voltei a abrir alguns anos depois, não lembro exatamente quando. E foi aí que fez-se a luz. A primeira parte é sobre coordenadas homogêneas.

Coordenadas homogêneas? A ideia parece simples (até demais) pra ser poderosa. Basicamente você representa uma coordenada em (X, Y) \in \mathbb{R}^2 com uma tripla ordenada [w, x, y] tal que x = \frac{X}{w} e y = \frac{Y}{w}. A reta tem a mesma representação.

1
2
3
4
5

struct ponto {
	int w, x, y;
};
 
typedef ponto reta;

E o que isso tem demais? Você deixa de precisar de pontos flutuantes pra maioria das operações geométricas; ganha pontos no infinito (eles são a interseção entre retas paralelas!) que permitem fazer fórmulas sem preocupação com casos especiais, usar a mesma fórmula pra determinar uma reta gerada por dois pontos ou por um ponto e um vetor etc.; tem representações iguais (e dualidade) entre pontos e retas (e.g. interseção entre retas p e q = reta determinada por pontos p e q); e mais um monte de outras coisas.

Uau! Como eu não ouvi falar disso antes? Eu não sei a razão, mas, embora tenham várias vantagens, as coordenadas homogêneas não são muito populares na universidade, nem entre os maratonistas. No entanto, são usadas em projetos grandes que usam muita geometria (e.g. OpenGL).

Quero código! Vou mostrar como resolvi o problema Symmetry (2002 TopCoder Inv Round 4 – Division I, Level Three).

O enunciado é simples: Dados n (2 \leq n \leq 200) pontos inteiros (com coordenadas de -10000 a 10000) determinar quantas linhas de simetria existem entre eles.

Dá pra fazer em O(n^3) com a seguinte ideia:

  1. Crie uma árvore binária balanceada indexada por retas. (em C++, map <reta,int>)
  2. Para cada par de pontos, determine a reta de simetria entre eles e adicione 2 a essa reta na árvore binária. (O(n^2 \log n))
  3. Para cada reta na árvore binária, adicione 1 para cada ponto que pertence a essa reta. (O(n^3))
  4. É fácil ver que a reta é uma reta de simetria do conjunto de pontos se e somente se seu valor na árvore binária for n.

O problema geométrico está no segundo passo: determinar a reta de simetria entre dois pontos. Sejam esses pontos p e q. É preciso:

  1. Determinar o ponto médio entre p e q.
  2. Determinar a reta que passa por p e q (o enunciado garante que p != q).
  3. Determinar uma reta (ou um vetor) perpendicular à reta do passo acima.
  4. Determinar a reta que passa pelo ponto médio e tem a direção do vetor perpendicular do passo 3.

Determinar o ponto médio sem usar ponto flutuante seria trivial de qualquer forma (basta multiplicar todas as coordenadas por dois), mas com coordenadas homogêneas isso é desnecessário. É fácil ver que o ponto médio m entre p = [w_0, x_0, y_0] e q = [w_1, x_1, y_1] é:

m = [ 2 w_0 w_1 , w_1 x_0 + w_0 x_1 , w_1 y_0 + w_0 q_1 ]

1
2
3

ponto ponto_medio(ponto p, ponto q) {
	return (ponto) { 2*p.w*q.w, q.w*p.x+q.x*p.w, q.w*p.y+q.y*p.w };
}

Três pontos [w_0, x_0, y_0], [w_1, x_1, y_1], [w_2, x_2, y_2] são colineares se

\left| \begin{array}{ccc} w_0 & x_0 & y_0 \\ w_1 & x_1 & y_1 \\ w_2 & x_2 & y_2 \end{array} \right| = 0 ,

o que nos permite concluir que a reta r = \langle W, X, Y \rangle que passa por p = [ w_0, x_0, y_0 ] e q = [ w_1, x_1, y_1 ] é:

r = \langle +x_0 y_1 - y_0 x_1, -w_0 y_1 + w_1 y_0, w_0 x_1 - w_1 x_0\rangle.

1
2
3

ponto reta_determinada_por(ponto p, ponto q) {
	return (reta) { +p.x*q.y-q.x*p.y, -p.w*q.y+q.w*p.y, +p.w*q.x-q.w*p.x };
}

(um ponto [w, x, y] pertence a r se Ww + Xx + Yy = 0)

1
2
3

int ponto_na_reta(ponto p, reta r) {
	return p.w*r.w + p.x*r.x + p.y*r.y == 0;
}

Agora a parte mais legal: a fórmula para determinar uma reta que passa por dois pontos funciona com pontos no infinito (pensemos em pontos no infinito como vetores, porque eles tem direção mas tem w = 0): o resultado é a reta determinada por um ponto e uma direção. O vetor perpendicular à reta \langle W, X, Y \rangle é [ 0, X, Y ].

1
2
3

ponto ponto_infinito_na_reta_perpendicular(reta r) {
	return (reta) { 0, r.x, r.y };
}

E isso é tudo. Agora basta criar uma representação única da reta pra guardar na árvore binária.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

reta reformata_reta(reta r) {
	if (r.w < 0) {
		r.w = -r.w;
		r.x = -r.x;
		r.y = -r.y;
	} else if (r.w == 0) {
		if (r.x < 0) {
			r.x = -r.x;
			r.y = -r.y;
		} else if (r.x == 0 && r.y < 0) {
			r.y = -r.y;
		}
	}
	int d = gcd(r.w, gcd(abs(r.x), abs(r.y)));
	return (reta) { r.w/d, r.x/d, r.y/d };
}

Usando essas funções, primeiro e segundo passos da solução são:

map <reta,int> M;
for (int i = 0; i < n; i++) {
	for (int j = i+1; j < n; j++) {
		reta s = reformata_reta(reta_determinada_por(P[i], P[j]));
		ponto pm = ponto_medio(P[i], P[j]);
		ponto dir = ponto_infinito_na_reta_perpendicular(s);
		reta r = reformata_reta(reta_determinada_por(pm, dir));
		if (M.find(s) == M.end())
			M[s] = 0;
		if (M.find(r) == M.end())
			M[r] = 0;
		M[r]+= 2;
	}
}

Terceiro e o quarto são:

1
2
3
4
5
6
7
8

int output = 0;
for (map <reta,int>::iterator i = M.begin(); i != M.end(); i++) {
	for (int j = 0; j < n; j++)
		if (ponto_na_reta(P[j], i->first))
			i->second++;
	if (i->second == n)
		output++;
}

O código completo ficou com umas 90 linhas com comentários e linhas em branco e foi aceito na primeira submissão (ok, na verdade na segunda, mas não foi devido à geometria muito menos à precisão): symmetry.cpp. Não é lindo?

Tags: , , , , ,
Posted in Ciência da Computação | No Comments »

Vergonha

Tuesday, November 24th, 2009

O disciplina é “Princípios de Desenvolvimento de Algoritmos” e ela está sendo ministrada neste semestre pelo Prof. Dr. Carlos Eduardo Ferreira, participante do grupo de otimização combinatória, diretor nacional da Maratona de Programação e orientador da minha iniciação científica.

A turma é do Bacharelado em Ciência da Computação no IME-USP.

Acabei de receber a seguinte mensagem de um dos monitores:

Screenshot

Preciso dizer mais alguma coisa?

Tags: , , , , , ,
Posted in Ciência da Computação | 4 Comments »

Bacharelado em Ciência da Computação

Tuesday, March 31st, 2009

Os jovens saem do Ensino Médio, enlouquecem fazendo cursinhos pra passar no vestibular e entram num curso universitário sem saber o que isso significa.

Em primeiro lugar observo que o curso de Ciência da Computação hoje é o que o esteriótipo afirma: é um curso de viciados em jogos. Até aí tudo bem, cada um faz o que bem entende nos seus momentos de lazer.

O problema é que acredito que isso colaborou para viror um reduto de usuários de computador, pessoas que leram “Computação” no nome e pensaram: Eu gosto de mexer no computador, acho que este é o meu curso.

Our new mobile lab
Creative Commons License photo credit: Christy Tvarok Green

Vejo que os adolescentes que hoje entram em Ciência da Computação desprezam a matemática e não vêem sentido em provar as propriedades básicas dos números em disciplinas como Álgebra. Ouvi esses dias na minha sala de aula: Se nós já sabemos que funciona, pra que provar? São pessoas que entram num bacharelado sem vontade de estudar teoria.

A realidade que percebo, tanto na UFSC quanto no IME-USP, é decepcionante. E em muitas universidades o curso está mudando de cara pra satisfazer estes estudantes e não o contrário, como deveria ser. O IME-USP ainda tem um curso excelente, mas advinhe o que os alunos aprendem na primeira matéria do curso (chamada de Introdução à Computação)? Java e programação orientada a objetos. Eles aprendem classes e métodos antes de aprenderem operadores lógicos e laços.

Estou no curso errado? Prefiro pensar que não. Porque a definição está ao meu lado. Às vezes penso que o nome do meu curso deveria mudar, para não pegar desavisados que não procuram o que é antes de entrar. Deveria ser algo como Bacharelado em Ciência dos Algoritmos, Bacharelado em Matemática Discreta… não sei. Mas é claro que tudo isso seria besteira. Na verdade quem precisa mudar são as pessoas. Tanto as que entram no curso, quanto as pesoas em geral, que pedem favores pra cientistas da computação pensando que eles são técnicos de informática. Elas precisam pesquisar o que é o curso antes de entrar nele, precisam saber que Ciência da Computação é um ramo da matemática que existe desde muito antes da criação dos computadores digitais.

Acredito que todos que são capazes de passar na carreira da Poli na Fuvest são capazes de ler o primeiro parágrafo do texto da Wikipedia em português sobre Ciência da computação, que diz:

Ciência da computação é o estudo dos algoritmos e suas aplicações, bem como das estruturas matemáticas indispensáveis à formulação precisa dos conceitos fundamentais da teoria da computabilidade e da computação aplicada. Desempenha por isso um papel importante na área de ciência da computação a formalização matemática de algoritmos, como forma de representar problemas decidíveis, i.e., os que são suscetíveis de redução a operações elementares básicas, capazes de serem reproduzidas através de um qualquer dispositivo mecânico/eletrônico capaz de armazenar e manipular dados. Um destes dispositivos é o computador digital, de uso generalizado, nos dias de hoje, pelo custo reduzido dos componentes eletrônicos que formam o seu hardware.

Bom, é apenas um desabafo. Espero que ninguém se ofenda, e preciso torcer fortemente pra isso mesmo porque é certo que os ofendíveis são maioria. Pois ando percebendo que estou fora de moda. Revolto-me quando ouço um professor uspeano elogiar o Java, alegando ser uma linguagem moderna e maravilhosa porque aceita acentos nos nomes das funções enquanto o C é antiquado. Abandono a sala ao ouvir que hoje em dia classes são mais importantes do que laços e nomear corretamente funções é mais importante do que conhecer algoritmos.

Sem dúvidas o problema sou eu, que serei talvez um dos últimos Bacharéis em Ciência da Computação que sabe implementar uma estrutura de dados, afinal (sic) se o Java já tem um heap implementado para que reinventar a roda?

Talvez eu seja um dos últimos a lembrar e valorizar o trabalho de verdadeiros cientistas da computação como Edsger Wybe Dijkstra, que certa vez disse:

Ciência da Computação está tão relacionada aos computadores quanto a Astronomia aos telescópios, Biologia aos microscópios, ou Química aos tubos de ensaio. A Ciência não estuda ferramentas. Ela estuda como nós as utilizamos, e o que descobrimos com elas.

Precision knob?
Creative Commons License photo credit: gogoninja

Declaro-me a favor de um curso de Ciência da Computação onde os computadores sejam tratados apenas como ferramentas. Há outros cursos para quem não pensa assim e entra na universidade buscando uma formação sobre desenvolvimento ágil e produtividade. Não estou criticando quem busca isto. Porém, na minha opinião, estes definitivamente não deveriam entrar num curso chamado Bacharelado em Ciência da Computação.

Tags: , ,
Posted in Ciência da Computação | 15 Comments »