算法设计类课程分层大案例库设计与构建方法研究

卢 玲，曾庆森

（重庆理工大学 计算机科学与工程学院，重庆 400050）

算法设计类课程分层大案例库设计与构建方法研究

卢 玲，曾庆森

（重庆理工大学 计算机科学与工程学院，重庆 400050）

分析算法设计类课程实践教学案例存在规模小、背景简化、数据形态单一、不利于观察算法的时空效率问题，提出以数据结构课程为对象，建立分层大案例库的研究目标，阐述大案例的特点并结合具体教学实践介绍大案例库的设计与构建方法。

算法设计；教学案例；数据形态；案例库

1 背 景

算法设计类课程包括程序设计基础、数据结构、算法分析与设计、面向对象程序设计等，是普通高校计算机各专业及部分信息类非计算机专业重要的专业基础课[1]。课程受众广泛，其受众关系如图1所示。从图1可见，数据结构、算法分析与设计课程由于具有逻辑性强、抽象性高[2]的特点，在课程体系中承上启下，是将学生的综合能力从实践向理论层面提升的重要环节。

图1 算法设计类课程及其受众关系图

目前，从计算科学的应用现状看，随着云计算等分布式计算平台的发展，数据规模不断扩大，以大数据为背景的数据分析、信息检索等应用已成为计算科学领域的重要热点。这类应用面向具有超大规模、异构、多源、多维特征的数据，其研究往往需要较强的理论基础和创新能力。这些具有大数据特征的现实问题，对学生的分析能力和研究创新能力提出了比以往任何工程项目都更高的新要求。在培养研究创新能力方面，算法设计类课程是重要的支撑。课程通过学习算法理论为学生的模型抽象能力[3]和创新能力的形成奠定基础。为使抽象的算法具体化、形象化[4]，课程往往设计实验案例并辅以课程设计等综合实践。从教学实践看，现有实验案例多以验证性、小型综合性实验为主。这些实验多对问题背景设置约束条件，将问题规模限制在一定范围之内。实验使用的测试数据不是真实数据，其数据规模小、数据结构单一。这使得学生常常对算法的应用场景产生疑惑，难以理解算法在真实环境中的适用性及效果。由于这一阶段的学生缺少工程实践经验，难以预期真实环境的数据规模及数据形态，对算法的时间、空间性能缺乏真实感受，使所学算法分析理论变成纸上谈兵，无法将基础算法规律化[5]，出现理论与实践脱节，学生虽学而不以为然的问题。

可见，传统教学中基于虚拟、小型、受约束数据的案例，逐渐与大数据背景下的工程实践问题脱节，成为制约分析和研究能力的瓶颈，是算法设计类课程面临的现实问题。在这样的背景下，我们以数据结构课程为研究对象，提出对课程的案例库进行梳理和更新，设计具有多种数据规模、多元数据形态的分层大案例库;并提出针对分层大案例库的多元考核体系，使大案例库的应用具有可行性和良好的可操作性。

2 分层大案例库结构设计

1）大案例及其特点。

我们把大案例定义为具有一定规模、一定逻辑结构、一定形态的数据处理实例。大案例中的“大”体现为数据规模、数据元素的形态是复杂的，意味着案例中将要处理数据的未知性，包括规模未知、形态未知、结构未知。其“一定规模”是指数据量小规模、数据量中规模、数据量大规模。“一定逻辑结构”是指数据具有线性、树形、图形结构。“一定形态”是指数据元素包括简单类型（整型、浮点型、字符型）、复杂类型（文本、图像、声音）。结合这3个“一定”对大案例进行定义和筛选，并将案例库进行组织及结构分层，由此得到如图2 所示的分层案例库逻辑结构。

如图2所示，大案例库是一个3维结构，具有“数据规模层次”“数据形态层次”“逻辑结构层次”3个维度。每个维度上分别按数据规模、数据形态、逻辑结构进行层次划分。可见，大案例库中的每一个案例是3维空间中的1个点，如图2所示的大案例k。

图2 分层大案例库示意图

2）大案例设计的重点。

大案例设计的重点在于突出数据处理实例中数据的不可预知性、不可观察性。以数据结构课程的“哈夫曼树及哈夫曼编码”为例，传统实验案例中，通常给定字符频度或分布（通常为整型或浮点型数据），要求学生基于给定的分布进行实验;在测试哈夫曼编码时，一般也以给定的文本为测试数据。这种案例设计限定了字符的范围和分布，限定了测试数据的规模。虽然这些限定简化了问题的复杂度，使学生能快速掌握算法原理，但从算法分析的角度，问题数据及其规模的简化使学生难以对真实数据形成认知。由于算法的时空指标及算法策略的优劣，只有在测试数据达到一定规模对计算机的存储形成压力时才能观察到，进而迫使学生考虑算法的适用性问题，主动寻求优化方案。简化的案例背景及数据使某些算法评估指标不易呈现，难以激励学生对算法优劣进行主动评价。实践中发现，大多数学生对算法优劣的理解源于书本知识，很少通过实验主动观察和体验到。由此，针对“哈夫曼编码问题”设计的大案例分为L1～L3三层，描述如下：

L1：给定训练文本，限定字符范围，包括大小写英文字符、常见标点符号（逗号，句号）。

L2：自行搜集训练文本（文本数＜1 000篇），手动整理字符，保留大小写英文字符、常用标点符号。

L3：自行搜集训练文本（文本数＞1 000篇），保留全部（多种）字符、多种标点符号。

在案例级别L3上，由于训练文本数扩大，字符范围未知，需要对哈夫曼树的存储设计进行可行性分析和论证。对所生成的哈夫曼编码，由于符号数量多，难以进行人工观测，只能通过编程计算哈夫曼编码与其他（如定长编码）编码的电文压缩比，由此促使学生为寻求合理的解决方案，运用多种技术对数据进行观察和分析，展开研究性学习。

3 大案例库构建的关键问题

如前所述，大案例处理的数据应具有一定的未知性和不可观测性。可将这种未知性分为3个维度：规模未知、形态未知、逻辑结构未知，基于此，建立大案例库需解决4个关键问题。

3.1 合理定义大案例数据的规模

可将大案例的数据规模定义为简化数据、中等规模数据、大（在现有实践条件之内）规模数据。实践中可分3阶段进行案例实施：

（1）STEP 1：简化数据。使算法快速实施;形成简化数据的测试报告;属于封闭答案的问题，其测试结果及算法策略是确定的。

（2）STEP 2：中等规模数据。例如将排序数据规模设置为5 000～5 000 000整数，要求进行多组数据规模、多种算法策略的测试，并以数据表的形式记录测试的时空开销，最终形成中等规模数据的测试报告;属于开放答案的问题，包括多样的测试结果及多种算法优化策略。

（3）STEP 3：大规模数据。例如将排序数据规模设置为5 000 000整数以上，对由此可能产生的存储异常及时间代价问题，要求采取合理的方法进行解决，最终形成大规模数据的测试报告;属于开放答案的问题，包括无解、多种测试结果及多种存储方式、多种算法优化策略。

由此可见，基于大案例展开的实践总是包含多数据规模、多种算法的测试。基于此进行对比分析形成分析报告，有助于学生主动发现和解决问题，对其研究能力形成有针对性的引导。

3.2 选取具有多种形态的数据

一般数据处理问题中的信息包括文本、图像、声音，这些信息的编码可能表现为整型、浮点型，在非数值计算方面的数据则具有更为复杂的表现形式，如计算机人机对弈中的一次棋盘状态。对此，可针对不同类型的数据设置案例，具体有：①文本类：包括中文、英文长文本（如新闻文本）、短文本（如网络评论性）文本;②图像和音频类：包括彩色、灰度、二值图像、各种音频信号等;③非数值计算类数据：如地图、棋盘等。

上述数据具有多样、规模各异且规模不确定的特点（如新闻文本的长度常常是无法预知的）。在进行案例设计时，可提供模拟（简化）数据、仿真数据、真实数据3类。其中，真实数据可从实际工程项目中获取，仿真数据可基于真实数据进行一定的人工调整和简化。由于仿真数据和真实数据具有规模大的特点，难以进行人工观测，将促使学生运用编程技术、算法设计方法，以寻求观测数据的最佳途径，从而形成启发式的主动学习。另外，还可要求学生自行进行数据采集和整理，从数据采集、整理方面，对学生进行训练。

3.3 选取具有多样逻辑结构的案例

在算法设计中，逻辑结构通常指数据元素具有线性、树形、图形的逻辑关系，在大案例库中应包含具有这几类逻辑结构的案例。当数据规模较小时，数据的逻辑结构是易于观测和判断的;在大案例中，由于数据规模增大，数据元素间的逻辑关系变得难以感知，无法进行主观臆测。这一方面要求学生借助经验进行分析，例如分析认为人机对弈的棋盘格局形成了树形结构;另一方面，也需要通过一定的策略对数据的逻辑结构进行学习和挖掘，例如对数值化的图形结构，发现其是有向关系还是无向关系等。通过这种分析，也可以促使主动学习模式的形成。

3.4 设计多元考核体系

分层大案例库具有丰富的层次性，形成多样化、有吸引力的实验内容，可激励学生展开主动学习。为便于进行自主学习，同时对教学产生实时反馈，有必要设计相应的评价机制，以保证大案例库应用的可行性和可操作性。针对案例库分层、多样的特点，评价体系也应是多层次、多元化的。另外，为能有效反馈教学，评价体系应是定量与定性评价相结合的多元系统，具有良好的可操作性。例如展开形式多样的测验，持续开展算法设计系列竞赛并以此作为评价指标等。同时也应结合定性评价，例如以项目小组的方式展开实验，进行团队协作能力、沟通能力等评价。

我们在教学实践中运用的评价指标，与传统实验差别最大之处在于实验报告环节。由于本科教学往往更注重应用能力培养，所以传统的实验报告多以描述实验过程和实验结论为主。大案例库的层次性及数据规模各异性，可能使实验结论也是各异的，这是展现学生分析能力的良好观测点。实践中，可启发学生综合运用图、表、伪代码等多种手段，观测实验结果，编写分析报告。对分析报告的质量，尤其是分析部分的内容进行重点评价，由此将学习的注意力从单纯追求实验结果转移到关注实验过程，为培养研究创新能力打下基础。

4 结 语

上述分层大案例库的设计及构建方法是结合数据结构课程的教学实践提出的，是在现有课程建设的基础上对实践教学环节的细化和深人求精。大型、综合型案例设计，与大数据背景下对研究型、创新性计算机本科人才培养的要求密切相关，是在计算机应用型人才培养与强化理论研究、鼓励思维创新有效结合方面进行的一次有益探索。将大案例库运用于我校计算机类各专业的数据结构课程教学，实践中取得了显著的效果。近3年来，我校计算机类本科学生广泛参与各类学科竞赛，如CCF中文信息评测、ASC国际大学生超算竞赛、中国大数据创新创业大赛等，参与学生面逐年扩大，这与教学中注重启发式、研究式的学习是密切相关的，从一定程度上验证了数据结构课程的教学效果。由于数据结构课程理论与实践兼备，具有其他算法类课程的普遍特征，因此分层大案例库的设计与构建对其他算法设计类课程也具有良好的借鉴意义。后续将在如何保证多种案例，尤其是较难大案例实施的有效性方面展开进一步的研究。

[1] 陈越, 何钦铭. 数据结构MOOC实践[J]. 中国大学教学, 2015(12): 46-50.

[2] 霍玲玲, 王智, 孙江. 数据结构教学方法的研究[J]. 计算机教育, 2015(2): 73-76.

[3] 陈欲强, 周国军, 吴庆军, 等. 非重点院校的数据结构课程教学改革[J]. 计算机教育, 2015(14): 52-55.

[4] 王丹, 付利华, 杜金莲. 算法分析与设计课程中的”三化一体”教学方法[J]. 计算机教育, 2016(7): 120-122.

[5] 代文征, 杨勇, 蒋文娟. 数据结构程序库建设[J]. 计算机教育, 2016(6): 70-71.

（编辑：郭田珍）

1672-5913(2017)01-0143-04

G642

2014重庆市研究生教育教学改革项目（yjg143011）；2015重庆理工大学高等教育教学改革研究项目（2015YB23）。

卢玲，女，副教授，研究方向为机器学习、信息检索、并行计算，ll@cqut．edu．cn。