《算法与程序设计》教学大纲 ?适用专业：信息与计算科学专业 ?课程性质：专业基础课、必修课 ?课程内容构成 第一篇? （C语言）程序设计基础 第二篇? 数据结构与非数值算法基础（含数据结构、算法设计与分析两个模块） 第三篇? 数值算法(计算方法)基础 ?开课计划 ??? 依序开设在一年级下期至二年级上、下学期，共开设3个学期 ?授课学时安排 （C语言）程序设计基础，51学时 数据结构与非数值算法基础，102学时 数值算法基础，51学时 ?课程目标 本课程首先讲授一门高级语言（C语言），然后以此为基础给学生讲授数据结构、非数值算法和数值算法等基础知识，使学生能立足于高级语言，充分理解并掌握程序设计基本方法、程序设计中的各种常用的数据结构，能进行正确的算法分析与设计，了解并掌握常用的非数值算法和数值算法，为逐步形成和提高学生的程序设计能力、开发计算机软件以及进一步学习后继课程打下良好的基础。 ?选用教材：参考每篇给出的“教材与参考书” ?各部分授课大纲 第一篇? （C语言）程序设计基础 ??? 一、任务和目的 本篇主要以PC系列微机上使用的C语言为支撑介绍程序设计基础知识。通过学习，使学生掌握C语言的基本语法和基本结构，掌握程序设计的基本知识和基本思想，能熟练运用C语言进行程序设计，编写出简单的科学计算程序及非数值处理程序。 ??? 二、授课内容 （一）?? 绪论及C语言简介 软件产业的发展过程，C语言的基本特点。 ??? （二）数据类型、运算符和表达式 ???? 基本数据类型、标识符、常量、变量，枚举类型、运算符和表达式、运算符的优先级与结合性。 （三）简单程序设计 ???? 程序的基本控制结构、C程序结构及特点、数据的输入输出，简单程序设计，Turbo C2.0集成环境介绍。 ??? （四）数组 ???? 一维数组，二维数组，三维数组。 （五）基本语句 ???? 赋值语句，条件语句和分支语句，循环语句。 ??? （六）程序设计方法 ???? 尝试法及其程序模块结构，递推算法程序，迭代算法程序。 ??? （七）函数 ???? 函数的定义及调用，函数的数据传递，函数的嵌套调用与递归调用，函数举例，变量的作用域、类型及生命期，编译预处理。 ??? （八）指针 ???? 指针与地址，指针变量的使用，指针与数组，指针在函数中的使用，指针和字符串，指针数组与多级指针，指向函数的指针。 ??? （九）结构体与共用体 ???? 结构体，结构体数组，结构体类型的指针，共用体。 ??? （十）文件 ???? 文件定义，文件的打开与关闭，文件的顺序读写，文件的随机读写。 ??? 三、与其它课程或篇章的联系 ??? 本篇是在《计算概论》课程基础之上的高级语言课程，是学习程序设计的基础，也是整个计算学科的入门课程，其后继内容有数据结构与算法（数值及非数值）等。 ??? 四、基本要求 ??? 1．掌握C语言程序设计特点及方法。 ??? 2．领会程序设计思想。 ??? 3．能运用C进行编程，解决实际问题。 ??? 五、实践 本部分内容实践性较强，每个学生要完成总学时30左右（有教师指导）的上机实践，目的是加深理解和巩固所学内容，同时锻炼学生使用计算机解决实际问题的编程方法和技巧。教材中共安排了12个实验和9套习题，原则上每个学生均必须完成。此外，学生还可从课堂讲授或教材中选一些例题或习题来编程上机调试。 六、授课学时分配 本篇讲授51学时，教师可根据学生实际情况酌情略去部分内容。学时分配建议如下： 序? 号 内????? 容 学时  （一） 绪论及C语言简介 1  （二） 数据类型、运算符和表达式 4  （三） 简单程序设计 6  （四） 数组 5  （五） 基本语句 8  （六） 程序设计方法 5  （七） 函数 8  （八） 指针 8  （九） 结构体与共用体 3  （十） 文件 3  合????? 计 51  ??? 七、教材与参考书 1. 张世禄、潘大志、冯天敏编著，C语言程序设计，电子工业出版社，2005.07 2. 耿国华、索琦编著，计算机基础与C语言程序设计，电子工业出版社，2002.2 3．谭浩强著，C程序设计（第二版），清华大学出版社，1999.12 ????? 4．钱能编著，C++程序设计教程，清华大学出版社，1999 5．李春葆编著，C程序设计教程（基于Visual C++平台），清华大学出版社，2004 6．Brian W.Kernighan、Dennis M.Ritchie著，徐宝文、李志译，C程序设计语言（第2版），机械工业出版社，2004 ? 第二篇? 数据结构与非数值算法基础 ??? 一、任务和目的 ??? 本篇首先讲授用高级语言（C语言）描述的各种基本数据结构及其应用。通过学习，使学生透彻地理解各类数据对象的特点，学会数据的组织方法和实现方法。然后在此基础上讲授算法设计的基本策略及算法分析的基本方法，使学生掌握算法设计的常用方法及有关算法，熟悉它们的典型实例及算法实现技巧，并掌握算法分析的主要方法，为独立地进行算法设计和对给定算法进行复杂度分析奠定基础，也为进一步学习奠定基础。 ??? 二、授课内容 ?? （一）绪论 ??? 数据结构及其相关名词、术语的精确含义；算法的描述及分析；数据结构课程简介。 ?? （二）线性表 ??? 线性表的逻辑结构定义和各种存储结构的描述方法；线性表基本运算的各种实现；稀疏多项式的表示和相加。 ?? （三）栈和队列 ??? 栈和队列的结构特性；基本运算的实现；栈和队列的应用。 ?? （四）数组 ??? 数组的逻辑结构和存储方式；特殊矩阵和稀疏矩阵的压缩存储方法。 ?? （五）树和二叉树 ??? 二叉树的定义、性质和存储结构；二叉树的遍历和线索化；树的定义、存储及应用。 ?? （六）图 ??? 图的定义、存储结构和遍历，最小生成树，拓扑排序，关键路径，最短路径。 ?? （七）查找 ??? 顺序表、树表、哈希表的查找方法及效率分析。 ?? （八）内部排序 插入排序、快速排序、选择排序、归并排序、堆和基数排序的特点、过程分析以及时间复杂度的讨论。 ?? （九）复杂度及其分析 算法的复杂度，算法分析，复杂度分析，展开法，母函数法。 ?? （十）算法设计 回溯法，动态规划分法，贪婪法，分而治之法，分枝界限法，局部搜索法。 ?? （十一）外部排序 外排序及广义斐波那契（FEIBONACCI）数。 ?? （十二）非递归化 递归问题，栈，递归过程的改写。 ??? 三、与其它课程或篇章的联系 高等数学、概论统计、离散数学、高级语言（PASCAL或C）等，为本篇的先修课程或篇章，操作系统、编译原理、数据库原理、计算机图形学、数学模型、运筹与优化、数值计算方法等，为其后继课程或篇章。 四、基本要求 1．了解数据结构的分类，掌握各种基本数据结构及其特点，学会根据实际问题要求设计、实现数据结构的方法。 2．掌握基本的、良好的程序设计技巧、技能和基本的算法分析方法。 3．掌握在不同的数据结构上实现查找与排序的方法和各种基本数据结构的应用。 ??? 4. 掌握算法，算法设计内容及步骤，算法分析内容、方法及时间渐近表示等基本知识。了解递归算法设计及分析技术，并能将递归算法转换为非递归算法。 ??? 5. 掌握分治、贪婪、动态规划、分枝界限及回溯等算法设计方法和有关实例、效率及复杂性分析。 五、实践 每个学生需要完成总机时为48学时（有教师指导）左右的上机实验，题目可根据具体条件和课堂情况确定（详见《实验教学计划》）。每个教学单元都应有一定数量习题以帮助学生理解基本内容，培养良好编程风格。参考教材《数据结构题集》中难度系数为3及其以下的习题原则上均要求完成。 六、授课学时分配 本篇讲授102学时，在学时少的情况下教师可根据学生实际情况酌情略去某些内容。学时分配建议如下： 序? 号 内???????? 容 学? 时  （一） 绪论 5  （二） 线性表 6  （三） 栈和队列 6  （四） 数组 6  （五） 树和二叉树 10  （六） 图 10  （七） 查找 10  （八） 内部排序 10  （九） 复杂度及其分析 12  （十） 算法设计 15  （十一） 外部排序 6  （十二） 非递归化 6  总计 ? 102  ??? 七、教材与参考书 1. 严蔚敏、吴伟民，数据结构（C语言第二版），清华大学出版社，2002.6 2. 严蔚敏、吴伟民，数据结构题集（C语言版），清华大学出版社，2001.7 3. 耿国华等编著，数据结构—C语言描述，西安电子科技大学出版社，2002.2 4. [美]Bruno R. Preiss, Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons,Inc., 1999.12 5. 张益新、沈雁编著，算法引论，国防科技大学出版社，1997.11 6. 王晓东编著，计算机算法设计与分析，电子工业出版社，2004.7 7. [美]Clifford A. Shaffer, A Practical Introduction to Data Structures and Algorithm Analysis,Second Edition, Publishing House of Electronics Industry, 2002.1 ? 第三篇? 数值算法(计算方法)基础 一、任务和目的 本篇主要讲授误差理论，解线性代数方程组的直接方法和迭代方法，解非线性方程的对分法、牛顿法，矩阵特征值与特征向量数值解法、数值微积分、常微分方程数值解等。通过本篇学习，使学生掌握常用的数值方法，能用计算机求解相应的数值问题，为工作和进一步学习奠定基础。 二、授课内容 （一）绪论 计算方法概论，误差来源，误差表示法，算法选择。 （二）解线性代数方程组的直接方法 高斯消去法，主元素法，直接三角分解法，追赶法，平方根法与改进的平方根法，误差分析。 （三）非线性方程的数值解法 ? 对分法，逐次迭代法，牛顿法，双点割线法和单点割线法。 （四）解线性代数方程组的迭代法 ? 简单迭代法，赛德尔迭代法，松弛法，迭代法的收敛条件。 （五）求矩阵特征值和特征向量的数值方法 ?? 幂法，原点平移法，逆幂法，求实对称矩阵特征值的对分法。 （六）代数插值 ?? 代数插值基本性质，Lagrange插值，Newton插值，新代数插值。 （七）样条函数 样条函数的形成和定义，三次样条插值。 （八）数值积分 ???? 数值积分初步，梯形公式，Simpson公式，等距节点的牛顿-柯特斯公式，龙贝格算法，高斯型求积公式。 （九）常微分方程初值问题的数值解法 ? 欧拉法，预估-校正法，龙格-库塔法，阿达姆斯法以，收敛性与稳定性。 ?（十）基本算法及其基本程序模块（主要在实验课中讲授） ???? 基本算法，连乘积计算及其基本程序模块，累加和计算及其基本程序模块，递推算法，迭代法（1），迭代法（2），只存非零元素的迭代法。 三、与其它课程或篇章的联系 ????? 微积分、高等代数、（C语言）程序设计基础、数据结构等为其先修课程或篇章。逼近论等为其后继课程。 四、基本要求 1．了解误差理论。 2．掌握第二至第十章介绍的全部计算方法并能上机实现。 五、实践 每个学生需要完成总机时为30学时（有教师指导）左右的上机实验，题目可根据具体条件和课堂情况确定（详见《实验教学计划》及教材的《数学实验》部分）。每个教学单元都应有一定数量习题以帮助学生理解基本内容，培养良好编程风格。教材中每章习题的非证明性题目原则上均要求完成。 ?? 六、授课学时分配 本篇讲授51学时，教师可根据学生实际情况酌情略去部分内容。学时分配建议如下： 序 号 内??? 容 学时  （一） 绪论、误差 2  （二） 解线性代数方程组的直接方法 6  （三） 非线性方程的数值解法 6  （四） 解线性代数方程组的迭代法 4  （五） 求矩阵特征值和特征向量的数值方法 6  （六） 代数插值 6  （七） 样条函数 4  （八） 数值积分 6  （九） 常微分方程初值问题的数值解法 6  （十） 基本算法及其基本程序模块 5  总计 ? 51  七、教材及参考书 1．张世禄、陈豫眉、熊华等编，计算方法，电子科技大学出版社，1999.9 2．李庆扬、王能超、易大义编，数值分析，华中科技大学出版社，2003.1 3．奚梅成编著，数值分析方法，中国科学技术大学出版社，2003.1 4．Reiner Kress,Numerical Analysis，世界图书出版公司北京公司，2003.6 5．J.stoer,R.Bulirsch，Intoduction to Numerical Analysis，世界图书出版公司北京公司，1998.3