华科计算机方法论精炼知识

1、计算机科学与技术1201班 作者 木子三金o 二维定义矩阵o 理论、抽象和设计o 数据库领域的三个形态实例o 程序设计语言三种形态实例o 图灵机o 冯诺依曼型计算机o 博弈与搜索树o 12个核心概念o 集合、关系、布尔逻辑o 递归与迭代计算学科的根本问题是：什么能被（有效地）自动执行计算的本质即符号串的变化一、发展沿革 1623年，什卡尔特（Schikad），第一个演算机， 加、乘法 1641年，帕斯卡（Pascal），齿轮，加、减法计算器 1672年，莱布尼兹（G.W.Leibniz），手摇计算机奠基 （提出2进制运算法则） 1820年，托马斯（C.Thomas），生产100台演算机 184

2、21848年，巴贝奇（C.Babbage），发明差分机和解析机原理，提出程序控制计算的思想，助手Ada 1946.2.14美国宾夕法尼亚大学研制成功的ENIAC电子数字积分器和计算器）是世界第一台多功能、全电子数字计算机。 19451952年，冯诺依曼（Von.Neuman），第一台存储程序的通用电子数字计算机EDVAC为现代计算机奠定了基础。建议采用二进制，存储程序和程序控制的思想，“计算机之父”。 1951年，威尔斯（M.V.Wilkes），批量生产EDSAC 1946年，宾夕法尼亚大学莫尔学院电工系，第一台 通用电子数字计算机，ENIAC 缺点：未实现babbage关于“程序控制计算的思

3、想”第一代第四代计算机的主要特征 第一代1946-1957 第二代1957-1964 第三代1964-1972 第四代1972-至今 逻辑元件电子管晶体管中小规模集成电路大规模与超大规模集成电路存 储 器延迟线、磁鼓、磁芯磁芯、磁带、磁盘磁芯、磁盘、磁带半导体、磁盘、光盘软 件 机器语言汇编语言高级语言管理程序操作系统结构化程序设计 数据库、软件工程、程序设计自动化 应 用科学计算数据处理工业控制科学计算 系统模拟系统设计大型科学计算科技工程各项域事务处理、智能模拟、大型科学计算，普及到社会生活的各方面 第五代计算机（人工智能计算机） 面向科学计算、工程设计、模拟仿真的SIMD、MISD、 M

4、IMD并行多机系统，高性能计算机 面向人工智能求解的LISP机、归约机、逻辑推理机 量子计算机 DNA计算机（分子计算机）、DNA芯片与生物计算机 光计算机计算机的发展方向 未来的计算机以超大规模集成电路为基础，向以下方向发展 巨型化（不是体积大，而是速度高、容量大、功能强） 微型化（体积缩小、重量减轻） 网络化（分散的计算机联成网） 智能化（计算机将具有一定的“思维能力”）相同之处：资源共享、虚拟计算网格计算云计算并行计算为主：依托网络将跨地域的计算机组织起来并行作业，但需要通过调度系统将作业分解到各个不同的物理节点去。集群计算为主：节点自主、自治，节点之内常常是集群计算屏蔽异构：用中间件屏

5、蔽异构系统，使用户面向同一环境，实现资源共享承认异构：承认节点在原理、规模、能力上的差异性，依靠互操作来实现节点之间的资源共享完成一次性特定任务：要完成的任务是预先设定的完成持久性多样化服务：中心提供计算、存储等资源，用户利用云计算按需聚合、柔性重组，获取持久、个性化服务，协作式运营：带宽保证、性能保障商业式运营：尽力而为的服务、按租使用，按用付费，多租赁，即用即散确定的交互：按规定要求和程序输入/输出，人不主动参与人机交互、群体智能：大众参与的计算，包括不确定性、软计算，相互沟通交流当今互联网用户的需求是什么？ 接入能力 可以从任何地点、任何设备接入服务和数据 共享能力 数据的建立和存储共享

6、 容易方便 自由 不希望受数据的影响 简单 容易学会, 容易使用 安全 相信数据不会丢失或不会被不允许的人看到 三个过程主领域抽 象理 论设 计1. 离散结构 (DS)2. 程序设计基础 (PF)3. 算法与复杂性 (AL)4. 体系结构 (AR)5. 操作系统 (OS)6. 网络计算 (NC)7. 程序设计语言 (PL)8. 人机交互 (HC)9. 图形学和可视化计算 (GV)10. 智能系统 (IS)11. 信息管理 (IM)12. 软件工程 (SE)13. 社会和职业的问题 (SP)14. 科学计算 (CN)博弈树搜索o 所谓双人完备博弈就是两位选手对垒，轮流走步，其中一方完全知道另一方

7、已经走过的棋步以及未来可能的走步，对弈的结果要么是一方赢（另一方输），要么是和局。n 国际象棋、西洋跳棋、围棋、中国象棋都属于双人完备博弈。o 对于任何一种双人完备博弈，都可以用一个博弈树（与或树）来描述，并通过博弈树搜索策略寻找最佳解。o 博弈树类似于问题求解搜索中使用的搜索树。n 搜索树上的第一个结点对应一个棋局，树的分支表示棋的走步，根节点表示棋局的开始，叶节点表示棋局的结束。n 一个棋局的结果可以是赢、输或者和局。o 博弈树的规模：n 国际跳棋-1040个结点n 国际象棋-10120个结点（棋局总数）n 中国象棋-估计有10160个结点，n 围棋-盘面状态达10768。o “井字棋”游

8、戏（又叫“三子棋”），是一款十分经典的益智小游戏。“井字棋”的棋盘很简单，是一个33的格子，很像中国文字中的“井”字，所以得名“井字棋”。o 设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，棋子放完后，可以向周围空的格子移动棋子，每次一步，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。 用叉号表示MAX，用圆圈代表MIN。抽象理论设计（三种形态）：计算学科中的基本内容，基本概念；同时反映了人们的认识是从感性认识（抽象）到理性认识（理论），再由理性认识（理论）回到实践（设计）中来的一般科学思维方法1、抽象形态 科学抽象是指

9、在思维中对同类事物去除其现象的、次要的方面，抽取其共同的、主要的方面，从而做到从个别中把握一般，从现象中把握本质的认知过程和思维方法。 学科中的抽象形态包含着具体的内容，它们是学科中所具有的科学概念、科学符号和思想模型。抽象形态源于现实世界（建立对客观事物进行抽象描述的方法，建立概念模型） 形成假设 建造模型并作出预测 设计实验并收集数据 对结果进行分析 2、理论形态 科学认识由感性阶段上升为理性阶段，就形成了科学理论。科学理论是经过实践检验的系统化了的科学知识体系，它是由科学概念、科学原理以及对这些概念、原理的理论论证所组成的体系。 理论源于数学，是从抽象到抽象的升华，它们已经完全脱离现实事

10、物，不受现实事物的限制，具有精确的、优美的特征，因而更能把握事物的本质。理论形态源于数学（建立理论体系，建立数学模型） 表述研究对象的特征（定义和公理） 假设对象之间的基本性质和对象之间可能存在的关系（定理） 确定这些关系是否为真（证明） 结论3、设计形态 设计形态与抽象、理论两个形态存在的联系设计源于工程，用于系统或设备的开发，实现给定的任务 设计形态和抽象、理论两个形态都须以对自然规律的认识为前提 设计必须创造出相应的人工系统和人工条件，还必须认识自然规律的具体表现形式 设计形态的主要特征与抽象、理论两个形态的主要区别：设计形态具有较强的实践性、社会性、综合性设计形态源于工程（完成一个具体

11、任务，总结与升华） 需求分析 建立规格说明 设计并实现该系统 对系统进行测试与分析三个学科形态的内在联系 在计算机科学与技术方法论的原始命题中，蕴含着人类认识过程的两次飞跃，第一次飞跃是从物质到精神，从实践到认识的飞跃。这次飞跃包括两个决定性的环节：一个是科学抽象，另一个是科学理论。 第二次飞跃是从精神到物质，从认识到实践的飞跃。这次飞跃的实质对技术学科（计算学科就是一门技术学科）而言，其实就是要在理论的指导下，以抽象的成果为工具来完成各种设计工作。 抽象源于现实世界。建立对客观事物进行抽象描述的方法，建立具体问题的概念模型，实现对客观世界的感性认识。 理论源于数学。建立完整的理论体系，建立具

12、体问题的数学模型，从而实现对客观世界的理性认识。 设计源于工程。对客观世界的感性认识和理性认识的基础上，完成一个具体的任务；对工程设计中所遇到的问题进行总结，提出问题，由理论界去解决它。二 信息系统（数据库）三种形 态实例 （P44-P48）操作系统（operating system，OS）数据库管理系统 DBMS (Database management system)中间件及工具软件Middleware应用软件Application信息管理系统涉及的软件：系统软件（还包括编译软件）语言低高抽象形态建模 概念模型：用于信息世界的建模，是客观世界到信息世界的抽象。 概念模型不是机器世界所支持的

13、数据模型，而是客观世界到机器世界的一个中间层次。 概念模型还需要转换成机器世界能支持的数据模型。 在数据库领域中，数据库管理系统（DBMS）能支持的数据模型有：层次、网状、关系以及面向对象等数据模型。 E-R模型转换成计算机可处理的数据库模型，层次模型、网状模型、关系模型三大数据库模型。 关系模型支持的是一种二维表结构的数据模型，其中关系就是一张二维表。转换：学生（学号，姓名，年龄，性别）；课程（课程号，课程名）；学生选课（学号，课程号，成绩） 概念模型是对现实原形的理想化，因此，将概念模型直接转换成关系模型，还不能说完全达到了对“学生选课”这一客观世界的理性认识，换言之，就是所转换的关系模型

14、有可能还存在问题。 若A=1, 2, 3，B=a, b 求ABAB=(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)每个子集都是A、B上的一个二元关系，有多少个子集？ 例如：(1,a), (2,a), (1,a), (3,a), (1,a), 空集等都是AB上的关系，AB中有6个元素，则一共有26个子集感性认识中存在的问题 插入异常 删除异常 冗余太大 数据冗余太大 浪费大量的存储空间 例：每一个系主任的姓名重复出现 更新异常（Update Anomalies） 数据冗余 ，更新数据时，维护数据完整性代价大。 例：某系更换系主任后，系统必须修改与该系学生有关的每

15、一个元组 3.插入异常（Insertion Anomalies） 该插的数据插不进去 例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。 删除异常（Deletion Anomalies） 不该删除的数据不得不删 例，如果某个系的学生全部毕业了， 我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。Student关系模式不是一个好的模式。“好”的模式： 不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。解决方法：通过分解关系模式，分解为三个（2）函数依赖：属性间的关系 定义：设有关系模式R（A1, A2, , An），X和Y均为A1, A2, ,

16、An的子集，r是R的任一具体关系（R-型 r-值）。如果R的所有关系r都存在着：对于X的每一个具体值，都有Y唯一的具体值与之对应，则称X函数决定Y，或Y函数依赖于X。记为X Y 函数依赖判别简法：设有属性集X、Y及关系模式R 如果X、Y之间是“1:1”关系，则 XY YX 如果X、Y之间是“N:1”关系，则 XY 如果X、Y之间是“N:M”关系，则 X、Y之间不存在函数依赖 平凡函数依赖与非平凡函数依赖 在关系模式R(U)中，对于U的子集X、Y，如果 XY，但Y X则称XY是非平凡的函数依赖。 XY，但YX 则称XY是平凡的函数依赖。 若不特别指定声明，我们总是讨论非平凡函数依赖。 例：在关系

17、SC(Sno, Cno, Grade)中， 非平凡函数依赖： (Sno, Cno) Grade ， 平凡函数依赖： (Sno, Cno) Sno ，(Sno, Cno) Cno 范式定义 范式（NF）是符合某一种级别的关系模式的集合。 3NF2NF1NF 若R(U，F)符合x范式的要求，则称R为x范式，记作：RxNF 1NF（1 Normal Form）:每个属性值都是不可再分的 最小单元如果一个关系模式R的所有属性都是不可分的基本数据项,则 R 1NF不满足1NF的数据库模式不能称为关系数据库满足1NF的数据库并一定是一个好的关系模式2NF：若R1NF，且每一非主属性不存在对关键字的 部分依

18、赖，则R2NF。 部分依赖：设R中XY，YXf，如果存在X的真子集X1Y成立，则称Y部分依赖于X，否则称Y完 全函数依赖于X。 例1：成绩表（学号，课程号，成绩）关系中， （学号，课程号） 成绩，学号 成绩， 课程号 成绩，所以（学号，课程号） 成绩 是完全函数依赖 。 例2：在学生表（学号，姓名，性别，班级，年龄）关系， （学号，姓名） 性别，学号 性别，所以（学号，姓名） 性别 是部分函数赖 3NF：若R2NF，且每一非主属性不存在对关键字的传递依赖，则R3NF。 传递依赖：对R，X、Y、Z均为R的属性子集，如果 XY，YZ，则称Z传递依赖于X。例：关系S1（学号，系名，系主任）， 学号

19、系名，系名 系主任， 并且 系名 学号，所以 学号 系主任 为传递函数依赖 在数据库的模型设计中目前一般采用第三范式，它有非常严格的数学定义。如果从其表达的含义来看，一个符合第三范式的关系必须具有以下三个条件： 每个属性的值唯一，不具有多义性； 每个非主属性必须完全依赖于整个主键，而非主键的一部分； 每个非主属性不能依赖于其他关系中的属性，因为这样的话，这种属性应该归到其他关系中去。 第三范式的定义基本上是围绕主键与非主属性之间的关系而作出的。 还有改进的3NF -BCNF(BoyeeCodd Normal Form）、第四范式(4NF) 、第五范式(5NF) 结论：从感性认识（抽象）而来的关

20、系模式，必须 用规范化（理论）方法，使之在3NF以上。设计形态依赖具体的DBMS进行定义与应用 （SQL语句）SQL功能操作符数据查询SELECT数据定义CREATE，ALTER，DROP数据操纵INSERT，UPDATE，DELETE数据控制GRANT，REVOKE基本表的定义示例 S: 学号: char 4; 姓名: char 8 非空; 年龄: int 3; 性别: char 1;主关键字: 学号；性别: 只能取 0 或者 1学生基本表：CREATE TABLE S ( S# CHAR（4）, SNAME CHAR（8） NOT NULL, AGE INT (3), SEX CHAR（1

21、）, PRIMARY KEY (S#), CHECK (SEX=0 OR SEX=1) )关系课程C：课程号: char 4; 课程名称: char 10 非空；任课教师姓名: char 8; 主关键字: 课程号课程基本表：CREATE TABLE C ( C# CHAR（4）, CNAME CHAR（10） NOT NULL, TEACHER CHAR（8）, PRIMARY KEY (C#), ) 例：查询成绩低于75的学生的姓名、系别、成绩 SELECTsname, depart, grade FROM student , sc WHERE grade 75 AND student.sn

22、o=sc.sno 例：查询选修了“数据库”课程的学生学号、姓名和成绩 SELECT student.sno,sname, grade FROM student, course, SC WHERE student.sno=sc.sno AND o=o AND ame=数据库 Ex 1: 查询工资低于2000的老师的姓名、工资、系别 SELECTpname , sal , dname FROM Prof , Dept WHERE sal 2000 AND Prof.d# = Dept.d#Ex 2: 查询工资在1000-2000之间的老师姓名 SELECT pname FROM Prof WHER

23、E sal BETWEEN 1000 AND 2000客观世界 抽象 关系模型 理论（规范化） 设计（SQL）程序设计语言三种形态实例自然语言应用语言（4GL）高级语言汇编语言机器语言（表3.3）P72（表3.2）P70（表3.1）P66（表3.4）P73抽象 设计 理论 t计算机语言在裸机级所取得的主要成果计算机语言抽象理论设计裸机级的主要内容和成果语言的符号集为：0，1；用机器指令对算法进行描述图灵机（过程语言的基础）、波斯特系统（字符串处理语言的基础）、-演算（函数式语言的基础）等计算模型冯诺依曼型计算机等实现技术；数字电子计算机产品1、自然语言与形式语言人类的语言（文字）是人类最普遍使

24、用的符号系统。其最基本、最普遍的形式是自然语言符号系统 歧义性； 不够严格和不够统一的语法结构。 他的发理得好。 他的理发水平高； 理发师理他的发理得好。 他的小说看不完。 他写的小说看不完； 他收藏的小说看不完； 他是个小说迷。 高级程序设计语言其实也有语义的歧义性问题,高级程序设计语言存在较少的歧义性而已 例3.4 IF (表达式1) THEN IF (表达式2) THEN 语句1 ELSE 语句2。 IF (表达式1) THEN (IF (表达式2) THEN 语句1 ELSE 语句2)； IF (表达式1) THEN (IF (表达式2) THEN 语句1) ELSE 语句2。 形式语

25、言人工语言符号系统发展的第二阶段叫形式化语言，简称形式语言。形式语言是进行形式化工作的元语言，它是以数学和数理逻辑为基础的科学语言。 有一组初始的、专门的符号集； 有一组精确定义的，由初始的、专门的符号组成的符号串转换成另一个符号串的规则。 在形式语言中，不允许出现根据形成规则无法确定的符号串。 形式语言的语法：形式语言中的转换规则。 语法不包含语义。 在一个给定的形式语言中，可以根据需要，通过赋值或模型对其进行严格的语义解释，从而构成形式语言的语义。 语法（Syntax）和语义（Semantics）要作严格的区分。语言W定义为： 初始符号集：a，b，c，d，e。 形成规则：上述符号组成的有限

26、符号串中，能组成一英语单词的为一公式；否则不是。 问：W是否为一形式语言？ 答：不是。 因为，根据形成规则，无法精确地定义转换规则。 原因：形成规则（语法）中包含了语义。语言X定义为： 初始符号集：a，b，c，d，e，(，)，+，-，。 形成规则：上述符号组成的有限符号串中，构成表达式的为一公式，否则不是。 问：X是否为一形式语言？ 答：不是。 原因：与例3.5相同。 语言Y定义为： 初始符号集：a，b，c，d，e，(，)，+，-，。 形成规则：上述符号组成的有限符号串中，凡以符号“(”开头且以“)”结尾的符号串，为一公式。 问：Y是否为一形式语言？ 答：不是。 因为，根据形成规则，无法对不是

27、以符号“(”开头且以“)”结尾的符号串进行判定。例如，(a+b)c。 语言Z定义为： 初始符号集：a，b，c，d，e，(，)，+，-，。 形成规则：上述符号组成的有限符号串中，凡以符号“（”开头且以“）”结尾的符号串，为一公式，否则不是。 问：Z是否为一形式语言？ 答：是。图灵机计算模型（理论） 图灵计算机科学之父冯诺依曼型计算机计算机组织结构（设计） 冯诺依曼计算机器之父 图灵的观点及结论： 凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。 与图灵机等价的计算模型： 递归函数 -演算 POST规范系统 图灵机是从过程这一角度来刻画计算的本质，其

28、结构简单、操作运算规则也较少，从而为更多的人所理解。 图灵机可以计算 S(x)x1（后继函数）， N(x)0（零函数）， Ui(n)(x1，x2，xn)xi，1in（投影函数） 上述3个函数的任意组合。 从递归论中，我们知道这3个函数属于初始递归函数， 任何原始递归函数都是从这3个初始递归函数经有限次的复合、递归和极小化操作得到的。 从可计算理论可知每一个原始递归函数都是图灵机可计算的。 冯诺依曼型计算机的组织结构 冯诺依曼计算机的体系结构基于总线的计算机系统的硬件组成1.输入设备和输出设备作用：是将信息输入计算机和输出计算机。运算器和控制器寄存器、控制单元 计算机中控制数据操作的电路并不与主

29、存直接相连 这些电路被封装在一起，即CPU CPU含有自己的存储单元（register） 寄存器（Register）作为临时空间来存储CPU所操作的数，保存算术逻辑单元的输入与输出数据 控制单元负责将主存中的数据移到register，然后通知算术逻辑单元所需要的数据在哪个register 总线：CPU与主存之间用总线连接 利用总线 CPU通过提供存储单元目标地址以及读信号来选择、读取数据 CPU通过提供存储单元目标地址以及写信号来放置、写入信号基于冯诺依曼计算机体系结构的程序执行 冯诺依曼计算机的体系结构，也即存储程序式计算机的体系结构，则是将程序与数据一样看待，对程序像数据那样进行适当的编码

30、，然后与数据一起共同存放在存储器中。 计算机可以通过改变存储器中的内容，对数据进行操作。 从原来对程序和数据的严格区别到一样看待，这个观念上的转变是计算机史上的一场革命，它反映的正是计算的本质，即符号串的变化。4、机器指令（语言）指令系统 CPU必须能够解码并且执行的机器指令很少 一旦计算机可以执行一些基本的而且是精选的操作，加入额外的操作理论上是不会改变计算机的能力的。是否充分利用这种特性导致了两种不同的计算机设计： CISC(Complex instruction set computer) RISC(Reduced instruction set computer) 最初人们采用的是进一

31、步增强原有指令的功能，并设置更为复杂的指令的方法。 采用这种设计思路的计算机被称为复杂指令系统计算机（CISC）。 CISC的思路是由IBM公司提出的，并以1964年IBM研制的IBM 360系统为代表。CISC缺点 80%的指令只在20%的运行时间里用到。一些指令非常繁杂，而执行效率甚至比用几条简单的基本指令组合的实现还要慢。 庞杂的指令系统也给超大规模集成电路（VLSI）的设计带来了困难， 它不但不利于设计自动化技术的应用，延长了设计周期，增加了成本， 容易增加设计中出现错误的机会，从而降低了系统的可靠性。 RISC 思路主要是通过减少指令总数和简化指令的功能来降低硬件设计的复杂度，从而提

32、高指令的执行速度。 优点：与CISC技术相比 简化了指令系统，适合超大规模集成电路的实现； 提高了机器执行的速度和效率； 降低了设计成本，提高了系统的可靠性； 提供了直接支持高级语言的能力，简化了编译程序的设计。机器指令系统每台数字电子计算机在设计中，都规定了一组指令。机器语言用机器指令形式编写的程序。在裸机级，计算机语言关于算法的描述采用的是实际机器的机器指令，它的符号集是0, 1。支撑实际机器的理论是图灵机等计算模型；在图灵机等计算模型理论的指导下，有关设计形态的主要成果有冯诺依曼型计算机等具体实现思想和技术，以及各类数字电子计算机产品。数据类型的抽象数据类型的抽象 相对于汇编语言和机器语

33、言，高级语言的数据类型的抽象层次有了很大地提高，出现了 整型 实型 字符型 布尔型 用户自定义类型 抽象数据类型 数据类型的抽象极大地方便了用户对数据的抽象描述，为实现软件设计的工程化奠定了基础。 计算机处理分为四个层次： 第一层次是文字和语音，即基本语言信息的构成； 第二层次是语法，即语言的形态结构； 第三层次是语义，即语言与它所指的对象之间的关系； 第四层次是语用，即语言与它的使用者之间的关系。虚拟机的层次结构应用语言虚拟机高级语言虚拟机汇编语言虚拟机操作系统虚拟机固件虚拟机实际机器概念机抽象向上增向下逐级编译或解释执行易用性向上增执行效率向上增减占用硬软件资源向上增每个上层都是下层的虚拟

34、机，越上越虚拟；往上是概念机的抽象学科的核心概念是学科中最关键、最重要的概念，它涉及学科研究的内涵、对象、本质、核心要素等内容，其基本特征有以下4点： （1）在学科中多处出现； （2）在各分支领域及抽象、理论和设计的各个层面上都有很多示例； （3）在技术上有高度的独立性； （4）一般都在数学、科学和工程中出现。算法、数据结构、程序、软件、硬件、计算机中的数据等与CC1991报告提取的12个核心概念一起统称为计算学科中的核心概念。流程图的基本符号：ISO 8631-1986E 算法是计算学科中最具方法论性质的核心概念，也被誉为计算学科的灵魂。算法设计的优劣决定着软件系统的性能算法的定义与特征 定

35、义（非形式化）：一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一类特定类型问题的运算序列。 特征 有穷性：步骤是有限的 确定性：无歧义性 初始值（输入）：零或多个 结果（输出）：一个或多个 能行性:待执行的运算和操作是相当基本的算法分析 在算法的复杂度分析中，经常使用一个记号O（读作“大O”），为Order（数量级）的第一个字母，它允许使用“=”代替“”。如n2+n+1=O(n2)，该表达式表示，当n足够大时表达式左边约等于n2。设f(n)是一个关于正整数n的函数，若存在一个正整数n0和一个常数C，当n n0时，T(n)C f(n)均成立，则称f(n)为T(n)的同数量级的函数。

36、于是，算法时间复杂度T(n)可表示为： T(n)= O(f(n) 内容 (1) 时间复杂度 (2) 空间复杂度 (3) 便于阅读、修改与测试 常见的复杂度等级 (1) O(l)：常数级 (2) O(logn)：对数级 (3) O(n)：线性级 (4) O(nc)：多项式级 (5) O(cn)：指数级 (6) O(n!)：阶乘级三、程序程序 = 算法 + 数据结构问题：给定一个k值，如k=50，快速找出k=50的单元地址算法一：顺序查找 确定变量和数据结构 定义数组Ai, i=1,n，给定了k值算法二：二分查找 定义数组Ai, i=1,n，给定了k值 另外设置变量low, high, mid数据

37、存储和表示计算机用位的形式来表示数据。位（binary digit，二进制数字，缩写为bit）是存储在计算机中的最小数据单位，位表示二进制数字的0或1，8位表示1个字节（byte）。存储一个位需要用一个有两种状态的设备。例如，电子开关就能表示并存储位，通常用“开”（合上）状态表示“1”，用“关”（断开）表示“0”。现代计算机使用各种各祥的两态设备来存储数据。1.字符 目前被广泛采用的字符编码是由美国国家标准局（American National Standards）制定的美国标准信息交换码（America Standard Code for Information Interchange ，A

38、SCII），该编码被国际标准化组织（ISO）定为国际标准，称为ISO 646标准。 ASCII码用8位二进制码来表示英文中的大小写字母、标点符号、数字0到9以及一些控制数据（如换行、回车和制表符等），最高位为0。若将最高位设为1，还可以将标准的ASCII进行适当的扩展（可增加128个字符）。为了支持不同国家的语言字符集，ASCII码正在被Unicode码所代替，Unicode是一个16位的编码系统。它用16位二进制来表示每一个符号，这样Unicode就有216 （65536）种不同的二进制编码。足以将日语、韩语和中文等的常用字都表示出来。为了简化ASCII与Unicode之间的转换，Unico

39、de的设计者还使其向后兼容ASCII码。原来用ASCII码能表示的字符，其Unicode码只是在原来的ASCII码前加上8个0。在计算机中表示图像的技术两种：位图和矢量图。最普遍的系统是将每个像素用24位来表示。 理论上，凡能被计算机处理的问题均可以转换为一个数学问题，凡能以离散数学为代表的构造性数学方法描述的问题，当该问题所涉及的论域为有穷，或者为无穷但存在有穷表示时，这个问题也一定能用计算机来处理。数学有连续数学和离散数学之分，离散数学源于算术，连续数学源于几何。 自牛顿开创微积分后，连续数学就以微积分为基础。 计算学科与物理等学科不同，它的根本问题是“能行性”问题。“能行性”这个根本问题

40、决定了计算机本身的结构和它处理的对象都是离散型的，而连续型的问题只有经过“离散化”的处理后才能被计算机处理。因此，在计算学科中，采用的数学方法，主要是离散数学的方法。论域：一定场合（语境）中思考和议论所涉及的对象的范围。即某一范围内被论及对象的全部所构成的集合。1集合的概念集合是数学的基本概念，它是构造性数学方法的基础。 集合就是一组无重复的对象的全体。集合中的对象称为集合的元素。 2集合的描述方法通常用大写字母表示集合，用小写字母表示元素，描述集合的方式主要有以下3种：（1）枚举法：列出所有元素的表示方法。如1至5的整数集合可表示为：A=1，2，3，4，5；（2）外延表示法：当集合中所列元素

41、的一般形式很明显时，可只列出部分元素，其他则用省略号表示。如斐波那契数列可表示为： 0，1，1，2，3，5，8，13，21，34， ；（3）谓词表示法：用谓词来概括集合中元素的属性。如斐波那契数列可表示为：Fn|Fn+2=Fn+1+Fn，F0=0，F1=1，n0。4）集合的补设I为全集，A为I的任意一子集，IA则为A的补集，记为 。可表示为 =IA=xxI，xA求补集的运算称为补（运算）。 例5.4 若I=x5x5，A=x0x1，求 。 解： IA=x5x01x5关系定义：A1A2 An中的任一子集称为A1, A2, , An的一个n元关系。n 二元关系： A1A2 的一个子集，或称有序对。

42、例，选课关系：R=(张, 文)，(张, 哲)， (李, 数)，(李, 艺)，(王, 史)，( 王, 文)给定R=1, 2, 3, 4，写出关系r1(xy)和r3(x=y)的元组 。R R=(1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4) (4,1), (4,2), (4,3), (4,4)r1(xy)= (2,1), (3,1), (3,2), (4,1), (4,2), (4,3)r3(x=y)= (1,1), (2,2), (3,3), (4,4)n 集合A上的关系性质 设r

43、是集合A上的关系。 若对于所有的 a A。有ara，则称r是自反的。 对于所有的 a, b A，若每当有arb就有bra， 则称r 是对称的。 对于所有的a, b, c A，若每当有arb和brc就有 arc，则称r是可传递的。n 价关系：集合A上的关系r ，如果它是自反、对称且可传递的，则称r为A上的等价关系。n 等价类 设r是A上的等价关系，若arb成立，则a等价 于b（在r下）。 定义：设r是A上的等价关系，则A中等价于a 的全 体元素的集合称为a所生成的等价类。 记为ar=b|bA, arb 例 5.6，“同余关系”是等价关系 例 5.7，“并发关系”是非等价关系 例，“小于”关系r不

44、具备自反性和对称性；“等于”关系r具备自反性、对称性、可传递。命题：一个能分辨真假的陈述句称作一个命题。 析取表示“可兼或”例，P：刘翔是100米冠军 Q：刘翔是200米冠军 P Q 为复合命题，表示“刘翔或者是100米冠军，或者是200米冠军”例，今天晚上我在家看电视或去剧场看戏。 P Q？不能兼或异或：P和Q相反时， P Q为真可用、 来表达,一般不将列为基本联结词蕴含：表示“如果，则”P Q，若P，则Q。当且仅当P为真，Q为假，P Q为假。否则P Q总为真关于等值： 当前件后件取同一值时，等值PQ为真谓词逻辑 存在一条会叫不咬人的狗，即会叫的狗不一定咬人 x(（Q(x) P(x) Q(x)例，