理论计算机科学电子笔记224（2009）77-88www.elsevier.com/locate/entcs利用TRAKLA2进行空间数据算法Jussi Nikander1，Juha Helminen2 和阿里·科尔霍宁3赫尔辛基理工芬兰埃斯波摘要本文报道了一个为期两年的项目，其中可视化算法模拟练习开发的空间数据算法课程的结果。从几个角度研究了该项目的成功，即，从开发者、教师和学生的角度。工作量，学习成果和系统的可行性已根据项目期间收集的数据进行了估计。 结果是令人鼓舞的，这激励着在未来将这一概念扩展到其他课程关键词：算法，算法可视化，TRAKLA2，空间数据算法，地理信息学，教学1介绍空间数据算法（SDA）是处理位置数据（如地理数据）的算法。这些算法是地理信息学的一个组成部分，地理信息学是将信息技术应用于制图和地球科学的一个科学由于地理信息学经常使用插图，如地图和其他图表，学生非常熟悉可视化。因此，软件可视化是一个自然的工具，教学SDA及其应用的地球科学家。有许多软件系统可以可视化空间数据算法或其他对地理信息学很重要的概念例如，GASP [19，20]，GAWAIN [5]和Vega [6]说明了几种几何算法，而Hull2VD [3]和VoroGlide [7]提供了Voronoi图的可视化[1]。此外，LEDA算法库4包含其自己的可视化工具GeoWin [2]，该可视化工具可以用于可视化1 电子邮件地址：jtn@cs.hut.fi2电子邮件地址：jhhelmi2@cs.hut.fi3电子邮件地址：archie@cs.hut.fi4 http://www.algorithmic-solutions.com/leda/about/index.htm1571-0661/© 2008 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2008.12.05178J. Nikander等人/理论计算机科学电子笔记224（2009）77空间数据算法。然而，似乎对地理信息学重要的算法的可视化目前不是一个非常活跃的研究领域最近一篇关于MAVIS算法可视化工具的论文作为一个空间算法的案例[8]，但我们无法找到该领域的其他最新进展现有的系统通常向用户提供两种类型的交互。首先，用户可以通过不同的输入查看动画有时，输入可以由用户自由定义。此外，系统支持通过实现自己的算法并使用系统可视化来创建新的算法动画。这些交互方法对应于参与分类的查看、更改和构建级别[14]。跟踪练习是许多教师采用的一种教学方法，在这种方法中，学生通过跟踪数据结构的变化来跟踪算法，同时逐步完成算法。在可视化算法模拟练习中，该过程由提供可视化的图形学习环境支持，这消除了反复绘制相同数据结构的负担。TRAKLA2是一个学习环境，利用可视化算法模拟向学生提供跟踪练习[13]。该系统可以自动评估解决方案，并对仿真的正确性提供反馈TRAKLA2中的可视化与以前的系统之间存在两个主要差异。首先，TRAKLA2练习是为在地理信息学教学中使用而设计的。其他系统，即使它们包含例如几何算法，似乎是为教授计算机科学而设计的。selitt mik第二，跟踪练习提供了与其他系统不同的交互类型。学生在解题过程中通过视觉交互构建自己的算法动画序列。这是参与分类法的构建级别[14]。然而，与其他系统不同，不需要编写任何算法代码来创建新的动画。以前的研究[10，11]表明，只要作业相同，在网络上解决视觉算法模拟练习的测试组和在教室里解决跟踪练习的对照组之间的学习结果没有差异这是一个令人鼓舞的结果，激励我们应用可视化算法模拟练习空间数据算法。挑战在于扩展TRAKLA2系统，使其涵盖算法的一个新领域。主要的研究问题是，是否适用于新的应用领域的可视化算法模拟的概念是值得的扩展框架的花费。这个问题有三个独立的方面：开发者的观点，教师的观点和学生的观点。从开发商的角度来看，我们正试图找出在什么情况下这种项目支付佣金。特别是，扩展系统以覆盖新的应用领域需要花费多少时间和精力。 在实现和设计新的可视化过程中，我们预计会遇到什么样的挑战从教师的角度来看，我们感兴趣的是学习结果：学习者的参与程度（即，他们做了多少工作）和最终考试的整体表现（即，的相关性J. Nikander等人/理论计算机科学电子笔记224（2009）7779练习和取得的学习成果）。最后，从学生在实施之后（即，扩展应用程序框架并实现练习），系统的使用仅需要最小的开销。因此，本研究的目的不是回答是否有人应该重复我们的实验，而是回答可视化算法模拟练习的概念是否足够成熟，可以应用于数据结构和算法以外的其他学科。主要的挑战是，它要求教师是主动的，而不是被动的，也就是说，在课程之前的工作量比在传统的教学中，工作（评分练习）是在课程期间或之后完成的要高得多。这也许可以解释为什么在日常教学中采用这种系统的速度很慢在本文中，我们报告的结果，我们的经验，从一个为期两年的项目中，我们实施了空间TRAKLA2演习。总的来说，考虑到这部分是一个研究项目，部分是一个课程开发项目，这是一个成功的。然而，从单个教师的角度来看，两年的时间似乎太短，无法此外，学生的反馈表明，他们希望在课程中进行更多的可视化算法模拟练习。2TRAKLA2的空间扩展TRAKLA2是一个自动评估可视化算法模拟练习的框架[13]。该系统是建立在可视化算法仿真的概念。用户可以通过GUI动作（如拖放数据项）构建算法执行的动画。在练习中，学生可以自由地在这些动画中后退和前进他们还可以重置练习并获得新的随机生成的输入。一个模型的答案也可以作为一个动画。这些练习在Web环境中部署为Java小程序。图1显示了TRAKLA2环境的屏幕截图Fig. 1. TRAKLA 2练习，用于Douglas-Peucker线简化。80J. Nikander等人/理论计算机科学电子笔记224（2009）77TRAKLA2的SDA扩展由三个主要部分组成：空间基元、空间数据结构和空间数据可视化。此外，还需要几何函数和算法的实现，用于处理空间数据目前，该扩展仅限于空间数据结构和算法所操作的基元是几何实体，例如点、线和多边形。这种多维数据可以以从其几何属性导出的键值的形式存储。在这方面，空间数据元素是值的有序列表，元组，在空间上下文中表示特定的几何实体。例如，多边形可以存储为其顶点坐标的有序列表。在基本的TRAKLA 2练习中，数据是一维的、单字母字符和整数。它们之间的关系简单明了，无需任何额外的可视化。SDA扩展引入了两种用于空间数据的新可视化。首先，空间基元的元组表示可以以简单而精确的表格形式可视化。尽管很精确，但这种数据密集型方法在传达数据元素的几何性质和数据元素之间的关系方面做得很差。因此，需要不同的可视化来说明空间属性。这就是区域可视化，它基本上是一个此外，空间数据表示在三个不同的可视化水平首先，在确切的数据项级别，数据根据其几何属性显示为值的元组。其次，在数据结构层面，我们有特定于数据结构的规范化可视化，其中空间数据项被标记为唯一标识符或显示为元组。在最高的抽象层次上，概念关系和空间属性用显示数据项和结构的区域可视化来说明，该区域可视化具有可能的附加视觉提示来表示算法构造，例如扫描线或圆内测试。图2描绘了包含多边形的相同R树的两个可视化。区域可视化显示多边形和树节点覆盖的区域树可视化显示了树是如何组织的。空间数据分析工作的一个特殊挑战是生成空间数据，用作算法的输入。为了使可视化有助于学习，生成的数据集必须清晰且视觉上令人愉悦。几何图元之间必须有足够的间距以区分和选择它们。此外，标签不能重叠太多。此外，每个练习对数据都有非常具体的约束，这使得很难创建通用的数据源。因此，大多数练习都有自己的生成数据（如简单多边形）的机制。目前，SDA扩展包括12个可视化算法模拟练习。所有的练习都可以在我们的网站上找到5.练习分为两类：追踪练习和开放追踪练习[9]。在跟踪练习中，5http：//www.cs.hut. fi/Research/TRAKLA2/exercises/index.shtmlJ. Nikander等人/理论计算机科学电子笔记224（2009）7781图二、 R树a）画成一个区域，b）画成一棵树。给出了算法及其输入，学生的任务是计算出输出，并通过逐步模拟来构造算法进程的动画。模拟是通过拖放和选择数据项来模拟算法的操作，以及通过其他GUI组件（如按钮）调用操作来完成的然后将用户创建的动画与由算法的实际执行创建的正确状态序列进行比较我们的目标是给出算法的概念性理解。在开放追踪练习中，算法没有严格规定，因此练习更具探索性。学生被赋予一个目标，例如创建点集的Delaunay三角剖分[16]，以及实现它的方法，例如。在顶点之间添加边并进行圆内检验。然后，学生可以通过对它们进行修改并观察变化来交互式地探索结构。最后，通过将最终状态与预期结果进行比较来评估正确性。总体目标不是教一些特定的算法，而是一个概念，例如与Delaunay三角剖分相关的最小-最大-角度准则。3结果空间TRAKLA2练习首先在2007年春季空间数据算法课程中采用，并在2008年春季课程中再次使用。该课程针对地理信息学三年级学生。除了空间练习外，课程还包括其他一些TRAKLA2练习这些练习涵盖了对理解空间算法很重要的数据结构。课程详情见表1。 该表显示了有多少学生开始了课程，有多少人参加了最终考试，有多少TRAKLA282J. Nikander等人/理论计算机科学电子笔记224（2009）77课程中的练习（以及其中有多少是空间练习），TRAKLA2提交的总数，以及获得的平均分数（与最高分数相比）。表1空间数据算法课程年学生人数 #在考试中#exer。(SDA)订阅数量avg. 评分20072008162091615（9个SDA）16（10 SDA）7231036百分之六十七百分之八十三在TRAKLA 2推出之前，空间数据算法课程包括讲座和工作室课程，编程项目和考试。在工作室课程中，学生以小组为单位学习概念层面的空间算法在编程项目中，学生实现了课程中讨论的一种算法。考试是在最后一堂课之后举行的。TRAKLA2的加入并没有减少对课程的任何其他要求在课程中，每个学生都获得了所有TRAKLA2练习的个性化输入。演习分为几轮，每轮1-3个练习。想要通过这门课程，每一轮都需要获得至少50%的积分。学生们不会因为迟交作业而受到处罚。TRAKLA2练习不检查学生3.1开发商2006年2月启动了创建TRAKLA 2空间扩展的项目。第一次演习于2007年1月开始。当时，课程中使用了9个空间练习。在该项目中，共开展了12项空间数据工作，其中11项已在实践中使用。这一未经测试的练习完成得太晚，无法添加到2008年春季课程中。有几个人参与了这个项目，但大多数时候都是两个人在做这个项目，投入这个项目的工作量粗略估计是10实施工作本身可以分为两个独立的任务：扩展演习框架和实施演习。该项目的大部分工作总工程量中只有不到20%根据我们的经验，空间练习的实现通常比基本数据结构或算法练习更3.2老师学生的学习成绩数据这两年的数据是以同样的方式收集的使用线性回归来观察学生的TRAKLA2表现是否分析结果显示，J. Nikander等人/理论计算机科学电子笔记224（2009）7783TRAKLA2结果和考试结果作为一个整体，以及TRAKLA2结果和涵盖R树的单个考试问题之间的关系在这两年中，有两个TRAKLA2练习和一个关于R树的考试问题。结果总结见表2。表2中的结果分为三类。第一类是通过TRAKLA 2练习并参加第一次期末考试的学生人数;第二类是TRAKLA 2成绩与考试成绩整体线性回归分析的特征;第三类是R树练习的回归结果。对于线性回归ρ（相关性），报告了调整后的R2及其统计显著性。表2空间数据算法课程课程信息整个考试r树年Nρadj. R2pρadj. R2p200720089160,830,480,650,180,0050,0580,850,600,690,310,0030,015于二零零七年至二零零八年期间，TRAKLA2业绩出现重大变动。然而，这一变化可以通过两个课程之间对TRAKLA 2练习所做的修改来解释。删除了一个练习，增加了两个新练习2007年课程后删除的练习是最难的练习之一（平均得分54%），而2008年课程中添加的练习是最容易的（平均得分98%）。这两年的考试成绩差不多从表2中可以看出，在这两年中，学生在TRAKLA2和课程考试中的表现之间有很强的相关性，特别是对于R树练习。除TRAKLA2结果与2008年检查结果之间的相关性几乎显著（p= 0， 058）外，所有结果均具有统计学显著性（p0，05）。在数据结构和算法课程中也观察到了类似的结果[10]。3.3学生在2008年春天，我们进行了采访，了解学生的经验与空间练习。我们使用了面试指导方法[17]，面试官有一个要涵盖的主题大纲，但可能会在一定程度上改变问题的措辞和顺序。我们共采访了4名学生（两名男性和两名女性），他们来自两个不同的国家，因此其中两次采访是用芬兰语进行的，两次是用英语进行的。受访者的年龄（22至28岁）和背景各不相同，因为他们在不同的国家和大学/高中接受过教育。两个主要的提问路径进行了探讨：什么是学生表3列出了主要问题。对于每一个问题，我们还提出了一系列后续问题，这些问题扩展了主题，84J. Nikander等人/理论计算机科学电子笔记224（2009）77帮助我们获得更多的信息反馈。表3主要面试问题。意见你认为这个系统有多有用？你认为这个系统对学习的贡献有多大？您认为系统提供的反馈有多有用？你是如何发现系统的可用性的？我们将来是否应该继续在课程中使用该系统？比较您如何将TRAKLA 2空间算法练习与其他教学方法和材料（如讲座、课堂）进行练习和单独学习课本？所有受访者都认为该系统是有益的，并认为这是一个重要的学习工具，应继续在课程中使用。此外，他们认为与讲座相比，他们从TRAKLA2练习中了解了更多关于算法的细节与阅读文章中的算法相比，他们觉得从TRAKLA2练习中掌握思路更快。然而，在尝试练习之前，学生们认为他们应该先对算法有一些基本的了解。提到的主要好处是视觉外观和交互性。学生们认为，通过观察算法的动画，他们能够更好地理解算法的原理。的确，大家都说，模拟答案动画很有帮助。然而，从回答中还不清楚他们是否真的认为它有助于学习算法，或者它只是帮助他们成功地解决了这个问题。同样，学生们发现，系统的模拟方面，这使他们能够实际实践算法，使其更容易记住算法的原则。一位学生指出，通过观察和操作可视化，您实际上可以看到算法是如何进行的，这与编程练习不同，在编程练习中，您需要实现算法，但通常无法很好地观察其执行该系统的问题与自动反馈和特定于运动的模拟界面有关当提交不正确的解决方案时，系统将从动画开始时开始回答正确的步骤数。所有人都认为，虽然你可以通过这种方式找到第一个错误，但通过长模型答案动画来搜索它是很麻烦的。此外，学生们认为这是不公平的，因为在第一次错误之后，系统不会对正确执行算法给予任何分数，并且您不能继续J. Nikander等人/理论计算机科学电子笔记224（2009）7785从你犯错误的地方开始解决这个问题，让你从一开始就一遍又一遍地跟踪算法。此外，他们抱怨算法操作和模拟界面操作（如按下按钮和拖动数据项）之间的映射。根据学生们的说法，这种运动特有的行为没有得到很好的记录，正如一名学生所说的那样，学习如何让物体以应有的方式移动需要一些时间。每个TRAKLA2练习中包含的伪代码被认为是完全无用的或非常有用的，这取决于受访者对编程的熟悉程度。一个有很强编程技能的学生发现伪代码很有用，而技能较低的学生没有注意到它。4讨论4.1开发商在这个项目中，空间数据练习的设计和实现被发现比在这个实验之前完成的大多数数据结构练习花费更多的时间和时间最重要的因素是，在项目开始时，空间算法对开发团队来说大多是陌生的。因此，对于每一个练习，都需要研究所讨论的算法，以便在实现、可视化和教授算法所需的水平上理解它。这是一项此外，使用更复杂的可视化增加了所需的电子邮件数量。例如，区域可视化的使用不像使用基本数据结构级可视化那样直接。区域视图是灵活的，但是指定如何使用它来可视化数据比使用规范数据结构视图更两年10个人月的时间来创建12个练习似乎是一个很大的代价，至少从一个教练的角度来看。然而，一旦实施了练习，在课程上使用它们只需要非常小的、恒定的量的练习，而不管课程的大小或在其上使用的练习的数量。这种主动的方法与手动评估课堂练习的传统被动方法直接相反。在手工评估中，大多数的评估都是针对学生的答案，并且它与练习的数量和课程的规模成正比。 此外，这一比较并不直接，因为如果允许重新提交，这一数字会更大（通常情况并非如此，因为这会增加后勤问题和工作量）。此外，需要在课程的每次迭代中进行手动评估。因此，自动化练习使用的时间越长，它们的好处就越多。最终，自动化练习将比传统的课堂练习需要更少的总体时间，因为这项工作只需要做一次。这需要的时间取决于练习的数量和课程的学生。在大型课程（许多学生）中，这个时间限制很快就会达到（几年内）。例如，在一门数据结构和算法课程中，大约500名学生提交了大约50.000份意见书，其中有40个练习（ap-86J. Nikander等人/理论计算机科学电子笔记224（2009）77方案2.5重新提交/演习）。因此，很容易看出，在这种情况下，该系统很快就支付了费用（很难找到足够的人员在可行的时限内对如此数量的提交物进行评分，更不用说这项工作不是很愉快）。然而，对于空间数据算法等较小的课程来说，定义精确的时间限制更加困难。1000份提交（在2008年）是一个相当容易的任务，即使是由一个单一的教师处理，可能只需要几天的时间来手动评分。即使如此，我们相信，如果我们也考虑到教师和学生的观点，投资是值得的4.2老师学习结果表明，TRAKLA2练习和空间数据算法课程的练习之间的相关性很强，具有统计学意义。它甚至比基本数据结构课程中的相关性更强[10]。然而，这可能是SDA课程样本量小的人为因素。 由于最小的样本只有9个人，一个人的结果可能会对整体相关性产生很大的影响。尽管如此，TRAKLA2运动结果似乎是考试结果的一个很好的指标。TRAKLA2结果的一个有趣的方面是学生们投入了多少精力。在数据结构和算法课程中，TRAKLA2直接执行课程评分，大部分学生获得最高分，即使在获得90%的分数后没有进一步的好处[12]。在空间数据课程中，TRAKLA2点对课程成绩没有影响。尽管如此，学生们似乎想尽可能多地做TRAKLA2练习。即使这远不及学生在数据结构和算法课程中使用的电子邮件数量，这表明大多数学生愿意做比要求更多的工作。这支持了这样一种观点，即这种练习不仅被学生接受，而且比传统的教学设置更能激励学生做更多的工作。4.3学生访谈的结果表明，学生们觉得他们从系统中受益事实上，对该系统的总体态度是非常积极的，当被要求给它一个从0到5的评分时，所有受访者对该系统的评分都在4左右。在采访过程中，大多数受访者还要求进行更多的练习，以涵盖课程中讨论的其他算法尽管如此，讲座仍然被认为是最重要的教学方法，而练习应该起辅助作用。与大多数人的观点相反，一个在计算机科学方面比其他人更有背景的学生认为，这些练习对他来说不是一个非常重要的学习工具。然而，即使他说，一两个练习实际上已经纠正了他对所讨论的算法的现有误解。也就是说，通过可视化算法模拟，J. Nikander等人/理论计算机科学电子笔记224（2009）7787学习算法的一些细节，并调整他不正确的预先存在的心理模型，而不深入研究实现。受访者还提出了这样一个概念，即这种更具参与性的交互式可视化学习将比简单的阅读带来更持久的效果。从本质上讲，他们觉得这些练习更有效地吸引了他们，他们会更长时间地记住这些课程。因此，学生的意见与[14]的结论一致。5结论本文介绍了在空间数据算法课程中实施和使用TRAKLA2系统的经验。该系统的实施是一项比原先预期更具挑战性的任务。需要大量电子邮件的一个重要原因是我们对这个主题不太SDA练习对学生学习的影响与TRAKLA 2练习对基本数据结构课程的影响相似。此外，学生从学生的角度来看，该系统的弱点是对不正确的解决方案和复杂的特定于练习的模拟界面的反馈非常少。提高反馈的质量是目前正在研究的一个主题[18]。为可视化算法模拟设计直观界面的难度比基于先前经验的预期更具挑战性。为了创建自动评估的算法练习，将复杂的数学运算映射到仿真接口动作也是开放的，以进行更多的研究。尽管创建练习需要大量的电子邮件，但我们认为该项目是成功的。可视化算法模拟可用于基本数据结构和算法之外的教学主题。此外，在初步工作投入实施后，该系统可以很好地使用。它使用的时间越长，节省的时间就越多引用[1] Aurenhammer，F.，Voronoi图-一个基本的几何数据结构的调查，ACM计算。监视器23（1991），pp.345-405[2] Bske n，M. 和S. N？aher，Geow是一种通用的几何几何图形可视化方法，在：S。Diel，editor，SoftwareVisualization，Lecture Notes in Computer Science2269，Springer，2002 pp. 637-639.[3] Fisher，J.，凸壳、Voronoi图与Delaunay三角剖分之视觉化连结，于：第37届中西部教学与计算研讨会，2004。[4] Guttman，A.，R-树：一种用于空间搜索的动态索引结构，在：SIGMOD '84：会议录1984年ACMSIGMOD数 据 管 理 国际会议（1984年），pp. 四十七比五十七[5] Hausner，A.和D. P. Dobkin，Gawain：Visualizing geometric algorithms with web-based animation，in：SCG411-412.88J. Nikander等人/理论计算机科学电子笔记224（2009）77[6] 希普克角A.和S. Schuierer，Vega -一种以[7] 伊 金 角 ， R. Klein ， P. Kollner and L. Ma ， Java applets for the dynamic visualization of voronoidiagrams，http://www.pi6.fernuni-hagen.de/publ/ikkm-jadvv-03.pdf。[8] 科 夫 曼 岛 I. Shimshoni 和 A. Tal ， Mavis ： A multi-level algorithm visualization system within acollaborative distance learning environment，Journal of Visual Languages Computing19（2008），pp.182-202.[9] Korhonen，A.和L. Malmi，可视化算法模拟练习分类，在：A。 Korhonen，editor，Proceedings of theThird Program Visualization Workshop，The University of Warwick，UK，2004，pp. 118比125[10] K or honen，A.， L. M almi，P. 我会告诉你的。科学家们，如果在网络上或在教室里执行学习，这是否是一种重复？第七届SIGCSE/SIGCUE计算机科学教育创新与技术年会论文集，ITiCSE'02（2002），pp.121-124[11]Laakso，M. J.，T. Salakoski和A. Korhonen，自动评估和反馈的可行性，在：数字时代的认知和探索性学习程序（CELDA 2005），IEEE技术委员会学习技术和日本教育信息和系统学会，葡萄牙波尔图，2005年，第100页。113-122[12] 马尔米湖V. Karavirta，A. Korhonen和J. Nikander，不同重新提交策略的自动评估算法模拟练习的经验，计算教育资源杂志5（2005）。[13] 马拉米湖、V. Karavirta，A. Korhonen，J. Nikander，O. 我在P. 刘伟，《计算机模拟教学系统与自动评估》，北京：清华大学出版社，2004年。267-288.[14] 午睡，T。 L.， G. Rolinging，V. 很抱歉，W。 丹河 Fle ischer r，C. H undhausen，A. 科尔霍宁湖妈妈咪呀，M. M c N all y，S. Rodgers和J。 A'ngelVel'azquez-Iturbide，Exploringtheheroleoffvisualizationandengagement in computer science education，SIGCSE Bulletin 35（2003），pp. 131-152.[15] Nikander，J.和J. Helminen，空间数据算法教学中的算法可视化，第11届国际信息可视化会议IV2007（2007），pp. 505-510网址http://www.graphicslink.co.uk/IV07/[16] Okabe，A.，B. Boots，K. Sugihara和S. N.邱，[17] 巴顿，M.，“Qualitative Research and Evaluation Methods,” Sage Publications,[18] Seppéalaé，O.， L. 我是我和A。 Korhonen，Observationsonsudenter rorsinalgorithmsimulationexercises，in：Proceedings of the 5th Annual Finnish / Baltic Sea Conference on Computer Science Education，University of Joensuu，2005，pp. 81-86号。[19] Shneerson，M.和A. Tal，几何计算的交互式协作可视化环境，Journal of Visual Languages Computing11（2000），pp. 615-637[20] Tal，A.和D.张文，一个基于图形的计算机图形学系统，北京，2000。可视化'94，会议记录。IEEEConference on（1994），pp. 149
我的内容管理
展开
