《4计算学科中的核心概念》由会员分享，可在线阅读，更多相关《4计算学科中的核心概念（8页珍藏版）》请在金锄头文库上搜索。
1、第第4章章 计算机学科中的核心概念计算机学科中的核心概念 算法描述（算法描述（p79） 例例1、欧几里得算法、欧几里得算法求两个正整数的求两个正整数的m和和n的最大的最大 公因子。公因子。 一、算法（一、算法（Algorithm） 定义（非形式化）：一个算法，就是一个有穷规则的集合，其中定义（非形式化）：一个算法，就是一个有穷规则的集合，其中 之规则规定了一个解决某一类特定类型问题的运算序列。之规则规定了一个解决某一类特定类型问题的运算序列。 特征特征 有穷性有穷性 确定性确定性 初始值（输入）初始值（输入） 结果（输出）结果（输出） 能行性能行性 形式化定义（形式化定义（Q，I， ，F） 2
2、、算法的定义与特征、算法的定义与特征 3、算法实例（表示方法：自然语言、算法实例（表示方法：自然语言流程图流程图 程序设计语言）程序设计语言） 例例1，求，求 例例2，求解调合级数，求解调合级数 Hn= 例例3，求解斐波那契数：，求解斐波那契数：0，1，1，2，3，5，8， 13，21，34， 每个数都是前两数之和每个数都是前两数之和 F0=1，F1=1，Fn+2=Fn+1+Fn，n0 100 k=1K111213141N+ + + + +4、算法分析、算法分析 内容内容 (1) 时间复杂度时间复杂度 (2) 空间复杂度空间复杂度 (3) 便于阅读、修改与测试便于阅读、修改与测试 常见的复杂度
3、等级常见的复杂度等级 (1) O(l)：常数级常数级 (2) O(logn)：对数级对数级 (3) O(n)：线性级线性级 (4) O(nc)：多项式级多项式级 (5) O(cn)：指数级指数级 (6) O(n!)：阶乘级阶乘级二、数据结构二、数据结构1、数据结构的基本概念、数据结构的基本概念 定性的数学模型：非数值性的数据结构及其定性的数学模型：非数值性的数据结构及其 运算运算 数据逻辑结构：数据逻辑结构：DS= 数据的存储结构：顺序，链式数据的存储结构：顺序，链式 数据结构的基本运算：建立、清除、插入元数据结构的基本运算：建立、清除、插入元 素、删除元素、更新元素、查找元素、排序素、删除元
4、素、更新元素、查找元素、排序 2、线性表与数组、线性表与数组 线性表线性表 数组数组3、树与二叉树、树与二叉树 树树 二叉树二叉树4、图、图三、程序三、程序程序程序 = 算法算法 + 数据结构数据结构四、软件四、软件1、系统软件、系统软件2、支撑软件、支撑软件3、应用软件、应用软件五、硬件五、硬件六、十二个反复出现的核心概念六、十二个反复出现的核心概念1、绑定（、绑定（Binding）2、大问题的复杂性（大问题的复杂性（Complexity of Large Problems）3、概念和形式模型（概念和形式模型（Conceptual and Format Models）4、一致性和完备性（一致性和完备性（Consistency and Completeness）5、效率（效率（Efficiecy）6、演化（演化（Evolution）7、抽象层次（、抽象层次（Levels of Abstraction）8、按空间排序（按空间排序（Ordering in Space）9、按时间排序（按时间排序（ Ordering in Time）10、重用（重用（Reuse）11、安全性（安全性（Security）12、折衷和结论（折衷和结论（Trade off and Consequences）
