8-dez-2003
|
Aluno: Leandro Esteves Barion |
Orientador: Eduardo Colli |
Essa monografia tem como objetivo descrever o trabalho que meu orientador e eu desenvolvemos para a criação de material didático multimídia visando o ensino de topologia algébrica.
Para muitas pessoas, estudar matemática não é exatamente algo prazeroso, ou sequer interessante. Seja por culpa de um professor “carrasco” na 4ª série, por sentirem dificuldade no aprendizado, ou simplesmente por não verem utilidade prática naquele monte de números e letras, muitas pessoas terminam os estudos com um certa fobia de matemática.
Este trabalho aborda uma área específica da matemática - a topologia algébrica -, procurando ensiná-la de forma agradável e assim mostrando que o estudo não precisa ser necessariamente encarado como uma obrigação chata. O assunto é tratado com uma linguagem simples, exemplos práticos, imagens e animações, além de um jogo que permite ao leitor exercitar de forma desafiadora o conteúdo aprendido.
O material introduz alguns conceitos básicos da topologia - como definição de curvas, superfícies e nós - e avança com toda a teoria necessária para se enunciar e provar o Teorema de Classificação das Superfícies, abrangendo tópicos como homeomorfismos, característica de Euler, orientabilidade e soma conexas, entre outros.
Minha principal responsabilidade nesse projeto foi desenvolver os softwares de auxílio ao aprendizado.
A princípio, foi estabelecido que o projeto deveria ter duração de cerca de um ano. Não houve, contudo, uma estipulação rígida de prazos. A cada reunião, eu e meu orientador conversávamos e decidíamos qual seria o próximo passo a ser dado. Realizávamos novas reuniões após qualquer avanço significativo que eu realizasse, ou caso eu encontrasse algum obstáculo que não conseguisse transpor sozinho.
O projeto acabou durando muito mais do que o esperado inicialmente por um série de fatores, dentre os quais o principal foi a minha falta de conhecimento inicial sobre diversos assuntos (como programação orientada a objetos, computação gráfica, geometria computacional, algoritmos em grafos), e, mais tarde, minha falta de tempo devido ao próprio andamento do curso de bacharelado em ciências da computação.
Toda a teoria foi transcrita para HTML, de forma que pode ser visualizada em qualquer navegador da Internet. A grande vantagem na escolha deste formato, além da boa organização e navegação agradável que ele proporciona, foi a possibilidade de incluir imagens e animações interativas como exemplos.
Para as animações interativas, utilizamos JavaScripts para que o leitor pudesse pausar a animação, avançar ou retroceder quadro a quadro, ou ir diretamente a um quadro específico da animação.
Esses scripts carregam as imagens de cada quadro das animações no início de cada animação. O objetivo disso é impedir que a animação fique lenta devido à carga de imagens durante a animação, ou que a página se torne demasiadamente pesada (no caso de tentarmos carregar todos os quadro junto com a página principal).
Os demais recursos utilizados são nativos do formato HTML.
O jogo foi desenvolvido para que, ao fim dos estudos, o leitor possa exercitar parte do conhecimento adquirido.
A idéia é simples: uma superfície qualquer é selecionada aleatoriamente e recortada em pedaços (durante o recorte, cada pedaço deve ter seus lados identificado para que a superfície original seja a única superfície que pode ser remontada). Esse pedaços serão as "peças" com que o usuário vai interagir. O objetivo é descobrir qual a superfície original selecionada pelo jogo.
A interface é bastante simples, composta por três quadros principais: um menu contendo todas as "peças" que formam a superfície recortada, um painel que mostra uma prévia da peça selecionada no menu, e uma área de jogo (que chamo de tabuleiro), onde o jogador pode recortar e colar as peças. A peça selecionada no menu sempre é mostrada no painel de prévia. Um clique duplo numa peça do menu coloca ou retira a peça em questão do tabuleiro, observando-se que pode haver no máximo duas peças simultaneamente no tabuleiro.
Além disso, temos acima uma barra de ferramentas com os botões "Novo Jogo", "Responder" e "Ajuda", e uma barra de status abaixo, que mostra algumas mensagens úteis.
As arestas das peças são identificadas através de cores e setas, de forma que duas arestas só podem ser coladas se forem da mesma cor, e as setas precisam estar apontando na mesma direção quando a colagem for feita. Após feita a colagem de todas as peças formando uma só, há uma série de passos a serem seguidos que facilita a solução do jogo. Todos esses passos são explicados no material teórico.
Os seguintes algoritmos foram estudados e implementados em Java para utilização durante o projeto.
Dado um polígono de n lados, com os vértices nas coordenadas (x1, y1), (x2, y2), ..., (xn, yn), podemos realizar a rotação desse polígono de theta graus em torno de um ponto (a, b) com as seguintes operações:
Para cada i, com 1 <= i <= n, fazemos:
xi = (xi - a) . cos (theta) - (yi + b) sen (theta) + a
yi = (xi - a) . sen (theta) + (yi - b) cos (theta) + b
Dado um polígono de n lados, com os vértices nas coordenadas (x1, y1), (x2, y2), ..., (xn, yn), podemos transladar esse polígono de px pontos na direção do eixo x e py pontos na direção do eixo y realizando as seguintes operações:
Para cada i, com 1 <= i <= n, fazemos:
xi = xi + px
yi = yi + py
Dado um polígono de n lados, com os vértices nas coordenadas (x1, y1), (x2, y2), ..., (xn, yn), podemos modificar a escala desse polígono baseados em 2 fatores sx (que será o fator de escala na direção do eixo x) e sy (que será o fator de escala na direção do eixo y) com as seguintes operações:
Para cada i, com 1 <= i <= n, fazemos:
xi = xi . sx
yi = yi . sy
Como exemplo, seja um quadrado de vértices (0,0), (0,1), (1, 1), (1,0). Tomando sx = 50% e sy = 70%, teríamos como resultante um retângulo de vértices (0,0), (0, 0.7), (0.5, 0.7), (0.5, 0).
Devido ao fato de estarmos tratando cada vértice do polígono como um vetor que vai da origem do sistema de coordenadas até o ponto do vértice, essa modificação de escala será em torno da origem do sistema de coordenadas. O que fazemos então é realizar uma translação do polígono logo após cada passo da modificação de escala, para que a modificação de escala seja feita em torno de um ponto desejado.
Dado um polígono P de n lados, com os vértices nas coordenadas (x1, y1), (x2, y2), ..., (xn, yn), e um ponto p = (x0, y0), o seguinte algoritmo é capaz de descobrir se o ponto p está dentro do polígono P:
N = 0 {inicialização}
para i de 1 até n {teste cada lado pipi+1 de P}
se yi <> yi+1 então {lado não é horizontal}
(x, y) = a intersecção de pipi+1 com L
se x = x0 então
p0 é da fronteira: PARE.
senão, se x > x0 e y > min(xi, xi+1) então {não tem y mínimo}
N = N + 1
senão, se p pertence ao lado horizontal pipi+1 então
p é da fronteira: PARE.
se N é ímpar, então p é interior a P; senão, p é exterior.
Alguns algoritmos de triangulação de polígonos foram estudados com o objetivo de já ter clara a superfície que será a solução do Jogo do Aderbal desde o início. Contudo, a solução adotada na implementação final do jogo foi outra, mais "preguiçosa": geramos aleatoriamente uma quantidade de polígonos de 3, 4 ou 5 lados, damos identificações (cores) e orientações, também aleatoriamente, para cada aresta, apenas tomando cuidado para que cada aresta possua um par e para que não hajam peças isoladas (isto é, para que todas as peças possam ser coladas, formando uma só peça).
Essa abordagem garante que as superfícies geradas pelo jogo possam ser de qualquer tipo, e variem bastante entre um jogo e outro, o que seria um pouco difícil de implementar de outro modo. A superfície gerada aleatoriamente pode ser descoberta mais tarde, através da Característica de Euler da superfície.
Para garantir que todas as peças possam ser coladas em uma só, conforme expliquei acima, crio um grafo que contenha um vértice para cada lado dos polígonos do jogo, e crio uma aresta entre dois desses vértices se os lados pertencem ao mesmo polígono ou se os lados têm a mesma cor (identificação).
A partir daí, com uma busca simples (no caso, em profundidade, mas poderia perfeitamente ter sido em largura) no grafo consigo determinar se o grafo construído é conexo, e assim se há apenas uma superfície a ser identificada no jogo.
Após estudar orientação a objetos e padrões, refatorei o código de forma a implementar alguns padrões de projeto que considerei importantes e úteis:
O padrão de projeto (design pattern) Singleton busca garantir que uma classe tenha somente uma instância e fornece um ponto global de acesso para ela.
Uma das classes implementadas no jogo requer exatamente este tipo de comportamento com relação a ela. A classe chamada SacoDePeças representa de fato a instância do problema que o jogo propõe, e as outras classes, que proporcionam ao usuário os meios para solucionar o problema, trabalham como suas clientes. Dessa forma, deve haver apenas uma instância dessa classe por jogo, e essa instância deve dar acesso aos clientes através de um ponto de entrada bem conhecido.
Do ponto de vista da teoria de orientação a objetos, a utilização desse padrão nos dá diversas vantagens, tais como:
- Acesso controlado à instância única: o encapsulamento que é feito da instância da classe que implementa esse padrão permite que haja total controle sobre como e quando os clientes acessam a instância.
- Espaço de nomes reduzido: esse padrão não "polui" o espaço de nomes com variáveis globais que representam instâncias únicas.
- Permite um número variável de instâncias: é possível deixar uma porta aberta para o caso de se desejar criar mais instâncias da classe singleton.
- Maior flexibilidade do que operações de classe: ao invés de utilizarmos o padrão singleton, poderíamos utilizar, por exemplo, funções-membro estáticas. Isso, contudo, impede, por exemplo, o número variável de instâncias citado acima.
Este padrão tem como objetivo a criação de uma interface que permita a geração de famílias do objetos relacionados ou dependentes, sem contudo especificar suas classes concretas. O objetivo aqui é fornecer uma biblioteca de classes de produtos revelando somente suas interfaces.
Esse padrão se mostrou conveniente para a criação de uma aplicação escalável. Na versão atual, as peças possuem uma interface que foi sendo desenvolvida por mim no decorrer do projeto, e contém diversas particularidades de implementação. No caso de existir a necessidade de modificar a implementação dessas peças, esse padrão garante facilidade nessa mudança.
A principal vantagem na implementação desse padrão no jogo é, portanto, a facilidade que ele nos dá na troca de famílias de produtos. Mas ele também nos dá outras facilidades, como:
- Isolamento das classes concretas: a classe que implementa a "fábrica" torna-se a responsável por criar os objetos-produto, isolando os clientes das classes de implementação - os clientes manipulam os objetos-produto através de suas interfaces abstratas somente.
- Garante a integração entre os objetos-produto: como os objetos-produto são projetados para trabalharem juntos, é importante que apenas uma família de objetos seja usada de cada vez. Esse padrão assegura isso.
Há, contudo uma desvantagem na utilização desse padrão, no que diz respeito à teoria de orientação a objetos. Essa desvantagem, contudo, não é impeditiva nesse caso:
- É difícil suportar novos tipos de produtos: caso por algum motivo seja necessário modificar a interface do produto, será necessário modificar a classe que implementa a Abstract Factory e todas as suas subclasses.
As atividades que realizei durante o projeto não se limitaram pura e simplesmente a programação.
Foi feita bastante pesquisa antes de se decidir qual a linguagem de programação que seria utilizada. A linguagem Java foi escolhida devido a diversos fatores:
Um problema com o qual nos deparamos então foi a forma de distribuição do programa. Vislumbramos então duas opções: criaríamos executáveis para as plataformas mais comuns (como Windows, Linux e MacOS) ou disponibilizaríamos um ambiente de execução Java (Java Runtime Environment) junto com o aplicativo.
Esse problema ainda está em estudo, mas segunda alternativa nos parece mais palpável, principalmente por não encontrarmos um gerador gratuito de executáveis Java para outra plataforma além do Linux.
Também realizamos alguma pesquisa em torno da licença do formato GIF. Independentemente dessa licença (que venceu esse ano, atualmente o GIF é um formato público), contudo, decidimos que seria mais interessante o uso dos Javascripts para as animações no material HTML, que permitiria maior interação do usuário com os exemplos.
O projeto teve início na metade do ano de 2001, quando ainda cursava o segundo ano do curso e tinha assistido somente a disciplinas introdutórias de computação. Isso fez com que eu tivesse que pesquisar sobre diversos assuntos que poderia vir a aprender mais tarde durante o curso.
Certamente muitas disciplinas do curso foram importantes para a realização do projeto, algumas mais diretamente (através de algoritmos que formam implementados no projeto, por exemplo), outras indiretamente.
Algumas matérias optativas que não cursei por motivos diversos teriam sido de grande apoio no desenvolvimento do projeto:
Considero que todas as disciplinas do BCC foram de alguma forma úteis à minha formação. Porém, entre as matérias cujo conteúdo considero de utilidade duvidosa, destaco:
Algumas matérias do BCC, como Laboratório de Programação e Engenharia de Software, têm o diferencial de nos propor um projeto de duração de um semestre. Elas são bastante interessantes na medida em que participamos de todas as fases de um projeto, e somos forçados a estar atentos à documentação, clareza de código e outros assuntos que muitas vezes ignoramos em outros trabalhos.
Nesse sentido, essas matérias proporcionam um aprendizado muito importante. Porém, um aspecto que dificilmente pode ser visto em um projeto de uma disciplina são as escolhas que você precisa fazer durante um projeto.
Numa matéria, devido ao tempo limitado e à necessidade de uma certa padronização dos projetos para possibilitar a correção, há alguns pontos do projeto que ficam engessados.
No projeto de formatura, grande parte das decisões sobre tecnologia, foram tomadas por mim. Isso proporcionou um aprendizado diferente do conhecimento técnico ao qual estava acostumado.
Durante o último ano do curso, realizei estágio na Editora Abril. Apesar disso, preferi fazer meu trabalho de formatura baseado em um projeto desenvolvido ao longo do curso, por considerá-lo um trabalho mais interessante do que aquele que desenvolvi no estágio.
Contudo, o estágio que realizei foi bastante importante por proporcionar um visão muito diferente das alternativas que temos ao escolher a área de trabalho que posso atuar. O estágio que realizei foi bastante focado no negócio da empresa e nos processos relacionados a esse negócio. A visão que eu possuía, e que acredito ser compartilhada por muitos alunos do IME, é uma visão muito mais técnica, voltada para a tecnologia por si só, e não para a tecnologia num papel secundário, utilizada como suporte ao negócio principal da empresa.
Essa nova opção que percebi, sem dúvida nenhuma, requer muito menos conhecimento técnico do que o que foi aprendido na faculdade. Porém, o aprendizado em torno do que a empresa realiza é muito recompensador, e fez com que eu me perguntasse qual o sentido de estudar novas tecnologias, aprofundar meu conhecimento em uma área da computação e talvez até criar algum tipo de nova tecnologia ou teoria. Qual é a razão disso?
Ainda estou amadurecendo a resposta a essa pergunta, mas acredito que cada um de nós, que somos "apaixonados" pela computação, deve ter uma resposta diferente. E acho fundamental que não percamos essa resposta de vista jamais durante nossas carreiras nessa área.
[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L. , Introduction Algorithms. MIT Press. 1990.
[2] Gamma, E. , Helm, R., Johnson, R. , Vlissides, J., Padrões de Projeto. Bookman. 2000.
[3] O'Rourke, J., Computational Geometry in C. Cambridge University Press 1998
[4] Gilbert Strang, Linear Algebra and its Applications, Hartcourt Brace and Company International Edition, 1988.
[5] Java API Documentation. http://java.sun.com/api/index.html
[6] Deitel, H. M., Deitel, P. J., Java Como Programar. Bookman.2001