论文部分内容阅读
网络中存在大量的程序设计资源,比如各大程序设计网站(Online Judge[1])上的题目和程序设计爱好者所提交的解题代码。这些资源都是初学者学习程序设计十分有用的材料。但是这些程序设计资源都没有很好的组织起来,无法特别有效率的提供给学生学习程序设计知识。
为了将网络中的程序设计资源有效的组织起来,很多方法应用于这个领域。一种方法提出使用初级语言级知识点来表示程序设计中的算法知识,并且通过形式概念分析(FCA[2])的方法生成了教学序列[3],教学序列中的题目的难易程度是由简单到复杂。学生可以按照教学序列的题目顺序在网络中寻找题目进行训练。另一种方法是根据自定义的算法知识的结构[4],对网络中的题目进行划分,比如说排序相关的题目划分到统一个分类下方。这样学生可以根据分类中的知识点可以进行有针对性的训练。这两种方法都是基于预定义的专家库进行算法知识划分,但往往,针对预定义的知识库,我们很难事先去确定专家库中的算法知识的数量和类别,针对知识结构,我们还需要重新调整知识结构框架。这样就造成了诸多不便。
为了摆脱预定义知识库的困恼,一些方法提出根据神经计算的方法去有效的组织网络中大量的程序设计资源,其中有通过自组织映射图的聚类方法去挖掘主流解题方法[5],还有使用神经网络算法去识别程序资源[6]。虽然已经摆脱了预定义知识库的束缚,但是这类方法仅仅是通过神经网络算法聚类得到主流解题方法和识别算法知识,题目的难易程度也很难体现出来。
基于这些方法的缺陷,我们提出使用自主心智发育的方法使得机器能够自动的去组织散落在网络中的程序设计资源。该方法不需要预定义的专家库。
本文将按以下步骤展开:
第一步,我们介绍算法知识表示,因为程序代码作为高级语言,机器并不能自动的挖掘出存在于程序代码中的算法知识,因此我们通过一种知识表示方式-抽象语法树作为程序设计代码的知识表示。
第二步,当得到每个程序代码的知识表示之后,为了衡量每个程序代码的相似性,我们提出了两种衡量方法,一种是基于树大小的相似度计算,该方法以抽象语法树中树节点的数量进行比较。另一种是基于树结构相似度的计算方式,该方式通过对树与树之间结构的比较进行相似度的计算。
第三步,当我们对程序代码的语法树进行以代码块为单位切割之后会得到许多的语法树的分支,我们称每个分支为一个子树,每个子树对应一个算法知识。因为不同代码中可能相同的算法知识,而且他们的子树应该是十分相似的,为了统一表示这些相似的子树,我们提出用自组织映射图的聚类算法得到中心子树,每一棵中心子树都代表与其相似的子树。
第四步,在第三步中,我们得到了表示整个子树集合的中心子树,因此对于每个程序代码都可以被这组基所表示。我们提出用代码向量的方式表示每一个代码。
第五步,当得到所有代码的向量之后,我们运用叶分量分析的方法挖掘出所有的解题方法,并且通过叶向量得到解题方法的难易程度。
第六步,通过解题方法的难易程度,以及解题方法中包含的算法知识个数进行排序,得到适用于老师教学的教学序列。序列中的题目难易程度是递增的,而且针对每一道试题都有学生的主流解题方法。
为了将网络中的程序设计资源有效的组织起来,很多方法应用于这个领域。一种方法提出使用初级语言级知识点来表示程序设计中的算法知识,并且通过形式概念分析(FCA[2])的方法生成了教学序列[3],教学序列中的题目的难易程度是由简单到复杂。学生可以按照教学序列的题目顺序在网络中寻找题目进行训练。另一种方法是根据自定义的算法知识的结构[4],对网络中的题目进行划分,比如说排序相关的题目划分到统一个分类下方。这样学生可以根据分类中的知识点可以进行有针对性的训练。这两种方法都是基于预定义的专家库进行算法知识划分,但往往,针对预定义的知识库,我们很难事先去确定专家库中的算法知识的数量和类别,针对知识结构,我们还需要重新调整知识结构框架。这样就造成了诸多不便。
为了摆脱预定义知识库的困恼,一些方法提出根据神经计算的方法去有效的组织网络中大量的程序设计资源,其中有通过自组织映射图的聚类方法去挖掘主流解题方法[5],还有使用神经网络算法去识别程序资源[6]。虽然已经摆脱了预定义知识库的束缚,但是这类方法仅仅是通过神经网络算法聚类得到主流解题方法和识别算法知识,题目的难易程度也很难体现出来。
基于这些方法的缺陷,我们提出使用自主心智发育的方法使得机器能够自动的去组织散落在网络中的程序设计资源。该方法不需要预定义的专家库。
本文将按以下步骤展开:
第一步,我们介绍算法知识表示,因为程序代码作为高级语言,机器并不能自动的挖掘出存在于程序代码中的算法知识,因此我们通过一种知识表示方式-抽象语法树作为程序设计代码的知识表示。
第二步,当得到每个程序代码的知识表示之后,为了衡量每个程序代码的相似性,我们提出了两种衡量方法,一种是基于树大小的相似度计算,该方法以抽象语法树中树节点的数量进行比较。另一种是基于树结构相似度的计算方式,该方式通过对树与树之间结构的比较进行相似度的计算。
第三步,当我们对程序代码的语法树进行以代码块为单位切割之后会得到许多的语法树的分支,我们称每个分支为一个子树,每个子树对应一个算法知识。因为不同代码中可能相同的算法知识,而且他们的子树应该是十分相似的,为了统一表示这些相似的子树,我们提出用自组织映射图的聚类算法得到中心子树,每一棵中心子树都代表与其相似的子树。
第四步,在第三步中,我们得到了表示整个子树集合的中心子树,因此对于每个程序代码都可以被这组基所表示。我们提出用代码向量的方式表示每一个代码。
第五步,当得到所有代码的向量之后,我们运用叶分量分析的方法挖掘出所有的解题方法,并且通过叶向量得到解题方法的难易程度。
第六步,通过解题方法的难易程度,以及解题方法中包含的算法知识个数进行排序,得到适用于老师教学的教学序列。序列中的题目难易程度是递增的,而且针对每一道试题都有学生的主流解题方法。