分治算法的自动可视化设计" - 理论计算机科学电子笔记

理论计算机科学电子笔记224（2009）159-167www.elsevier.com/locate/entcs分治算法的自动可视化设计J. A'ngelVel'azquez-Iturbide1，AntonioP'ereez-Carrasco2和JaimeUrquiza-Fuentes3DeartamentodeLenguajesySistemasInforma'ticosIUniversidad Rey JuanCarlos西班牙马德里摘要本文讨论了程序可视化的设计，足以表示分而治之算法。首先，我们提出了几个调查的结果进行可视化的分治算法在文献中。其次，我们提出了三个互补的，协调的意见，这些算法的建议。总之，它们分别基于激活树的动画、数据结构的动画和子结构的可视化序列。保留字：可视化，动画，分治，激活树，数据结构1引言程序可视化和算法动画之间有一个非正式的区别。前一个术语描述了与程序源代码紧密相关的外部表示。后一个术语是指一段程序（通常是算法）的抽象行为的外部表示。由于程序可视化的抽象级别较低，它们通常是自动生成的，而算法动画的抽象级别较高，需要人工干预。由于电子邮件是教师不使用可视化的主要原因之一-软件在教育中的应用，值得进一步探索不同的方向 程序可视化[14]。 我们已经解决了一系列的研究，包括在生成程序可视化的基础上，他们的底层算法设计1电子邮件：angel. urjc.es2电子邮件：antonio.perez. urjc.es3电子邮件：jaime. urjc.es1571-0661/© 2008 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2008.12.060160J.Á. Velázquez-Iturbide等人理论计算机科学电子笔记224（2009）159技术，例如分而治之或回溯。因此，想要理解和分析常见设计技术的算法行为的学生可以生成算法的表达性自动可视化我们设计了一个实现框架[6]来开发几个可视化系统，每种设计技术一个。为了说明这个框架的可行性，我们实现了第一个可视化递归的系统，称为SRec [20]。现在，我们正在解决一个适当的算法设计技术，即分治的可视化系统的设计。本文的目标是提出足够的分而治之技术的可视化设计。在第二部分中，我们提出了几个研究的结果，我们进行了可视化的分治算法在文献中。第三部分是我们的建议，包括三个互补的、协调的观点。最后，我们总结了我们的结论和未来的工作。2分治算法可视化研究综述在本节中，我们展示了我们对分治算法的可视化进行的几项研究的结果。我们假设分治算法的定义是众所周知的，但我们在这里列出了本文其余部分使用的术语。分而治之的解决问题分解成子问题。它们被递归地求解，从而产生子解，子解的组合让位于原问题的解。分治算法经常遍历和操作数据结构。每个子问题被约束到结构的一部分，即子结构。 我们这里只处理一维和二维数组，因此我们经常使用术语（子）数组，（子）向量和（子）矩阵。 最常见和最有效的方法 定义子数组的方法是使用一个范围，用一个较低的索引和一个较高的索引定义。2.1递归的可视化分治算法是递归算法的一种特殊情况。因此，在第一种方法中，我们试图利用递归算法的可视化。这些可视化在CS中是众所周知的：激活（或递归）树、执行堆栈、跟踪和（代码或变量的）多个副本。这些可视化对于线性和多重递归算法并不同样有效。 特别是，激活树对于显示行为更有用 多个递归算法，例如，分治算法激活树对于分而治之算法有局限性。它们对于只有几个简单参数或结果的算法是最有效的。 但是，它们对于较大的数据结构并不有效。以下两个文件说明了合并排序的不足之处。这两个数字都是用SRec生成的J.Á. Velázquez-Iturbide等人理论计算机科学电子笔记224（2009）159161图1.一、显示数组内容和索引的{0，4，2，9，6，8，3，1，5，7}合并排序的激活树图二、用于{0，4，2，9，6，8，3，1，5，7}的合并排序的激活树仅显示数组索引[20 ]第20段。系统允许用户选择要显示的参数或结果;当方法不返回任何值但产生副作用时，将显示参数的原始值和最终值。它还有几个工具（缩放+平移，概述+细节）来处理大规模的激活树。最后，可以使用用户定义的着色方案来区分输入/输出值，以及全局进程中调用的状态（已执行，活动或挂起）。尽管有所有这些设施，所得到的可视化效果并不令人满意。图1显示了数组的文本表示如何产生长节点，从而产生宽而浅的激活树，难以浏览和理解。此外，在每个递归调用中显示完整的数组使得识别其相应的子问题和子解决方案变得困难。图2显示了从节点中省略数组会产生更紧凑的显示，但是在排序过程中数组内容的变化是不可见的。162J.Á. Velázquez-Iturbide等人理论计算机科学电子笔记224（2009）1592.2算法动画算法课程包含许多分而治之的算法，主要是合并排序和快速排序。因此，许多动画系统的创建者已经为这些算法开发了动画。我们回顾并分析了Diehl [5]和Stasko [17]的参考书中包含的快速排序动画的显示。”[5]《明史》：“一者，一也。1.5 4.4）和Stasko [17]包含更高的数（pp. 41，42，91 ，151，158 ，254，374 ，377 ，379）。这项研究表明，由于以下几个原因，一些图形表示是无用的• 一些通用的图形表示太差。例如，仅仅显示要操作的数据结构是不够有表现力的（参见第103页）。42）。• 向量的表示，其中每个单元格仅与其大小成比例地显示，对于某些问题（例如排序）是有用的。 我们发现细胞的表示为垂直条（图）。1.5和4.4），水平酒吧（pp. 374，377）或在“点视图”（pp. 41，151，379）。然而，这些动画也包含可以成功地通用于其他分而治之算法的元素：• 它们使用盒子来封装每个递归调用处理的子数组（图1）。1.54.4）。• 它们根据元素在算法历史中的状态对元素进行分类通过使用形状（pp.41，91，158）或颜色（图。1.5和4.4，pp.91，158，374）。• 分割树（Partition Tree）41，91，158）是一个激活树的变体，它将递归和向量表示法巧妙地结合在一起。总之，它由一个与激活树同构的树组成，其中向量的元素被显示为树的节点（当它处于其最终位置时）或作为一个子向量（当它还没有被处理时）。对递归算法可视化的不同分析可以在Stern [18]中找到。他们提出了三种不同的算法，这取决于它们如何处理数据结构（即，修改，遍历或构造它的算法），而不是考虑它们的递归方案。然而，他们的可视化是否可以推广并不明显：他们提出的可视化包含第一类算法的向量，以及其他两类算法的树。 文章中包含的前一个类的可视化对应于分而治之的算法（即快速排序）。它水平地显示向量，并在其下面用水平条反映递归调用。2.3教科书中的可视化一个全面的研究分而治之算法的可视化必须考虑CS教师使用的表示。因此，我们研究了一些关于算法设计和分析的最负盛名的教科书[7]。选择必然是任意的，但我们认为它代表了高质量的算法教科书[1，2，3，4，19，8，9，10，11，12，13，15，16，21]J.Á. Velázquez-Iturbide等人理论计算机科学电子笔记224（2009）159163我们总结了我们的发现，在丢弃任何问题的可视化之后：• 通常包含一个可视化的递归算法，通过显示其元素来说明递归算法的归纳定义：问题，子问题，子结果和结果。• 通常包含激活树的可视化。在其图形表示中有许多变体可视化单个树或两个并行树，其中第二个显示辅助操作（例如，快速排序中的分区显示激活树或数据结构的可视化序列。注意，后者是一个隐式树，因为它对应于它的遍历。显示分隔索引或子数组的内容显示数据结构中包含的原始值或最终值。以升序或降序布局显示激活树。 我们还发现了两者的连接显示，代表前进和返回阶段递归的• 通常包括数据结构的可视化，并补充一些由分治算法执行的分区表示：通过嵌套框包围子数组。作为由连续调用处理的子结构的连续状态序列。每个子结构要么根据其定界索引对齐，要么与递归树同构3分治算法可视化自动生成的一种方案基于上一节的发现，我们提出了三种（协调的）分而治之算法行为的观点。我们对可视化提出了一个额外的要求：它们必须适用于一维和二维数组，即向量和矩阵。• 基于激活树的动画。每个节点都有一个它所关注的子结构的可视化• 一个基于数据结构的动画。它是补充与其划分的算法的示意图。• 子结构的可视化序列我们将在以下小节中详细阐述这些观点3.1基于递归过程的图3示出了该视图的示例。 与图1相反，每个阵列在每个节点中可视化一次。此外，用户定义的着色方案的应用·······164J.Á. Velázquez-Iturbide等人理论计算机科学电子笔记224（2009）159图3.第三章。基于激活树的{0，4，2，9，6，8，3，1，5，7}归并排序可视化图四、基于激活树的换位可视化图五、基于数据结构的{0，4，2，9，6，8，3，1，5，7}归并排序可视化允许一目了然地确定哪个子数组是递归调用的焦点，以及它是进入还是退出调用时的子数组状态。对于前一个问题，我们建议使用相同颜色的不同色调，对于第二个问题，我们建议使用不同的颜色。 在第五章中，蓝色和红色分别用于表示输入值和输出值。这种观点也可以应用于矩阵。图4对应于转置方阵的分治算法（无效的！）。3.2基于数据结构该视图提供了要操作的数据结构的连续状态的离散动画。它以常规格式显示矢量和矩阵。 下面显示了一组条形图，它们通过每个递归调用分隔的子数组来反映递归过程。图5示出了该视图的示例着色方案被应用于底层条以及它们的关联子阵列。第一种颜色（图中的5）用于标记递归调用，J.Á. Velázquez-Iturbide等人理论计算机科学电子笔记224（2009）159165图第六章基于数据结构的换位可视化执行结束，以及它们相应的子向量。 第二种颜色（图5中的蓝色）用于执行待定的递归调用及其相应的子向量。两种颜色的色调用于表示激活树中每个呼叫到活动呼叫的距离。活跃的呼叫总是彩色的光，更远的节点颜色更深。 在图5中，左侧部分已经排序，是集中在子数组3，8处并且即将退出的活动调用。这种观点也可以应用于矩阵。一组水平条被一组嵌套的提示子矩阵的框所取代。图6示出了用于转置方阵的算法的这一点。在这里，该算法只完成了三个基本情况，并专注于第四个。3.3数据结构的可视化序列第三视图显示自上而下显示的数据结构的可视化序列。每次调用递归调用时，该视图的底部都会显示一个新的数组可视化。为了突出递归过程，每一行只包含由其关联调用聚焦的子数组，根据166J.Á. Velázquez-Iturbide等人理论计算机科学电子笔记224（2009）159每次递归调用退出时，结果子数组的可视化显示在调用条目上显示的原始子数组下方。再次，颜色的使用允许区分它们。 图7a示出了用于图7a的该视图。 合并排序算法数组的左半部分已经排序，并且调用了对它的右半部分进行这个视图的主要优点是它允许生成反映递归算法的归纳定义的可视化。图7b说明了合并排序的这个特征。通过选择动画控件跳过递归调用并隐藏其底层显示的可视化，结果显示仅由原始数组，两个递归调用聚焦的两个子数组，这些递归调用的输出子数组和最终数组组成。4结论和今后的工作特定算法的自定义可视化（如算法动画中所示）可能是最具表现力的。 但是，手动生成所需的电子邮件每一个特定的动画是禁止的。因此，我们主张使用程序可视化作为一种替代，无边界的方法。我们在本文中已经证明了两个重要的结果。首先，我们已经提出了检查递归的可视化以及分而治之的可视化在文献中的结果。其次，我们已经提出了三个分而治之算法的程序可视化。其中两个分别基于激活树和数据结构的动画;在显示代码和数据元素的意义上是混合的。 第三个可视化是一个子结构序列，并且能够说明算法的归纳定义。我们已经实现了这里提出的设计的工作原型。然而，要成为一个全面运作的系统，还需要做更多的工作.如[20]中针对SRec系统所述，由专家（即教师）和在与学生的会话中进行的可用性评估对于评估其有效性非常重要引用[1] 啊哈，V，J. Hopcroft和J.Ullman，[2] Alsuwaiyel，M.，[3] Baase，S.和A. V. Gelderl，[4] Escherard，G.和p.Bratley，[5] Diehl，S.，[6] 弗恩安-穆恩诺兹湖，A. P'erez-Carrasco，J. Vel'azquez-Iturbide和J. Urquiza-Fue ntes，基于设计技术的算法动画自动生成框架，在：E。杜瓦，R. Klamma和M. Wolpers，editors，Creating New Learning Experiences on a Global Scale - EC-TEL 2007，LNCS4753，2007，pp. 475-480[7] 弗恩安湖和j.Vel'azquez-Iturbide，算法 设计技 术可 视 化 研 究 （ inspanish）， 在：C。 B. M. A' 。Redondo 和 M. Ortega ， editors ， VIICong resoInternacionaldeInte ra cio'nPersona-O rdenador ，2006，pp. 315-324J.Á. Velázquez-Iturbide等人理论计算机科学电子笔记224（2009）159167(a)（b）第（1）款图第七章完整的（a）和简化的（b）序列的可视化合并排序{0，4，2，9，6，8，3，1，5，7}[8] Gonnet，G.和R. Baeza-Yates，[9] Goodrich，M.和R. Tamassia，[10] Horowitz，E.和S. Sahni，[11] 约翰逊堡河和M. Schaefer，[12] Levitin，A.，“The Design and Analysis of Algorithms,” Addison-Wesley,[13] 曼伯大学，“Introduction to Algorithms,” Addison-Wesley,[14] 纳普斯，G. Roessling，V. Almstrum，W.丹恩河弗莱舍角Hundhausen，A.科尔霍宁湖马尔米，M. McNally，S. R o dger和J. Vel'azquez-Iturbide，探索可视化和参与计算机科学教育的作用，SIGCSEBulletin 35（2003），pp. 131-152.[15] 帕伯里岛，“Problems on Algorithms,” Prentice Hall,[16] Sahni，S.，“Data Structures, Algorithms and Applications in Java,” McGraw-Hill,[17] Stasko，J.，J. Domingue，M. Brown和B. Price，编者，“软件可视化”，麻省理工学院出版社，1998年。[18] 斯特恩湖和L. Naish，递归算法的可视化表示，在：第33届SIGCSE科学教育技术研讨会，SIGCSE 2002，2002年，pp.196-200[19] T.H. 科曼角L. 和R.Rivest，[20] Vel'azquez-Iturbide，J.，A. P'erez-Carrasco和J. Urquiza-Fue ntes，S rec：算法课程递归的动画系统，在：第13届计算机科学教育创新与技术年会，ITiCSE 2008年，2008年，pp. 225-229.[21] Weiss，M.，“Data Structures and Algorithm Analysis in Java,” Addison-Wesley,