Ensino de Teoria da Complexidade

• Alex Luciano Roesler Rese UNIVALI
• Rafael de Santiago UNIVALI

Resumo

Existem diversos trabalhos na literatura que estudam o problema do baixo interesse dos alunos por disciplinas relacionadas à Teoria da Computação. Estes trabalhos concordam que a causa deste problema é a presença de conteúdos exclusivamente teóricos. A alternativa apontada é o uso de materiais de ensino que visam a prática dos conteúdos. Como subárea da Teoria da Computação, encontra-se a Teoria da Complexidade, que visa o estudo do que faz alguns problemas serem fáceis ou difíceis de serem resolvidos pelo computador. Neste contexto, apresenta-se uma pesquisa para viabilizar o ensino de Teoria da Complexidade por meio de atividades práticas e avaliar se estas são mais eficientes na aprendizagem dos alunos. Quatro materiais foram desenvolvidos e experimentados com os alunos participantes, por meio de questionário e acompanhamento de desempenho de notas. Com os resultados obtidos, há evidências de que a aprendizagem foi beneficiada.

Palavras-chave: Ensino de Computação, Ensino de Teoria da Computação, Teoria da Complexidade Computacional

Referências

Aaronson, S. (2011) "The Complexity Zoo", [link], Janeiro.

Arora, S. e Barak, B. (2009), Computational Complexity: a modern approach. 1ª edição, Cambridge University Press, ISBN 9780521424264

Cavalcante, R., Finley, T. e Rodger, S. H. (2004). A Visual and Interactive Automata Theory Course with JFLAP 4.0. In Proceedings of 35th SIGCSE Technical Symposium on Computer Science Education, New York. ACM Press.

Chesñevar, C., Cobo, M. L. e Yurcik, W. (2003). Using Theoretical Computer Simulators for Formal Languages and Automata Theory. In 35th ACM SIGCSE Bulletin, New York. ACM. DOI: 10.1145/782941.782975.

Cogliati, J. J., Goosey, F. W., Grinder, M. T., Pascoe, B. A. e Ross, R. J. (2005). Realizing the Promise of Visualization in the Theory of Computing. In Journal on Educational Resources in Computing (JERIC), v.5. New York. ACM. ISSN 1531-4278.

Devedzic, V., Debenham, J. e Popovic, D. (2000). Teaching Formal Languages by an Intelligent Tutoring System. In Educational Technology Society, v.3. ISSN 1436-4522.

Garey, M. R. e Johnson, D. S. (1979), Computers and Intractability: a guide to the theory of NP-Completeness, Bell Telephone Laboratories Inc, ISBN 0-7167-1044-7.

Goyal, M.; Sachdeva, S. (2009). Enhancing Theory of Computation Teaching Through Integration with other Courses. In International Journal of Recent Trends in Engineering, v.1. Academy Publisher.

MEC (2009). "Referenciais Nacionais de Cursos de Graduação (LICENCIATURA E BACHARELADO): consulta pública", [link].

Ramos, M. V. M., José Neto, J. e Vega, I. S. (2009). Linguagens Formais: teoria, modelagem e implementação, Bookman, ISBN 978-85-7780-453-5.

Rese, A. L. R. e Santiago, R. (2011), "Materiais para o Ensino de Complexidade". [link], Dezembro.

Sipser, M. (2007). Introdução à Teoria da Computação, 2ª edição, Cengage Learning, ISBN: 978-85-221-0499-4.

Toscani, L. V. e Veloso, P. A. S. (2005). Complexidade de algoritmos, 2ª edição, Bookman.

Ziviani, N. (2007). Projeto de algoritmos, Thomson, 2007.