实验和实习指导

 

[实习平台]  [实习设计思想]  [实习效果]  [实习题例]

 “数据结构与算法”是问题求解的基础,主要体现经典的知识体系,培养学生问题分析、问题的数学模型建立和问题的逻辑模型建立能力,即分析问题的能力。对于经典数据结构和算法的实习,采用ACM/ICPCACM程序竞赛)在线提交评测系统(POJ,由北京大学李文新教授主持开发),并采用该系统进行算法能力测试实地测试。

针对计算机类的学生,单独设立“数据结构与算法实习”课程,注重数据结构与算法的经典知识体系与计算机科学技术的现代前沿研究课题相结合。强化培养学生问题求解模块的框架设计和详细设计、相关程序实现和调试能力,即实际动手能力。在综合实践训练环节,选取来自于计算机科学技术的现代前沿研究课题,例如编译栈、 Edlin 文本编辑器、 XML DOM 树解析器、外排序、散列字典、搜索引擎等等,建立了综合实习题(含参考解答)题库,对学生进行工业强度的综合训练。

经典课程内容与现代学科前沿有效结合的教学改革措施,培养了学生扎实的理论基础,帮助学生灵活地运用问题抽象、数据抽象、算法抽象来分析问题,应用数据结构和算法来设计和实现相应的程序,完成创新能力和实践能力的训练。


请点击上图观看演示视频

《数据结构与算法实习》网站

http://www.jpk.pku.edu.cn/
pkujpk/course/sjjg/shixi/

采用ACM/ICPC程序竞赛题库POJ系统(北京大学信息学院李文新教授主持开发)进行经典算法和验证型、小规模设计型实习训练。设计与学科前沿研究相结合的综合实习大项目进行设计型和综合型实践训练,同时也丰富了ACM/ICPC程序竞赛题库。作业题和实习题融合当前最新理论和技术,非常有前瞻性,学生受到创新思维能力训练、工程能力训练。
http://acm.pku.edu.cn/

1.实习课程设计思想[返回顶部]

着眼于数据结构原理和应用的结合点,引导学生应用书本知识解决实际问题,提高学生的实际动手能力和团队合作能力。通过动手实验,使得课程的涉及的数据结构理论、存储技术、算法技术变得“鲜活”起来,起到深化理解和灵活掌握教学内容的目的。

设计了验证型、综合型、设计型的实验,力求提高学生的动手能力,做到理论和实践相结合。使学生在实验过程中进一步掌握典型数据结构的逻辑结构、存储结构及算法的程序实现,并训练学生分析问题的能力和编程解决问题的能力。

2.实习课程设计效果[返回顶部]

经过多年的建设,形成了精巧而具前瞻性的实习题库。

从企业合作项目和学科前沿研究中提炼大规模的设计和综合型实习题,满足线性表、字符串、二叉树/树、图、排序、索引、检索等数据结构综合训练需求;ACM/ICPC实习题涵盖图搜索、枚举、贪心、递归分治、动态规划等经典算法练习。

对培养学生分析和解决问题、创造性思考和团队合作的能力起到了很好的作用,为学生学习后续课程,将来进行科学研究、工作创业等,打下了厚实的基础。实习课程受到学生尤其是毕业生的广泛好评。

3.实习题例[返回顶部]

配合“数据结构与算法”进行问题求解能力训练,注重实践能力和工程能力的培养,使得学生遵从软件开发的规范性。以项目驱动,从软件工程的角度对学生系统地进行需求分析、数学建模、数据结构与算法设计、程序实现测试调试、文档编写训练。不仅要求进行简单的实现,更要求进行工程实现的设计。学生不仅仅能完成自己承担的开发任务,还能从系统级认识整个项目,积累重大项目的组合、合作协调经验,培养项目组织和管理能力,能够创造性地解决工程中遇到的问题。

通过典型案例教学,引导学生深入思考,激发创新思想火花,充分调动学生学习的主动性,实现教与学的互动。学生从案例中进行研究型学习,并在学习过程中主动运用所学知识来分析问题、解决问题,根据问题的需求来主动获取新知识,从而强化创新意识和创新能力,相应地提高理论联系实际能力、实践动手能力和科研能力。

“数据结构与算法实习”是针对计算机和智能专业学生开设的,强化计算机类学生的实践能力训练。对于电子微电子的学生,只需要掌握“数据结构与算法”理论课程所介绍的基本数据结构和算法,编写简单的小程序。

序号

课堂教学

学时

知识点内容摘要

1

简介

2小时

数据结构与算法实习简介、C/C++基本程序技巧、界面排错和测试、问题空间和典型的算法思路、基本数学建模

2

设计风格

2小时

程序的良好风格、程序设计和实现技巧

3

对象技术

2小时

面向对象技术、STL的基本概念和常用容器

4

界面技术

2小时

人机界面基本原则、排错的技巧

5

测试

2小时

测试、性能、可扩展性

6

项目管理

2小时

项目需求分析、项目开发计划、软件项目的实施(控制)

7

基本算法与枚举法

2小时

问题状态空间的建立、枚举的原则

教学案例:百钱百鸡、猴子分桃、宴会彩灯、质数方阵

8

回溯法

2小时

递归强化、搜索解空间、DFSBFS搜索、分枝限定原理

教学案例:八皇后,0-1背包,火车进出栈

9

贪心法

2小时

最优子结构分解、最优解的正确性证明

教学案例:活动安排、可分割背包、区间覆盖

10

分治法

2小时

--的分治法原理、算法复杂性问题

教学案例:统计逆序对、导线与开关、二进制大整数乘法

11

动态规划

2小时

最优子结构和重复子问题、备忘录方法、各种算法的比较

教学案例:最优二叉搜索树、最长子序列、邮局问题

12

问题建模

2小时

问题建模专题讨论、数学模型

13

图的应用

2小时

图模型的建立、图的有效搜索、回溯高级技巧

14

数据结构综合应用

2小时

搜索引擎和数据库等应用系统中的线性表、字符串、图等基本数据结构;散列、索引和排序等数据结构技术的综合应用

15

习题讨论

4小时

对课程综合习题进行交流讨论,习题讲评

下面是选自POJ系统的部分ACM/ICPC实习题,这些题目主要体现了经典数据结构与算法的技术实践内容,培养学生算法和程序设计的基本实践能力。根据学生程度,在以下的POJ在线测试题目中,选择6-8道题目,覆盖经典数据结构与算法,总实习时间控制在30-50小时。

POJ实习

学时

题目网址

参考解答

二叉树

4小时

http://acm.pku.edu.cn/JudgeOnline/problem?id=1240

http://acm.pku.edu.cn/JudgeOnline/problem?id=1463

1240解答

1463解答

8小时

http://acm.pku.edu.cn/JudgeOnline/problem?id=1158
http://acm.pku.edu.cn/JudgeOnline/problem?id=1376

1158解答

1376解答

排序

4小时

http://acm.pku.edu.cn/JudgeOnline/problem?id=2377

http://acm.pku.edu.cn/JudgeOnline/problem?id=1694  

2377解答

1694解答

穷举法

4小时

http://acm.pku.edu.cn/JudgeOnline/problem?id=2179

http://acm.pku.edu.cn/JudgeOnline/problem?id=1411

2179解答

1411解答

回溯法

8小时

http://acm.pku.edu.cn/JudgeOnline/problem?id=2438

http://acm.pku.edu.cn/JudgeOnline/problem?id=1020

2438解答

1020解答

贪心法

4小时

http://acm.pku.edu.cn/JudgeOnline/problem?id=1716

http://acm.pku.edu.cn/JudgeOnline/problem?id=2092

1716解答

2092解答

分治法

8小时

http://acm.pku.edu.cn/JudgeOnline/problem?id=2104
http://acm.pku.edu.cn/JudgeOnline/problem?id=2084

2104解答

2084解答

动态规划

8小时

http://acm.pku.edu.cn/JudgeOnline/problem?id=1080
http://acm.pku.edu.cn/JudgeOnline/problem?id=1404

1080解答

1404解答

下面是部分综合实习样题,都需要学生查找大量的文献,具有很好的探索性。例如,XML文档DOM树处理、文本文件的搜索引擎等,受到学生的欢迎,有效地培养了学生的创新和科研能力。教员可以根据学生程度,选择3-4道题目,总实习时间控制在40-70小时。

综合实习

学时

题目网址

参考解答

字符串练习

10小时

http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/report/HWTest/2007Proj/P1_Edline/P1.doc

字符串解答

 

XML文档DOM树处理

20小时

http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/report/HWTest/2007Proj/P2_XMTree/P2.doc

XML解答

 

背包问题

8小时

http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/report/HWTest/2006Proj/P1_Knap/P1.doc

背包问题解答

 

并查集与等价类

10小时

http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/report/HWTest/2006Proj/P2_EqClass/P2.doc

等价类解答

 

基于字典的综合应用

20小时

http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/report/HWTest/2006Proj/P3_Dic/P3.doc

字典应用解答

 

文本文件的搜索引擎

30小时

http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/report/HWTest/2007Proj/P3_Index/P3.doc

倒排文件解答

 

除上述题目外,鼓励优秀学生和本科生科研基金项目学生自己组队选题。以合作学习的“文献调研—开题—项目分析—项目设计—成果汇报—总结评价”模式为主线,以学生自主探究和开发活动为主体,以教师点拨为主导,以培养学生学习的兴趣和能力为中心。强化创新意识和创新能力,相应地提高理论联系实际能力、实践动手能力和科研能力,也提高了学生的学习和研究积极性,优化实践教学的效果。

鼓励实验班的学生组队选择自己擅长的专题,给“数据结构与算法实习课”的计算机类学生作15分钟的讲座。很多学生非常重视这个走上讲台亲自拿起话筒的锻炼交流机会。从初期的收集资料,总结分析,以及演讲稿的准备,都让学生的独立思考能力、语言组织以及表达能力有了非常大的提高,也充分调动了其他很多同学的学习和研究的积极性。在下面网页的“数据结构与算法实习”讲义中提供了9组学生的交流讲稿:http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/report/frame/couseware.html

在实习课上,同学们把理论课上的很多算法得以实现,在助教的组织下,交流各种不同类型的解题方案,并且进行深入的数据结构和算法时间、空间效率讨论,达到了理论与实践水平共同提高目的。上述经典ACM/ICPC数据结构与算法实习题和综合探索实习题的参考解答如下:

http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/report/HWTest/2006index.htm

http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/report/HWTest/2007index.htm