知识图谱程序设计训练系统的设计与开发

浙江万里学院大数据与软件工程学院 朱梦涵 陈斌格 柴本成

程序设计是一个对于待定问题提出解决方案的过程，是软件构造活动中的重要组成部分。其通常以某种程序设计语言为工具，给出这种语言下的一定程序。而程序设计的过程包含有分析、设计、编码、测试、操作等不同的阶段，对程序设计者进行多方面的要求。在与计算机相关的课程学习中，程序设计扎根于每一种课程的学习之中，不仅占据举足轻重的地位，更起到了思维训练的效果。

1 程序设计的特点

程序设计的过程同其他设计活动一样，都是在各种约束条件和需要之间寻找一种平衡，以实现在客观条件允许的范围内解决问题。一般而言，因为早期对于机器资源的限制，我们对程序要求往往侧重于时间和空间代价这两个方面。而随着硬件技术的飞速发展和软件规模的日益庞大，程序的结构性、可维护性、复用性、可拓展性等因素日益重要，对于程序设计多方面的需求推动着其快速发展。

程序设计的过程一般要求设计者拥有以下能力（1）分析问题：对于接受的课题能够做出合理的分析，找出问题的本质规律并选择合适的解决方法。（2）设计算法：设计出合适的解题方法与具体步骤，在时间复杂度和空间复杂度上能够适应待定问题的客观条件。（3）编写程序：使用某种程序设计语言，完成源程序的编辑、编译。（4）运行结果，分析结果：对于可执行的程序，能够对于其运行结果进行分析，判断其是否符合要求，并对于程序中的故障进行调试处理。在此之上，一般将程序设计的方法分为三种方法：面向过程、面向对象、面向切面，要求程序设计者能够对于不同的生成环境选择合适的生成方法解决问题。程序设计的过程是一个自由度高、综合性强的逐步推进型过程，因此其对于学习者而言往往需要掌握大量的算法知识，具有较高的分析、编程能力，才能较好地实现一个设计过程。因此，对于一个程序设计的学习者而言，程序设计过程的不断训练，成为其拓展能力的直接渠道。

2 程序设计训练的问题

问题的局限性，程序设计的过程离不开问题的先一步提出，只有对于特定的问题进行分析之后，我们才能针对问题提出相对的解题方法。出于训练的目的性，对于问题的构造往往离不开涉及该问题的知识点以及出题人的主观性，由于出题人的主观性，问题的设置以及知识点的运用通常局限于出题人的理解范畴，这往往会导致学习者的片面认识，无论是对于知识点的理解还是知识点的拓展运用，都会有局限性。除此之外，因学习平台的多样化，经典问题往往较为分散，在缺乏有效整合的情况下，学习者往往被问题的重复性与局限性所困扰，缺乏高效刷题学习的方法。

知识点的拓展性受限，算法与数据结构是程序设计过程中的灵魂，只有掌握一定的算法与数据结构知识，才能对于特定的问题构造更加合理、有效的解决方案，这是程序设计过程之中的共性认识。而算法与数据结构的认知过程除了局限于教材的教学内容限制之外，还缺少大范围内对于算法与数据结构的网状联系构架。简单的可以认知为，知识点与知识点之间的联系性松散，当局部知识点的学习结束后，因为没有强联系网络的搭建，缺乏高效的学习拓展手段。

代码设计过程的枯燥性，代码是实现程序的基本手段，因此也是程序设计者最基本的能力之一，熟练的代码设计技巧往往逃不开长时间的训练与学习，我们往往强调通过增加学习者的程序设计次数与代码设计长度来提高学习者的代码设计能力，但这个过程往往伴随着长时间的书写与调试，容易对学习者造成消极影响，打击学习者的积极性，是学习兴趣低迷，直至最后丧失信心。因此问题的趣味性、学习过程的合理性、书写技巧的训练都至关重要，我们需要通过适当的方法，训练学习者的代码能力。

综上所述，程序设计的过程中，问题、知识点、代码设计过程三个方面的问题，严重制约并影响了学习过程中的效率。如何提高问题与问题、问题与知识点等方面的联系性，剪除由客观事物所造成的局限性、重复性等内容；如何更好地帮助学习者构建知识网络，进行高效的学习与拓展，成为了更好地进行程序设计训练的基本问题。

3 以程序设计为中心的知识图谱

程序设计的训练过程中，主要是算法与数据结构知识点的学习与特定题目的解答过程两部分构成，在两者相互作用的过程中，起到锻炼思维能力、代码能力的作用。通常我们将算法与数据结构中的内容进行拆分，进行一个循序渐进的过程性学习以掌握部分内容，其大致可以划分为基础算法（枚举、模拟、递归、分治、贪心、前缀和、差分、二分、倍增、构造），搜索、动态规划、字符串、数学、图论、计算几何、数据结构、图论等内容。除了其中硬性的算法与数据结构知识之外，还有部分需要发散思维的思考技巧即一定的思维能力，这些内容共同构建了程序设计所涉及到的算法知识点，这些知识点之间存在着相关性。可以理解为知识点与知识点之间存在着前置内容、组合内容等相关关系。例如：差分技巧常用于树上公共祖先的权值处理之中，DFS序、线段树、轻重链等算法与概念则成为了成功树链剖分这一算法知识点得到前置内容。由此我们可以发现，建立客观可见的知识图谱网络，有助于学习者理解知识点与知识点之间最本质的联系，大大地提升了知识之间的拓展性与学习的高效性。

知识图谱的网状构造对于前置内容的设置起到的极大的推动作用，但对于组合内容的设置体现并不直观，组合内容的使用更多的是在于对于特定问题模型的多方面处理之中，通过解决问题这一过程能过更好地实现对于组合内容的认知。例如：GRE官方指南中的GRE Words就运用到了AC自动机、Fail树、线段树、DFS序、动态规划等内容，进行了多方面的维护操作实现了程序设计。将问题加入网状结构有助于深化知识图谱中各种知识点的组合联系，通过学习者对于问题解决方法的进步，解决问题数量的增加，形成用于判断学习者知识体系掌握情况的依据，进而进一步构架专属于学习者个人的知识网络。

而这一套理论能够建立的前提就是知识图谱构架的知识网络能够在充分维护问题与知识点联系的同时，恰如其分地体现学习者个人的学习情况，这对于判断依据提出了更加严格的要求。此处提出以问题涵盖知识点作为范围判断标准，以问题难度赋予一定的权值作为水平判断标准，再加上一定的前置知识点要求，设置一个带权的知识图谱机制，以实现知识点学习掌握进度的逐步推进与学习者个人知识网络的构架，如图1所示。

图1 问题和知识点架构的知识图谱结构

由相关关系的问题作为判断回馈机制，前置关系为约束的知识图谱构架，能较好地表述学习者的知识网络。

4 训练系统的拓展性质

以学习者程序设计训练的目的性进行拓展，进一步加强对于学习者的服务且调动学习者的训练积极性，达到拓展系统功能与强化学习的重要目的。

程序设计学习者的基本目的主要区分为学业性学习、竞赛性学习与就业性学习，三者在程序设计训练方向的侧重性是不同的，应针对不同的学习方向，提供精确性的向导功能，使学习者的知识网络具有偏重性。对于学业性学习而言，结合相对应的课程内容知识点，达到专题性的训练即可；对于竞赛性学习而言，除了强化赛事相对知识点相关学习之外，还要对赛事信息进行一定程度的整合，方便学习者了解相关内容；对于就业性学习而言，除了相同的强化就业相关知识点之外，还要有就业信息的整合和当前行业的动态信息。

综上所述，拓展性质的本质是实现局部知识点的强化以及更高程度的信息整合，强化对于学习者的服务功能，其实用性很大程度取决于知识图谱内容相关性的设置与信息整合程度的高低。考虑强化知识图谱的构架，引入以程序设计相关数据、程序设计相关竞赛（蓝桥杯、ICPC、CCPC）、互联网公司（哔哩哔哩、腾讯、网易）等内容的相关信息，加强其与知识点以及问题之间的关联性，方便用户对学习方向做出选择并得到侧重性强的学习过程。对于知识图谱网络的进一步构架，如图2所示。

图2 拓展偏向性后的知识图谱结构

5 训练系统的构建过程

基于上述的知识图谱构建，本团队以“竞赛偏向的训练系统”为例，构建了一个知识图谱实例。基于搭建实例的基础性，我们尝试手工构建简单的知识图谱构架。主要从准备工作、主体搭建、成果检验三个方面进行阐述。

5.1 搭建知识图谱的前期准备工作

该工作主要涉及的内容有相关知识素材的收集与整合、开发平台的选择与存储方式的选择等。基于课程学习的内容，我们选择基于.NET Framework的Web平台的脚本语言ASP+，其参照Java、VB语言的开发优势加入许多新的特色，同时也修正以前ASP版本的运行错误等故障。而知识图谱的存储方式则采用了基于SQL Server数据库下的sql文件，并且使用Python组合作为信息收集工具，用于实现多方面的信息采集工作。在关于相关知识点的收集工作中，我们参考了经典的知识整合站点OI Wiki对于竞赛知识的整理归类方式，而赛事内容的获取，则参考了相对热门的codeforces、牛客等站点的训练获取。

5.2 知识图谱主题内容搭建

其主题内容的构建主要包含两个方面：知识点其属性与知识点与知识点之间的关系构架、问题与知识点的相关性以及权值配比。在知识点的梳理中，主要划分为了语言基础、算法基础、搜素、动态规划、字符串、数学、数据结构、图论、计算几何等9块内容，其中包含了前置关系这一条件，构架知识点与知识点之间的联系。而问题零散且广泛，大致可以以难度与知识相关性进行梳理，其与知识点之间构建相关性的逻辑关系。引入竞赛信息相关构架与知识点和问题之间的需求关系。在此，我们梳理了前置关系、相关关系、需求关系三块内容。

5.3 知识图谱的检验与评价

在知识图谱基础构建完成之后，需要对其的适用性与正确性进行评估，保证知识图谱的质量。其检验过程一般包含有语义一致性检验和用户自定义的一致性检验。在该知识图谱的构架中，只含有“问题”、“知识点”、“竞赛信息”三个概念，其概念之间的关系比较明确，其一致性上基本上不会产生问题。而为了避免用户自定义产生的逻辑矛盾，会对于环形前置关系进行topo判断，并采用向用户提出声明的方式辅助用户进行规避。

6 训练系统中的知识图谱应用

基于知识图谱构架的训练系统最本质的特点即为不同学习者能根据自己的学习方向和学习进度获取不同的知识网络构建，以便于学习者能根据自身情况得到不同的推荐学习内容。具体表现可以理解为，在同一个页面不同的学习者能够看到不同的学习内容，做到最大程度地适应学习者的学习情况，进一步找到最合适的强化学习途径。而其知识图谱对于学习者的引导主要分为下述两个方面。

6.1 指向性地为学习者提供呈现内容，支持学习者进行开拓式学习

系统会根据知识图谱的构架与用户当前的学习情况相结合，构架出学习者个人的网状知识构架，为其确定已掌握内容、推荐掌握内容、未掌握内容三块知识点构架。如K1和K2为K3的前置知识点，那么对于学习者而言，当K1和K2的评价达到掌握的程度之后，K3才会进入推荐掌握板块。对于三块内容的抉择上，已掌握内容的信息推荐上，采取巩固加深的思路，采取难度更高的问题进入学习者的学习范围，并给出相应的拓展性知识强化学习；而推荐掌握内容则以已掌握内容中知识点作为前置知识的知识点为主，主要推荐相对入门的问题以及经典问题，辅助学习者进行新知识点的学习与入门；最后对于未掌握内容则简单实行简单的从易到难排序机制，主要偏向于让学习者了解这一快内容的存在，加强学习者对于知识范畴系统性的认知。

6.2 在指向性提供内容呈现的同时，对于问题等学习资源进一步的进行细化处理

我们以学习者当前在该知识点所得到的权值和作为评判学习资源提供方式的标准：①首先以经典问题作为主要推荐方向，经典问题的学习有助于学习者对于当前知识点的本质理解，在学习途径中起到至关重要的地位。②以当前的权值和作为评价标准，设计相应的分值台阶，如S1，S2，S3，S4，S5五个评价等级，根据不同的等级推荐不同难度的题目用于强化训练，低等级的题目并不做舍弃处理，而是将优先级下降。通过较为简单且有效的二级排序方式，我们可以基本地建立一个相对合理的学习过程。

以上的论述中，本课题的知识图谱以较为简单的关系模式，建立了行之有效的推荐学习和强化学习机制，为学习者的训练学习过程提供了极大的自动性，并且具有较高的学习效率。

当前而言，通过知识图谱构建，采用适应性学习机制的训练系统，不失为一种有效的学习途径。但是，该训练系统的泛化行不强、长期使用的合理性验证不足，模型的优化有待加强等问题并没有得到有效解决。本研究只是建立并确定了一个较为合理的知识图谱的逻辑结构，一定程度上实验了知识图谱对于学习训练方式的促进作用。

研究团队将会围绕该课题的知识图谱进行深入的研究，着力于泛化知识图谱构架模型，进一步实现知识图谱对于学习过程的辅助效果。