Astral: Um Ambiente para Ensino de Estruturas de Dados através de Animações de Algoritmos^•

o Uma versão preliminar deste artigo foi publicada nos Anais do V Congresso Iberoamericano de Educação Superior em Computação, México, setembro de 1996.

Islene C. Garcia^†

Pedro J. de Rezende^†

Felipe C. Calheiros^†

† Instituto de Computação - Universidade Estadual de Campinas - Caixa Postal 6176

13083-970 Campinas, SP, Brasil - {islene|rezende|felipec}@dcc.unicamp.br

Suporte financeiro do RHAE.

Suporte financeiro do CNPq e Fapesp.

Suporte financeiro da Fapesp.

Sumário

Estendemos as abordagens passiva e ativa utilizadas para ensino de algoritmos e estruturas de dados através de recursos de animações gráficas, introduzindo uma nova abordagem construtiva e descrevemos o ambiente Astral projetado para explorar seus benefícios no contexto do ensino de disciplinas de graduação na área de computação. Nesta abordagem, além do estudante ter acesso a aplicativos exemplos providos de animações gráficas que ilustram o funcionamento de algoritmos, ele também realiza suas próprias animações durante o processo de implementação da estrutura e dos algoritmos de maneira simplificada mas com visualização gráfica notável e resultados sensivelmente positivos na aprendizagem.

Abstract

We extend the passive and active approaches employed in teaching algorithms and data structures using resources of graphics animations, introducing a new constructive approach and we describe the Astral programming environment designed to explore its benefits in the context of undergraduate disciplines in the computer science field. In this approach, a student, besides having access to sample applications with graphical animations that show the behavior of the algorithms, can also build his own animations during the implementation process in a rather simple manner, producing graphical visualization and leading to positive results in the learning process.

Palavras Chave: Estruturas de Dados, Animação de Algoritmos, Visualização de Algoritmos, Laboratório de Ensino, Ambientes de Aprendizagem Baseados em Computador.

1 Introdução

Diversos sistemas para implementação de animações de algoritmos e de estruturas de dados [14,16] foram produzidos desde o trabalho pioneiro de Brown [3,4], como por exemplo, [1,7,13]. Vários destes sistemas exploram muito bem a pontencialidade do uso de visualizações gráficas das operações realizadas nas estruturas de dados como ferramenta de ensino. O uso de movimento em tempo real, cores e sons enriquecem ainda mais o poder de comunicação [6].

De fato, algumas experiências positivas já foram relatadas na literatura [10] e [12], principalmente com o uso de sistemas que utilizam a abordagem ativa (veja seção 2) na qual o aprendiz interage com as animações na criação de instâncias testes. Por outro lado, a ênfase na qualidade da animação gráfica para enriquecer a abordagem ativa da maioria dos sistemas levou-os a um grau de complexidade que impede seu uso para fins de criação de animações pelos próprios aprendizes. Deste modo, sua utilização se limita à interação, ainda que ativa, com as animações pré-implementadas.

Do mesmo modo que a experimentação durante a operação das animações enriquece o aprendizado mais do que a mera observação passiva delas, é de se esperar que, com um sistema onde a própria implementação das animações gráficas é facilitada a ponto de poder ser realizada pelo estudante, a absorção do funcionamento dos algoritmos seja ainda mais intensa.

Com o objetivo de prover um tal sistema, desenvolvemos um ambiente para a arquitetura Macintosh utilizando a plataforma de programação Think Pascal.

Este artigo traz na seção 2 uma breve descrição das principais abordagens ao uso de animações de algoritmos no ensino. Na seção 3 são citados vários dos projetos mais relevantes na área. Descrevemos na seção 4 o ambiente que desenvolvemos, detalhando sua arquitetura e apresentando alguns exemplos. Finalmente, na seção 5 são colocadas algumas conclusões sobre os benefícios deste ambiente, tendo em vista a nossa experiência com seu uso no ensino de disciplinas de estruturas de dados.

2 Abordagens

Em livros textos e aulas convencionais, de modo a facilitar o aprendizado de algoritmos utilizam-se mecanismos que vão além da descrição em (pseudo) linguagem de programação, como ilustrações.

Por outro lado, o excesso destas mesmas ilustrações quando vistas estaticamente contribuem muito pouco para aumentar a compreensão dos algoritmos dado que, além das informações depictadas, há grande comunicação implícita na correlação entre elas. Esta correlação pode ser mostrada através da animação gráfica das imagens, dando ganho considerável de comunicação de informação.

Em [3], M. Brown introduziu a idéia de ambientes dedicados à construção de animação gráfica computadorizada como ferramenta para ensino em computação como já é também aplicado com sucesso em outras áreas, como química, anatomia e simulação de circuitos.

Um primeiro uso de animação de algoritmos é dado quando se assiste a um filme [11] ou à execução de uma seqüência pré-programada de eventos [3]. Esta abordagem é denominada passiva, pois o usuário se comporta como mero espectador e ela é útil para a complementação de livros-texto e aulas.

Uma limitação clara, no entanto, está no fato de o usuário não poder testar novos conjuntos de dados e ter de ficar limitado aos conjuntos a ele fornecidos. Para evitar esta restrição, alguns sistemas [1,7,13] introduziram facilidades para que seus usuários pudessem fazer as suas próprias experiências, direcionando o andamento do algoritmo. Tal abordagem é denominada ativa.

Resultados positivos para o uso desta abordagem foram relatados por Lawrence et al. em [12] em experiência realizada com o ambiente Polka. Estes resultados confirmam que a abordagem ativa é mais poderosa, pois tem-se uma participação maior por parte do usuário.

Diante da oportunidade de associar o ensino teórico de algoritmos e estruturas de dados a uma disciplina de laboratório de software, decidimos verificar se um acréscimo no nível de participação do aprendiz no processo de animação resultaria em ganho ainda maior na aprendizagem. Nossa tentativa visou incorporar à fase de implementação realizada pelos estudantes algumas chamadas a rotinas gráficas de alto nível para visualização tanto das estruturas de dados quanto das atuações dos algoritmos implementados para manipulação delas. Para viabilizar essa tarefa fez-se necessária a implementação de um ambiente de programação de animações em uma plataforma adequada e amigável. Criamos, para implementar esta nova abordagem, denominada construtiva, o ambiente Astral descrito na seção 4 com o qual mesmo um estudante iniciante pode realizar animações gráficas sofisticadas com um mínimo de esforço.

Esse ambiente foi utilizado em laboratório de software durante três semestres (2/94, 1/95, 2/95) com resultados muito positivos à aprendizagem, como descrevemos na seção 5.

3 Projetos Relacionados

Nesta seção são citados alguns trabalhos que influenciaram positivamente o projeto e desenvolvimento do ambiente Astral. Não houve pretensão alguma aqui de fazer uma resenha exaustiva de todos os trabalhos relacionados.

Balsa (Brown ALgorithm Simulator and Animator) [3] foi desenvolvido na Brown University no início dos anos 80 e seu intuito era o de servir como um laboratório de experimentação com representações dinâmicas de algoritmos em tempo real. Seu sucessor, Balsa-II introduziu uma interface mais amigável e uma maneira homogênea para a execução e interações com animações, trabalhando sobre a plataforma Macintosh e com a linguagem Pascal.

No início dos anos 90, surgiu o projeto Zeus <http://www.research.digital.com/SRC/zeus/home.html> de M. Brown [5,7,8,9] cujas contribuições incluíram uma proposta de separação entre algoritmo e visualizadores, colocando interfaces bem definidas entre eles; o suporte à construção de programas de grande porte, orientados a objetos e a utilização da linguagem Modula 3. Em Zeus, múltiplos algoritmos podem ser executados concorrentemente, facilitando a análise de diferenças e similaridades entre vários algoritmos.

O projeto Zada <http://ls4-www.informatik.unidortmund.de/RVS/zada.html> desenvolvido na University of Dortmund implementou algoritmos distribuídos utilizando o ambiente Zeus.

Xtango [13] <http://www.cc.gatech.edu/gvu/softviz/algoanim/xtango.html> é um sistema de animação de algoritmos de propósito genérico que permite a construção de animações em tempo real. O objetivo principal é prover facilidades para os usuários que irão construir as suas animações, fornecendo uma interface de alto nível. Utiliza a linguagem C e opera sobre plataformas Unix e X11 Window System. Polka <http://www.cc.gatech.edu/gvu/softviz/parviz/polka.html> é sucessor de Xtango e foi projetado para dar suporte ao desenvolvimento de animações concorrentes, de maneira a facilitar a exibição de algoritmos paralelos.

O projeto AnimA [1] foi desenvolvido na Unicamp por R. Amorim e P. de Rezende e seu principal objetivo é a produção sistemática de animações em C++ dentro de um ambiente de estações de trabalho Unix. As experiências obtidas através da implementação desse projeto foram de grande valia para a implementação do Astral.

4 Astral

O projeto do ambiente Astral <http://www.dcc.unicamp.br/~rezende/ASTRAL> visou atender as necessidades de preparação de diversos exercícios de implementação de estruturas de dados utilizando animações gráficas, de modo homogêneo sob uma interface consistente. A partir das características básicas do ambiente e de sua biblioteca de suporte, foram produzidos diversos destes exercícios que deram origem à primeira experiência de que temos conhecimento da aplicação da abordagem construtiva no ensino de estruturas de dados — o uso de mecanismos de animação para auxiliar na implementação de algoritmos pelos próprios estudantes.

O ambiente Astral foi desenvolvido para arquitetura Macintosh [2], sobre Mac/OS v. 7.5. Um ponto positivo desta escolha é relacionado às facilidades oferecidas por esta plataforma para a implementação de aplicativos gráficos, com mecanismos simples para gerenciamento de janelas, menus, assim como para o desenho e manipulação de objetos gráficos. Além disso, o fato de a interface oferecida ao usuário final ser extremamente amigável (e portanto excelente para pessoas com pouca experiência) faz o Astral ter grande apelo a esse público.

A linguagem escolhida para implementação foi Pascal que é adequada ao ensino de programação básica devido à sua simplicidade, verificação forte de tipos e mecanismos para estruturação e modularização. O processo de animação foi feito utilizando-se funções e procedimentos, sem alterações à linguagem ou utilização de pré-processadores. Em um nível acima do sistema operacional, temos uma camada que agrupa rotinas de interesse geral para a construção de animações que obedeçam ao nosso modelo, denominada camada básica. Fazem parte desta camada o encapsulamento de tópicos como manipulação de janelas de texto, a visualização e a comunicação com o usuário da aplicação assim como o tratamento de eventos e o gerenciamento de objetos gráficos.

Para cada animação é construída uma camada específica que contém o código referente à visualização da estrutura de dados que se pretende animar. Ao usuário do ambiente caberá escrever o seu algoritmo fazendo uso das interfaces oferecidas pelo conjunto de camadas que estão em níveis inferiores, como ilustra a figura 1.

Figura 1: Arquitetura básica do ambiente

As interfaces oferecidas ao usuário do ambiente são escolhidas de maneira a formar, para cada animação, um conjunto minimal e padronizado, não sobrecarregando a tarefa do aprendizado de sua utilização. É conseqüência deste requisito que a qualidade da animação final, em termos de detalhes dos passos exibidos, é função da criatividade do programador da camada específica que deve maximizar o conteúdo semântico da informação mostrada graficamente, sem estender o número de chamadas gráficas. Para ilustrar o poder que pode ter um tal conjunto minimal de chamadas gráficas, a figura 4, na seção 4.2, mostra que uma única chamada à função DrawTree é suficiente para a animação das alterações de uma árvore AVL devidas a uma inserção, incluindo os efeitos de rotação.

4.1 Arquitetura

A figura 2 ilustra de maneira mais detalhada o conteúdo de cada uma das camadas e os principais relacionamentos entre elas e mostra, de maneira resumida, o fluxo de execução de uma animação. O usuário que a executa gera eventos, como seleção de itens de menu ou entrada de dados, que são filtrados pelo gerenciador de eventos. A maior parte destes eventos é tratada na camada básica e são transparentes para os demais programadores.

Eventos específicos para uma animação, como a seleção de um item de menu indicando um pedido de execução de um algoritmo é passado para a camada específica, que irá ativar o código do usuário. É este quem irá se encarregar de fazer as alterações devidas na estrutura de dados e chamar as rotinas adequadas dos visualizadores. A cada vez que um visualizador é acionado, ele verifica o estado da estrutura de dados e reflete as alterações feitas de maneira suave (veja um exemplo na figura 4).

4.2 Utilização do Ambiente

A finalidade de cada uma das animações, ou exercícios, é que o usuário entenda o seu objetivo, consiga acompanhar os passos necessários para alcançá-lo e seja capaz de fazer sua própria implementação de cada algoritmo. Para isto, além dos elementos do ambiente propriamente dito contamos com uma camada de apoio, ilustrada na figura 3. Tal camada é fundamental para o sucesso do processo de aprendizado e pode complementar aulas expositórias.

Figura 2: Arquitetura detalhada do ambiente

Figura 3: Camada de Apoio

Para a compreensão dos objetivos é fornecido um arquivo texto explicativo e um aplicativo-exemplo sobre o qual o usuário pode explorar o comportamento dos algoritmos com conjuntos de dados sugeridos ou próprios (participação ativa).

Para a fase implementação contamos com o ambiente de programação Think Pascal [15]. Este contém um editor de texto que realiza verificação de erros sintáticos em tempo de digitação assim como indentação automática. Além disso, seu ambiente de depuração é bastante completo, permitindo a execução passo a passo, o estabelecimento de breakpoints (interrupção da execução em pontos específicos do código), de watchpoints (interrupção da execução quando determinada posição de memória é alterada) e depuração a nível de programa fonte, dentre outras facilidades.

Tal ambiente define uma aplicação como sendo um "projeto" formado por vários módulos. É entregue ao estudante um arquivo contendo a especificação da estrutura de dados e um modelo do módulo do usuário que consiste apenas de um esqueleto das operações que ele deve completar.

Além disso, a camada de apoio conta com um arquivo texto que contém as interfaces das rotinas de visualização que são usadas para a realização das animações pelo estudante. Podem ainda ser fornecidos arquivos de dados especiais para teste, como por exemplo um conjunto de elementos a serem inseridos em uma árvore AVL, causando rotações em série.

Figura 4: Animação de uma inserção em árvore AVL

4.3 Vantagens da abordagem construtiva

Dentre as vantagens da abordagem construtiva estão mecanismos para facilitar o processo de abstração, o fato de a animação refletir o código implementado pelo aprendiz e as várias facilidades para a detecção visual de erros. Com isso, está-se incentivando o processo de compreensão e auto-correção.

O uso de chamadas às rotinas gráficas pelo usuário desde as etapas iniciais de sua implementação se mostra uma excelente ferramenta de depuração. As animações que apresentamos refletem o estado da estrutura de dados como um conjunto, enquanto depuradores comuns permitem, na maioria das vezes, a visualização de apenas um único elemento por vez. Dessa forma, a detecção da correção das imagens torna-se mais rápida. Apenas com uma breve análise de uma imagem como as mostradas na figura 6, somos capazes de verificar se seus elementos estão ordenados ou não, enquanto a verificação se uma seqüência de números está em ordem crescente é bem mais lenta e cansativa.

A própria animação pode ser projetada de maneira a orientar o aluno, acrescentando informações para facilitar a detecção dos erros de implementação mais comuns. Na figura 4, por exemplo, podemos notar que cada nó mostra qual é o seu fator de balanceamento. Embora esse não seja um detalhe relevante à animação e até redundante em animações corretas, é de enorme valia para o desenvolvedor.

A soma desses dois itens, mostra da estrutura como um conjunto e exibição de informação para detecção de erros, possibilita a observação de efeitos colaterais em outras partes da estrutura, provocadas por erro na implementação de suas operações. Estamos, dessa forma, adiantando a manifestação do erro e portanto provendo mecanismos para que o estudante encontre-o e conserte-o de maneira mais rápida. Além disso, o fornecimento de arquivos para teste são úteis para aumentar a maturidade do estudante no que diz respeito ao teste do seu programa frente a várias possibilidades de entrada. A figura 5 mostra um exemplo de efeito colateral na remoção da raiz e de uma árvore de busca quando a sub-árvore direita (reduzida ao elemento i) do elemento escolhido para substituição desapareceu durante o processo. 

4.4 Exemplos de Animações Implementadas

Esta seção é dedicada à apresentação de figuras retiradas de algumas das animações implementadas por estudantes utilizando conjuntos minimais de funções gráficas providas pela biblioteca do ambiente Astral. Por limitações de espaço, serão colocadas apenas algumas imagens e uma breve explicação para cada um dos tópicos apresentados.

Iniciando com algoritmos de ordenação, podemos ver na figura 6(a) o QuickSort, cujo comportamento recursivo pode ser observado através da disposição dos elementos, que estão separados em grupos que vão se aproximando progressivamente da diagonal da janela. O segundo algoritmo, figura 6(b), ilustra o MergeSort cujo comportamento é exibido em três fases: antes da execução do algoritmo, com alguns grupos já ordenados e prontos para a realização de uma etapa de conquista do algoritmo e ao término da execução, com todos os elementos ordenados. Por fim, a figura 6(c) mostra o comportamento do HeapSort após o heap ter sido montado e com os elementos de maior valor do vetor sendo posicionados.

5 Conclusões

Foi descrito o ambiente Astral para auxílio ao entendimento e implementação de algoritmos utilizando-se animações gráficas. Este ambiente permite a exploração dos três tipos de abordagem citadas: passiva — através da utilização de ferramentas de gravação de eventos; ativa — através dos aplicativos-exemplo, e construtiva — através de interfaces minimais e padronizadas para implementação de animações.

Embora sem a aplicação de um método sistemático de análise de resultados quantitativos de aprendizado, depois de utilizarmos o Astral dentro de disciplinas de laboratório de software para ensino de estruturas de dados ao longo de um ano e meio, ministradas por três docentes, tivemos oportunidade de verificar uma sensível melhoria de desempenho dos estudantes comparando-se com semestres anteriores, onde os laboratórios de software utilizavam programação tradicional (sem animação). Este desempenho destacado foi observado tanto nas avaliações durante a própria disciplina, quanto também vem sendo observado neste momento (um ano mais tarde) quando os estudantes estão cursando uma disciplina de projeto e análise de algoritmos. A sua fixação das noções de algoritmos em estruturas de dados, de paradigmas de projeto de algoritmos e de análise de eficiência se percebe muito mais sólida que a de estudantes de semestres anteriores.

Agradecimentos

Nossos agradecimentos aos professores João Meidanis e Eliane Martins que se dispuseram a utilizar o Astral em suas disciplinas assim como aos estudantes envolvidos.

Referências

[1] Amorim, R. V.; de Rezende, P. J. Compreensão de Algoritmos através de Ambientes Dedicados a Animação. XX Semish, 1993.

[2] Apple Computer. Inside Macintosh, 1994.

[3] Brown, M. H. Algorithm Animation. The MIT Press, 1987.

[4] Brown, M. H. Exploring Algorithms Using Balsa-II. Computer, 21(5); 14-36, maio 1988.

[5] Brown, M. H. An Anthology of Algorithm Animations using Zeus. Digital Systems Research Center, 1991. Video 76b.

[6] Brown, M. H. Color and Sound in Algorithm Animations. Proc. IEEE Workshop on Visual Languages. 10-17, 1991.

[7] Brown, M. H. Zeus: A System for Algorithm Animation and Multi-View Editing. Proc. IEEE Workshop on Visual Languages, 1991.

[8] Brown, M. H. The 1992 SRC Algorithm Animation Festival. Technical Report 98, Digital Systems Research Center, março 1993.

[9] Brown, M. H. The 1993 SRC Algorithm Animation Festival. The Technical Report 126, Digital Systems Research Center, julho 1994.

[10] Brown, M. H.; Sedgewich, R. Progress Report: Brown University Instructional Computing Laboratory. ACM SIGCSE Bulletin, 16(1):91-101, fevereiro 1984.

[11] Hopgood, F. Computer Animation Used as a Tool in Teaching Computer Science. Proc. 1974 IFIP Congress, pp. 889-892, 1974.

[12] Lawrence, A. W.; Badre, A. N; Stasko, J. T. Empirically Evaluating the Use of Animations to Teach Algorithms. Technical Report GIT-GVU-94-07, Computer Science Department, 1994.

[13] Stasko, J. T. Tango: A Framework and System for Algorithm Animation. Computer, 23(9), 14-36, setembro 1990.

[14] Stubbs, D. F.; Webre, N. W. Data Structures with Abstract Data Types and Pascal. Pacific Grove, Brooks/Cole, second edition, 1988.

[15] Symantec Corporation. Think PASCAL User Manual, 1993 <http://www.symantec.com/>.

[16] Szwarcfiter, J.; Markenson, L. Estruturas de Dados e seus Algoritmos. LTC, 1994.