北大“数据结构与算法”实习教学大纲

“数据结构与算法”实习教学大纲对计算机和智能这两个计算机类专业的课程要求高于电子微电子的课程要求，单独设立实习课程，在同一个学期讲授。加强上机实践，强化算法能力，以及软件工程规范的训练。与理论课形成更好的互补。数据结构与算法实习配合“数据结构与算法”理论课程的学习，介绍一些程序风格、设计、测试和排错等软件工程的基本知识和方法；通过一些趣味例题，系统地介绍“数据结构与算法”理论课程涉及到的算法基本思想；灵活应用基本数据结构，并结合排序、检索、文件、索引等技术，合作编写比较综合的大型应用程，提高学生的实际动手能力。通过该课程的学习，为后续的专业基础课和专业课程打下坚实的实践能力和问题求解基础。1．课程基本情况学院设定课程编号048305170课程名称数据结构与算法实习PracticeofDataStructuresandAlgorithms开课时间一年级二年级三年级四年级秋春夏秋春夏秋春夏秋春夏适用院系计算机系和智能系课程定位专业必修学分2学分总学时32+80(理论+上机实习)先修课程数据结构与算法A后续课程算法分析与设计，程序设计语言原理教师设定教学方式理论与实践结合课时分配理论32学时：教员课堂讲授26小时，学生编程经验交流6小时学生独立实践80学时：数据结构与算法实验50小时，综合上机实习30小时考核方式平时20%，算法实验20%，综合上机题40%，期末考试20%。主要教材1.张铭、赵海燕、王腾蛟，《数据结构与算法习题指导》，高等教育出版社，2005年8月。参考资料2.张铭、王腾蛟、赵海燕，《数据结构与算法》，高等教育出版社，2008年6月。3.许卓群、杨冬青、唐世渭、张铭，《数据结构与算法》，高等教育出版社，2004年7月。4.ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein,InroductiontoAlgorithms,MITPress,2ndedition,2001.高等教育出版社影印。5.M.H.Alsuwaiyel,AlgorithmsDesignTechniquesandAnalysis,电子工业出版社影印，2003年1月。6.B.Kernighan&R.Pike,ThePracticeofProgramming,Addison-Wesley,1999.(中译本：《程序设计实践》，裘宗燕译，机械工业出版社，2000年8月其它信息同修课程：数据结构与算法A2．教学目的和要求配合“数据结构与算法”理论课程的学习，介绍一些程序风格、设计、测试和排错等软件工程的基本知识和方法；通过一些趣味例题，系统地介绍“数据结构与算法”理论课程涉及到的穷举法、回溯法、贪心法、分治法、动态规划等算法基本思想；介绍图和问题建模、数据结构与算法的应用和实践。培养学生独立地实现常用基本数据结构的ADT以及相应的STL数据结构，解决一些实际问题，独立编写中小型应用程序。灵活应用基本数据结构，并结合排序、检索、文件、索引等技术，合作编写比较综合的大型应用程，提高学生的实际动手能力。通过本课程的学习，为后续的专业基础课和专业课程打下坚实的基础。3．课程特色把《数据结构与算法实习》作为辅助《数据结构与算法》的计算机系和智能系学生必修课，强化了计算机类学生的实践能力训练。实习课内容划分为C/C++基本程序技巧训练、界面排错和测试、基本数据结构训练、基本算法、数学建模训练5个模块。从问题求解的角度，培养学生数据结构理论基础、问题抽象和算法抽象、数据结构与算法设计的能力。在培养基本问题求解能力的同时，注重实践能力和工程能力的培养，使得学生遵从软件开发的规范性。以项目驱动，从软件工程的角度对学生系统地进行需求分析、数学建模、数据结构与算法设计、程序实现测试调试、文档编写训练。不仅要求进行简单的实现，更要求进行工程实现的设计。学生不仅仅能完成自己承担的开发任务，还能从系统级认识整个项目，积累重大项目的组合、合作协调经验，培养项目组织和管理能力，创造性地解决工程中遇到的问题。通过典型案例教学，引导学生深入思考，激发创新思想火花，充分调动学生学习的主动性，实现教与学的互动。学生从案例中进行研究型学习，并在研究性学习过程中主动运用所学知识来分析问题、解决问题，根据问题的需求来主动获取新知识，从而强化创新意识和创新能力，相应地提高理论联系实际能力、实践动手能力和科研能力。4．课程内容摘要和知识点章节课时内容摘要和知识点重要性1简介2数据结构与算法实习简介C/C++基本程序技巧界面排错和测试问题空间和典型的算法思想数学建模基本思想难度▃▄▅重要性★★★★★2程序设计风格2程序的良好风格程序设计和实现技巧难度▃▄▅重要性★★★★3面向对象技术2面向对象技术STL的基本概念和常用容器难度▃▄▅重要性★★★4界面技术2人机界面基本原则排错的技巧难度▃▄▅▆重要性★★★★5测试2测试性能可扩展性难度▃▄▅▆重要性★★★★6项目管理2项目需求分析项目开发计划软件项目的实施（控制）难度▃▄▅重要性★★★7基本算法与枚举法2问题状态空间的建立枚举的思想例题：百钱百鸡、猴子分桃、宴会彩灯、质数方阵难度▃▄▅▆重要性★★★★8回溯法2递归思想强化搜索解空间的思想DFS和BFS搜索策略，分枝限定思想例题：八皇后，0-1背包，火车进出栈难度▃▄▅▆▇重要性★★★★★9贪心法2最优子结构分解最优解的正确性证明例题：活动安排、可分割背包、区间覆盖难度▃▄▅重要性★★★★10分治法2“分-治-合”的分治法原理思想算法复杂性问题例题：统计逆序对、导线与开关、二进制大整数乘法难度▃▄▅▆重要性★★★★★11动态规划2最优子结构和重复子问题，备忘录方法各种算法的比较例题：最优二叉搜索树、最长子序列、邮局问题、最大全1正方形难度▃▄▅▆▇重要性★★★★★12问题建模2问题建模专题讨论数学模型难度▃▄▅▆重要性★★★★13图的应用2图模型的建立图的有效搜索回溯高级技巧难度▃▄▅▆▇重要性★★★★14数据结构综合应用2搜索引擎和数据库等应用系统中的线性表、字符串、图等基本数据结构散列、索引和排序技术的应用难度▃▄▅▆▇重要性★★★★15习题讨论4对课程综合习题进行交流讨论，习题讲评难度▃▄▅▆▇重要性★★★★★