程序设计训练教学大纲.doc

程序设计训练教学大纲一、课程名称：程序设计综合训练Advanced Training for Programming Design二、学时与学分学时： 4年 学分：1三、授课对象计算机及相关专业大1到大4的本科生。四、先修课程数据结构、离散数学、C/C+、java程序设计、具体数学、组合数学、计算几何、数论、算法设计与分析五、后续课程本课程无直接后续课程，但它是所有计算机专业本科毕业生工作、科研的基础六、教学目的本课程设计是计算机各专业的学生编程能力的一个综合培养和测试，目的是使学生掌握必须的计算机算法的基本知识与基本技能，培养学生的分析问题、解决问题能力和计算机算法设计与分析方面的技巧，提高学生数学思维方式和程序设计方面的能力，为以后的工作打下良好的基础。七、主要内容、基本要求、上机（实验）要求及学时分配主要内容：1 基本算法实训1.1 递归算法：最常用的算法设计思想，主要介绍递归算法的设计思想和实现技巧 1.2 分治法： 主要介绍分而制之的算法思想；1.3 模拟法：主要介绍模拟算法求解的基本问题；1.4 贪心算法：主要介绍采用贪心策略的算法设计； 1.5 状态空间搜索法：主要介绍回溯法、分支定界法等； 1.6 随机算法：利用随机选择自适应地决定优先搜索的方向； 1.7 动态规划：主要介绍动态规划的基本思想、设计模式等。2 计算几何算法实训2.1 基本概念：矢量的概念、矢量加减法、矢量叉积；2.2 点、线、面的关系判定：折线段的拐向判断、判断点是否在线段上、判断两线段是否相交、判断线段和直线是否相交、判断矩形是否包含点、判断线段、折线、多边形是否在矩形中、判断矩形是否在矩形中、判断圆是否在矩形中、判断点是否在多边形中、判断线段是否在多边形内、判断折线是否在多边形内、判断多边形是否在多边形内、判断矩形是否在多边形内、判断圆是否在多边形内、判断点是否在圆内、判断线段、折线、矩形、多边形是否在圆内、判断圆是否在圆内；2.3 点、线、面的距离计算：计算点到线段的最近点、计算点到折线、矩形、多边形的最近点、计算点到圆的最近距离及交点坐标、计算两条共线的线段的交点、计算线段或直线与线段的交点、求线段或直线与折线、矩形、多边形的交点、求线段或直线与圆的交点2.4 凸包及其相关算法：凸包的概念、凸包的求法3 数据结构相关内容实训3.1 并查集3.2 堆、栈、树、网络；3.3 排序算法3.4 查找与匹配算法；4 数论相关算法4.1 数论的基本知识：介绍了数论的基本概念，例如可除性、模等价和唯一因子分解等。 4.2 最大公约数、模运算；4.3 求解模线性方程： 讨论了一个已知数a的倍数模n所得到的集合，并说明如何利用欧儿里德算法来求出方程ax=b(modn)的所有解；4.4 中国余数定理：阐述了中国余数定理和一些应用；4.5 元素的幂；4.6 RSA公开密钥加密系统；4.7 素数的测试：主要讨论了随机性素数测试，它可以用于有效地找出大素数；4.8 整数的因子分解：介绍了一种把小整数分解因子的简单而有效的启发性方法。5 图论的相关算法实训5.1 图论算法 5.2 图的遍历 5.3 图的连通性 5.4 最小生成树5.5 单源点最短路径5.6 所有点对最短路径6 组合数学算法实训6.1 排列与组合基本概念、分拆与置换的表示、排列与组合的生成算法、购票问题、“方程的解”问题习题；6.2 容斥原理基本概念、“被毁坏的玉米地”问题问题；6.3 母函数、普通型母函数、指数型母函数、质数分解问题、“红色病毒”问题、“自共轭Ferrers图”问题、常见组合计数方法；6.4 拟阵基本概念、拟阵的基本性质、拟阵与贪心算法；6.5 Plya定理、群与置换群、Burnside引理。7 其他算法7.1 最优化算法7.2 快速傅立叶变换7.3 基本要求：7.4 通过程序设计训练课的练习，使学生掌握基本的编程技巧，为后续工作和研究打下良好编程基础。上机（实验）要求：基本算法实训：熟悉基本算法设计的思想和编程技巧；计算几何算法实训：能够编成实现计算几何的基本算法，解决一些计算几何方面的问题数据结构相关内容实训：熟练掌握各种数据结构，并能编程实现；数论相关算法：熟练掌握数论的相关算法；图论的相关算法实训：熟练掌握最小生成树、单源点最短路径、BFS、DFS等算法；组合数学算法实训：熟练掌握排列、组合的相关算法、了解拟阵、了解Plya定理。学时分配：教学内容学时分配实验内容学时分配基本算法实训12计算几何算法实训9数据结构相关内容实训12数论相关算法6图论的相关算法实训6组合数学算法实训12八、考核方式在http:/acm.whu.edu.cn 完成编程练习，要求根据实训分类每一类别至少通过5道题（即Online Judge 给出Accepted），全部通过的题目不少于30道，如果没有达到该要求则不能获得学分。学生注册的用户名统一要求为：whucs+你的学号，比如：学生甲的学号为200901350016，那么注册的用户名为：whucs200901350016。九、教材自编教材：算法与程序设计，包含教案和PPT十、参考书目吴文虎国际大学生程序设计竞赛试题与解析（一）清华大学出版社卢开澄计算机算法导引设计与分析清华大学出版社王小东计算机算法设计与分析电子工业出版社郭嵩山崔昊国际大学生程序设计竞赛辅导教程北京大学出版社卢开澄卢开明组合数学清华大学出版社 大纲执笔者： 董文永 大纲审定者：