高级语言程序设计教学大纲

《高级语言程序设计》教学大纲 一、课程基本信息 课程代码：110421 课程名称：高级语言程序设计 英文名称：Advanced Programming 课程类别：专业基础课 学    时：90 学  分：4.5 适用对象：信息与计算科学专业大一本科生 考核方式：考试（平时成绩占总成绩的30%） 先修课程：数学分析、高等代数 二、课程简介 中文简介： 高级程序设计是必修基础课程。本课程以C++语言为工具，主要介绍面向对象的程序设计方法，C++面向对象程序设计语言和面向对象程序设计工具。使学生掌握面向对象的思想方法，是后续专业课程的基础。 英文简介： Advanced Programming is major basic course. Through this course, students should master the method of programming,the Object Oriented Language C++ ，and Object Oriented Design tool. This course is the base of several following speciality courses. 三、课程性质与教学目的 《高级语言程序设计》课程是信息与计算科学专业的专业必修课,要求掌握面向对象程序设计中基本的概念、方法，在理论、实践上为后续软件课程打下坚实基础。具体包括：基本语法成分、数据定义和相关运算、基本控制流程的概念和实现、函数的定义和调用、指针的基本概念、能够应用于数据组织和函数调用。以及面向对象程序设计的核心概念：封装、继承、多态和模板与群体数据组织。 四、教学内容及要求 第一章  绪论 (一) 目的与要求 1．掌握计算机程序设计语言的发展； 2．掌握在VC6.0集成开发环境下建立和运行Ｃ++程序的方法； 3. 了解面向对象的方法； 4. 了解面向对象的软件开发过程； 5. 了解信息的表示与存储。 (二) 教学内容 第一节 计算机程序设计语言的发展 1．主要内容 机器语言与汇编语言，主级语言，面向对象语言。 2．基本概念和知识点： 面向对象的语言，高级语言的概念。 3. 问题与应用（能力要求）： 了解程序设计语言的发展史与面向对象的语言。 第二节  面向对象的方法 1．主要内容 面向对象方法的由来，面向对象的基本概念。 2．基本概念和知识点   面向对象的基本概念。 3. 问题与应用（能力要求） 了解面向对象的由来与基本概念。 第三节  面向对象的软件开发 1．主要内容 软件开发的各个阶段及任务。 2．基本概念和知识点   分析、设计、编程、测试与维护。 3. 问题与应用（能力要求） 了解软件开发过程中的一般过程及各阶段的任务。 *第四节  信息的表示与存储 1．主要内容 计算机的数字系统，几种进行记数制之间的转换信息存储单位，二进制数的编码表示，定点数和浮点数，数的表示范围，非数值信息表示。 2．基本概念和知识点   数字系统，进位制及其转换，数的表示范围。 3. 问题与应用（能力要求） 掌握用二进制的编码表示，非数值信息表示。 第五节  程序的开发过程 1．主要内容 基本术语。 2．基本概念和知识点   程序开发的基本术语与开发的一般过程。 3. 问题与应用（能力要求） 了解程序开发的基本术语和开发的一般过程。 (三) 实践环节与课后练习 VC环境下运行一个简单的C＋＋程序。 (四) 教学方法与手段 课堂板书结合PowerPoint电子 教案 中职数学基础模块教案 下载北师大版¥1.2次方程的根与系数的关系的教案关于坚持的教案初中数学教案下载电子教案下载 讲授。 第二章  C++简单程序设计 (一) 目的与要求 1．了解C++语言产生和特点； 2．掌握基本数据类型和表达式； 3. 掌握数据的输入与输出； 4. 掌握算法的基本控制结构； 5. 掌握自定义数据类型。 (二) 教学内容 第一节 C++语言概述 1．主要内容 C++语言的产生，C++语言的特点，C++程序实例，字符集，词法记号。 2．基本概念和知识点 字符集，词法记号。 3. 问题与应用（能力要求） 掌握字符集，了解C++语言的特点与程序实例。 第二节 基本数据类型和表达式 1．主要内容 基本数据类型，常量，变量，运算符，表达式与语句。 2．基本概念和知识点   基本数据类型，常量，变量，运算符，表达式与语句。 3. 问题与应用（能力要求） 掌握基本数据类型，常量，变量，运算符，表达式与语句。 *第三节  数据的输入与输出（自学） 1．主要内容 I/O流，预定义的插入符和提取符，简单的I/O格式控制。 2．基本概念和知识点   I/O流，预定义的插入符和提取符， I/O格式控制。 3. 问题与应用（能力要求） 掌握I/O流，预定义的插入符和提取符。 第四节  算法的基本控制结构 1．主要内容 用if语句实现选择结构，多重选择结构，循环结构，循环结构与选择结构的嵌套，其它控制语句。 2．基本概念和知识点   用if语句实现选择结构，多重选择结构，循环结构。 3. 问题与应用（能力要求） 掌握用if语句实现选择结构，多重选择结构，循环结构。 第五节  自定义数据类型 1．主要内容 typedef声明，枚举类型，结构体，联合体。 2．基本概念和知识点   typedef声明，枚举类型，结构体，联合体。 3. 问题与应用（能力要求） 掌握枚举类型，结构体。 (三) 实践环节与课后练习 编写简单的C＋＋程序，使用枚举类型，结构体。 (四) 教学方法与手段 课堂板书结合PowerPoint电子教案讲授，程序演示。 第三章  函数 (一) 目的与要求 1． 正确掌握函数的定义； 2． 掌握内联函数； 3． 掌握带默认形参值的函数； 4． 掌握函数重载。 (二) 教学内容 第一节 函数的定义与使用 1． 主要内容 函数的定义，函数的调用，函数的参数传递。 2． 基本概念和知识点 函数的定义，函数的调用，函数的参数传递。 3． 问题与应用（能力要求） 掌握函数的定义，函数的调用，函数的参数传递。 *第二节  内联函数 1． 主要内容 内联函数的定义与使用。 2． 基本概念和知识点 内联函数的定义，内联函数在使用场合。 3． 问题与应用（能力要求） 掌握内联函数的定义，内联函数在使用场合。 第三节  带默认形参值的函数 1． 主要内容 带默认形参值的函数。 2． 基本概念和知识点 带默认形参值的函数及其使用法。 3． 问题与应用（能力要求） 掌握带默认形参值的函数及其使用。 第四节  函数重载 1． 主要内容 函数重载的概念与定义。 2． 基本概念和知识点 函数重载的概念与定义和使用。 3． 问题与应用（能力要求） 掌握函数重载的概念与使用。 *第五节  使用C++系统函数（自学） 1. 主要内容 C++系统函数。 2. 基本概念和知识点 C++系统函数及其查询与使用法。 3. 问题与应用（能力要求） 掌握简单的C++系统函数。 (三) 实践环节与课后练习 使用简单的系统函数编写程序。 (四) 教学方法与手段 课堂板书结合PowerPoint电子教案讲授，程序演示。 第四章  类与对象 (一) 目的与要求 1. 熟练掌握类与对象的概念； 2. 熟练掌握构造函数与析构函数； 3. 掌握类的组合； 4. 掌握UML图形标识。 (二) 教学内容 第一节 面向对象程序设计的基本特点 1． 主要内容 抽象，封装，继承，多态。 2． 基本概念和知识点 抽象，封装，继承，多态。 3． 问题与应用（能力要求） 理解抽象，封装，继承，多态。 第二节  类和对象 1． 主要内容 类的声明，类成员的访问控制，类的成员函数，对象，举例说明。 2． 基本概念和知识点 类的声明，类成员的访问控制，类的成员函数，对象。 3． 问题与应用（能力要求） 掌握类的声明，类成员的访问控制，类的成员函数，对象。 第三节  构造函数和析构函数 1． 主要内容 构造函数，拷贝构造函数，析构函数，程序举例。 2． 基本概念和知识点 构造函数，拷贝构造函数，析构函数。 3． 问题与应用（能力要求） 掌握构造函数，拷贝构造函数，析构函数。 第四节  类的组合 1． 主要内容 组合，引用声明。 2． 基本概念和知识点 组合，引用声明，程序举例。 3． 问题与应用（能力要求） 掌握组合，引用声明，程序举例。 *第五节  UML图形标识（自学） 1. 主要内容 UML简介，UML类图。 2. 基本概念和知识点 UML简介，UML类图。 3. 问题与应用（能力要求） 掌握UML类图。 (三) 实践环节 编写程序，要求含有类及类构造函数与析构函数和拷贝构造函数。 (四) 教学方法与手段 采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主，辅以程序演示。 第五章  C++程序的结构 (一) 目的与要求 1. 熟练掌握作用域与可见性的概念； 2. 熟练掌握对象的生存期； 3. 掌握类的静态成员； 4. *了解类的友元； 5. *掌握共享数据的保护； 6. *掌握多文件结构处理； 7. *理解编译预处理命令。 (二) 教学内容 第一节 标识符的作用域与可见性 1． 主要内容 作用域与可见性。 2． 基本概念和知识点 标识符的作用域与可见性。 3． 问题与应用（能力要求） 掌握标识符的作用域与可见性。 第二节  对象的生存期 1． 主要内容 静态生存期，动态生存期。 2． 基本概念和知识点 静态生存期，动态生存期。 3． 问题与应用（能力要求） 掌握静态生存期，动态生存期。 第三节  类的静态成员 1． 主要内容 静态数据成员，静态函数成员。 2． 基本概念和知识点 静态数据成员，静态函数成员。 *3.问题与应用（能力要求） 掌握静态数据成员，静态函数成员。 *第四节  类的友元 1． 主要内容 友元类，友元函数。 2． 基本概念和知识点 友元类，友元函数。 3． 问题与应用（能力要求） 了解友元类，友元函数。 *第五节  共享数据的保护（选学） 1. 主要内容 常引用，常对象。 2. 基本概念和知识点 常引用，常对象。 3. 问题与应用（能力要求） 掌握常引用，常对象。 *第六节  多文件结构和编译预处理命令（自学） 1. 主要内容 C++程序的一般组织结构，外部变量与外部函数， 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 C++库函数和命名空间，预处理。 2. 基本概念和知识点 C++程序的一般组织结构，外部变量与外部函数，标准C++库函数和命名空间，预处理。 3. 问题与应用（能力要求） 掌握一般组织结构，外部变量与外部函数，标准C++库函数和命名空间，预处理。 (三) 实践环节 编写程序，要求类含有静态成员，常引用常对象，使用多文件组织。 (四) 教学方法与手段 采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主。辅以程序演示。 第六章  数组、指针与字符串 (一) 目的与要求 1. 熟练掌握数组； 2. 熟练掌握指针； 3. 掌握动态内存分配； 4. 掌握深拷贝与浅拷贝； 5. *掌握字符与string类。 (二) 教学内容 第一节 数组 1． 主要内容 数据的声明与使用，数组的存储与初始化，数组作为函数参数，对象数组，程序举例。 2． 基本概念和知识点 数据的声明与使用，数组的存储与初始化，数组作为函数参数，对象数组。 3． 问题与应用（能力要求） 掌握数据的声明与使用，数组的存储与初始化，数组作为函数参数，对象数组。 *第二节  指针（部分选学） 1． 主要内容 内存空间访问方式，指针变量的声明，与地址运算，指针的赋值，指针运算，用指针处理数组元素，指针数组，用指针作为函数参数，指针型函数，指向函数的指针，对象指针。 2． 基本概念和知识点 内存空间访问方式，指针变量的声明，与地址运算，指针的赋值，指针运算，用指针处理数组元素； 其中选学：指针数组，用指针作为函数参数，指针型函数，指向函数的指针，对象指针。 3． 问题与应用（能力要求） 掌握：指针变量的声明，与地址运算，指针的赋值，指针运算，用指针处理数组元素，指针数组，用指针作为函数参数，指针型函数，指向函数的指针，对象指针。 第三节  动态内存分配 1． 主要内容 new运算和delete运算，动态内存分配与释放函数。 2． 基本概念和知识点 new运算和delete运算，动态内存分配与释放函数。 3． 问题与应用（能力要求） 掌握new运算和delete运算，动态内存分配与释放函数。 第四节  深拷贝与浅拷贝 1． 主要内容 深拷贝与浅拷贝。 2． 基本概念和知识点 深拷贝与浅拷贝。 3． 问题与应用（能力要求） 掌握深拷贝与浅拷贝。 *第五节  字符串（自学） 1. 主要内容 用字符数组存储和处理字符串，string类。 2. 基本概念和知识点 用字符数组存储和处理字符串，string类。 3. 问题与应用（能力要求） 掌握处理字符串和string类。 (三) 实践环节   编写程序，要求使用数组和指针，动态内存分配，另在拷贝构造函数中使用深拷贝，使用string类。 (四) 教学方法与手段 采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主。辅以程序演示。 第七章  继承与派生 (一) 目的与要求 1. 熟练掌握继承与派生； 2. 熟练掌握继承时的访问控制； 3. 掌握派生类的构造和析构函数； 4. 掌握派生类成员的标识与访问。 (二) 教学内容 第一节 类的继承一派生 1． 主要内容 继承与派生的实例，派生类的定义，派生类的生成过程，程序举例。 2． 基本概念和知识点 派生类的定义，派生类的生成过程。 3． 问题与应用（能力要求） 掌握派生类的定义，派生类的生成过程。 第二节  访问控制 1． 主要内容 派生时的公有继承，私有继承，保护继承。 2． 基本概念和知识点 派生时的公有继承，私有继承，保护继承。 3． 问题与应用（能力要求） 掌握：派生时的公有继承，私有继承，保护继承。 *第三节  类型兼容规则（选学） 1． 主要内容 各派生类的对象类型兼容规则。 2． 基本概念和知识点 各派生类的对象类型兼容规则。 3． 问题与应用（能力要求） 掌握各派生类的对象类型兼容规则。 第四节  派生类的构造和析构函数 1． 主要内容 派生类的构造函数，拷贝构造函数与析构函数。 2． 基本概念和知识点 派生类的构造函数，拷贝构造函数与析构函数。 3． 问题与应用（能力要求） 掌握派生类的构造函数，拷贝构造函数与析构函数。 *第五节  派生类成员的标识与访问（自学） 1. 主要内容 作用域与分辨率，虚基类，虚基类及其派生类的构造函数。 2. 基本概念和知识点 作用域与分辨率，虚基类，虚基类及其派生类的构造函数。 3. 问题与应用（能力要求） 作用域与分辨率，虚基类，虚基类及其派生类的构造函数。 (三) 实践环节     编写程序，要求使用继承与派生，正确书写派生类的构造函数，拷贝构造函数与析构函数，使用虚基类。 (四) 教学方法与手段 采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主。辅以程序演示。 第八章  多态性 (一) 目的与要求 1. 熟练掌握运算符重载； 2. 熟练掌握虚函数与抽象类。 (二) 教学内容 第一节  多态性概述 1． 主要内容 多态的类型，多态实现。 2． 基本概念和知识点 多态的类型，多态实现。 3． 问题与应用（能力要求） 掌握多态的类型，多态实现。 *第二节  运算符重载 1． 主要内容 运算符重载的规则，运算符重载为成员函数，运算符重载为友元函数。 2． 基本概念和知识点 运算符重载的规则，运算符重载为成员函数，运算符重载为友元函数。 3． 问题与应用（能力要求） 掌握：运算符重载的规则，运算符重载为成员函数。 第三节  虚函数 1． 主要内容 一般虚函数成员，虚析构函数。 2． 基本概念和知识点 一般虚函数成员，虚析构函数。 3． 问题与应用（能力要求） 掌握一般虚函数成员，虚析构函数。 *第四节  抽象类 1． 主要内容 纯虚函数，抽象类。 2． 基本概念和知识点 纯虚函数，抽象类。 3． 问题与应用（能力要求） 掌握纯虚函数，抽象类。 (三) 实践环节   编写程序，要求使用运算符重载，虚函数与虚基类。 (四) 教学方法与手段 采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主。辅以程序演示，分组讨论。 *第九章  群体类和群体数据的组织（自学） (一) 目的与要求 1. 掌握函数模板与类模板； 2. 掌握线性群体的概念； 3. 掌握数组模板类与链表模板类； 4. 掌握群体数据的常操作。 (二) 教学内容 第一节  多态性概述 1． 主要内容 函数模板与类模板。 2． 基本概念和知识点 函数模板与类模板。 3． 问题与应用（能力要求） 掌握函数模板与类模板。 第二节  线性群体 1． 主要内容 线性群体的概念，直接访问数组群体类模板，顺序访问的链表群体类模板。 2． 基本概念和知识点 线性群体的概念，直接访问数组群体类模板，顺序访问的链表群体类模板。 3． 问题与应用（能力要求） 掌握：直接访问数组群体类模板，顺序访问的链表群体类模板。 (三) 实践环节   编写程序，数组类模板与链表类模板，并要求用常用操作。 (四) 教学方法与手段 采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主,辅以程序演示.           *第十章  泛型程序设计与C++标准模板库（选学） (一) 目的与要求 1. 掌握泛型程序设计的概念和术语； 2. 掌握会使用简单的标准模板库中的容器与容器适配器。 (二) 教学内容 第一节  泛型程序设计的概念和术语 1． 主要内容 泛型程序设计，命名空间概念，头文件命名规则，标准模板库术语。 2． 基本概念和知识点 泛型程序设计，命名空间概念，头文件命名规则，标准模板库术语。 3． 问题与应用（能力要求） 了解泛型程序设计，命名空间概念，头文件命名规则，标准模板库术语。 第二节  C++标准模板库中的容器 1． 主要内容 顺序容器，容器适配器。迭代器。 2． 基本概念和知识点 顺序容器，容器适配器。迭代器。 3． 问题与应用（能力要求） 了解：顺序容器，容器适配器。迭代器。 (三) 实践环节     编写程序，使用顺序容器，及其相应的适配器（要求数组模板或链表模板）。 (四) 教学方法与手段 采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主，辅以程序演示。           *第十一章  流类库与输入/输出（自学） (一) 目的与要求 1. 了解I/O流的概念及流类库结构； 2. 了解输出流与输入流。 (二) 教学内容 第一节  I/0流的概念及流类库结构 1． 主要内容 基本概念，输出流，输入流。 2． 基本概念和知识点 基本概念，输出流，输入流语。 3． 问题与应用（能力要求） 了解基本概念，输出流，输入流。 (三) 实践环节   编写程序，使用输出输入流。 (四) 教学方法与手段 采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主，辅以程序演示。 *第十二章  异常处理（选学） (一) 目的与要求 1. 了解异常处理的基本思想； 2. 了解C++异常处理的实现； 3. 了解标准程序库异常处理。 (二) 教学内容 第一节  异常处理 1． 主要内容 异常处理的基本思想，异常处理的实现，标准程序库异常处理。 2． 基本概念和知识点 异常处理的基本思想，异常处理的实现，标准程序库异常处理。 3． 问题与应用（能力要求） 了解异常处理的基本思想，异常处理的实现，标准程序库异常处理。 (三) 实践环节     阅读书上例题程序，并上机验证，偿试编写异常处理程序。 (四) 教学方法与手段 采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主，辅以程序演示。       五、各教学环节学时分配 教学环节 教学时数 课程内容 讲 课 习 题 课 讨 论 课 实验 其他教学环节 小 计 第一章 绪论 2 2 第二章C++简单程序设计 3 3 第三章　函数 3 3 第四章 类与对象 3 3 第五章C++程序的结构 3 3 第六章 数组、指针与字符串 9 3 12 第七章 继承与派生 8 3 11 第八章 多态性 8 3 11 第九章 群体类和群体类数据的组织 9 9 第十章 泛型程序设计与标准模板库 9 0 ９ 第十一章 流类库与输入输出 6 6 第十二章 异常处理 3 3 派生继承与多态性（综合设计 性实验，学生自主设计完成） 9 9 期未复习巩固 6 6 合计 72 0 0 18 90 六、推荐教材和教学参考资源 推荐教材： 郑莉、董渊，C++语言程序设计（第3版）， 清华大学出版社。 教学参考资源： （1）郑莉、董渊，C++程序设计程序设计案例教程，清华大学出版社。 （2）郑莉、董渊，C++语言程序设计（第3版）学生用书，清华大学出版社。 七、其他说明 大纲中打星号的部分，教师可根据实际情况选择是否讲解。 大纲修订人：  孙红英                  修订日期：2007.4.25 大纲审定人：  胡小健                  审定日期：2007.5.28 《数据结构》课程教学大纲 一、课程基本信息 课程代码：110051 课程名称：数据结构 英文名称：Data Structure 课程类别：专业基础课 学    时：72 学  分：3.5 适用对象:信息与计算科学专业本科生 考核方式：考试、平时成绩占总成绩的30％ 先修课程：高级语言程序设计、离散数学 二、课程简介 数据结构是计算机学科的核心专业基础课程，是程序设计的重要理论和实践基础。课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、树和二叉树、图等典型数据结构的逻辑结构、存储结构和操作的实现方法，以及递归算法设计方法和各种典型排序和查找算法的设计方法。通过本课程的学习，一方面为后续课程，特别是软件分析和设计方面的课程，打下理论基础；另一方面，也进行了充分的实践动手训练。 Data Structure is a core specialty basic course for computer subjects. It is also an important theory and practice base for programming. The course discusses logical and storage structure of typical data structures, such as linear list, stack, queue, string, array, tree, binary tree and graph, as well as its operation’s implementing. Recursion algorithm and all sorts of typical sort and search algorithms are also included. Through learning this course, students could lay a theory foundation for later courses, especially for software analysis and design relative courses. On the other hand, abundant training is practiced in the process. 三、课程性质与教学目的 课程性质 是一门研究非数值计算的程序设计问题中计算机的操作对象及其之间关系与操作的学科，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，属于计算机学科中的一门综合性专业基础课程，是一般程序设计的基础，也是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。 教学目的 一方面学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 。如果说高级语言程序设计课程对学生进行了结构化程序设计的初步训练的话，那么数据结构课程就要培养他们的数据抽象能力。 四、教学内容及要求 第一章  绪论 (一) 目的与要求 1. 通过本章的学习，使学生领会数据、数据元素和数据项的概念及其相互间的关系； 2. 掌握数据结构的逻辑结构、存储结构的联系与区别； 3. 了解算法时间复杂度和空间复杂度的分析。 (二) 教学内容 第一节  什么是数据结构 1. 主要内容 由数学方程无法描述的非数值计算问题引出数据结构表、图、树的3种实例，数据结构的概念，数据结构的内涵和特点，数据结构所处的学科地位，数据结构的学科背景、起源、发展和现状。 2. 基本概念和知识点 数据结构的概念；数据结构的内涵和特点；数据结构所处的学科地位；数据结构的学科背景、起源、发展和现状。 3. 问题与应用（能力要求） 要求学生掌握数据结构的概念，能辨别数学模型中数学方程和表、图、树等数据结构的区别。     第二节  基本概念和术语 1． 主要内容 本课使用的一些基本概念，包括数据、数据元素、数据项、数据对象、数据结构、集合、结构、线性结构、树形结构、图状结构、网状结构、逻辑结构、物理结构、存储结构、位、元素、结点、数据域、顺序映像、非顺序映像、顺序存储结构、链式存储结构、指针、虚拟存储结构、数据类型、原子类型、结构类型、抽象数据类型、固定聚合类型、可变聚合类型、多形数据类型。 2． 基本概念和知识点 数据、数据元素、数据项、数据对象、数据结构、集合、结构、线性结构、树形结构、图状结构、网状结构等在内的所有基本概念。 3． 问题与应用（能力要求） 掌握包括数据、数据元素、数据项、数据对象、数据结构、集合、结构、线性结构、树形结构、图状结构、网状结构等基本概念。 第三节  抽象数据类型的表示与实现 1． 主要内容 抽象数据类型的常用表示方法。 2． 基本概念和知识点 抽象数据类型的常用表示方法，包括预定义常量和类型、数据结构的表示用类型定义（typedef）描述、函数表示法、各种赋值语句、选择语句、结束语句、输入和输出语句、基本函数、逻辑运算约定。 3． 问题与应用（能力要求） 掌握抽象数据类型的类C语言11种表示方法。 第四节  算法与算法分析 1． 主要内容 算法的定义，算法的5个重要特征。好算法设计的4个要求。算法效率的2种度量方法，时间复杂度的概念，频度的概念。空间复杂度的概念，空间复杂度的表示法，算法原地工作的概念。 2． 基本概念和知识点 算法的定义，算法的5个重要特征。好算法设计的4个要求。时间复杂度，空间复杂度的概念，空间复杂度。 3． 问题与应用（能力要求） 掌握算法的定义；理解算法的5个重要特征；理解好算法设计的4个要求；掌握空间复杂度的概念。 (三) 课后练习 配套习题集P7 1.1，P8 1.8 （1）、（6）， P10 1.12。 (四) 教学方法与手段 采用黑板板书和PowerPoint电子教案相结合的方式。 第二章  线性表 （一） 目的与要求 1． 了解线性表的基本概念和类型定义； 2． 熟练掌握顺序存储的线性表和单链表的算法设计及其程序实现； 3． 掌握循环链表和双向链表的操作。 （二） 教学内容 第一节 线性表的类型定义 1． 主要内容 线性结构的特点，线性表的抽象数据类型定义，数据项、 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 、文件的定义，实例说明线性表的插入、删除、归并等操作方式，并对算法做相应的分析。 2． 基本概念和知识点 线性结构的特点, 线性表的插入、删除、归并等操作。 3． 问题与应用（能力要求） 要求学生掌握线性表的概念和抽象数据类型定义。     第二节  线性表的顺序表示和实现 1． 主要内容 线性表的顺序表示的概念，顺序映像的方式，顺序映像的随机存取特性，实例描述线性表在顺序存储表示时进行插入、删除、合并操作的几种算法。 2． 基本概念和知识点 线性表的顺序表示的概念, 插入、删除、合并操作的几种算法。 3． 问题与应用（能力要求） 掌握线性表的顺序表示的概念和顺序映像的方式；理解线性表在顺序存储结构时的插入、删除、合并等操作方法。 第三节  线性表的链式表示和实现 1． 主要内容 线性链表的概念，单链表的插入、删除、合并操作处理算法，静态链表的算法；循环链表的概念，循环链表的操作特点；双向链表的概念和特点，双向链表的抽象数据类型定义，双向链表的几种操作算法。 2． 基本概念和知识点 几种链表的概念,操作特点及处理算法。 3． 问题与应用（能力要求） 掌握线性有序链表的概念；理解单链表的插入、删除、合并操作算法；掌握循环链表的概念；掌握双向链表的概念；了解双向链表的抽象数据类型定义；了解双向链表的操作算法。 *第四节  一元多项式的表示及相加（选学） 1． 主要内容 利用线性链表的基本操作来实现一元多项式的定义、相加和相乘运算。 2． 基本概念和知识点 一元多项式的定义、相加和相乘运算。 3． 问题与应用（能力要求） 掌握利用线性链表的基本操作来实现一元多项式的定义、相加和相乘运算。 （三） 实践环节 建立线性表类，实现相关操作，应用于多项式相加、相乘问题。 （四） 教学方法与手段 采用黑板板书和PowerPoint电子教案相结合的方式。 第三章  栈和队列 （一）目的与要求 1． 掌握栈和队列的定义； 2． 熟练掌握顺序和链接存储的栈和队列的算法设计及其程序实现； 3． 了解栈和队的各种应用。 （二）教学内容 第一节 栈 1． 主要内容 栈、栈顶、栈底、后进先出等概念，栈的抽象数据定义；栈的2种存储表示法：顺序栈和链栈的定义，顺序栈的模块说明。 2． 基本概念和知识点 栈及栈的相关概念，栈的抽象数据定义；顺序栈的定义。 3． 问题与应用（能力要求） 掌握栈及栈的相关概念；理解栈的抽象数据定义；掌握顺序栈的定义。     第二节  栈的应用举例 1． 主要内容 应用栈结构的后进先出特性，进行十进制N和其它d进制数的转换算法；进行圆括号和方括号书写格式是否正确的检查算法。 2． 基本概念和知识点 十进制N和其它d进制数的转换算法；圆括号和方括号书写格式是否正确的检查算法。 3． 问题与应用（能力要求） 理解应用栈结构的数制转换算法；理解应用栈结构的括号匹配检验算法。 第三节  栈与递归的实现 1． 主要内容 递归的概念、递归问题的特性，栈在n阶Hanoi塔问题等典型递归问题中的应用。 2． 基本概念和知识点 递归的概念、递归问题的特性，n阶Hanoi塔问题。 3． 问题与应用（能力要求） 理解栈在n阶Hanoi塔递归算法中的应用。 第四节  队列 1． 主要内容 队列、FIFO的概念，队列的特性，队列的抽象数据定义。队列链式表示的基本操作函数。循环队列的概念。 2． 基本概念和知识点 队列、FIFO的概念，队列的特性，队列的抽象数据定义。队列链式表示的基本操作函数。循环队列的概念。 3． 问题与应用（能力要求） 掌握队列的概念；理解队列的特性，队列的抽象数据定义；理解队列链式表示的基本操作函数。 （三）实践环节 建立顺序存储的栈类，应用于十进制向d进制数字转换问题。 （四）教学方法与手段 采用黑板板书和PowerPoint电子教案相结合的方式。 第四章  串 （一） 目的与要求 1. 掌握串的基本存储结构及基本操作； 2. 了解改进的模式匹配算法。 （二） 教学内容 第一节 串类型的定义 1． 主要内容 串产生的背景，串的概念，串长度、空串、子串、主串、位置、空格串等概念，串的抽象数据类型定义，串的基本操作集概念。 2． 基本概念和知识点 串的概念，串的抽象数据类型定义，串的基本操作集概念。 3． 问题与应用（能力要求） 掌握串及相关的概念，理解串的抽象数据类型定义。     第二节  串的表示和实现 1． 主要内容 串在机内的定长顺序表示，串的连接操作和子串操作，串的堆分配存储表示，在这种存储结构表示时如何实现串的插入操作。 2． 基本概念和知识点 串在机内的定长顺序表示及相关操作算法；串的堆分配存储表示及相关操作算法。 3． 问题与应用（能力要求） 掌握串的定长顺序存储表示；理解在定长顺序存储结构表示时实现串的连接操作和子串操作的方法；掌握串的堆分配存储表示；了解在堆分配存储结构表示时实现串的插入操作串的块链存储表示；了解串的块链存储表示。 *第三节  串的模式匹配算法（选学） 1． 主要内容 串的定位操作、匹配、模式匹配、模式串等概念，求子串位置的定位函数；KMP模式匹配算法。 2． 基本概念和知识点 串的定位操作、匹配、模式匹配、模式串等概念，求子串位置的定位函数；KMP模式匹配算法。 3． 问题与应用（能力要求） 掌握模式匹配的概念，熟悉求子串位置的定位函数，熟悉KMP模式匹配算法。 第四节  串操作应用举例 1． 主要内容 在文本编辑中使用串操作；使用串建立词索引表的方法，词索引表插入的实现算法。 2． 基本概念和知识点 在文本编辑中使用串操作；使用串建立词索引表的方法。 3． 问题与应用（能力要求） 理解文本编辑中串的用法，了解建立词索引表中串的用法。 （三） 实践环节 1. 熟悉串类型的实现方法，了解简单文字处理的设计方法。                   2. 熟悉C语言的字符和把字符串处理的原理和方法。 （四） 教学方法与手段 采用黑板板书和PowerPoint电子教案相结合的方式。 第五章  数组和广义表 （一） 目的与要求 1． 掌握数组的顺序存储结构及特殊矩阵的存储方式； 2． 掌握数组的顺序存储结构及特殊矩阵的存储方式； 3． 了解稀疏矩阵的压缩存储方式—三元组表； 4． 理解广义表的定义、术语、存储结构、运算。 （二） 教学内容 第一节 数组的定义 1． 主要内容 抽象数据类型数组的定义。 2． 基本概念和知识点 抽象数据类型数组。 3． 问题与应用（能力要求） 掌握抽象数据类型数组的定义。     第二节  数组的顺序表示和实现 1． 主要内容 数组的顺序存储结构，以列序为主序的二维数组存储方式，以行序为主序的二维数组存储方式，n维数组的数据元素存储位置的计算。 2． 基本概念和知识点 数组的顺序存储结构，n维数组的数据元素存储位置的计算。 3． 问题与应用（能力要求） 掌握数组的顺序表示法。 第三节  矩阵的压缩存储 1． 主要内容 矩阵、压缩存储、特殊矩阵的概念，特殊矩阵的压缩存储算法；稀疏矩阵的概念，稀疏矩阵的压缩存储算法，两个稀疏矩阵相乘的算法。 2． 基本概念和知识点 矩阵、压缩存储、特殊矩阵，特殊矩阵的压缩存储算法；稀疏矩阵的概念，稀疏矩阵的压缩存储算法，两个稀疏矩阵相乘的算法。 3． 问题与应用（能力要求） 掌握压缩存储、特殊矩阵的概念，熟悉特殊矩阵的压缩存储算法。掌握稀疏矩阵的压缩存储算法。 第四节  广义表的定义 1． 主要内容 抽象数据类型广义表的定义，列表的3个重要结论。 2． 基本概念和知识点 抽象数据类型广义表，列表的3个重要结论。 3． 问题与应用（能力要求） 掌握抽象数据类型广义表的定义。 第五节  广义表的存储结构 1． 主要内容 广义表的链式存储结构，广义表的头尾链表存储表示。 2． 基本概念和知识点 广义表的链式存储结构，广义表的头尾链表存储表示。 3． 问题与应用（能力要求） 熟悉广义表的存储结构。 （三） 实践环节与课后练习 利用稀疏矩阵的“三元组表”存储结构，实现两个矩阵的相加。 （四） 教学方法与手段 采用黑板板书和PowerPoint电子教案相结合的方式。 第六章  树与二叉树 （一） 目的与要求 1． 掌握树的定义、性质、存储结构； 2． 熟练掌握二叉树的遍历算法及其实现； 3． 哈夫曼树的构造方法和编码方法； 4． 了解树、森林和二叉树的转换及遍历。 （二） 教学内容 第一节 树的定义和基本术语 1． 主要内容 树型结构的背景，树、子树、结点、叶子、终端结点、分支结点、双亲、孩子、深度、有序树、无序树、森林抽象数据类型树的定义,树的4种表示法。 2． 基本概念和知识点 树、子树、结点、叶子、终端结点、分支结点、双亲、孩子、深度、有序树、无序树、森林抽象数据类型树的定义,树的4种表示法。 3． 问题与应用（能力要求） 掌握树的概念，树结构中结点、叶子、深度等术语的概念。     第二节  二叉树 1． 主要内容 抽象数据类型二叉树的定义；二叉树的5个重要性质；二叉树的顺序存储结构，二叉树的链式存储结构。 2． 基本概念和知识点 抽象数据类型二叉树；二叉树的5个重要性质；二叉树的顺序存储结构，二叉树的链式存储结构。 3． 问题与应用（能力要求） 掌握抽象数据类型二叉树的定义；掌握二叉树的5个重要性质，掌握二叉树的顺序存储结构，二叉树的链式存储结构。 第三节  遍历树和线索二叉树 1． 主要内容 遍历和遍历二叉树的概念，先序遍历二叉树的操作定义，中序遍历二叉树的操作定义，后序遍历二叉树的操作定义，先序遍历二叉树基本操作的递归算法在二叉链表上的实现；线索链表、线索、线索二叉树、线索化的概念，线索二叉树及其存储结构，后序后继线索二叉树。 2． 基本概念和知识点 遍历和遍历二叉树，先序遍历二叉树的操作，中序遍历二叉树的操作，后序遍历二叉树的操作，先序遍历二叉树基本操作的递归算法在二叉链表上的实现；线索链表、线索、线索二叉树、线索化，线索二叉树及其存储结构，后序后继线索二叉树。 3． 问题与应用（能力要求） 掌握遍历和遍历二叉树的概念；熟悉序遍历二叉树基本操作的递归算法在二叉链表上的实现；掌握线索、线索二叉树的概念；熟悉中序线索二叉树，中序线索链表。 第四节  树和森林 1． 主要内容   树的3种常用的链表存储结构。森林与二叉树的转换，森林转换成二叉树的定义，二叉树转换成森林的定义；森林的2种遍历方法。 2． 基本概念和知识点 树的3种常用的链表存储结构。森林与二叉树的转换，森林转换成二叉树，二叉树转换成森林；森林的2种遍历方法。 3． 问题与应用（能力要求） 掌握树的3种常用的链表存储结构；掌握森林转换成二叉树的定义，二叉树转换成森林的定义；了解森林的2种遍历方法。 第五节  赫夫曼树及其应用 1． 主要内容 最优二叉树的概念，构造赫夫曼树的算法；赫夫曼编码的定义，赫夫曼编码的存储表示。 2． 基本概念和知识点 最优二叉树，构造赫夫曼树的算法；赫夫曼编码，赫夫曼编码的存储表示。 3． 问题与应用（能力要求） 掌握最优二叉树的概念，构造赫夫曼树的算法；掌握赫夫曼编码的定义，赫夫曼和赫夫曼编码的存储表示。 （三） 实践环节 安排综合性实验，建立二叉树类，要求用先序、中序、后序遍历二叉树。 （四） 教学方法与手段 采用黑板板书和PowerPoint电子教案相结合的方式。 第七章  图 （一） 目的与要求 1． 掌握图的定义和术语； 2． 熟练掌握图的存储结构及深度和广度搜索算法思想及其实现； 3． 了解最短路径算法。 （二） 教学内容 第一节 图的定义和术语 1． 主要内容 图的概念，抽象数据类型图的定义，顶点、弧、有向图、无向图、完全图、有向完全图、稀疏图、稠密图、权、网、子图、邻接点、入度、出度、路径、回路、简单路径、连通、连通图、连通分量、强连通图、生成树、生成森林等概念。 2． 基本概念和知识点 图，抽象数据类型图的定义。 3． 问题与应用（能力要求） 掌握图以及与图有关名词的定义、掌握抽象数据类型图的定义。     第二节  图的存储结构 1． 主要内容 图的多重链表，图的数组表示法，网及其邻接矩阵；图的链式存储结构邻接表、逆邻接表；无向图的链式存储结构邻接多重表。 2． 基本概念和知识点 图的多重链表，图的数组表示法，网及其邻接矩阵；图的链式存储结构邻接表、逆邻接表；无向图的链式存储结构邻接多重表。 3． 问题与应用（能力要求） 掌握图的多重链表，熟悉图的数组表示法。掌握图的链式存储结构邻接表。有向图的链式存储结构十字链表；掌握有向图的链式存储结构十字链表。掌握无向图的链式存储结构邻接多重表。 第三节  图的遍历 1． 主要内容 图的遍历概念，遍历图的路径深度优先搜索；遍历图的路径广度优先搜索。 2． 基本概念和知识点 图的遍历，深度优先搜索；广度优先搜索。 3． 问题与应用（能力要求） 掌握深度优先搜索过程。掌握广度优先搜索过程。 第四节  图的连通问题 1． 主要内容 利用遍历图的算法求解连通和非连通无向图的连通性问题，无向图的连通分量和生成树的构成方式；求解有向图的强连通分量的步骤；最小生成树问题的概念，构造最小生成树的普里姆算法、克鲁斯卡尔算法。 2． 基本概念和知识点 连通和非连通无向图的连通性问题，无向图的连通分量和生成树的构成方式；最小生成树问题的概念，构造最小生成树算法。 3． 问题与应用（能力要求） 熟悉无向图的连通分量和生成树的构成方式，熟悉求解有向图的强连通分量的步骤，熟悉构造最小生成树的普里姆算法。 *第五节  有向无环图及其应用（自学） 1． 主要内容 有向无环DAG图的定义，在描述表达式时与二叉树的区别，拓扑排序、偏序、全序、拓扑有序的概念，拓扑排序的算法； AOE网，关键路径的算法。 2． 基本概念和知识点 有向无环DAG图的定义，在描述表达式时与二叉树的区别，拓扑排序、偏序、全序、拓扑有序的概念，拓扑排序的算法； AOE网，关键路径的算法。 3． 问题与应用（能力要求） 掌握有向无环DAG图的定义，熟悉拓扑排序、偏序、全序、拓扑有序的概念。熟悉AOE网的概念，了解关键路径的算法。 *第六节  最短路径（选学） 1． 主要内容 源点、终点的概念，分析带权有向图中从某个源点到其余各顶点的最短路径问题，讲解针对此问题的用C语言描述的迪杰斯特拉算法；分析带权有向图中每一对顶点之间的最短路径问题，讲解针对此问题的弗洛伊德算法。 2． 基本概念和知识点 源点、终点的概念，分析带权有向图中从某个源点到其余各顶点的最短路径问题，迪杰斯特拉算法；弗洛伊德算法。 3． 问题与应用（能力要求） 了解从某个源点到其余各顶点的最短路径问题，了解迪杰斯特拉算法。了解带权有向图中每一对顶点之间的最短路径问题，了解弗洛伊德算法。 （三） 实践环节 采用邻接矩阵存储结构建立图类，实现最短路径、图的深度优先遍历算法。 （四） 教学方法与手段 采用黑板板书和PowerPoint电子教案相结合的方式。 第八章  查找 （一） 目的与要求 1． 熟练掌握静态查找表的查找算法及其实现； 2． 熟练掌握二叉排序树的插入和查找算法及其实现； 3． 掌握散列表的造表方法； 4． 了解散列函数和处理冲突的方法。 （二） 教学内容 第一节 静态查找表 1． 主要内容 查找表的概念，动态查找表、关键字、查找的概念，抽象数据类型静态查找表的定义，顺序表的查找实现；有序表的折半查找实现，查找操作的性能分析，折半查找的性能分析；索引顺序表的分块查找算法。 2． 基本概念和知识点 查找表的概念，动态查找表、关键字、查找的概念，抽象数据类型静态查找表的定义，顺序表的查找实现；有序表的折半查找实现，查找操作的性能分析，折半查找的性能分析；索引顺序表的分块查找算法。 3． 问题与应用（能力要求） 掌握查找表的概念，动态查找表、关键字、查找的概念，顺序表的查找实现；掌握有序表的折半查找实现；熟悉静态树表的查找，静态最优查找树的概念；掌握静态最优查找树的概念。了解索引顺序表的分块查找算法。     *第二节  动态查找表（选学） 1． 主要内容 动态查找表的特点，抽象数据类型动态查找表的定义，二叉排序树的概念，二叉排序树的查找过程，二叉排序树的插入和删除，平衡二叉树（AVL）的概念，平衡树的生成过程，二叉排序树的平衡旋转图例； B－树的概念，B－树查找分析，B－树的插入和删除，B+树的概念；数字查找树的概念，数字查找树的2种存储结构，在双链树中查找记录的操作算法，Trie树的查找算法。 2． 基本概念和知识点 动态查找表的特点，抽象数据类型动态查找表的定义，二叉排序树的概念，二叉排序树的查找过程，二叉排序树的插入和删除，平衡二叉树（AVL）的概念，平衡树的生成过程，二叉排序树的平衡旋转图例； B－树的概念，B－树查找分析，B－树的插入和删除，B+树的概念；数字查找树的概念，数字查找树的2种存储结构，在双链树中查找记录的操作算法，Trie树的查找算法。 3． 问题与应用（能力要求） 熟悉抽象数据类型动态查找表的定义，二叉排序树的概念，二叉排序树的查找过程，平衡二叉树（AVL）的概念；熟悉抽象数据类型动态查找表的定义，二叉排序树的概念，二叉排序树的查找过程，平衡二叉树（AVL）的概念，B－树的概念，B－树查找分析，B+树的概念。了解数字查找树的概念，了解键树的2种存储结构，了解Trie树的查找算法。 第三节  哈希表 1． 主要内容 哈希表、哈希函数的概念。哈希函数的6种构造方法：即直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法；哈希造表处理冲突的4种方法，即开放地址法、再哈希法、链地址法和建立一个公共溢出区；哈希造表处理冲突的4种方法，即开放地址法、再哈希法、链地址法和建立一个公共溢出区。以开放定址等方法处理冲突的哈希表的查找算法，哈希表查找的分析。 2． 基本概念和知识点 哈希表、哈希函数的概念；哈希函数的6种构造方法；哈希造表处理冲突的4种方法；哈希造表处理冲突的4种方法。以开放定址等方法处理冲突的哈希表的查找算法，哈希表查找的分析。 3． 问题与应用（能力要求） 掌握哈希表、哈希函数的概念，熟悉哈希函数的6种构造方法，即直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。熟悉以开放定址等方法处理冲突的哈希表的查找算法。 （三） 实践环节 设计哈希表类，采用除留余数求哈希地址，将学生的信息存储到该地址空间，并且采用线性探测法解决冲突问题。 （四） 教学方法与手段 采用黑板板书和PowerPoint电子教案相结合的方式。 第九章  内部排序 （一） 目的与要求 1． 熟练掌握简单的排序方法的基本思想及排序过程； 2． 掌握各种排序的特点、时间复杂度和空间复杂度。 （二） 教学内容 第一节 概述 1． 主要内容 排序的概念，内部排序和外部排序的概念；建立排序的概念。 2． 基本概念和知识点 排序的概念，内部排序和外部排序的概念；建立排序的概念。 3． 问题与应用（能力要求） 理解内部排序和外部排序的概念。     第二节  插入排序 1． 主要内容 直接插入排序的概念，直接插入排序的算法；折半插入排序的概念和算法，2－路插入排序的概念和算法；希尔排序的概念和算法，缩小增量排序的序列特点。 2． 基本概念和知识点 直接插入排序的概念，直接插入排序的算法；折半插入排序的概念和算法，2－路插入排序的概念和算法；希尔排序的概念和算法，缩小增量排序的序列特点。 3． 问题与应用（能力要求） 掌握直接插入排序的概念；了解直接插入排序的算法；了解折半插入排序的概念和算法，2－路插入排序的概念和算法；了解希尔排序的概念和算法；了解缩小增量排序的序列特点。 *第三节  快速排序（自学） 1． 主要内容 起泡排序的概念和算法，快速排序的概念和算法。 2． 基本概念和知识点 起泡排序的概念和算法，快速排序的概念和算法。 3． 问题与应用（能力要求） 掌握起泡排序的概念和算法，了解快速排序的概念和算法。 （三） 实践环节 编写程序实现简单选择排序、堆排序（或归并排序），进行比较分析。 （四） 教学方法与手段 分组讨论。           五、各教学环节学时分配 教学环节 教学时数 课程内容 讲 课 习 题 课 讨 论 课 实验 其他教学环节 小 计 第一章 绪论 3 0 0 0 0 3 第二章 线性表 6 0 0 6 0 12 第三章 栈和队列 6 0 0 3 0 9 第四章 串 3 0 0 0 0 3 第五章 数组和广义表 6 0 0 3 0 9 第六章 树和二叉树 9 1 0 6（综合性实验） 0 16 第七章 图 9 1 0 0 0 10 第八章 查找 4 0 1 0 0 5 第九章 内部排序 4 0 1 0 0 5 课程设计一周 合计 50 2 2 18 0 72 六、推荐教材和教学参考资源 推荐教材： 殷人昆等编著，数据结构（用面向对象方法与C++描述），北京：清华大学出版社，1999.7。 教学参考资源： （1）严蔚敏、吴伟民，数据结构 (C语言版)，北京：清华大学出版社，2002.7。 （2）Bruno R. Preiss，Data Structures and Algorithms with Object-Oriented Design Patterns in C++，John Wiley & Sons，Inc.，1999.12。 3．Clifford A. Shaffer，A Practical Introduction to Data Structures and Algorithm Analysis，Second Edition, Publishing House of Electronics Industry，2002.1。 七、其他说明 大纲中打星号的部分，教师可根据实际情况选择是否讲解。 大纲修订人： 吴东庆                       修订日期：2007.4.7 大纲审定人： 胡小健                  审定日期：2007.5.28  《数据库原理与应用》 一、课程基本信息 课程代码：110438 课程名称：数据库原理与应用 英文名称：Database Principle and Application 课程类别：专业基础课 学    时：总学时72(含实验学时：18) 学  分：3.5 适用对象：信息与计算科学专业本科生 考核方式：考试(闭卷)、平时成绩占总成绩的30％ 先修课程：离散数学、高级语言程序设计、数据结构 二、课程简介 《数据库原理与应用》是信息与计算科学专业必修课程之一。数据库技术是计算机软件与理论学科的一个重要分支，它研究如何存储、使用和管理数据，有较强的理论性和实用性。随着计算机应用的发展，数据库应用领域已从数据处理、信息管理、事务处理扩大到计算机辅助设计、人工智能、办公信息系统等新的应用领域。 《Database Principle and Application》is one of the required courses of speciality of information and computation. Database techonology is a important branch of computer software and theory. It will be studied in this course that how to storage ,use and manage data. With the development of application of computer, the application area of database including data processing,information management, transaction processing becomes more and more broadly. 三、课程性质与教学目的 本课程将数据库的基本原理和数据库应用系统紧密地联系在一起。主要内容包括数据库系统概述、关系模型、标准查询语言、数据库规范化、数据库设计、数据库保护、数据库新技术和数据库应用系统。在理论讲解中穿插大量教学实例。 基于简明易懂、便于软件实现、鼓励探索的原则介绍数据库原理与应用系统。学生主要掌握数据库基本原理和技术，能灵活和教好地应用现有的数据库管理系统，掌握数据库结构的设计和数据库应用系统的开发方法，数据库设计的方法和工具，学会使用数据库管理系统，并运用于数据库应用系统的开发。 重点掌握下列几方面的知识。     （1）关系数据库。     （2）关系统数据库标准语言SQL。     （3）关系数据库规范化理论。     （4）数据库设计与数据库保护。     （5）数据库新技术。 （6）使用ADO.NET开发应用系统。 四、教学内容及要求 第一章 绪论 （一）目的与要求 1．了解数据和信息的基本含义及它们之间的相互关系； 2．了解数据管理技术的发展历程； 3．理解数据库系统的组成和功能； 4．理解数据库、数据库管理系统和数据库系统的概念及它们之间的联系； 5．掌握数据库系统的三级模式结构及它们之间的映像； 6．了解现实世界、信息世界和数据世界的含义及它们之间的相互关系； 7．理解概念模型和数据模型的相关概念； 8．掌握常见的四种数据模型； 9．了解数据库技术新进展。 （二）教学内容 1．数据库的特点及相关概念。 2．数据管理技术的发展。 3．数据抽象与数据库的三级模式。 4．数据模型。 5．*数据库技术的发展。 （三）实践环节与课后练习 上机了解Access数据库或SQL Server数据库环境。 （四）教学方法与手段 课堂PPT讲解与分组讨论。 第二章 关系数据库 （一）目的与要求 1．掌握关系模型的组成三要素； 2．掌握关系数据库的一些基本概念； 3．掌握如何用关系代数表达式来表达实际查询问题。 （二）教学内容 关系模式在某一时刻对应的关系的集合，通常称之为关系数据库。关系数据库采用关系模型来组织数据。关系模型由关系数据结构、关系操作集合和关系完整性约束三部分组成。关系模型的数学基础是集合理论，在集合代数理念中对“关系”给出了严格的数学定义，而且还支持关系进行各种操作。 本章将从集合论的观点出发，介绍支持关系模型的关系数据库的基本理论，包括关系数据结构、关系操作、关系完整性及关系的运算等。 第一节  关系数据结构及形式化定义 1. 主要内容 关系、关系模式和关系数据库。 2. 基本概念和知识点 关系、关系模式和关系数据库。 3. 问题与应用(能力要求) 理解关系、关系模式和关系数据库。 第二节  关系操作 1. 主要内容 基本的关系操作、关系数据语言的分类。 2. 基本概念和知识点 基本的关系操作、关系数据语言的分类。 3．问题与能力 正确理解和运用基本的关系操作、关系数据语言的分类，会进行相关运算。 第三节  关系模型的完整性 1．主要内容 实体完整性、参照完整性、用户定义完整性。 2. 基本概念和知识点 实体完整性、参照完整性、用户定义完整性。 3．问题与能力 正确理解完整性，完整性的实际意义。 第四节  关系代数 1．主要内容 传统的集合运算、专门的关系运算。 2. 基本概念和知识点 集合运算、关系运算。 3．问题与能力 能通过关系运算查询所需要的数据集合。 *第五节  关系演算（选学） 1．主要内容 元组关系演算、域关系演算、关系数据库语言。 2. 基本概念和知识点 元组关系演算、域关系演算、关系数据库语言。 3．问题与能力 能通过关系运算从表中查询所需要的数据集合。 （三）实践环节与课后练习 上机熟练关系数据的使用及各种运算操作。 （四）教学方法与手段 课堂内多媒体讲解，分组讨论，讲练结合。 第三章 关系数据库标准语言SQL （一）目的与要求 1．了解SQL语言的发展历程、体系结构及组成等； 2．掌握使用SQL语言定义、修改、删除数据库、表、索引等； 3．掌握如何使用SQL语言进行数据查询和数据更新操作； 4．掌握如何使用SQL文创建、删除视图等； 5. 掌握如何使用SQL言语实现数据控制功能； 6. 理解触发器、存储过程； 7. 理解嵌入式SQL的含义和作用。 （二）教学内容 本章主要介绍根据关系运算概念提出的SQL语言。SQL言语是一种介于关系代数与关系演算之间的国际标准语言，其功能包括查询、操作、定义和控制四个方面，是一个通用性极强的关系数据库标准语言。目前，SOL文己被绝大多数商品化关系数据库系统(如Oracle、SQL Server 2000、DB2等)采用。 第一节  SQL概述及特点 1. 主要内容 SQL的发展历程、SQL数据库的体系结构、SQL的组成。 *第二节  学生-课程数据库（自学） 1. 主要内容 学生-课程数据库示例。 第三节  数据定义(DDL) 1. 主要内容 模式的定义与删除；基本表的定义删除与修改；索引的建立与删除。 2．基本概念和知识点 模式的定义与删除；基本表的定义删除与修改；索引的建立与删除。 3．问题与能力 熟练掌握模式的定义与删除；基本表的定义删除与修改；索引的建立与删除。 第四节  数据查询 1．主要内容 单表查询；连接查询；嵌套查询；集合查询。 2．基本概念和知识点 单表查询；连接查询；嵌套查询；集合查询。 3．问题与能力 熟练掌握单表查询；连接查询；嵌套查询；集合查询。 第五节  数据更新 1．主要内容 插入数据；修改数据；删除数据。 2．基本概念和知识点 插入数据；修改数据；删除数据。 3．问题与能力 要求能够熟练地在数据库的表中插入数据；修改数据；删除数据。 第六节  视图 1．主要内容 定义视图；查询视图；更新视图；视图的作用。 2．基本概念和知识点 定义视图；查询视图；更新视图；视图的作用。 3．问题与能力 要求能够熟练定义视图、查询、更新视图。 （三）实践环节与课后练习 上机熟练数据库、视图及各种表的创建、删除更新等各种运算操作。 （四）教学方法与手段 课堂内多媒体讲解，分组讨论，讲练结合。上机进行实践操作。 第四章 数据库安全性 （一）目的与要求 1．了解计算机系统的安全性问题； 2．理解数据库安全性控制； 3．了解视图机制、审计、数据加密与统计数据库安全性。 （二）教学内容 *第一节  计算机安全性概述（选学） 1.  主要内容 系统的三类安全性问题、安全标准简介。 2. 基本概念和知识点 系统的三类安全性问题、安全标准简介。 3．问题与能力 了解系统的三类安全性问题、安全标准简介。 第二节  数据库安全性控制 1. 主要内容 用户标识与鉴别、存取控制；自主存取控制方法、授权与回收、数据库角色与强制存取控制。 2. 基本概念和知识点 用户标识与鉴别、存取控制；自主存取控制方法、授权与回收、数据库角色与强制存取控制。 3．问题与能力 理解用户标识与鉴别、存取控制；自主存取控制方法、授权与回收、数据库角色与强制存取控制。 *第三节  视图机制 1．主要内容 视图机制。 2. 基本概念和知识点 视图机制。 3．问题与能力 理解视图机制。 （三）课后练习 上机熟练视图及各种表的创建、删除更新操作。 （四）教学方法与手段 课堂内多媒体讲解，针对一具体案例进行分组讨论，讲练结合。 第五章 数据库完整性 （一）目的与要求 1．理解实体完整性、参照完整性及用户完整性； 2．了解完整性约束命名子句； 3．了解触发器。 （二）教学内容 第一节  实体完整性 1.  主要内容 实体完整性的定义、实体完整性检查和违约。 2. 基本概念和知识点 实体完整性的定义、实体完整性检查和违约。 3．问题与能力 理解实体完整性的定义、实体完整性检查和违约。 第二节  参照完整性 1. 主要内容 参照完整性定义。 2. 基本概念和知识点 参照完整性定义。 3．问题与能力 理解参照完整性定义。 第三节  用户定义的完整性 1．主要内容 属性上的约束条件的定义、检查和违约处理；元组上的约束条件、检查和违约。 2. 基本概念和知识点 属性上的约束条件的定义、检查和违约处理；元组上的约束条件、检查和违约。 3．问题与能力 理解属性上的约束条件的定义、检查和违约处理；元组上的约束条件、检查和违约。 *第四节  完整性约束命名子句（选学） *第五节  域中的完整性限制（选学） 第六节  触发器 1．主要内容 定义触发器、激活触发器、删除触发器。 2. 基本概念和知识点 定义触发器、激活触发器、删除触发器。 3．问题与能力 要求理解定义触发器、激活触发器、删除触发器。 （三）课后练习 上机熟练使用触发器、视图及各种表相关操作，设置相关完整性约束。 （四）教学方法与手段 课堂内多媒体讲解，针对一具体案例进行分组讨论，讲练结合。 第六章 关系数据理论 （一）目的与要求 1．理解关系模式中数据冗余和更新异常产生的根源； 2．掌握函数依赖、多值依赖和码的概念； 3．掌握1NF、2NF、3NF和BCNF的含义、联系与区别； 4．了解4NF的概念； 5. 了解关系模式的分解原则和分解算法。 （二）教学内容 在设计数据库时如何将数据正确的颁到数据库的表中。本章将介绍关系模式规范化的必要性、关系数据库规范化理论的基本概念和方法以及一些需要注意并力求避免的常见问题。 第一节  问题的提出 1.  主要内容 以实例说明关系模式的属性之间存在复杂的决定关系，会产生插入异常、删除异常、数据冗余和数据更新方面的问题。 第二节  规范化 1. 主要内容 函数依赖、码、范式。 2. 基本概念和知识点 函数依赖、码、范式。 3．问题与能力 理解函数依赖、码、范式。 *第三节  数据依赖的公理系统（选学） *第四节  关系模式的分解算法（选学） （三）课后练习 上机熟练使用规范化理论来设计模式。 （四）教学方法与手段 课堂内多媒体讲解，针对一具体案例进行分组讨论，讲练结合。 第七章 数据库设计 （一）目的与要求 1．了解数据目标、方法和步骤； 2．理解需求分析的任务、内容和步骤； 3．理解概念结构的设计方法与步骤； 4．理解逻辑结构设计的任务和步骤； 5. 了解物理设计的内容； 6. 了解数据库实施阶段的工作； 7. 了解数据库运行与维护阶段的工作； 8. 重点掌握数据流图、数据字典、E-R模型设计及E-R模型向关系模型的转换。 （二）教学内容 第一节  数据库设计概述 1. 主要内容 数据库设计的任务、内容和特点，数据库设计方法与基本步骤。 各级模式。 第二节  需求分析 1. 主要内容 需求分析的方法、具体步骤、数据流图与数据字典。 2. 基本概念和知识点 需求分析的方法、具体步骤、数据流图与数据字典。 3．问题与能力 要求熟练掌握方法、需求分析，针对具体案例绘出数据流图，给出数据字典。 第三节  概念结构的设计 1．主要内容 概念结构概述，数据抽象与局部视图设计，全局概念结构设计。 2. 基本概念和知识点 概念结构，数据抽象与局部视图，全局概念结构设计。 3．问题与能力 要求熟练掌握概念结构的设计。 第四节  逻辑结构设计 1．主要内容 E-R图向关系模型的转换，用关系规范化理论优化关系数据模型，设计用户子模式。 2. 基本概念和知识点 E-R图向关系模型的转换，用关系规范化理论优化关系数据模型。 3．问题与能力 要求熟练掌握逻辑结构设计。 *第五节  数据库的物理设计（自学） 1.  主要内容 确定数据库的物理结构，物理结构的评价，SQL Server 2000中具体物理设计。其中数据库的物理设计包括数据库设计、表设计、约束设计、视图设计、安全性实现、业务规则的实现。 2. 基本概念和知识点 数据库设计、表设计、约束设计、视图设计、安全性实现、业务规则。 3．问题与能力 要求理解数据库的物理结构，能独立设计数据库。 *第六节  数据库实施与维护（自学） 1. 主要内容 定义数据库结构、组织数据入库、编制与调试应用程序、数据库试运行。 2. 基本概念和知识点 数据库结构、组织数据入库、编制与调试应用程序、数据库试运行。 3．问题与能力 独立设计数据库，独立设计调试应用程序，并进数据库访问控制。 （三）实践环节与课后练习 要求进行数据库的需求分析与数据库的详细设计。综合案例分析。 （四）教学方法与手段 课堂内多媒体讲解，分组讨论，讲练结合。上机进行实践操作。 第八章 数据库编程 （一）目的与要求 1．熟练嵌入式SQL； 2．理解存储过程； 3. 了解ODBC编程。 （二）教学内容 第一节  嵌入式SQL 1. 主要内容 嵌入式SQL的处理过程、式嵌入式SQL语句与主语言之间的通信。 *不用游标的SQL语句与使用游标的SQL语句（选学）。 *动态SQL（选学）。 2. 基本概念和知识点 嵌入式SQL的处理过程、式嵌入式SQL语句与主语言之间的通信。 3．问题与能力 掌握嵌入式SQL的处理过程、式嵌入式SQL语句与主语言之间的通信。 *第二节  存储过程（选学） 1. 主要内容 PL/SQL的块结构、变量常量的定义、控制结构、存储过程。 2. 基本概念和知识点 PL/SQL的块结构、变量常量的定义、控制结构、存储过程。 3．问题与能力 要求了解PL/SQL的块结构、变量常量的定义、控制结构、存储过程。 *第三节 ODBC编程（自学） 1．主要内容 数据库互连概述、ODBC工作原理、API基础，ODBC的工作流程。 2. 基本概念和知识点 数据库互连概述、ODBC工作原理、API基础，ODBC的工作流程。 3．问题与能力 要求了解数据库互连概述、ODBC工作原理、API基础，ODBC的工作流程。 （三）实践环节与课后练习 要求上机进行数据库的ODBC数据库访问实践练习。 （四）教学方法与手段 课堂内多媒体讲解，分组讨论，讲练结合。上机进行实践操作。 第九章  关系查询处理和查询优化 （一）目的与要求 1．了解关系数据库系统的查询处理； 2．理解关系数据库系统的查询优化； 3．理解代数优化； 4．了解物理优化。 （二）教学内容 第一节  关系数据库系统的查询处理 1. 主要内容 查询处理步骤、实现查询操作的算法示例。 2. 基本概念和知识点 查询处理步骤、实现查询操作的算法。 3．问题与能力 要求理解查询处理步骤、实现查询操作的算法。 第二节  关系数据库系统的查询优化 1. 主要内容 查询优化概述、优化实例。 2. 基本概念和知识点 查询优化概述、优化实例。 3．问题与能力 要求理解查询优化。 *第三节  代数优化（选学） 1．主要内容 关系代数表达式等价变换规则、查询树的启发式优化。 2. 基本概念和知识点 关系代数表达式等价变换规则、查询树的启发式优化。 3．问题与能力 要求理解关系代数表达式等价变换规则、查询树的启发式优化。 *第四节  物理优化（自学） 1．主要内容 基于启发式规则的存取路径选择优化、基于代价的优化。 2. 基本概念和知识点 基于启发式规则的存取路径选择优化、基于代价的优化。 3．问题与能力 理解基于启发式规则的存取路径选择优化、基于代价的优化。 （三）实践环节与课后练习 综合案例分析。 （四）教学方法与手段 课堂内多媒体讲解，分组讨论，讲练结合。上机进行实践操作。 第十章  数据库恢复技术 （一）目的与要求 1．理解事务的基本概念； 2．了解故障的种类； 3．了解恢复的实现技术； 4．了解恢复策略 （二）教学内容 第一节  事务的基本概念 1. 主要内容 事务的基本概念。 2. 基本概念和知识点 事务及其基本概念。 3．问题与能力 要求熟练掌握事务的基本概念。 *第二节  数据库的恢复概述（自学） 1. 主要内容 数据库的恢复。 2. 基本概念和知识点 数据库的恢复。 3．问题与能力 要求了解数据库的恢复。 *第三节  故障的种类 1．主要内容 故障及其分类。 2. 基本概念和知识点 故障的概念。 3．问题与能力 要求了解故障。 第四节  恢复的实现技术 1．主要内容 数据的转储、登记日志文件。 2. 基本概念和知识点 数据的转储、登记日志文件。 3. 问题与能力 了解据的转储、登记日志文件。 （三）实践环节与课后练习 无。 （四）教学方法与手段 课堂内多媒体讲解，分组讨论，讲练结合。上机进行实践操作。 *第十一章 并发控制（自学） （一）目的与要求 1．了解并发控制、封锁、活锁与死锁； 2．了解并发调度的或串行性。 （二）教学内容 第一节  并发控制概述 1. 主要内容 并发的概念。 2. 基本概念和知识点 并发及其概念。 3．问题与能力 理解并发的概念。 第二节  封锁、活锁与死锁 1. 主要内容 封锁、活锁与死锁的概念。 2. 基本概念和知识点 封锁、活锁与死锁的概念。 3．问题与能力 要求了解封锁、活锁与死锁的概念。 第三节  并发调度的可串行性 1．主要内容 可串行化调度、冲突可串行化调。 2. 基本概念和知识点 可串行化调度、冲突可串行化调。 3．问题与能力 要求了解可串行化调度、冲突可串行化调。 第四节  两段锁 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 与封锁的粒度 1．主要内容 两段锁协议与封锁的粒度的概念。 2. 基本概念和知识点 两段锁协议与封锁的粒度的概念。 3. 问题与能力 了解两段锁协议与封锁的粒度的概念。 （三）实践环节与课后练习 综合案例分析。练习P274，习题8。 （四）教学方法与手段 课堂内多媒体讲解，分组讨论，讲练结合。课程设计。 五、各教学环节学时分配 教学环节 教学时数 课程内容 讲 课 习 题 课 讨 论 课 实验 其他教学环节 小 计 第一章 3 3 第二章 9 9 第三章 12 3 15 第四章 9 9 第五章 9 3 12 第六章 6 3 9 第七章 3 3 第八章 3 3 第九章 第十章 第十一章 综合性实验（综合性实验，学生自主设计完成）   9   9 课程设计（综合性实验，学生自主设计完成） 一周 合计 54 18 72 六、推荐教材和教学参考资源 推荐教材（“十五”国家级规划教材）： 王珊 萨师煊，数据库系统概论，第四版，高等教育出版社。 刘国燊，数据库技术基础及应用，电子工业出版社。 教学参考资源： 张健沛，数据库原理及应用系统开发，中国水利水电出版社，1998年4月。   七、其他说明      大纲中打星号的部分，教师可根据实际情况选择是否讲解。 大纲修订人：  胡小健                    修订日期：2007.4.8 大纲审定人：  吴东庆                    审定日期：2007.4.12 《软件工程》课程教学大纲 一、课程基本信息 课程代码：110425 课程名称：软件工程 英文名称：Software Engineering 课程类别：专业基础课 学    时：72 学    分：3.5 适用对象：信息与计算科学、计算机、信息管理等专业本科 考核方式：考试（闭卷），平时成绩占总成绩的30% 先修课程：离散数学、高级语言程序设计、数据结构、算法分析与设计、数据库原理与应用 二、课程简介 中文简介：软件工程是研究和指导软件开发和维护的工程类学科，它以计算机科学理论及其他相关学科的理论为指导，采用工程化的概念、原理、规范、技术和方法进行软件工程项目的开发和维护，把经过实践证明正确的管理措施和当前能够得到最好的技术方法结合起来，以较少的代价获取高质量的软件产品。通过40余年的努力，软件工程已逐步发展成为一门成熟的专业学科。 软件工程作为一门专业主干课，重点要求学生学习与软件开发和维护有关的四个方面的主要内容——过程与模型、方法与技术、工具与环境、标准与规范。进而通过课程实践培养学生运用软件工程基本原理解决实际问题，并从事复杂软件项目开发和维护的实践应用能力与创新能力，努力成为当今信息社会和知识经济时代所需要的高素质计算机专业人才。 Brief introduction of English: The soft project is project discipline of studying and guiding software development and safeguarding, it regards the scientific theory of the computer and the theories of other relevant disciplines as guidance, adopt project concept , principle , norm , technology and method to carry on the development and maintenance of the software project, can receive through control measures that practice justify best technological method conbine together at present, obtain the high-quality software product with less cost. Through the efforts of more than 40 years, the soft project has already developed into a ripe professional discipline progressively . Soft project as each professional for backbone lesson,especially it require student study with software development and not maintaining about content not main of respect of four pieces - -Course and model , method and technology , tool and environment , standard and norm. And then train students to use the basic principle of the soft project to solve the practical problem through the course practice, practice engaged in the project of the complicated software and develop and maintain uses ability and innovation ability, nowadays make great efforts to become the information-intensive society and high-quality computer qualified personnel needed in era of knowledge-driven economy. 三、课程性质与教学目的 本课程是信息与计算科学专业的专业主干课。通过本课程的学习，使学生初步建立工程化意识，学会用工程化思想（包括技术、方法与环境）开发各种软件，以软件的生命周期作为主线，掌握软件工程的基本理论，进一步系统化、工程化，为今后实际工程中能够进行系统分析与设计奠定良好的基础。 通过本课程的教学,应使学生达到以下要求: 1.熟练掌握软件与软件工程基本概念和基本知识。 2.熟练掌握生存周期与软件开发模式。 3.掌握结构化程序设计的编程思想。 4.掌握面向对象分析、设计与编码方法。 5.掌握有关软件的评审、测试与维护，项目计划与项目管理方法。 6. 能用软件工程的方法参与软件项目的分析、设计、实现和维护。 四、教学内容及要求 第一章  软件工程基础 （一）目的与要求 1、使学生了解软件和软件工程的基本概念； 2、了解软件及软件工程的发展历史； 3、软件生命周期及软件开发的各个模型。 （二）教学内容 第一节 计算机系统工程 1．主要内容 硬件与硬件工程、软件与软件工程、人机工程、数据库工程、网络工程。 2．基本概念和知识点 硬件、硬件工程、软件、人机工程、数据库工程、网络工程。 3．问题与应用（能力要求） 了解信息化建设中的主要工程及其特点。 第二节 软件工程 1．主要内容 软件工程的概念、软件生命周期、软件开发模型。 2．基本概念和知识点 软件工程、软件生存周期与软件开发模型。 3．问题与应用（能力要求） 掌握软件生存周期中各阶段的内容和特点，软件开发模型的特点和使用。 第三节 软件生存期模型 1．主要内容 软件生存期模型基础、瀑布模型、原型模型、螺旋模型、基于四代技术模型、喷泉模型、增量模型。 2．基本概念和知识点 软件生存期模型基础、瀑布模型、原型模型、螺旋模型、喷泉模型、增量模型。 3．问题与应用（能力要求） 理解各种模型的特点和适用情况。 第四节 软件开发方法 1．主要内容 结构化方法、面向数据结构方法、面向对象方法、原型法。 2．基本概念和知识点 结构化方法、面向数据结构方法、面向对象方法、原型法。 3．问题与应用（能力要求） 掌握不同软件的开发应该采用的开发方法及各种方法的特点对比。 第五节 软件工程环境 1．主要内容 软件工程环境的定义、软件开发环境的特点。 2．基本概念和知识点 软件工程环境。 3．问题与应用（能力要求） 软件工程环境包含的要素及各要素的含义。 （三）实践环节与课后练习 要求学生查阅相关读物以加深了解。 （四）教学方法与手段 课堂讲授、课后分组讨论书上练习题。 第二章 软件项目管理基础 （一）目的与要求 1．了解项目管理的重要性； 2．掌握软件项目管理的基本概念和活动。 （二）教学内容 第一节 软件项目管理概述 1．主要内容 软件项目管理的概述。 2．基本概念和知识点 软件项目管理。 3．问题与应用（能力要求） 掌握软件项目管理的概念。 第二节 软件项目管理的基本概念 1．主要内容 任务和活动、工作产品、工作包和角色、工作分解结构、任务模型、技能矩阵、组织、呈现组织结构、软件项目管理计划。 2．基本概念和知识点 任务和活动、工作分解结构、任务模型、技能矩阵、软件项目管理计划。 3．问题与应用（能力要求） 掌握软件项目管理中的主要概念，掌握工作分解结构、技能矩阵任务模型的画法，掌握软件项目管理计划的编写方法。 第三节 软件项目管理活动 1．主要内容 计划项目、组织项目、控制项目、终结项目。 2．基本概念和知识点 计划项目、组织项目、控制项目。 3．问题与应用（能力要求） 了解项目管理各阶段的工作要点和应注意的问题。 （三）实践环节与课后练习 进行项目管理的实验，主要内容是几个项目管理方面图表的分析制作。 （四）教学方法与手段 课堂讲授、分组讨论、上机实践。 第三章  软件需求分析基础 （一）目标与要求 1．了解需求分析的重要性； 2．掌握需求分析的方法； 3．掌握需求分析的任务和原则。 （二）教学内容 第一节 需求分析的概念和原则 1．主要内容 需求分析、需求分析中的沟通方法、分析原则、需求规格说明、评审。 2．基本概念和知识点 需求分析、分析原则、需求规格说明书。 3．问题与应用（能力要求） 掌握需求任务分析的方法和原则。 第二节 传统的软件需求分析基础 1．主要内容 数据流图、数据字典、实体-关系图、状态转换图。 2．基本概念和知识点 数据流图、数据字典、实体-关系图、状态转换图。 3．问题与应用（能力要求） 掌握数据流图、实体-关系图、状态转换图在需求分析阶段的作用和画法，掌握数据字典的描述方法。 （三）实践环节与课后练习 进行数据流图与数据字典的相关实验。 （四）教学方法与手段 课堂讲授、分组讨论、上机实践。 第四章  软件设计基础 （一）目标与要求 1．软件设计的概念与原则、步骤、方法； 2．软件设计文档与评审内容。 （二）教学内容 第一节 软件设计的目标与任务 1．主要内容 软件设计的目标、软件设计的任务。 2．基本概念和知识点 软件设计的目标与任务。 3．问题与应用（能力要求） 掌握软件设计的目标与任务。 第二节 软件设计基本概念 1．主要内容 模块与模块化、抽象与逐步求精、信息隐藏、模块独立性、软件体系结构、程序结构、数据结构。 2．基本概念和知识点 模块与模块化、模块独立性、软件体系结构、数据结构。 3．问题与应用（能力要求） 掌握模块与模块化、抽象与逐步求精、信息隐藏、模块独立性的概念和思想，模块独立性原理，了解软件体系结构、程序结构、数据结构的概念和原理。 第三节 软件设计规则 1．主要内容 软件设计规则。 2．基本概念和知识点 软件设计规则。 3．问题与应用（能力要求） 了解软件设计规则规则。 第四节 软件设计的启发式原则与优化要求 1．主要内容 启发式原则。 2．基本概念和知识点 启发式原则、优化要求。 3．问题与应用（能力要求） 掌握启发式原则，了解优化要求。 第五节 设计规格说明书与设计复审 1．主要内容 设计规格说明书、设计复审。 2．基本概念和知识点 设计规格说明书、设计复审。 3．问题与应用（能力要求） 掌握设计规格说明书的格式和编制方法，了解设计复审的内容、依据和方法。 （三）实践环节与课后练习 通过具体的项目实验来检验和加深学生对设计规格说明书的掌握。 （四）教学方法与手段 课堂讲授、分组讨论、上机实践。 第五章  软件体系结构设计 （一）目标与要求 1．了解软件体系结构设计的要求； 2．软件体系结构设计方法； 3．软件体系结构设计设计规格说明与评审。 （二）教学内容 第一节 软件体系结构 1．主要内容 软件体系结构的概念、为什么软件体系结构重要。 2．基本概念和知识点 软件体系结构。 3．问题与应用（能力要求） 掌握软件体系结构，理解软件体系结构的重要性。 *第二节 数据体系结构设计（选学） 1．主要内容 数据体系结构设计。 2．基本概念和知识点 数据体系结构。 3．问题与应用（能力要求） 掌握数据体系结构设计的方法。 第三节 软件体系结构风格 1．主要内容 软件体系结构风格。 2．基本概念和知识点 软件体系结构风格。 3．问题与应用（能力要求） 了解不同软件体系结构的风格。 *第四节 软件体系结构中的技术（选学） 1．主要内容 软件体系结构的开发技术、软件分治策略、软件可变性和依赖性管理、集成管理。 2．基本概念和知识点 共性和可变性分析、可变设计、程序生成技术、软件分治策略、依赖性管理、集成管理。 3．问题与应用（能力要求） 理解软件体系结构的各种开发技术、不同的软件分治策略，了解软件可变性和依赖性管理、集成管理。 第五节 将需求映射到软件体系结构 1．主要内容 变换流、事务流。 2．基本概念和知识点 变换流、事务流。 3．问题与应用（能力要求） 掌握变换流、事务流的概念和特点。 第六节 面向数据流方法设计过程 1．主要内容 变换映射、事务映射、体系结构设计求精。 2．基本概念和知识点 变换映射、事务映射、设计求精。 3．问题与应用（能力要求） 掌握变换映射、事务映射的方法和步骤、掌握体系结构设计求精的方法和原则。 （三）实践环节与课后练习 通过数据流图转化体系结构的实验加深学生对所学知识的理解。 （四）教学方法与手段 课堂讲授、上机实践。 *第六章  人机交互界面设计（选学） （一）目标与要求 1．理解人机设计界面的重要性； 2．了解人机设计界面设计的历史和未来发展方向； 3．掌握人机设计界面的过程、原则和标准。 （二）教学内容 第一节 人机界面设计的历史、现状和未来 1．主要内容 人机界面设计的历史、人机界面的现状、人机界面的未来。 2．基本概念和知识点 人机界面。 3．问题与应用（能力要求） 掌握人机界面的概念，了解人机界面设计的历史、人机界面的现状、人机界面的未来。 第二节 人的因素 1．主要内容 人类感知基础、用户技巧、任务与用户的特殊要求。 2．基本概念和知识点 用户技巧、任务，用户的特殊要求。 3．问题与应用（能力要求） 了解人类感知基础，理解用户技巧、任务与用户的特殊要求。 第三节 人机界面风格 1．主要内容 人机界面风格。 2．基本概念和知识点 人机界面风格。 3．问题与应用（能力要求） 了解观察人机界面风格的不同角度，了解人机界面风格的发展。 第四节 人机界面设计过程 1．主要内容 界面设计的模型、任务分析与建模、界面设计的一般问题、构造界面原则、界面设计的评估。 2．基本概念和知识点 界面设计的模型与建模、界面设计的一般问题、构造界面原则、界面设计的评估。 3．问题与应用（能力要求） 掌握界面设计的任务分析与建模方法、了解界面设计的一般问题、掌握构造界面原则、理解界面设计的评估方法。 第五节 人机界面设计的原则与标准 1．主要内容 界面设计原则、界面设计标准。 2．基本概念和知识点 界面设计原则与标准。 3．问题与应用（能力要求） 掌握界面设计原则与标准。 （三）实践环节与课后练习 通过具体的项目实验加深对人机界面设计相关内容的掌握。 （四）教学方法与手段 课堂讲授、分组讨论、上机实践。 *第七章  构件级设计与实现 （一）目标与要求 1．了解常用程序设计语言的特性； 2．了解程序设计语言的基本机制； 3． 学习养成良好的程序设计风格； 4． 学会根据实际情况选择语言。 （二）教学内容 第一节 程序设计语言的特性 1．主要内容 心理特性、工程特性。 2．基本概念和知识点 心理特性、工程特性。 3．问题与应用（能力要求） 了解程序设计语言的心理特性、工程特性。 第二节 程序设计语言的基本机制 1．主要内容 对象说明、数据类型的定义、子程序和方法、控制结构。 2．基本概念和知识点 对象说明、数据类型的定义、子程序和方法、控制结构。 3．问题与应用（能力要求） 掌握程序设计语言的基本机制。 第三节 程序设计风格 1．主要内容 命名、表达式和语句、程序注释、输入与输出。 2．基本概念和知识点 如何命名、如何写好表达式和语句、任何进行程序注释、如何编写输入与输出程序段。 3．问题与应用（能力要求） 掌握如何命名、如何写好表达式和语句、任何进行程序注释、如何编写输入与输出程序段。 第四节 程序设计语言的选择 1．主要内容 程序设计语言的分类、程序设计语言的选择、程序设计支持环境； 2．基本概念和知识点 程序设计语言的分类、选择，程序设计支持环境； 3．问题与应用（能力要求） 掌握程序设计语言的分类，能够根据实际情况合理地选择语言，程序设计支持环境的要领。 （三）实践环节与课后练习 通过综合性实验加深构件级设计的知识理解。 （四）教学方法与手段 课堂讲授、分组讨论、上机实践。 *第八章  面向对象的概念和记号（选学） （一）目标与要求 1．掌握面向对象的概念和思想； 2．掌握面向对象的建模的记号。 （二）教学内容 第一节 面向对象的概念 1．主要内容 对象概念、类及其它关系概念。 2．基本概念和知识点 对象、类、实例、消息、方法、属性、封装、继承、多态性及重载。 3．问题与应用（能力要求） 掌握面向对象及其常用概念。 第二节 面向对象建模中的记号 1．主要内容 用例图、类图、交互图、状态图、活动图。 2．基本概念和知识点 用例图、类图、交互图、状态图、活动图。 3．问题与应用（能力要求） 掌握用例图、类图、交互图、状态图、活动图的作用及画法。 （三）实践环节与课后练习 通过实验来熟悉面向对象及其常用图的画法。 （四）教学方法与手段 课堂讲授、分组讨论、上机实践。 *第九章  面向对象的需求获取和需求分析（选学） （一）目标与要求 1．掌握面向对象的需求获取的方法； 2．掌握面向对象的需求获取的管理方法。 （二）教学内容 第一节 面向对象的需求获取概述 1．主要内容 对需求获取的总的看法、需求获取概念。 2．基本概念和知识点 需求获取的总的看法、需求获取概念。 3．问题与应用（能力要求） 掌握需求获取的活动和过程。 第二节 需求获取活动 1．主要内容 标识参与者、标识场景、标识用例、求精用例、标识参与者和用例之间的关系、标识初始的分析对象、标识非功能需求。 2．基本概念和知识点 标识参与者、标识场景、标识用例、求精用例、标识参与者和用例之间的关系、标识初始的分析对象、标识非功能需求。 3．问题与应用（能力要求） 了解需求获取的主要步骤。 第三节 需求获取管理 1．主要内容 “客户谈判规格说明：联合应用设计”、追踪性维护、需求获取的书面说明。 2．基本概念和知识点 “客户谈判规格说明：联合应用设计”、追踪性维护、需求获取的书面说明。 3．问题与应用（能力要求） 掌握需求获取管理的方法货物和维护。 第四节 面向对象分析 1．主要内容 分析的概述、分析的概念、分析活动：从用例导出对象。 2．基本概念和知识点 分析、分析活动：从用例导出对象。 3．问题与应用（能力要求） 掌握面向对象分析的概念和主要活动。 （三）实践环节与课后练习 安排学生课外通过查阅资料进一步熟悉面向对象的分析方法。 （四）教学方法与手段 课堂讲授、分组讨论。 *第十章  面向对象设计（自学） （一）目标与要求 1．掌握用面向对象的思想进行系统设计； 2．掌握面向对象目标贯彻。 （二）教学内容 第一节 面向对象的系统设计 1．主要内容 系统设计概述、系统设计概念、系统设计活动：从对象到子系统。 2．基本概念和知识点 系统设计、系统设计活动：从对象到子系统。 3．问题与应用（能力要求） 掌握面向对象的系统设计。 第二节 面向对象目标贯彻 1．主要内容 面向对象设计的目标贯彻、系统设计活动概述、UML部署图、系统设计活动中的设计目标贯彻、管理系统设计。 2．基本概念和知识点 面向对象设计的目标贯彻、系统设计活动、UML部署图、系统设计活动中的设计目标贯彻、管理系统设计。 3．问题与应用（能力要求） 掌握如何进行面向对象设计的目标贯彻。 第三节 面向对象的对象设计 1．主要内容 使用模式设计对象、对象设计总论、重用中的概念：解对象、继承和设计模式。 2．基本概念和知识点 使用模式设计对象、对象设计总论、重用中的概念：解对象、继承和设计模式。 3．问题与应用（能力要求） 掌握如何进行面向对象的对象设计。 第四节 接口设计 1．主要内容 接口规格说明综述、接口规格说明概述、接口规格说明活动、管理对象设计。 2．基本概念和知识点 接口规格说明综述、接口规格说明概述、接口规格说明活动、管理对象设计。 3．问题与应用（能力要求） 掌握如何进行接口设计。 （三）实践环节与课后练习 自行上机练习。 （四）教学方法与手段 自学。 第十一章  软件测试 （一）目标与要求 1．掌握软件质量保证的概念、策略和方法，软件评审或测试的方法和步骤； 2．掌握软件测试过程。 （二）教学内容 第一节 导言 1．主要内容 软件测试的意义、基本概念、软件测试的定义、目的、原则和研究对象、软件测试的发展历史及趋势。 2．基本概念和知识点 软件测试、软件测试目的、原则和研究对象、软件测试的发展历史及趋势。 3．问题与应用（能力要求） 理解软件测试的意义、基本概念、软件测试的定义、目的、原则和研究对象，了解软件测试的发展历史及趋势。 第二节 软件审查活动概述 1．主要内容 审查过程、审查过程实施。 2．基本概念和知识点 审查过程、审查过程实施。 3．问题与应用（能力要求） 了解软件审查活动的过程和实施方法。 *第三节 软件质量度量（选学） 1．主要内容 实施软件度量程序的策略、软件质量度量框架、有助于软件确认活动的度量。 2．基本概念和知识点 软件度量程序的策略、软件质量度量框架。 3．问题与应用（能力要求） 掌握软件质量度量的方法。 第四节 基本测试方法 1．主要内容 静态测试、动态测试、测试用例设计实例。 2．基本概念和知识点 静态测试、动态测试、测试用例的设计。 3．问题与应用（能力要求） 掌握什么是静态测试、动态测试，掌握如何设计测试用例。 第五节 软件测试策略 1．主要内容 单元测试、集成测试、确认测试、系统测试、验收测试、其它测试种类、排错。 2．基本概念和知识点 单元测试、集成测试、确认测试、系统测试、验收测试、其它测试种类、排错。 3．问题与应用（能力要求） 掌握常见软件测试策略、步骤。 *第六节 面向对象软件测试的基本思想（自学） 1．主要内容 测试面向对象软件的特殊性、面向对象软件的测试。 2．基本概念和知识点 测试面向对象软件的特殊性。 3．问题与应用（能力要求） 掌握如何进行面向对象软件的测试。 （三）实践环节与课后练习 通过综合性实验练习软件测试的策略和步骤。 （四）教学方法与手段 课堂讲授、分组讨论、上机实践。 第十二章  软件维护 （一）目标与要求 1．掌握软件维护的分类、策略、过程及模型； 2．了解软件维护的度量方法； 3. 了解软件维护的副作用。 （二）教学内容 第一节 软件维护概述 1．主要内容 软件维护及分类、软件维护成本、软件维护策略。 2．基本概念和知识点 软件维护及分类、软件维护成本、软件维护策略。 3．问题与应用（能力要求） 掌握软件维护及分类，了解软件维护成本、常用软件维护策略。 *第二节 软件维护过程及其模型（选学） 1．主要内容 软件维护活动、软件维护过程模型。 2．基本概念和知识点 软件维护活动、软件维护过程模型。 3．问题与应用（能力要求） 了解软件维护活动、软件维护过程模型。 *第三节 软件的可维护性及其度量 1．主要内容 软件的可维护性、软件的可维护性度量、提高可维护性的方法。 2．基本概念和知识点 软件的可维护性、软件的可维护性度量、提高可维护性的方法。 3．问题与应用（能力要求） 了解软件的可维护性、软件的可维护性度量、提高可维护性的方法。 第四节 软件维护的副作用 1．主要内容 软件维护的副作用。 2．基本概念和知识点 软件维护的副作用。 3．问题与应用（能力要求） 了解软件维护的副作用。 第五节 软件再工程 1．主要内容 什么是软件再工程、软件再工程过程、软件再工程的方法。 2．基本概念和知识点 软件再工程、软件再工程过程、软件再工程的方法。 3．问题与应用（能力要求） 了解什么是软件再工程、软件再工程过程、软件再工程的方法。 （三）实践环节与课后练习 安排学生查阅相关资料加深理解维护的重要性和方法。 （四）教学方法与手段 课堂讲授、分组讨论。 五、各教学环节学时分配 教学环节 教学时数 讲课 习题课 讨论课 实验 其他教学环节 小计 课程内容 第一章 6 0 0 0 0 6 第二章 6 0 0 3 0 9 第三章 8 0 0 3 0 11 第四章 8 0 0 0 0 8 第五章 5 0 0 3 0 8 第六章 3 0 0 0 0 3 第七章 3 0 0 3 0 6 第八章 3 0 0 0 0 3 第九章 3 0 0 0 0 3 第十章 0 0 0 0 0 0 第十一章 6 0 0 0 0 6 第十二章 3 0 0 0 0 3 个人备忘录系统设计开发（综合设计性实验，学生自主设计完成） 0 0 0 6 0 6 合计 54 0 0 18 0 72 六、推荐和教学参考资源 推荐教材 叶俊民，《软件工程》，北京，清华大学出版社，2006年。 教学参考资源 （1）郑人杰、殷人昆、陶永雷，《实用软件工程（第二版）》，北京，清华大学出版社，1997年； （2）shari Lawrence，软件工程—理论与实践（第二版、影印版） 高等教育出版社 2001年 （3）（美）Joey F.George,Dinesh Batra,Joseph、S.Valacich,Jeffrey A.Hoffer，梁金昆译，《面向对象的系统分析与设计》，北京，清华大学出版社，2003年。 七、其他说明 （一）课程中的综合性实验要求： 1、将所学的软件工程理论知识应用于软件开发实践中去，做到学以致用。 2、把小问题当作大任务来看待，一步一个脚印进行，从而积累开发大工程的经验和方法。各个阶段的文档完整、规范，建模工具使用得当。 3、要求学生采用“项目小组”的形式，结合具体的开发项目进行设计。具体实施的要求如下： 1）每个班级按项目小组进行分组，每组人数在4人左右； 2）每个项目小组选出项目负责人或项目经理（项目经理适当加分），由项目经理召集项目组成员讨论、选定开发项目，项目的选定必须考虑“范围、期限、成本、人员、设备”等条件；项目经理负责完成“可行性研究报告”、制定“项目开发计划”、管理项目并根据项目进展情况对项目开发计划进行调整；对于调整的项目开发计划必须存档； 3）项目开发计划必须具备可行性，每项任务要落实到人且规定该任务的起止日期和时间；明确每个阶段提交文档的日期和时间；每个项目小组必须明确指定文档的审查小组和审查人员以及审查结果的返回日期；审查小组和审查人员不得是完成被审查内容的完成者；审查结果至少包括：存在的问题、出现问题的所在文档的位置及页码、具体建议等；每个阶段的审查结果不得少于6个问题； 4）每个项目小组必须按照给定的文档规范标准提供下列文档，文档中必须注明执笔者、完成者（签名）和完成日期，其中完成需求分析和设计工作的人员不能相同，完成编码和审查/测试的人员不能相同；文档至少包括以下文件中的三个： ● 可行性研究报告 ● 项目开发计划（包括调整的项目开发计划） ● 需求分析规格说明 ● 概要设计规格说明 ● 详细设计规格说明 ● 编码清单（部分或全部） ● 审查/测试问题清单 4、主要仪器设备 ● 硬件设备：微机和打印机 ● 操作系统：Windows 2k以上系统 ● 图文排版：Microsoft Office 2K及其以上系统 ● 软件开发工具：Microsoft Visual Studio、Borland Delphi 等 ● 数据库系统：Microsoft SQL Server 等 ● 建模工具软件：PowerDesigner或者ROSE 5、大纲中打星号的部分，教师可根据实际情况选择是否讲解。 大纲修订人： 王  前                    修订日期：2007.4.9 大纲审定人： 胡小健                    审定日期：2007.5.28 《算法分析与设计》课程教学大纲 一、课程基本信息 课程代码：110426 课程名称：算法分析与设计 英文名称：Analysis and Design of Algorithms 课程类别：专业基础课 学    时：45 学  分：2 适用对象: 信息与计算科学专业本科生 考核方式：考试（平时成绩占总成绩的30％） 先修课程：数学分析、高级语言程序设计、数据结构 二、课程简介 中文简介 《算法分析与设计》是软件开发人员必修专业课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和软件类专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。 英文简介     Analysis and Design of Algorithms is a compulsory specialty course for software developer. Efficiency and stability of software depends on algorithms used in it. For common coders and software relative students, learning this course could expand their programming vision and help them programming high quality codes. 三、课程性质与教学目的 通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。    鼓励学生运用算法知识解决各自学科的实际问题，培养学生的独立科研的能力和理论联系实践的能力。 四、教学内容及要求 第一章  算法概述 (一) 目的与要求 掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。 (二) 教学内容 1. 主要内容 算法，算法复杂度的基本概念，及时间复杂度。 2. 基本概念和知识点 算法，算法复杂度的基本概念，及时间复杂度。 3. 问题与应用（能力要求） 掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。 (三) 课后练习 函数的渐进表达式。 (四) 教学方法与手段 课堂讲授为主，结合课堂分组讨论。 第二章  递归与分治法 （一） 目的与要求 1. 掌握递归的概念，学会用递归方法解决实际问题； 2. 熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。  （二） 教学内容 1． 主要内容 递归概念，分治法基本思想，二分搜索技术，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择，最接近点对问题，循环赛日程表。 2． 基本概念和知识点 递归概念，分治法，二分搜索，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序。 3． 问题与应用（能力要求） 掌握递归的概念，学会用递归方法解决实际问题，熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。 （三） 课后练习 Hanoi塔问题的非递归算法。 （四） 教学方法与手段 课堂讲授为主，结合课堂分组讨论。 第三章  动态规划 （一） 目的与要求 1． 熟练掌握利用动态规划方法解决问题的基本思想； 2． 学会如何将问题化为多阶段图的方法； 3． 能对具体问题写出正确的递推公式。 （二） 教学内容 1． 主要内容 动态规划的基本要素，矩阵连乘，最长公共子序列，最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线，流水作业调度，0-1背包问题，最优二叉搜索树。 2． 基本概念和知识点 动态规划的基本要素，最长公共子序列，最大子段和，凸多边形最优三角剖分,0-1背包问题，最优二叉搜索树。 3． 问题与应用（能力要求） 熟练掌握利用动态规划方法解决问题的基本思想。 （三） 课后练习 最长单调递增子序列。 （四） 教学方法与手段 课堂讲授为主，结合分组课堂讨论。 第四章  贪心算法 （一） 目的与要求 1． 掌握利用贪心算法解决问题的基本思想； 2． 会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。 （二） 教学内容 1． 主要内容 贪心算法的基本要素，活动安排问题，最优装载，哈夫曼编码，单源最短路径，最小生成树，多机调度。 2． 基本概念和知识点 贪心算法，哈夫曼编码，单源最短路径，最小生成树。 3． 问题与应用（能力要求） 掌握利用贪心算法解决问题的基本思想。 （三） 实践环节与课后练习 活动安排问题的贪心选择算法。 （四） 教学方法与手段 课堂讲授为主，结合课堂分组讨论。 第五章  回溯法 （一） 目的与要求 1． 掌握利用回溯法解决问题的基本思想； 2． 会用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等，并能准确地分析回溯法的效率及稳定性。 （二） 教学内容 1. 主要内容 回溯法的算法框架、符号，三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题，圆排列问题，连续邮资问题，电路板排列问题。 2. 基本概念和知识点 回溯法，三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题。 3. 问题与应用（能力要求） 掌握利用回溯法解决问题的基本思想。 （三） 课后练习 装载问题的改进回溯法。 （四） 教学方法与手段 课堂讲授为主，结合课堂分组讨论。 第六章  分支限界法 （一） 目的与要求 1. 掌握利用分支限界法解决问题的基本思想； 2. 能用多种不同方法解法同一问题，并分析各方法的效率。 （二） 教学内容 1． 主要内容 分支限界的基本思想，单源最短路径，布线问题，0－1背包问题，批处理作业调度问题。 2． 基本概念和知识点 分支限界，单源最短路径，布线问题，0－1背包问题，批处理作业调度问题。 3. 问题与应用（能力要求） 掌握分支限界法解决问题的基本思想，能用多种不同方法解法同一问题，并分析各方法的效率。 （三） 实践环节 0-1背包问题的栈式分支限界法。 （四） 教学方法与手段 课堂讲授为主，结合课堂分组讨论。 *第七章  概率算法（选学） （一） 目的与要求 1. 掌握利用概率算法的基本思想； 2. 会用概率算法解决有关问题。 （二） 教学内容 1． 主要内容 概率算法的基本思想，随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法。 2． 基本概念和知识点 概率算法，随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法。 3. 问题与应用（能力要求） 掌握利用概率算法的基本思想,会用概率算法解决有关问题。 （三） 实践环节与课后练习 模拟正态分布随机变量。 （四） 教学方法与手段 课堂讲授为主，结合课堂分组讨论。 *第八章  线性规划和网络流（自学） （一） 目的与要求 1. 了解线性规划模型的特点、线性规划问题的标准型及退化处理； 2. 掌握线性规划问题解的概念、有关解的基本定理； 3. 掌握单纯形法的的原理和求解方法； 4. 掌握实践中常见问题的建模方法； 5. 掌握最大网络流问题的求解方法和最小费用流问题的求解方法。          （二） 教学内容 1． 主要内容 线性规划的基本概念、定理及单纯形算法，最大网络流和最小费用流问题的解法。 2． 基本概念和知识点 线性规划概念、定理及单纯形算法，最大网络流和最小费用流问题的解法。 3. 应用（能力要求） 掌握线性规划问题解的概念、有关解的基本定理；掌握单纯形法的的原理和求解方法；掌握实践中常见问题的建模方法。掌握最大网络流问题的求解方法和最小费用流问题的求解方法。  （三） 实践环节与课后练习 单源最短路径与线性规划。 （四） 教学方法与手段 课堂讲授为主，结合课堂分组讨论。 *第九章  NP完全性理论与近似算法（选学） （一） 目的与要求 1． 了解NP完全性问题； 2． 掌握P类与NP类问题的划分； 3． 掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析。 （二） 教学内容 1． 主要内容 计算模型，P类与NP类问题，NP完全问题，合取范式（CNF）顶点覆盖问题，哈密顿回路问题；近似算法的基本思想及性能，顶点覆盖问题的近似算法，集合覆盖问题的近似算法，子集合问题的近似算法。 2． 基本概念和知识点 计算模型，P类与NP类问题，NP完全问题，合取范式（CNF）顶点覆盖问题，哈密顿回路问题。 3． 问题与应用（能力要求） 了解NP完全性问题,掌握P类与NP类问题的划分。掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析。 （三） 实践环节与课后练习 RAM和RASP程序。 （四） 教学方法与手段 课堂讲授为主，结合课堂分组讨论。           五、各教学环节学时分配 教学环节 教学时数 课程内容 讲 课 习 题 课 讨 论 课 实验 其他教学环节 小 计 第一章  算法概述 3 0 0 0 0 3 第二章  递归与分治法 6 0 0 0 0 6 第三章  动态规划 6 0 0 3 0 9 第四章  贪心算法 6 0 0 0 0 6 第五章  回溯法 6 0 0 3 0 9 第六章  分支限法 6 0 0 0 0 6 第七章  概率算法 3 0 0 0 0 3 第八章  线性规划和网络流 0 0 0 0 0 0 第九章NP完全性理论与近似算法 3 0 0 0 0 3 课程设计一周 合计 39 0 0 6 0   45 六、推荐教材和教学参考资源 推荐教材： 王晓东，计算机算法设计与分析(第二版)，北京：电子工业出版社，2004。 教学参考资源： （1） D．E．Knuth著，管纪文译，计算机程序设计技巧第一卷（1978），第二卷（1982），长沙：国防工业出版社，1978。 （2）卢开澄，计算机算法导引，北京：清华大学出版社，2000。 七、其他说明 大纲中打星号的部分，教师可根据实际情况选择是否讲解。 大纲修订人： 吴东庆                           修订日期：2007.4.9 大纲审定人： 胡小健                        审定日期：2007.5.28 《操作系统原理》课程教学大纲 一、课程基本信息 课程代码：110427 课程名称：操作系统原理 英文名称：Principle of Operating System 课程类别：专业基础课 学    时：54 学    分：3 适用对象：信息与计算科学、计算机、信息管理等专业本科 考核方式：考试（闭卷），平时成绩30%，期末考试占70%。 先修课程：数据结构、高级语言程序设计 二、课程简介 中文简介：《操作系统原理》是信息与计算科学专业的专业基础课，它在计算机知识结构中有着极其重要的地位和作用，可为学生较全面的建立起关于计算机系统的概念。 操作系统是配置在计算机硬件上的第一层软件，是对硬件的第一次扩充。其它所有的系统软件和应用软件都必须依赖于操作系统的支持。本课程从处理机管理，存储管理，设备管理，文件管理和用户接口等角度介绍操作系统的基本原理，并辅以Linux系统为实例。 通过本课程学习，使学生了解什么是操作系统，掌握操作系统的基本原理，实现机制和基本算法，并结合目前的典型操作系统进行具体分析，加深对操作系统基本原理的理解和认识。在教学过程中通过CAI 教学软件的演示及使用，使学生加深对操作系统概念的认识。 Brief introduction of English: <