网络环境下机器可联想算法知识表示发育模型研究

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 课题背景及意义
• 1.2 研究内容与解决方法
• 1.2.1 程序代码中算法知识的表示方式
• 1.2.2 算法知识表示模型
• 1.2.3 算法知识表示模型的自主发育
• 1.2.4 挖掘算法知识之间的联系
• 1.3 技术路线
• 1.3.1 从程序代码中提取算法知识实例
• 1.3.2 找出知识实例中的聚点
• 1.3.3 知识实例的向量表示
• 1.3.4 算法知识表示的自主发育
• 1.3.5 算法知识的联系
• 1.4 论文的组织结构
• 1.5 本章小结
• 第2章 算法知识表示
• 2.1 引言
• 2.2 算法知识表示方式
• 2.2.1 抽象语法树简介
• 2.2.2 语法树的生成
• 2.2.3 算法知识表示方式
• 2.3 本章小结
• 第3章 算法知识的度量
• 3.1 引言
• 3.2 树大小相似度
• 3.3 树结构相似度
• 3.3.1 编辑距离
• 3.3.2 树编辑距离
• 3.3.3 树结构相似度
• 3.4 本章小结
• 第4章 自组织映射图
• 4.1 引言
• 4.2 自组织映射图
• 4.2.1 自组织映射图简介
• 4.2.2 基于树大小相似度的SOM
• 4.2.3 基于树结构相似度的SOM
• 4.3 本章小结
• 第5章 算法知识表示发育模型研究
• 5.1 引言
• 5.2 代码向量
• 5.3 叶分量分析方法
• 5.4 算法知识表示发育模型
• 5.5 本章小结
• 第6章 算法知识表示模型之间的联系
• 6.1 引言
• 6.2 算法知识表示模型之间的联系
• 6.3 向量的基本操作
• 6.4 主流方法
• 6.5 教学序列
• 6.6 本章小结
• 第7章 实验及结果
• 7.1 实验前言
• 7.2 基于大小相似度的自组织映射图实验
• 7.3 基于树结构相似度的自组织映射图实验
• 7.4 算法知识表示发育模型研究实验
• 7.5 教学序列的生成
• 7.6 实验原型系统
• 7.7 实验的不足
• 7.8 本章小结
• 第8章 结束语
• 8.1 研究工作总结
• 8.2 研究贡献与创新
• 8.3 未来工作与展望
• 参考文献
• 攻读学位期间的研究成果目录
• 致谢