复杂算法可视化框架构建方案研究
发布时间：2015-07-11 10:02
摘 要 算法设计是计算机系统基本构件设计的核心，在程序设计中占据非常重要的地位，算法的理解是困扰学生编程能力提高的难点，算法的不可见性是影响学生理解算法的关键因素。本文介绍了一个复杂算法的可视化系统，该系统可使复杂、抽象的算法能够通过计算机图形化模拟。
关键字 算法；可视化模拟；框架
程序设计能力是计算机专业学习的基础，同时也是学生能够向软件开发更高层次迈进的前提，而算法的设计能力又是程序设计能力提高的关键因素。在学生进入计算机专业学习的初期，常常因为对于算法理解困难，从而失去专业学习兴趣，甚至是丧失继续学习的勇气。本人经过深入的研究发现，理解算法的难度在于其抽象性和不可见性。即使是很简单的算法，对于初学者来说，由于没有直观的外在表现，也是很难理解的。那么通过一套算法图形模拟系统，使任何复杂的算法能够让计算机在运行中来动态的模拟其实现的全过程。
1 设计思想
本系统主要进行两个阶段工作：①对程序设计教学中遇到的算法进行收集和分类。②搭建算法模拟系统框架[1]。
1.1 算法的收集和分类
算法的收集和分类是前期的基础准备工作，也是本系统能否成功的关键。首先，确定此系统所支持的课程体系，例如《程序设计基础》、《数据结构》等入门级课程体系。其次，收集在这些课程中所需要的算法及基本程序。最后，对这些算法及基本程序，按照难易度、知识点、及学习面进行分类和细化。
1.2 搭建算法模拟系统框架
本系统主要分为三个主体部分：①算法以及基本程序部分。②系统核心及调度控制部分。③系统交互控制及演示界面部分。如图1所示。
图1 系统框架
算法及基本程序部分是指需要模拟演示的程序，该部分的所有算法必须用可运行的程序实现，同时在该部分中，确定其内存单元的控制和数据的变化。
系统核心及控制调度部分是本系统的中心部分，主要由中心调度和控制子系统、算法公共接口子系统、交互管理子系统、文件管理子系统、图形显示子系统、文档管理子系统、帮助子系统构成。如图2所示。
系统交互及演示界面部分，主要是系统的主体操作界面、算法程序代码的运行界面、图形化模拟界面、人机交互界面、内存控制及数据变化演示界面、通用接口挂接界面、出错提示界面、数据初始化及结果输出界面、帮助及算法解释界面。
2 关键问题
2.1对算法的研究
因为本系统的根本是解决其所支持的课程体系中的算法和基本程序的图形化模拟，所以需要系统设计者要详细的研究这些课程中每一个要可视化图形模拟的算法，确定其数据初始化及变化范围，存储空间变化过程，程序执行流程，程序编写技巧等环节。
2.2 程序动态跟踪及演示
在算法设计中常常也配有相关的图形工具来帮助学生对算法的理解，例如流程图、N-S图、PAD图等。但是这些图形只是能静态的反映程序的执行过程，对于复杂的算法并不能很好的捕捉程序的动态运行过程以及数据和存储空间的状态变化。在本系统中可以对程序进行中断和单步执行来利用图形化演示程序的动态执行过程，以及数据和存储空间的状态变化。
2.3 图形化演示
图形化演示是将算法由抽象变具体，不可见变为可见，使学生的学习由枯燥变生动的关键。对于众多的、不同知识点的、不同类型的算法，以其各自的特点用图形模拟。建立图形库与程序的语句进行映射，系统通过捕捉程序的每一部执行来触发图形界面的切换控制系统，实现图形的变化。
2.4算法的文字解释
对于任何图形化模拟都不能完全描述算法的细节和其中的技巧，这恰好需要文字来进行必要的补充和描述。在算法程序运行时，帮助系统可以同步用文字来描述算法的核心思想和执行步骤，并且对于程序的每一步运行，调用帮助及解释子系统进行配套的文字解释。
图2 系统概要设计
2.5 界面设计
界面设计是本系统的关键工作之一，其直接影响到系统的可用性和趣味性。特别是人机交互界面，通过此界面来对算法进行初始化数据设置和算法程序的运行操作控制。对于不同的算法程序采用与其相匹配的初始化设置界面，例如对于递归算法应限制其递归的深度，对于排序算法即可以让用户自行输入，也可以设定随机数据序列。
3 系统应深入研究的方面
对于同样的问题，必将会有多种算法。为了提高学生的探索能力，应让学生尝试自己设计算法并编写程序，能够通过本系统进行图形化模拟演示。这就需要进一步设计通用公共算法接口子系统，使用户自己的算法能挂接到本系统。为了解决这个问题，需要设计一套框架，来使用通用图形库、通用帮助库与需要模拟演示的程序进行挂接。
因为本系统是一个算法教学辅助系统，那么能够给予使用者提供动态的智能化学习帮助是本系统的关键特色。在下一步研究中将与人工智能、数据挖掘、人工神经网络、计算机图形学等技术相结合，构建经验模型，加入提问推理单元，对于不同的使用者构建问题资料库。能够给学习者建立算法帮助和学习路径，达到自动化算法教学的目的。
4 结束语
本系统是教学方法、专业知识教学、图形化模拟等方面的全新探索。随着可视化教学辅助系统的不断发展，使得在程序设计等专业基础课程体系的教学中增加了新的教学手段。使得学生从枯燥的算法学习中解脱出来，增加了教学中的趣味性和实效性。
参考文献
Robin , Kristian d and Vladimir in. Question-Answering from Frequently-Asked Question Files: Experiences with the FAQ-Finder System[R]. Technical Report TR-97-05, University of Chicago, Department of Computer Science, 1997
D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing,6(1): 323-350, 1977
Wong Y F, Sideris A . Learning convergence in cerebellar model articulation controller[J]. IEEE Trans on Neural Networks, 1992, 3(1)
下一篇：口令认证协议的分析与设计