《命令式计算原理》课程大纲一、课程名称：命令式计算原理二、课程性质：选修、理论课三、学时与学分：32学时，2学分四、课程先导课：C语言程序设计，计算思维，数据结构等五、课程简介“命令式计算原理”是一门关于程序设计方法学的计算机类专业课程，具有很强的理论性、技术性和实践性，在计算机学科系列课程中与程序设计基础、计算思维、数据结构和算法基础等课程紧密相关。课程从计算思维、程序设计技巧和数据结构与算法等三个维度，讲授命令式程序设计方法以及确保程序正确性方法。介绍了利用函数前置条件、函数后置条件、循环不变量、数据结构不变性等来编写程序，对代码进行逻辑上和操作上的严格推理；讨论了在编程中有效使用一些基本的数据结构和算法，包括二分搜索，次二次排序，栈和队列，哈希表，优先队列，平衡二分查找树，特里树，二分决策图，简单图算法等。课程强调对抽象和接口的理解，对顺序计算进行渐进复杂性分析和效率分析。六、课程目标通过相关教学活动，帮助学生掌握命令式程序设计方法，以及通过推理和分析，来确保程序正确性的方法。培养学生计算思维能力，掌握程序设计技能，并掌握基本算法与数据结构的有效使用，用于编程解决实际问题课程的具体目标包括：目标1：理解诸如变量、表达式、循环、数组和函数等基本的程序设计要素，掌握命令式程序设计以及确保程序正确性的方法目标2：培养计算思维，具体包括：对抽象和接口的理解：用合适的数据结构描述事物的属性和状态，用运算模拟事物的变化和相互作用：视代码如数据；目标3：掌握程序设计技能，具体包括：将算法转化成正确的命令式代码；用不变式验证程序的正确性；算法复杂性分析，包括简单的分步分析和对一般复杂性的认识(O(n)，O(n*log(n))，O(n2)，O(2")；对程序静态语义和动态语义的理解；算法设计中分治策略的应用；代码的开发、测试、改写和优化；目标4：掌握基本算法和数据结构的有效使用。包括二分查找、排序、栈和队列，哈希表、优先队列、平衡二叉搜索树、二分决策图，简单的图算法；七、课程目标对毕业要求的支撑关系
《命令式计算原理》课程大纲 一、课程名称：命令式计算原理 二、课程性质：选修、理论课 三、学时与学分：32 学时，2 学分 四、课程先导课：C 语言程序设计，计算思维，数据结构等 五、课程简介 “命令式计算原理”是一门关于程序设计方法学的计算机类专业课程，具有 很强的理论性、技术性和实践性，在计算机学科系列课程中与程序设计基础、计 算思维、数据结构和算法基础等课程紧密相关。课程从计算思维、程序设计技巧 和数据结构与算法等三个维度，讲授命令式程序设计方法以及确保程序正确性方 法。介绍了利用函数前置条件、函数后置条件、循环不变量、数据结构不变性等 来编写程序，对代码进行逻辑上和操作上的严格推理；讨论了在编程中有效使用 一些基本的数据结构和算法，包括二分搜索，次二次排序，栈和队列，哈希表， 优先队列，平衡二分查找树，特里树，二分决策图，简单图算法等。课程强调对 抽象和接口的理解，对顺序计算进行渐进复杂性分析和效率分析。 六、课程目标 通过相关教学活动，帮助学生掌握命令式程序设计方法，以及通过推理和分 析，来确保程序正确性的方法。培养学生计算思维能力，掌握程序设计技能，并 掌握基本算法与数据结构的有效使用，用于编程解决实际问题。 课程的具体目标包括： 目标 1：理解诸如变量、表达式、循环、数组和函数等基本的程序设计要素， 掌握命令式程序设计以及确保程序正确性的方法； 目标 2：培养计算思维，具体包括：对抽象和接口的理解；用合适的数据结 构描述事物的属性和状态，用运算模拟事物的变化和相互作用；视代码如数据； 目标 3：掌握程序设计技能，具体包括：将算法转化成正确的命令式代码； 用不变式验证程序的正确性；算法复杂性分析，包括简单的分步分析和对一般复 杂性的认识(O(n)，O(n*log(n))，O(n 2)，O(2 n))；对程序静态语义和动态语义的理 解；算法设计中分治策略的应用；代码的开发、测试、改写和优化； 目标 4：掌握基本算法和数据结构的有效使用。包括二分查找、排序、栈和 队列，哈希表、优先队列、平衡二叉搜索树、二分决策图，简单的图算法； 七、课程目标对毕业要求的支撑关系
支撑的毕业要求二级指标点对应课程目标3.2掌握程序设计的基本方法、算法设计与分析的基本方法目标14.3能综合应用数学物理知识、自然科学知识、工程知识，并通过文目标2献分析和研究，对本学科的复杂工程问题提出解决问题的思路5.2了解计算机科学与技术工程问题特征，掌握解决本学科复杂工程目标3问题的基本方法5.3具备选择合适的开发工具，设计（开发）满足特定功能要求的软目标3/硬件系统、单元（部件）或工艺流程的能力6.2能正确选择工具，采用科学方法和本学科的专业知识，对本学科目标3的复杂工程问题设计研究方案6.3能正确使用和处理实验或研究数据，通过信息综合处理，对本学目标4科的复杂工程问题进行预测或提出优化方案12.1能认识到计算机技术日新月异的发展特点，认同自主学习和终目标2身学习的必要性12.2具备自主学习能力，能通过多种途径拓展自己的知识和能力，目标2包括理解能力、归纳总结能力和提出问题的能力等八、教学设计及对课程目标的支持第1讲命令式计算原理简介介绍命令式计算的概念，每讲课程教学内容及学时安排，课程学习要求和课程成绩评价方法。第2讲约定与程序推理1.教学目标1）计算思维：算法的描述与实现，程序正确性：2）算法与数据结构：高效率和低效率实现的区别；3）程序设计：约定的概念及表示。本讲教学支持课程目标1、课程目标2和课程目标3。2.教学重点1）函数前置条件、函数后置条件、循环不变量和断言这四种约定的表示和使用；2）如何寻找循环不变量，以及如何证明循环不变量，理解循环不变量如何对函数后置条件其到支撑；3）常用的循环可终止性判断方法；3.教学难点
支撑的毕业要求二级指标点 对应课程目标 3.2 掌握程序设计的基本方法、算法设计与分析的基本方法 目标 1 4.3 能综合应用数学物理知识、自然科学知识、工程知识，并通过文 献分析和研究，对本学科的复杂工程问题提出解决问题的思路 目标 2 5.2 了解计算机科学与技术工程问题特征，掌握解决本学科复杂工程 问题的基本方法 目标 3 5.3 具备选择合适的开发工具，设计（开发）满足特定功能要求的软 /硬件系统、单元（部件）或工艺流程的能力 目标 3 6.2 能正确选择工具，采用科学方法和本学科的专业知识，对本学科 的复杂工程问题设计研究方案 目标 3 6.3 能正确使用和处理实验或研究数据，通过信息综合处理，对本学 科的复杂工程问题进行预测或提出优化方案 目标 4 12.1 能认识到计算机技术日新月异的发展特点，认同自主学习和终 身学习的必要性 目标 2 12.2 具备自主学习能力，能通过多种途径拓展自己的知识和能力， 包括理解能力、归纳总结能力和提出问题的能力等 目标 2 八、教学设计及对课程目标的支持 第 1 讲 命令式计算原理简介 介绍命令式计算的概念，每讲课程教学内容及学时安排，课程学习要求和课 程成绩评价方法。 第 2 讲 约定与程序推理 1. 教学目标 1）计算思维：算法的描述与实现，程序正确性； 2）算法与数据结构：高效率和低效率实现的区别； 3）程序设计：约定的概念及表示。 本讲教学支持课程目标 1、课程目标 2 和课程目标 3。 2. 教学重点 1）函数前置条件、函数后置条件、循环不变量和断言这四种约定的表示和 使用； 2）如何寻找循环不变量，以及如何证明循环不变量，理解循环不变量如何 对函数后置条件其到支撑； 3）常用的循环可终止性判断方法； 3. 教学难点
1）约定的表示和约定的重要性2）利用约定进行推理4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论围绕约定在函数测试上的重要性，循环不变量的确定、循环不变量的证明等问题展开。2）作业围绕循环不变量的使用来布置。3）在线讨论如何判断循环不变量是否足够充分，以足以支撑函数后置条件的正确性。第3讲整数类型1.教学目标1）计算思维：对资源限制的理解：2）算法与数据结构：二进制加法运算，用大小固定的数据结构表示数：3）程序设计：不同范围整数类型的使用。本讲教学支持课程目标1和课程目标2。2.教学重点1）溢出的处理，模运算的性质，向下取整和向零取整：2）二进制补码表示与模运算的内在关联；3）位运算和颜色类型数据的计算；3.教学难点1）模运算里的加法逆元2）溢出的判断4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论在早期的计算机中，机器字的大小通常是8位，后来扩展到16位，现在是32或者64位。为什么对机器字的位宽进行扩展？能否无限扩展？2）作业
1）约定的表示和约定的重要性 2）利用约定进行推理 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 围绕约定在函数测试上的重要性，循环不变量的确定、循环不变量的证明等 问题展开。 2）作业 围绕循环不变量的使用来布置。 3）在线讨论 如何判断循环不变量是否足够充分，以足以支撑函数后置条件的正确性。 第 3 讲 整数类型 1. 教学目标 1）计算思维：对资源限制的理解； 2）算法与数据结构：二进制加法运算，用大小固定的数据结构表示数； 3）程序设计：不同范围整数类型的使用。 本讲教学支持课程目标 1 和课程目标 2。 2. 教学重点 1）溢出的处理，模运算的性质，向下取整和向零取整； 2）二进制补码表示与模运算的内在关联； 3）位运算和颜色类型数据的计算； 3. 教学难点 1）模运算里的加法逆元 2）溢出的判断 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 在早期的计算机中，机器字的大小通常是 8 位，后来扩展到 16 位，现在是 32 或者 64 位。为什么对机器字的位宽进行扩展？能否无限扩展？ 2）作业
围绕循环不变量的使用来布置。3）在线讨论在高级语言中，有人更倾向于认为int类型的整数本质上是无穷大的。能否设计机器字的长度可随着计算过程而改变？基本操作例如加法不再是直接映射到一条机器指令，而是用小程序来实现。而这种开支是否可接受？第4讲数组及其安全访问1.教学目标1）计算思维：程序的安全性定义；2）算法与数据结构：大小固定的数组：3）程序设计：利用数组和循环处理批量数据。本讲教学支持课程目标1和课程目标2。2.教学重点1）数组作为数据聚合体的基本特征：2）程序的安全性定义，及数组使用上的安全性；3）数组的复制和数组别名；3.教学难点1）数组复制和数组别名的理解；2）数组相关的循环不变量；4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论如果数组的越界访问不受限制，将使缓冲区溢出攻击有机可乘，带来哪些信息安全隐患？2）作业围绕数组使用上的安全性来布置。3）在线讨论在使用C语言编程时碰到过哪些不安全的问题？第5讲线性查找1.教学目标
围绕循环不变量的使用来布置。 3）在线讨论 在高级语言中，有人更倾向于认为 int 类型的整数本质上是无穷大的。能否 设计机器字的长度可随着计算过程而改变？基本操作例如加法不再是直接映射 到一条机器指令，而是用小程序来实现。而这种开支是否可接受？ 第 4 讲 数组及其安全访问 1. 教学目标 1）计算思维：程序的安全性定义； 2）算法与数据结构：大小固定的数组； 3）程序设计：利用数组和循环处理批量数据。 本讲教学支持课程目标 1 和课程目标 2。 2. 教学重点 1）数组作为数据聚合体的基本特征； 2）程序的安全性定义，及数组使用上的安全性； 3）数组的复制和数组别名； 3. 教学难点 1）数组复制和数组别名的理解； 2）数组相关的循环不变量； 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 如果数组的越界访问不受限制，将使缓冲区溢出攻击有机可乘，带来哪些信 息安全隐患？ 2）作业 围绕数组使用上的安全性来布置。 3）在线讨论 在使用 C 语言编程时碰到过哪些不安全的问题？ 第 5 讲 线性查找 1. 教学目标
1）计算思维：①开发约定（前提条件、后置条件、断言和循环不变性）来创建安全和正确的命令式程序；②利用有序性（已排序数据）来解决问题；③识别规范和实现之间的区别：2）算法与数据结构：线性查找的描述：3）程序设计：我们在这一讲将练习深度编程。识别、描述和有效地使用“短路”布尔运算。本讲教学支持课程目标2和课程目标3。2.教学重点1）无序数组里的线性查找；2）有序数组里的线性查找；3）分析操作次数；3.教学难点1）有序性的使用；2）利用“短路”布尔运算，避免不安全操作；4.教学环节设计围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教学形式。1）课堂讨论程序正确性和程序效率的重要性。2）作业围绕线性查找算法布置作业题。3）在线讨论在以往编程中，哪些场合利用了“短路”布尔运算来避免不安全操作？第6讲二分查找1.教学目标1）计算思维：理解在不同算法问题中排序所起的作用，及循环不变量在编写正确代码上的重要性：2）算法与数据结构：大小固定数组的二分查找；3）程序设计：深思熟虑的编程，在测试、推理及确保安全与正确性中约定的重要性，利用局部推理来证明程序的正确性。本讲教学支持课程目标1、课程目标2、课程目标3和课程目标4。2.教学重点
1）计算思维：① 开发约定（前提条件、后置条件、断言和循环不变性）来 创建安全和正确的命令式程序；② 利用有序性(已排序数据) 来解决问题；③ 识 别规范和实现之间的区别； 2）算法与数据结构：线性查找的描述； 3）程序设计：我们在这一讲将练习深度编程。识别、描述和有效地使用“短 路”布尔运算。 本讲教学支持课程目标 2 和课程目标 3。 2. 教学重点 1）无序数组里的线性查找； 2）有序数组里的线性查找； 3）分析操作次数； 3. 教学难点 1）有序性的使用； 2）利用“短路”布尔运算，避免不安全操作； 4. 教学环节设计 围绕教学重点和教学难点，综合运用课堂讲授与讨论、作业、在线讨论等教 学形式。 1）课堂讨论 程序正确性和程序效率的重要性。 2）作业 围绕线性查找算法布置作业题。 3）在线讨论 在以往编程中，哪些场合利用了“短路”布尔运算来避免不安全操作？ 第 6 讲 二分查找 1. 教学目标 1）计算思维：理解在不同算法问题中排序所起的作用，及循环不变量在编 写正确代码上的重要性； 2）算法与数据结构：大小固定数组的二分查找； 3）程序设计：深思熟虑的编程，在测试、推理及确保安全与正确性中约定 的重要性，利用局部推理来证明程序的正确性。 本讲教学支持课程目标 1、课程目标 2、课程目标 3 和课程目标 4。 2. 教学重点