（课程与教学论专业论文）基于三层结构模型的算法可视化教学研究与实践.pdf

摘要 数据结构和算法是计算机课程教学的核心，教学难点在于它们的 抽象性和动态性。应用可视化教学，能使抽象的知识变得具体。 本文首先介绍了算法可视化的由来、常用动画技术和国外有代表 性的算法可视化教学软件。然后通过调查分析得出可视化软件没能在 教学中得到普及的主要原因：( 1 ) 创建可视化非常耗时，得不偿失； ( 2 ) 现存的许多算法可视化系统缺乏与用户的交互性，学生只能被 动的观看而不能参与实践，一定程度上降低了可视化的教学效果；( 3 ) 没有提供利用可视化软件学习的反馈。接着根据参与性分类和b l o o m 的认知分类原理，讨论了决定可视化效果的衡量标准，并提出测评可 视化教学效果的实验设计。 为克服现存可视化教学软件的缺点，提高算法可视化系统与用户 的交互性与创建可视化的简易性，本文提出基于三层结构模型的算法 模拟和建立在该模型之上的教学应用。算法的执行过程可以看成是对 特定数据结构的操作或修改，那么可以通过数据结构状态的变化来研 究算法，所以称为算法模拟。根据抽象层次的不同，本文将数据结构 分为三个结构层次，分别是与现实生活的逻辑结构相对应的抽象数据 类型( a d t ) ，与计算机实现的物理结构相对应的基础数据类型( f d t ) ， 而中间层称之为概念数据类型( c d t ) 。算法模拟和教学应用就是建 立在这三个抽象层次上的。 基于三层结构模型的算法模拟不仅具备传统算法可视化的优点， 还加入了新的特性，如交互性、创建算法动画的简易性以及提供反馈 和自动评价。该模型的算法可视化对于普及可视化教学和提高可视化 的教学效果有着积极的意义。 关键词：算法可视化；三层结构模型；算法模拟；可视化教学；交 互式学习 i i a b s t r a c t d a t as t r u c t u r e sa n da l g o r i t h m sa r ei m p o r t a n tc o r ei s s u e si nc o m p u t e r s c i e n c e e d u c a t i o n h o w e v e r , p e o p l eu s u a l l y h a v e d i f f i c u l t y t o u n d e r s t a n d ，b e c a u s eo ft h e i ra b s t r a c ta n dd y n a m i cf e a t u r e s o n ew a yt o i m p r o v et h e i ru n d e r s t a n d i n gi s t o p r o v i d ev i s u a l i z a t i o n st om a k et h e a b s t r a c tc o n c e p t sm o r ec o n c r e t e t h i st h e s i sf i r s ti n t r o d u c e st h eo r i g i no fa l g o r i t h mv i s u a l i z a t i o n ， c o m m o na n i m a t i o nt e c h n i q u e sa n ds o m ef o r e i g n r e p r e s e n t a t i v e so f a l g o r i t h mv i s u a l i z a t i o ns y s t e m s t h e nt h ep a p e ra n a l y z e st h em a i n r e a s o n sw h i c hb l o c kt h e s es y s t e m sw i d e l yu s e di nt e a c h i n gf r o ms u r v e y ： ( 1 ) d e v e l o p i n gv i s u a l i z a t i o n sc o s t s al o to ft i m e ；( 2 ) t h ec u r r e n t a l g o r i t h mv i s u a l i z a t i o ns y s t e m sl a c ki n t e r a c t i o nw i t hu s e r s ，s ol e a r n e r s c a no n l yv i e wa n i m a t i o n sp a s s i v e l yw i t h o u ta c t i v ee n g a g e m e n t t h i sm a y l e a dt or e d u c et h ev i s u a lt e a c h i n ge f f e c t ；( 3 ) m o s to ft h es y s t e m sg i v en o f e e d b a c ko ns t u d e n t sp e r f o r m a n c e b a s e do ne n g a g e m e n tt a x o n o m ya n d b l o o m st a x o n o m y , m e t r i c sf o rd e t e r m i n i n ge f f e c t i v e n e s so f v i s u a l i z a t i o n a r ed i s c u s s e da n da ne x p e r i m e n ti s g i v e nt om e a s u r et h er e l a t i o n s h i p b e t w e e ne n g a g e m e n tl e v e l sa n dl e a m e r sd e p t ho f u n d e r s t a n d i n g i no r d e rt oo v e r c o m et h e p r e s e n td e f i c i e n c y ，t h ec o n c e p to f a l g o r i t h m s i m u l a t i o ni sa p p l i e da n dat h r e e - l a y e rs t r u c t u r em o d e li sp r o v i d e d t h e e x e c u t i o no fa l g o r i t h mc a nb er e g a r d e da s c h a n g i n gp e r f o r m a n c eo n 1 1 1 s p e c i a ld a t as t r u c t u r e a l g o r i t h m sc a nb es t u d i e db yd i v e r s es t a t e so fd a t a s t r u c t u r e a c c o r d i n gt ot h eh i e r a r c h yo fd i f f e r e n tc o n c e p m ，t h ed a t a s t r u c t u r e sa r ed i v i d e di n t ot h r e es t r u c t u r a ll e v e l s ：a b s t r a c td a t at y p e s ( a r r r ) w h i c hc o r r e s p o n dt ol o g i cs t r u c t u r eo fa c t u a ll i f e ；b a s i cd a t at y p e s ( f d t ) w h i c hc o r r e s p o n dt op h y s i c a ls t r u c t u r er e a l i z e di nc o m p u t e r ； c o n c e p td a t at y p e s ( c d t ) w h i c ha r et h ei n t e r m e d i a t el a y e rb e t w e e na d t a n df d t a l g o r i t h ms i m u l a t i o na n dt e a c h i n ga p p l i c a t i o na r eb a s e do nt h e t h r e ea b s t r a c tl e v e l s b a s e do l l t h r e e l a y e r s t r u c t u r e m o d e l ，n o to n l ya l g o r i t h m s i m u l a t i o n p o s s e s s e s t h e a d v a n t a g e o ft h et r a d i t i o n a l a l g o r i t h m v i s u a l i z a t i o n , b u ta l s oj o i n st h en e wc h a r a c t e r i s t i cs u c ha st h ei n t e r a c t i o n , e a s i l yc r e a t i n ga l g o r i t h ma n i m a t i o na n do f f e r i n ga u t o m a t i cf e e d b a c k a l g o r i t h mv i s u a l i z a t i o nb a s e do nt h i sm o d e lh a sp o s i t i v em e a n i n g si n p o p u l a r i z i n gv i s u a l i z a t i o ni nc o m p u t e ri n s t r u c t i o na n di m p r o v i n gt h e t e a c h i n gr e s u l t s k e y w o r d s ：a l g o r i t h mv i s u a l i z a t i o n ；t h r e e l a y e rs t r u c t u r em o d e l ； a l g o r i t h ms i m u l a t i o n ；v i s u a l i z a t i o ni nc o m p u t e ri n s t r u c t i o n ；i n t e r a c t i v e l e a r n i n g i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标 明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：主1 匆j 夸洲净f 月弓日 ， 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在- 年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打, i ) 作者签名：叠磷日期：许c 一月1 日 导师签名： 嗍御年么月午日 f 基于三层结构模型的算法可视化教学研究与实践 1 1 选题背景与意义 第一章绪论 与可视化相对应的英文单词v i s u a l i z a t i o n 中包含着v i s u a l 字 根，它源自于拉丁语v i s u a l i s 及v i s u s ，意为“视觉”。牛津词典对 v i s u a l 一词的解释共有7 种定义，其中有六种最常见的定义都涉及到 人们用眼睛所看到的影像，第7 种定义为形成心理图像的意思，而这 种图像与人们的视觉没有必然的联系，后来这种定义从广义上给出了 可视化的含义，即形成某些不可见对象或抽象事物的心理图像的能力 或过程，使不可见事物变成可见。 数据结构与算法是计算机科学与技术专业以及相关专业的一门 专业基础课程，同时它也是计算机科学与技术专业课程体系中的核心 课程之一，它在计算机科学与技术专业的课程体系，特别是软件系列 课程体系中处于承上启下、联系左右的中心地位。大量的实践表明， 是否学好数据结构与算法课程对于能否学好计算机本科课程有着相 当重要的作用，同时也对后续的工作和研究有着深远的影响。 目前，各大学的数据结构与算法课程和教材的内容都主要集中 在“基本数据结构的阐述和分析、基本数据结构的应用、典型基本算 法的适当渗透”这三个方面。 在数据结构和算法日益受到重视的同时，此课程的学习却一直使 硕士学位论文 学生感到复杂和困难。因为该课程主要讨论抽象数据关系和算法的定 义、表示及实现。而常规的板书或一般的幻灯投影授课均难以有效地 展示数据结构和算法的抽象性和动态性，最终容易造成教学低效和学 时膨胀。学生在面对抽象概念而无法在心中产生具体的影像时，容易 在学习过程中遭遇困难；教材在呈现数据结构概念时也受到多方面的 限制，由于受到篇幅的限制，常省略算法部分细节过程，而让学生自 己发挥想象力去补足；再者，学生经常只能依照教材所提供的算法范 例去执行而无法修改，这对有意深入探索算法的学生而言是一项困 扰。 本文从教育的角度探讨如何利用算法可视化达到更好的教学效 果以及在教育原则的指导下设计更有效的算法可视化工具。算法可视 化的设计研究和应用实践极大的丰富了教学内容的组织手段和教学 内容的呈现方式，有利于减轻教师的教学负担和促进学生更有效的学 习。， 1 2 国内外研究现状 算法可视化是近几十年新兴起的一个算法研究方向。通过可视 化，算法的执行过程更直观，理解起来也更容易。到目前为止， 已 经出现了许多功能强大的算法可视化系统，促进了算法可视化的进一 步发展。 国内的可视化教学研究可以归纳为：算法动画，像电影一样连续 的描述算法的执行过程；可视化调试，将算法具体实现为程序，通过 基于三层结构模型的算法可视化教学研究与实践 运行调试程序来理解算法的思想。 从9 0 年代初起，清华大学严蔚敏教授编著配有算法演示软件的 数据结构系列教材( 1 9 9 2 年获第二届全国高校优秀教材特等奖， 1 9 9 6 年获国科技进步三等奖) 的基础上，积极开发和应用可视化c a i 软件，在数据结构课程的各个主要教学环节初步形成了综合的可视化 c a i 教学模式。为教材配套的“数据结构的算法动态模拟辅助教学软 件d s d e m o 川”对八十余个典型算法进行动态交互式模拟跟踪，将抽象 的数据结构和算法实现动态同步可视化。 “p a s c a l 可视集成环境v p i ”，它集编辑器、调试器和演示器于 一体，实现t p a s c a l 虚拟机的可视化和数据结构的可视变换，可同步 演示算法和数据的动态视图，为理解算法、学习编程、调试程序和演 示师生编写的算法实例与作业提供了便利。教师授课和讲评的正例和 反例程序，学生编写的算法程序，都可以在这个软件环境上进行动态 可视化运行，为数据结构的教学提供了一个师生共用的高效的可视化 备课、演示、讲评、调试和观察工具。 此外，排序算法演示与比较软件“s o r t d e b l o ”等用于特定章节的 课件也进一步丰富了数据结构和算法可视化的内容和形式。 上述可视化c a i 软件支持课堂教学、个人学习、实验作业及其成 绩管理等主要教学环节，为探索数据结构课程的授课、作业、实验和 讲评的全面可视化c a i 教学模式提供了基本的软件条件。 国外的可视化教学软件各种产品丰富多彩。许多基于计算机教育 的可视化工具被陆续开发并展示在s i g c s e 和i t i c s e 会议上。这些算法 硕士学位论文 可视化系统的共有特性如下：它们允许学生输入数据，或者提供预先 准备好的数据集。它们能追踪算法在数据集上的工作过程或者以动画 形式播放或者分步演示。随着算法的运行，可视化能呈现对数据集的 修改并更新视图显示。一些系统还能提供伪代码使学生能够观看到每 行代码是怎样作用于数据的。还有一些系统提供了历史记录机制，学 生能够回顾前面执行过的步骤。 例如j a w a a 晗1 允许学生创建他们自己的可视化，因为亲自实践的 过程能够加深学生对算法工作过程的理解。而h a l v i s 衄1 提供了一个独 有的特征，引入提问机制，在学生观看算法动画的过程中提出和其相 关的问题，并要求学生回答后才能继续观看。 1 3 论文研究内容和思路 从教育学的观点来看，算法动画停留在观看算法执行的层面上， 并不能满足教学的需要，而可视化调试总是和实际的源码绑定，表现 范围有所局限。无论是算法动画还是可视化调试，仍然是系统做了所 有的工作而学习者仅仅是观察它的行为。因此，这需要在可视化系统 中引入交互，及时给学生的表现以评价和反馈，让学生在反复实践的 中升华理解。数据结构和算法比起基础的编程课程来说要抽象，教学 感兴趣的是算法的逻辑行为而不是它的实现细节。值得深入探究的是 系统如何在抽象的逻辑层实现与用户的交互并给出学习者表现的及 时反馈。p i l o t m l 是接近这种思想的系统，该系统主要针对与图算法 有关的问题，学习者能获得问题答案的图形化解释以及系统对于学习 基于三层结构模型的算法可视化教学研究与实践 者的表现给出的评分和出错时的信息。 本文将应用算法模拟的概念来弥补算法动画和可视化调试的不 足。思想是提出三层结构模型的算法可视化来解释算法的逻辑和行 为。而且，该模型允许用户以算法模拟方式交互，同时也支持算法模 拟练习并能自动产生可视化反馈。 论文内容共分为5 章： 第一章是绪论，介绍选题背景、意义以及国内外算法可视化教学 的研究现状。 第二章介绍了算法可视化的由来和算法动画的常用实现技术。 第三章比较了国外典型的算法可视化教学软件的特点并对可视 化在教学中的使用情况做了调查和分析。 第四章根据教学效果的参与性分类原理和b l o o m 认知分类原理， 提出测评可视化教学效果的实验设计。 第五章引入了算法模拟的概念并提出了基于三层结构模型的算 法模拟和建立在该模型之上的教学应用。从提高可视化教学效果的角 度出发，基于三层结构模型的算法模拟不仅能提高与用户的交互性还 能保持创建可视化的简易性。这对于提高可视化教学效果有着积极的 意义。 最后总结全文的研究内容，并展望了今后的研究工作。 硕士学位论文 2 1 软件可视化 第二章算法可视化概述 软件的主体是程序。当程序编写完装入计算机后，就“消失”在 那些存储介质上了。此后，程序结构、运行行为都看不见摸不着，这 使得对大型复杂软件的直接理解几乎不可能，给软件开发、测试、维 护和评价带来极大的困难，阻碍了软件的发展和应用。因此软件界一 直在研究软件可视化技术。软件可视化技术是利用印刷术、图形、动 画和具有现代人一机交互功能的电影制片技术和计算机图形技术等手 段，使得软件便于理解和有效使用口1 。 。 在软件可视化的文献中，涉及的可视化内容和术语很多，可以用 图2 - i 表示他们相互之问的关系。 图2 一l 有关术语示意图 图2 - 1 是一个表明软件可视化文献中有关术语的示意图。其尺寸 基于三层结构模型的算法可视化教学研究与实践 是不相关的，相交部分表示可视程序设计( v p ) 和示范程序设计( p b d ) 。 但v p 和p b d 并不是程序可视化( p v ) 的子集合，他们仅仅有一个局部 的重叠。 “ 下面就此对软件可视化做进一步的讨论。 软件可视化( s v ：s o f t w a r ev i s u a l i z a t i o n ) 指对计算机程序( 较 底层) 或算法( 较高层) 的可视化，所以分为为程序可视化和算 法可视化 程序可视化( p v ：p r o g r a mv i s u a l i z a t i o n ) 指对程序代码或数据 结构的静态或动态特征进行的可视化。可分为静态代码可视化、 动态代码可视化( 代码动画) 、静态数据可视化、动态数据可视 化( 数据动画) 。 算法可视化( a l g o r i t h mv i s u a l i z a t i o n ) 指对软件高层抽象的可 视化，也有一个从静态到动态的范围问题，所以分为静态算法可 视化、动态算法可视化( 算法动画) 。流程图就是一个简单的静 态算法可视化的例子。 可视程序设计( v p ：v i s u a lp r o g r a m m i n g ) 指在构造程序时，利 用“可视的”技术对程序进行规范说明：v i s u a i b a s i c 和v i s u a l c + + 就是具有一定可视编程能力的可视程序设计语言，v p 本身已形成 一个领域。v p 和s v 之间的主要差异是蕴涵的目标：v p 试图使程序 的规范说明与设计变得较容易，而s v 试图使程序和算法变得容易 理解。v p 本身可以传递程序的信息，它是静态代码数据可视化的 一种。许多v p 系统就提供了某种s v ，但这不是它的主要功能。 硕士学位论文 示范程序设计( p b d ：p r o g r a m m i n gb yd e m o n s t r a t i o n ) 示范程序 设计是通过用户的演示实例来实现程序的规范说明。它是一个类 似s v 和v p 有关的领域，在早期的文献中有时称作实例程序设计 ( p r o g r a m m i n gb ye x a m p l e ) 。意思是用户创建一个程序时可以 不需要高级的程序设计技巧，可以只演示一个实例，而由系统推 导出一个程序。因此，如果用户知道如何在计算机上完成一个任 务，那么就可以建立一个程序去完成该任务。 2 2 算法可视化 ，算法可视化啪( a l g o r i t h mv i s u a l i z a t i o n ) 是将一个程序的数 据、操作和语义提取出来并进行动态演示，利用诸如图形、文本、颜 色、声音、编码、动画和视频等多媒体工具集合来描述算法。算法可 视化一般分为两类：静态算法可视化，通过一系列静止的图像来展 示算法的执行过程；动态算法可视化，即算法动画，像电影一样连 续的描述算法的执行过程。设计算法可视化系统需要遵循以下十大准 则嗍：一致性，交互性，清晰简明，容错性，能够适应使用者的 知识水平，强调可视化部分，能够吸引使用者，符号和图标结合使 用，包括算法分析并且能够与其它同类算法进行比较，包括系统执行 的历史记录。算法可视化主要有两种用途：研究和教学。 算法可视化( a v ) 用离散的或是连续的图片来描述算法的执行， 可视化的过程能被用户所控制。通过算法可视化提供图形或动画的展 示能够使意识模型具体化。 基于三层结构模型的算法可视化教学研究与实践 在执行算法的过程中，算法可视化感兴趣的是所有数据结构状态 的变化。为了从逻辑层上理解算法的行为，算法可视化是一种有选择 性的可视化，会忽略一些不能提供算法行为信息的数据类型或变量。 算法可视化可以看成由一系列离散的数据结构视图组成，包含足够的 图片数来充分解释算法的行为，同时也展现了数据结构的本质特征。 2 3 算法动画实现技术 算法动画( a l g o r i t h ma n i m a t i o n ) 系统利用计算机视觉技术来 帮助学习者有效地以视觉行为直接了解、领悟一个抽象算法的行为。 不过，将算法动画化这个过程并不容易，人们常常很难用图形展示一 个算法的精髓。因此，动态可视化能起到不可代替的作用。 算法动画将执行中算法当时的状态以可视化映射展示给用户。可 视化能被动画化是基于在两个连续的状态之间执行的操作。目前已有 一些技术能使算法与可视化发生联系，这些技术按实现方法可以分为 以下几类，有些系统不属于某个单独的分类。 2 3 1 注释方法 注释是产生算法动画的经典方法。例如用c + + 代码编写的软件 p o l k a 舾1 ，通过对c h 实现的算法程序后添力h p o l k a 伪代码的方法建立 算法和动画页面之间的联系。通常，用户能手动扩展源程序，添加用 以产生动画的注释行代码。 注释方法的主要思路是：先构造一个动画子程序库，对源程序进 硕士学位论文 行分析处理，在必要的地方添加某个动画子程序，动画子程序的参数 从源程序中提取，最后得到一个程序执行与动画演播同时进行的新程 序；触发方法是在“程序状态( 程序中某几个有代表性的数据值) 和 图形表示之间定义某种联系，用程序状态的改变触发图像的相应改 变；还有提供用户可视化语言，支持用户以指令方式编写可视化代码 或以规格说明方式描述可视化等。 自动注释是注释里一种有意义的方式，系统通过调用源代码自动 添加必要的动画。在程序动画里采用这种技术的系统有e l i o t m 以及 后来的j e l i o t 嗍。例如，e l i o t 钉是基于s e l f - a n i m a t i o n 类，使用p o l k a 嘲 包提供的服务。系统利用s e l f a n i m a t i o n 组件从源代码里自动抽取数 据对象，而s e l f - a n i m a t i o n 本身依赖于c + + 运算符重载的能力。 。当然，注释方法还能应用于对并行算法可视化，但由于注释代码 行可能会破坏源程序的执行顺序，改变相对执行速率，从而产生不同 的结果。 2 3 2 脚本语言方法 脚本语言方法顾名思义，就是采用编写脚本语言的方法来产生动 画，如b a l s a - i i 口1 和j a w a a 。j a w a a 动画系统是用j a v a 语言编写的，任 何语言编写的程序都可以使用j a w a a 命令编写脚本程序，然后使用兼 容j a v a 的w e b 浏览器将命令序列( 脚本语言) 动画化演示。j a w a a 动画 系统还提供了编辑器，允许用户拖放图形化的动画元素。可编辑的动 画元素能够和j a w a a 脚本语言相结合产生动画，这样会减少创建复杂 i o 基于三层结构模型的算法可视化教学研究与实践 动画的时间。 2 3 3 侵略式方法 当系统在执行程序时并行的进行可视化，是否会打断程序的执 行? 如果会被打断，则可视化具有侵略式的性质。 可视化与被可视化的算法程序的连接方法分为侵略式和非侵略 式。侵略式影响源代码，如在感兴趣的事件处加入打印可视化命令的 语句，像前面提到的注释方法等；非侵略式不影响源代码，如提供了 某种可视化的执行环境( 解释器或编译器) ，可视化者以一种声明方 式附加非侵略“探头”到数据结构或代码上，实行监控显示。 非侵略式方法能够改变算法的行为而不需要修改算法本身。这种 方法允许多种功能包括改变输入、范围和交互式算法动画的布局。添 加注解是固有的侵略式方法，其他方法或多或少的涉及到侵入。 2 3 4 事件驱动v s 状态驱动方法 对动画系统的一个基本分类方式取决于该系统是由事件驱动还 是由状态驱动。在事件驱动方法里，可视化设计者诠释程序代码里的 关键点并发送能改变演示的有意义事件。该方法允许产生直观的定制 动画。定制动画需要利用源代码并且要求可视化设计者对操作有着深 刻的理解。基于有意义事件的代表系统包括b a l s a i i 恻，p o l k a 隋1 和 a n i m a l n 町。 状态驱动方法在算法执行的过程中监视数据结构的改变，观察有 硕士学位论文 意义变量的变化并创建计算状态到可视化的映射。该方法不需要或者 只需要一点关于源代码的知识。基于状态映射的两个著名系统是 p a v a n e 和l e o n a r d o 。 2 3 5 动画框架 框架是针对给定问题域的引用数据类型集合，包括控制流系统， 控制实例对象进行交互。框架被广泛采用，因为它是一个框架，修改和 定制框架比从零开始写应用程序要容易的多。根据组合和类继承的原 则，应用程序接口( a p i ) 通常用来支持引用数据类型的重用( 如j d s l v i s u a l i z e r n 钉) 这样的框架称为应用框架，区别于和目标程序联系 松散的概念框架。 一 ， 根据框架与目标程序交互的层次来区分为不同的规格类型。应用 框架和被可视化的程序关系密切，因此动画库应属于这个分类，而概 念框架不需要任何系统代码。 当然，从这个意义上来说存在既不是应用框架也不是概念框架的 系统。例如，很多调试器就划入这样的分类，即使它们和软件可视化 有一些联系，但是这些系统并不是以产生算法动画为目的。 2 3 6 从上往下v s 从下往上可视化 ，软件可视化领域存在许多应用框架。t a r r a i n g i m “郇是由n o b l e 创 建的框架。它的设计思想是监视目标程序并搜集程序行为信息。目标 程序的实现是封装在接口里的。t a r r a i n g i m 从上往下产生可视化一即 基于三层结构模型的算法可视化教学研究与实践 从抽象开始而不是从具体实现开始；而从下往上的技术是使用注解或 根据映射规则从程序实现里提取抽象信息。 对算法可视化而言，从上往下的可视化是非常有意义的思想。因 为在算法可视化里关心的是抽象的算法和数据结构，比如关注栈的通 用行为入栈和出栈，这与栈是用c 语言实现还是j a v a 语言实现或者是 数组实现还是链表实现的细节无关。因此可视化系统只需要知道怎样 利用被可视化的概念抽象，而不需要知道怎样实现它们。此外，不同 的视图可以被重复利用来展示所需要接口的任何对象。 2 4 本章小结 从能否达到教育目标的教学观点来看，各种连接技术和规格类型 都有他们自己的利与弊。一种可能的教学方法是通过培养学生制作算 法动画的创造性来达成教学的目的，就像s t a s k o n 5 1 ，涉及到系统的用 户干预性和交互性特征。 不需要用户干预的动画系统只包含了有限的算法动画，例如， j e l i o t 嘲算法动画包有许多预定义好的算法动画如串的模式匹配算 法和冒泡排序算法，无须用户对算法本身进行手工干预。自动动画 能帮助学生理解算法行为并通过可视化调试来追踪错误。然而，从研 究的观点来看，可以通过应用程序接口( a p i ) 来实现低层次应用，因 此，无需通过深究原代码来弄清楚他们是如何工作的。算法动画的研 究者一直致力于研究在动画系统中如何让程序员的手工干预降到最 低的技术，并取得了一些进展。例如，a s t r a c h a n 小组。嗣基于早期 硕七学位论文 b a l s a n 7 1 ，t a n g o “时，和p o l k a 阳1 开发了一种有意义事件方法。 另一个问题是交互的层次。程序动画本质上需要“调试功能”。 概念动画似乎提供更复杂的交互显示。学生可利用j d s l v i s u a l i z e r n 3 1 通过编写新方法来改变系统的行为，或者通过模拟原始操作序列来改 变系统的行为。一般来说，在程序动画中可以通过关注数据结构可 视化来研究算法，在概念动画中可以通过关注算法和其行为来研究数 据结构。 最近的许多研究关注于开发交互性更强的系统来辅助数据结构 和算法的教与学。这些系统大多具有程序语言的依赖性，目的是改 善计算机程序的质量和功能。在这种交互式过程中，反馈的质量显得 尤其重要。然而，这些系统大多没有给出怎样评价或如何获得学生绩 效的反馈。仅有少数的系统能够自动评估学生表现。这些系统大多为 测试在给定的输入下学生的程序是否输出正确。 虽然反馈的最根本形式是反馈给学生，但是仅有极少的系统能够 评价学生的工作，以及把学生的表现不断反馈到老师那里。在改善教 + 学的过程中这一点是非常重要的。另外一些软件关注的是学生是否 能够使用这些工具作一些有用的事情，或仅仅娱乐和享受，例如，有 的动画没有实际的学习价值。如由b a k e rn 9 1 报告的那样，有些学生 不把这些系统看作补充工具，因而不能以最有效的方式使用他们。 基于三层结构模型的算法可视化教学研究与实践 第三章算法可视化应用情况调查 3 1 国外若干算法可视化教学软件 为了解决学生学习抽象概念的困扰，辅助算法和数据结构学习的 可视化软件便应运而生。实践证明动画比文字叙述更有助于学生理解 和记忆，尤其当学生可以通过参数的输入去观察不同的动画展示时， 最为明显。接下来列举几个有代表性的国外算法可视化教学软件。 ( 1 ) j a w a a 羽 图3 1j a w a a 实例 j a w a a ( j a v aa n dw e b b a s e da l g o r i t h ma n i m a t i o n ) 使用一种简单 的命令语言来实现数据结构的模拟，并通过w e b 浏览器来查看。它能 够创建和移动原子对象( 圆，线，文本，矩形) 和数据结构对象( 数 组，栈，队列，链表，树和图) 。能为任何语言编写的程序创建易于 理解的数据结构和算法动画。 硕士学位论文 ( 2 ) a n i m a l 图3 - 2 a n i m a l 实例 a n i m a l 是用j a v a 语言编写的软件，具有平台独立性。a n i m a l 的可 视编辑器提供了基本的原子对象如多边形、文本、链表元素和弧，方 便外行创建和编辑动画。当然有编程经验的用户也可以利用a n i m a l 提供的内嵌脚本语言或调用a n i m a la p i 来达到迅速创建动画的目 的。因此，该软件具有通用性，并不仅仅能产生算法动画。 ( 3 ) j e l i o t 8 1 图3 - 3j e l i o t 实例 1 6 基于三层结构模型的算法可视化教学研究与实践 j e l i o t 是一个实现程序动画的可视化工具，能够运行在任何平台， 包括w i n d o w s 、l i n u x 和m a c ，但需要安装j i 也环境。它可以动画化 大多数j a v a 程序，产生程序动画，但不支持内部类和j a v a l 5 引入的 新概念。4 一 在j a v a 程序设计课堂中，教师可以边讲解概念边给学生演示程 序的具体执行过程。学生也可以使用j e l i o t 在课外时间可视化自己的 j a v a 程序。 以上三种可视化教学软件都能可视化算法和数据结构抽象概念， 但各有其特点。按教学软件应用范围和领域分，a n i m a l 和j a w a a 属 于通用工具，需要编程和注解，能制作几乎任何类型的内容；j e l i o t 属于专用工具，需要编程并且不支持交互，只应用于计算机学科领域。 3 2 可视化软件使用情况调查 通过对湖南长沙6 所高校( 包括职业院校) 的1 0 0 名( 师生比为 1 ：4 ) 计算机专业师生使用可视化软件情况的调查发现，尽管可视化 软件有许多优点，然而在教学中普及使用情况和实际收效却不佳。造 成这种结果的原因是多方面的，如创建可视化非常耗时以及许多算法 可视化系统缺乏与用户的交互和反馈等。下面选取了调查中一些有代 表性的问题，并对问题的回答情况做了整理和统计。 ( 1 ) 如何使用可视化软件 主要针对静态可视化和动态可视化的使用情况。 硕士学位论文 表3 h 可视化的使用频度 几乎每周每学期 使用类型 从不使用 每天使用使用一次使用几次 静态 7 2 2 0 8 o 动态 1 0 2 3 5 4 。 1 3 课堂以外 的动态 5 1 9 5 3 2 3 如表3 1 所示，回答者表示他们经常使用静态可视化如幻灯片、 图片和在黑板上手工绘制图。对于动态可视化比如计算机软件、动画 和交互式示范，过半以上的回答者在教室使用动态可视化一学期仅几 次，1 3 从没有利用过动态可视化。只有四分之一的回答者使用动态 可视化每周一次。从上表中也可以看到学生在课外如何使用动态可视 化的情况。有四分之一的回答者说学生从不在课外使用动态可视化； 过半的回答者说学生在课程外使用动态可视化每学期也只有几次。 ( 2 ) 不愿意或者不能使用动态可视化的原因 考察的原因主要包括三个方面的因素：时间因素( 包括制作可视 化教学案例、安装软件、学习新的工具和备课所耗的时间) ；信赖度 因素( 包括哪些是有效的和值得信赖的软件) ；适应性因素( 教师利 用可视化如何教和怎么教等如何有效整合的问题) 。 回答者可以任意选择他们认为不利于动态可视化使用的两个选 项( 主要因素和次要因素) 。选择频率按降序排列如下： 9 3 ：需要时间来搜索好的实例( 从w e b 或者书本) 9 0 ：需要时间来学习新工具 9 0 ：需要时间制作可视化教学案例 l 冀 基于三层结构模型的算法可视化教学研究与实践 8 3 ：缺乏有效的开发工具 7 9 ：需要时间将可视化结合到教学方法和教学内容中去 6 9 ：缺乏有效的和值得信赖的工具 6 6 ：不确定如何将技术成功整合到课堂 6 6 ：需要时间来安装软件 5 9 ：缺乏有效性证明 4 8 ：不确定算法可视化技术对学生有益 3 8 ：学生反应被动 31 ：算法可视化可能会隐藏很多重要的细节和概念 ( 3 ) 教师从使用可视化经历中的获益 以下是按选择频率的降序排列对最主要的收益和次要的受 益的选择。 9 0 ：教学经历是一种乐趣 8 6 ：提高学生的参与层次 8 3 ：课堂对于学生来说更加有趣 7 6 ：可视化为讨论算法的概念基础提供了强大的依据 7 6 ：改进学生的学习动机 7 6 ：可视化允许有意义的使用可利用的技术 7 2 ：提高学生的学习效果的依据 6 2 ：当使用可视化时，理解变得很容易 5 2 ：提高学生学习的主观依据 ( 4 ) 教师评价可视化的效果所采用的技术 硕士学位论文 回答者可以选择两个选项包括主要信息来源和次要信息来 源。以下是按选项选择频率的降序排列： 8 3 ：在课堂上非正式的反馈 8 3 ：课外非正式的反馈 5 2 ：学期末简要的问卷调查 4 8 ：在课堂上简要的问卷调查 4 5 ：非正式的比较两组的教学效果 3 4 ：学期末在线问卷调查 2 1 ：在课堂上在线问卷调查 3 3 国外可视化教学实践经验 国外可视化教学日趋成熟，积累了一些经验。比如r , ：h u r i 锄1 认为 在可视化中要考虑色彩、声音和交互的问题。对于算法可视化软件的 要求没有统一的标准，下列十一点是被普遍认可并从长期可视化教学 实践中总结出来的建议。 ( 1 ) 提供资源帮助学生理解可视化 可视化能使抽象的知识变得具体，但有的时候，可视化本身却很 难理解。学习者可能会发现把可视化和被设计表现的底层的算法做映 射很困难。图形表示的含义以及图形与程序的关系可以采用以下两种 方法帮助学习者理解：可以通过在系统里内嵌文本描述的方法来解释 关系，或者通过在课堂中为其分配指导的时间来加强对关系的理解。 ( 2 ) 适应不同知识层次的用户 2 0 基于三层结构模型的算法可视化教学研究与实践 初学者往往看到很多复杂的细节和窗口就望而却步，他们通常愿 意使用预先定义好的数据去测试一个算法动画，而高阶学习者却喜欢 能够自定义输入数据更充分的测试算法。初学者可能更容易理解基于 幻灯片和电子书这样的表现形式，而高阶学习者可能会从多视角观察 中受益。 ( 3 ) 提供多视图 在可视化中提供多视图能够促进学习者的理解。算法能够从不同 的角度来观看，例如源代码的控制流或者是数据结构的状态。算法也 可以表现为不同抽象层次上的可视化，如提供算法实现的程序动画视 图( 在程序执行时候执行处代码会显示为高亮) 和抽象的算法动画视 图。这样，前者把算法行为和程序代码关联起来。后者提供算法伪代 码而不是程序实现的源代码以“。可以通过模拟伪代码来实现算法动 画，那么动画应该与伪代码保持一致。从教育学的观点来看提供不同 角度的视图是有益的。例如h a l v i s 池1 系统设计三步来展示动画：一个 熟悉的比喻能帮助学习者理解问题；展现多视图动画并伴随有解释； 应用实例。 ( 4 ) 包含性能信息 效率分析是理解算法的重要部分，因此若能显示算法执行时相关 的数据将加强学习者对算法效率的理解。其次也可以通过同时动画化 几个算法来比较每个算法性能。这样用户能够通过可视化来推论不同 算法解决同一问题时效率的差别。 ( 5 ) 包含执行历史 硕士学位论文 在算法动画的若干步骤后，学习者通常容易遗忘前面的步骤，而 造成对先前执行步骤的误解或者有的学习者希望对历史执行过程有 个全局的把握，那么利用历史信息可以帮助学习者克服前面的问题。 历史信息能够明确的提供或者整合到算法视图中去。在j f l e a p ， 当逐步执行非确定自动机的例子时，学习者可以选择任何结构并观看 从初始状态到现选结构的路径历史。 ( 6 ) 支持灵活的执行控制 可以对可视化进行灵活的控制，包括能够前进和后退的执行可视 化。用于可视化控制的用户接口就像一个视频播放器，有包含下面功 能的按钮：终止，暂停，单步前进，单步后退和退回到初始位置。 ( 7 ) 支持学习者建构可视化 。 s t a s k o “踟提倡学习者建构他们自己的可视化。因为学习者们亲手 建构的前提是他们对算法本质有了深刻认识，同时该建构过程中也是 用实践检验所学理论的过程。 ( 8 ) 支持用户化输入数据集 允许学习者为算法指定他们自己的输入数据集，如为冒泡算法指定待 排序记录，一定程度的参与性能激发学生学习的兴趣。鼓励学生主动 去探索各种情况下算法的执行效率。例如学习者可以通过几组有代表 性的数据来测试算法，从而理解算法在最好情况下、最坏情况下和平 均情况下的时间复杂度。 。 ， ( 9 ) 支持动态提问 、为了鼓励学习者在观看可视化的过程中能同步思考，可视化系统 基于三层结构模型