| |
| Acadêmico(a): Alesson Ricardo Bernardo |
| Título: FURB GRAPHS: uma ferramenta web para ensino-aprendizagem de teoria dos grafos |
| |
| Introdução: |
A teoria dos grafos é um ramo da matemática amplamente utilizado para a representação de modelos estruturais
que beneficiam o estudo de múltiplas áreas de conhecimento tais como física, química, engenharia, computação, dentre
outras. (SHRINIVAS; VETRIVEL; ELANGO, 2010). Esta teoria é relativamente nova e sua primeira evidência data de
1736, quando o matemático suíço Leonhard Euler resolveu o problema das “Pontes de Königsberg”.
Königsberg foi uma importante cidade da Prússia, hoje chamada de Kalin-ingrado, cortada pelo rio Pregel, o
qual a dividia em duas ilhas I1 e I2. Havia uma ponte ligando uma ilha à outra e seis outras pontes, ligando-as às
margens M1 e M2, exatamente como mostra a Figura 1.
A pergunta que atormentava os moradores era se seria possível realizar um passeio pelas ilhas, passando uma
única vez em todas as sete pontes, voltando ao ponto de origem. Para resolver o Problema de Königsberg, Euler
eliminou os detalhes que não influenciavam o problema, como a distância entre as ilhas e tamanho das ilhas, e se
concentrou apenas nos aspectos que considerou importantes. Com isso, Euler representou o problema de uma forma
bastante simples, como mostra a Figura 2 e, a partir disso, acredita-se que esta estrutura tenha sido o primeiro exemplo
de grafo.
Atualmente, os conceitos teóricos de grafos são aplicados nos estudos das moléculas e átomos na química, no
estudo do impacto da migração de espécies e na difusão de doenças em biologia, e na busca pela solução ótima na
execução de tarefas em ambientes competitivos na área de teoria dos jogos (SHRINIVAS; VETRIVEL; ELANGO,
2010). No que tange a ciência da computação, Hartsfield e Ringel (2013) alegam que a teoria de grafos está se tornando
cada vez mais essencial, tendo importância principalmente no entendimento de estruturas de dados abstratas e na análise
de algoritmos. Shrinivas, Vetrivel e Elango (2010) destacam a mineração de dados, segmentação e captura de imagens,
clustering, alocação de recursos, escalonamento, bancos de dados e a modelagem da topologia de redes como exemplos
de uso de grafos na computação.
Hartsfield e Ringel (2013) também apontam para a necessidade de formar profissionais cada vez mais capazes
de lidar com o tema. No entanto, o alto nível de abstração requerido no aprendizado e modelagem de grafos são
obstáculos recorrentes (SILVEIRA; SILVA, 2007). Santos e Costa (2006) destacam que a maioria dos estudantes
sentem dificuldades na assimilação de conceitos e no desenvolvimento de algoritmos. Segundo Halim et al. (2012), tal
dificuldade amplifica-se a partir dos modelos tradicionais de ensino, que consistem somente em textos, apresentações
com exemplos pré-definidos e estáticos, explicações e o uso de quadros para realizar manualmente a definição dos
grafos e simular a execução dos algoritmos. Para aprimorar o processo de aprendizagem, Santos et al. (2005) indicam
que é essencial atualizar as didáticas de ensino considerando a tecnologia, “procurando transformar processos abstratos
em concretos através de produtos de software”.
Segundo Halim et al. (2012) uma forma de auxiliar o processo de ensino-aprendizado é a utilização de
ambientes virtuais que propiciem a visualização e execução de algoritmos, pois facilitam o entendimento das
informações apresentadas, otimizam o tempo gasto nas abordagens tradicionais anteriormente descritas e promovem
maior interação entre docentes e alunos. Um exemplo de ambiente virtual que tem como objetivo apoiar o estudo da
teoria de grafos é o Furb Graphs (BERNARDES, 2016). O protótipo desenvolvido inicialmente por Zatelli (2010),
estendido por Borba (2014) e posteriormente aprimorado por Bernardes (2016), contempla a execução de diversos
algoritmos de grafos, oferecendo suporte para a visualização gradual de alguns deles, em conjunto com seus respectivos
pseudocódigos e logs de informações. O protótipo ainda permite a criação, edição, inspeção de propriedades e geração
parametrizável de grafos através de uma interface gráfica interativa.
Com base neste contexto e visando aprimorar o ensino e a aprendizagem de teoria de grafos, este trabalho
apresenta uma reconstrução do Furb Graphs (BERNARDES, 2016) para um ambiente on-line, acrescentado
mecanismos que facilitem a visualização e o entendimento dos algoritmos, assim como, a disponibilização de um
assistente virtual que auxilie e motive os estudantes da disciplina. Dessa forma, têm-se os seguintes objetivos
específicos: (i) disponibilizar o protótipo do Furb Graphs em um ambiente on-line; (ii) implementar um assistente
virtual com o propósito de orientar os alunos quanto à utilização do protótipo, e auxiliar na compreensão dos algoritmos
de busca em grafos e caminhamento mínimo; (iii) fornecer um módulo que centralize o acesso ao material de apoio à
disciplina; (iv) avaliar o uso e a eficiência do protótipo como instrumento de aprendizagem |
| |
|
