Ferramenta para a visualização de algoritmos

Rodrigo Filev Maia. São Bernardo do Campo 2019 Fernando Bueno de Lima FERRAMENTA PARA VISUALIZAÇÃO DE ALGORITMOS Trabalho de Conclusão de Curso, apresentado ao Centro Universitário FEI, como parte dos requisitos necessários para obtenção do título de Bacharel em Ciência da Computação. Comissão julgadora ________________________________________ Orientador e presidente _______________________________________ Examinador (1) _______________________________________ Examinador (2) São Bernardo do Campo Data de aprovação Dedico este trabalho aos meus pais, Elisabete e Jose Antonio, que sempre me amaram incondicionalmente e cujos bons exemplos me ensinaram a trabalhar duro para as coisas que aspiro alcançar. AGRADECIMENTOS Agradecido por ter realizado minha graduação em uma instituição tão conceituada como o Centro Universitário FEI.  Eu gostaria de agradecer aos professores Rodrigo Filev e Leandro Alves, e à minha família.

” Nikola Tesla RESUMO A melhor maneira de entender estruturas de dados complexas ou algoritmos é vê-los em ação.  O presente trabalho apresenta uma nova ferramenta de aprendizado interativo de estrutura de dados, especialmente útil para estudantes e professores da área da computação.  É escrito em C# (linguagem de programação - C Sharp ou C-Sharp) e desenvolvido na plataforma Unity.  Seu objetivo é ajudar alunos a entender os algoritmos clássicos de ordenação e multiplicação de matrizes e com as interfaces desta ferramenta se pretende transmitir para os estudantes a importância de separar o tipo específico de uma aplicação de estruturas de dados, o que facilita a compreensão intuitiva das implementações de ordenação e multiplicação de matrizes comuns, além disso permite a comparação entre os diferentes algoritmos de ordenação implementados, que pode ser útil para todos os interessados ​​em algoritmos, em particular para estudantes de ciência da computação que desejam melhorar suas leituras e professores universitários em seu grande esforço para melhorar o curso de estruturas de dados e algoritmos.

Palavras-chave: Estrutura de Dados. Figura 2: Exemplo de Ordenação por Quick Sort 19 Figura 3:Exemplo de Ordenação por ShellSort. Figura 4: Exemplo de Multiplicação de uma Matriz por Escalar 21 Figura 5: Exemplo de Multiplicação de uma Matriz por outra Matriz 21 Figura 7: Visualizador de Algoritmos – Menu Principal 25 Figura 8: Visualizador de Algoritmos – Multiplicação de Matrizes 26 Figura 9: Visualizador de Algoritmos – Ordenação 26 Figura 10: Visualizador de Algoritmos – Multiplicação de Matrizes – Método Iterativo 27 Figura 11: Visualizador de Algoritmos – Multiplicação de Matrizes - Dividir para Conquistar 28 Figura 12: Visualizador de Algoritmos - Ordenação - Buble Sort 29 Figura 13: Visualizador de Algoritmos - Ordenação - Selection Sort 29 Figura 14: Visualizador de Algoritmos - Ordenação - Insertion Sort 30 Figura 15: Visualizador de Algoritmos - Ordenação - Comparação 31 Figura 15: Arquivos para a Ferramenta para Visualização de Algoritmos 32 LISTA DOS QUADROS Quadro 1: Características de alguns procedimentos dos Algoritmos 14 Quadro 2: Trabalhos Relacionados 22 Quadro 3: Tecnologia Utilizada na Ferramenta 24 LISTA DAS TABELAS Tabela 1:Exemplo Matriz Bubble Sort 16 Tabela 2: Exemplo de Matriz Selection Sort.

Tabela 3:Exemplo de Matriz Insertion Sort 17 SUMÁRIO 1 INTRODUÇÃO 11 1. Justificatva 12 1. objetivo 12 1. Multiplicação de uma matriz por um escalar 20 2. Multiplicação de uma matriz por outra matriz 21 2. Problemas clássicos 21 2. Trabalhos relacionados 22 3 METODOLOGIA 24 3. Tecnologia Utilizada 24 4 RESULTADOS E DISCUÇÕES 25 5 CONCLUSÕES 33 REFERÊNCIAS 34 APÊNDICE A – FERRAMENTA PARA VISUALIZAÇÃO DE ALGORITMOS 36 1 INTRODUÇÃO Cursos dentro da área da ciência da computação possuem em seu conteúdo programático, muito de programação e espera-se dos alunos que aprendam as práticas do campo através de uma experiência prática e ao lado dos elementos práticos, os alunos também devem adquirir grande parte de conhecimento.  Isso não é uma surpresa, pois muitas dessas ferramentas foram desenvolvidas mais com vistas a gráficos sofisticados do que para a pedagogia.

 (MOTA, 2008). No entanto, mesmo para ferramentas que têm um foco pedagógico específico, as avaliações são vagas (Lawrence 1994). Com ferramentas de visualização de algoritmos os alunos podem aprender, no entanto, precisam ser planejadas e avaliadas adequadamente.  Com os avanços tecnológicos e interfaces cada vez mais amigáveis, os alunos com dificuldades em entender as estruturas de dados, podem obter uma melhor compreensão dos algoritmos de busca. As visualizações no AV tendem a proporcionar uma abstração de baixo nível para expor detalhes sobre a execução do programa. SORVA et al. Existe uma variedade de ferramentas disponíveis na Web e devido aos avanços significativas nos últimos anos, as ferramentas têm rapidamente avançado e passou de tecnologias obsoletas como Java Applets para tecnologias modernas e poderosas como HTML.

VERAS et al. Apesar de avanços recentes, questões relativas usabilidade e extensibilidade permanecem.  Um algoritmo deve ter as seguintes características: • Não ambíguo - o algoritmo deve ser claro e inequívoco.  Cada um dos seus passos (ou fases) e suas entradas / saídas devem ser claros e devem levar a apenas um significado. • Entrada - Um algoritmo deve ter 0 ou mais entradas bem definidas. • Saída - Um algoritmo deve ter 1 ou mais saídas bem definidas e deve corresponder à saída desejada. • Finito - Algoritmos devem terminar após um número finito de etapas.  O termo triagem entrou em cena, quando foi percebido a importância de pesquisar rapidamente, como por exemplo quando é preciso procurar, como um registro específico no banco de dados, números dentro de uma lista ou um número de telefone específico, uma página em particular em um livro etc.

KARAVIRTA e SHAFFER,2015). Tudo isso teria sido uma bagunça se os dados foram mantidos desordenados e não selecionados, mas felizmente o conceito de classificação passou a existir, tornando mais fácil para todos organizar os dados em uma ordem, facilitando assim a busca. A classificação organiza os dados em uma sequência que facilita a pesquisa. SORVA et al. Ele é conhecido como método bolha porque a cada iteração completa é o maior elemento na matriz vai para o topo em direção ao último lugar ou ao índice mais alto, assim como uma bolha d'água sobe até a superfície da água. CORMEN, 2015) Segundo Veras, 2010, a classificação ocorre percorrendo todos os elementos um por um e comparando-o com o elemento adjacente e trocando-os, se necessário.

Na tabela abaixo, uma matriz simula o algoritmo.  O maior elemento, 7 passa para o topo: Tabela 1:Exemplo Matriz Bubble Sort 7, 5, 2, 4, 3, 9 5, 7, 2, 4, 3, 9 5, 2, 7, 4, 3, 9 5, 2, 4, 7, 3, 9 5, 2, 4, 3, 7, 9 5, 2, 4, 3, 7, 9 Fonte: ADAMCHIK3, 2009 2. Selection Sort A ordenação por Selection Sort é conceitualmente o algoritmo de classificação mais simples.  Como o Bubble Sort, o tipo de inserção também requer um único espaço de memória adicional. É uma técnica de classificação estável, pois não altera a ordem relativa dos elementos que são iguais. Tabela 3:Exemplo de Matriz Insertion Sort 29, 20, 73, 34, 64  29, 20, 73, 34, 64  20, 29, 73, 34, 64  20, 29, 73, 34, 64  20, 29, 34, 73, 64  20, 29, 34, 64, 73  Fonte: ADAMCHIK5, 2009 2. Merge Sort A ordenação por Merge Sort segue a regra de dividir e conquistar para classificar um determinado conjunto de números / elementos, recursivamente, portanto, consumindo menos tempo. À medida que o tamanho da entrada aumenta, Selection Sort e Insertion Sort podem levar muito tempo para serem executadas.

Conforme Veras 2010, é também chamado de classificação de troca de partição.  Este algoritmo divide a lista em três partes principais: 1. Elementos menores que o elemento Pivô 2. Elemento de pivô (elemento central) 3. Elementos maiores que o elemento pivô O elemento dinâmico pode ser qualquer elemento da matriz, pode ser o primeiro elemento, o último elemento ou qualquer elemento aleatório.  No ShellSort, a matriz h é ordenada por um grande valor de h e contínua reduzindo o valor de h até que ele se torne 1. CORMEN, 2015). Figura 3:Exemplo de Ordenação por ShellSort. Fonte: CARVALHO8, 2011 2. C# No desenvolvimento da ferramenta foi utilizado C# que é uma linguagem de programação orientada a objetos (OOP) geral para redes e desenvolvimento da Web. • O C # gerencia automaticamente a memória de objetos inacessíveis usando um coletor de lixo, o que elimina preocupações do desenvolvedor e vazamentos de memória.

• O tipo C # é mais seguro que o C ++ e possui apenas conversões padrão seguras (por exemplo, ampliação de inteiros), que são implementadas durante a compilação ou o tempo de execução. Propriedades da multiplicação de matrizes Existem dois tipos de multiplicação de matrizes, a multiplicação de uma matriz por um escalar e multiplicação de uma matriz por outra matriz. CORMEN, 2015). Multiplicação de uma matriz por um escalar Conforme Tenenbaum 1995, a multiplicação de uma matriz por um escalar é multiplicar cada elemento na matriz pelo mesmo número. Algumas ferramentas auxiliam para encontrar estes erros, os depuradores textuais de baixo nível e ambientes de desenvolvimento industrial. Mesmo essas “boas” linguagens de programação provenientes de profissionais e plataformas que possuem uma boa automação para estes processos, muito dependem de abstração para os algoritmos.

O comportamento do algoritmo é ofuscado pelo programa irrelevantes detalhes. CORMEN, 2012). Trabalhos relacionados Considerando a importância da disciplina de estrutura de dados para os estudantes da área da engenharia computacional e inúmeros trabalhos têm sido desenvolvidos ao longo dos anos, seja com foco no processo de desenvolvimento de software ou no produto propriamente dito. Com a união da metodologia para o pior caso, e a idéia da análise automática de programas, foi proposto o desenvolvimento do protótipo de sistema ANAC, que é uma ferramenta para análise automática da complexidade de algoritmos não recursivos. Hundhausen e Douglas 2001 Os autores descrevem o software de visualização de algoritmos (AV) para criar representações gráficas de algoritmos para uso como auxílios visuais em palestras ou como base para laboratórios interativos.

As visualizações ilustram o algoritmo de destino para alguns conjuntos de dados de entrada cuidadosamente escolhidas e tendem a ter uma aparência esboçada e não polida.  Para explorar o espaço de design da tecnologia AV de baixa fidelidade, apresentam um protótipo de linguagem e sistema para usuários finais enraizados em estudos empíricos em que os alunos construíram e apresentaram.  O protótipo de linguagem e sistema para usuários finais são pioneiros em uma nova técnica de programação de visualizações baseada em relações espaciais e uma nova interface de apresentação que suporta discussões humanas sobre algoritmos, permitindo execução reversa e marcação e modificação dinâmicas. Estão incluídas nesta área as atividades referentes à estrutura de dados, tais como algoritmos de ordenação com possibilidades infinitas, como por exemplo a multiplicação entre matrizes.

O método utilizado para o desenvolvimento da ferramenta apresentada neste trabalho foi iniciar com uma pesquisa exploratória com coleta de dados através de pesquisas bibliográficas para a identificar e analisar artigos publicados envolvidos nesta temática. Utilizados os conceitos dos conteúdos disponíveis em livros, bases de dados eletrônicas. A seleção dos dados ocorreu através de dois critérios de inclusão, sendo a base de dados cientificamente confiável e, sua disponibilização gratuita e integral dos materiais eletrônicos. Deste modo, foi possível selecionar três fontes de dados: Biblioteca Digital Brasileira de Computação – BDBComp; Google Acadêmico e Scientific Eletronic Library Online – Scie. Figura 8: Visualizador de Algoritmos – Multiplicação de Matrizes Fonte: Próprio autor, 2019. Dentro dos menus de cada problema podem ser selecionados os respectivos algoritmos implementados.

Figura 9: Visualizador de Algoritmos – Ordenação Fonte: Próprio autor, 2019. Nas telas dos algoritmos de multiplicação de matrizes, são apresentadas duas matrizes do tipo 4x4 preenchidas com valores aleatórios e uma matriz resultante com todos os valores zerados. Ao longo da execução são exibidos marcadores nos números que serão multiplicados no próximo passo da operação, e os valores já calculados são exibidos na matriz resultante. Figura 13: Visualizador de Algoritmos - Ordenação - Selection Sort Fonte: Próprio autor, 2019. Na tela de comparação de algoritmos, os marcadores e principalmente o código de cores permitem que o aluno identifique facilmente, de maneira visual, a diferença de performance entre os métodos selecionados. Figura 14: Visualizador de Algoritmos - Ordenação - Insertion Sort Fonte: Próprio autor, 2019.

Adicionalmente, os valores aleatórios gerados são os mesmos para os vetores dos dois métodos sendo comparados, facilitando a comparação. Figura 15: Visualizador de Algoritmos - Ordenação - Comparação Fonte: Próprio autor, 2019. Finalmente, temos vindo a perceber que a ferramenta é uma plataforma para estudar algoritmos de ordenação e multiplicação de matrizes, fácil de usar, flexível e razoavelmente completo. Seu modelo de dados é facilmente extensível a implementações futuras e visualizações algorítmicos. Ao fornecer plugins de entrada e saída foi possível fornecer melhores visualizações e melhor interatividade, ficando mais fácil desenvolver visualizadores especializados a partir do zero. REFERÊNCIAS AMADEU, C. V. F. SOUSA, Paulo A. G. Bases de Dados NoSQL. Dissertação para obtenção do Grau de Mestre em Engenharia Informática, Área de Especialização em Arquiteturas Sistemas e Redes.

RIVEST, Ronald L. STEIN, Clifford. Algoritmos – Teoria e Prática. ° Edição. pg. pg. KARAVIRTA, Ville; SHAFFER, Clifford A. JSAV: The JavaScript Algorithm Visualization Library. Dept. of Computer Science and Engineering Alto University and Dept. MALMI, L. A Review Of Generic Program Visualization Systems For Introductory Programming Education. ACM Trans. Comput. Educ. ISBN-10: 8522108218. ISBN-13: 9788522108213. TENENBAUM, Aaron M. et al. Estruturas de dados usando C. Departamento de Informática e Estatística, Universidade Federal do Piauí(UFPI) Teresina – PI – Brasil 2Engenharia da Computação, Universidade Federal do Cear ˜ a - Campus de Sobral (UFC) ´ Sobral – CE – Brasil. Webgrafia ADAMCHIK. Disponível em: www. cs. cmu. com. br. Acesso em 31/01/2019. CAVALGA. Disponível em: https://diegocavalca. ebiografia. com/nikola_tesla/. Acesso em 31/01/2019. WIKI, Engenharia. Disponível em: http://wiki.