La simulación por computadora como estrategia didáctica para la enseñanza de la complejidad algorítmica

Abstract

El proceso de enseñanza-aprendizaje del concepto de complejidad algorítmica, acarrea dificultades especiales debido al carácter abstracto de dicha noción. El uso de autómatas para el modelado de algoritmos, permite la aplicación de herramientas tales como simuladores de máquinas abstractas, a través de los cuales, se puede construir una imagen intuitiva del proceso al visualizar el comportamiento de dichos autómatas. Además los simuladores proveen información útil para el posterior cálculo de expresiones generales de la complejidad algorítmica. Se propone un ejercicio de aplicación integrador, a través del cual, con auxilio de un simulador de máquinas de Turing, se comparan las expresiones de la complejidad obtenidas para dos soluciones distintas de un mismo problema, empleando además conceptos previamente adquiridos en otras asignaturas, lo que favorece la transposición tanto horizontal como verticalmente respecto del diseño curricular de la carrera.