计算模型与计算机体系结构
理论计算机
冯,诺依曼型计算机
计算机网络
新型计算机
计算机发展反思,动力,社会需求 ;
目标,追求新型计算模型,制造先进计算机 ;
条件,理论指导,技术支持。
理论计算机
布尔代数
数理逻辑与哥德尔定理
计算模型与图灵机
可计算性,在有限步骤内可完成。
图灵机可计算性。
计算复杂性 返回计算复杂性
算法的概念
几个例子
算法的评价
证比求易问题
相似性原理
对偶性原理
NP完全性问题 返回几个例子
计算,x+1” 的图灵机
选择排序问题,将 3,74,23,89,22,99,65,109,55、
45十个数按从小到大的顺序排列。步骤：
1、取未排序的数中的第一个数，假设它是其中最小的数。
2、将它依次与其后的数相比较，若发现某个数更小，则目前为止发现的最小数是该数，并假设它是最小数，重复
2直到比较到最后一个数，此时，假设的最小数就是未排序的数中的最小数。
3、将该最小数与未排序的数中的第 1个数交换位置。回到
1，直到所有数都排序。
执行该步骤 1-3，产生以下的 排序过程,返回选择排序过程第 1遍,3,74,23,89,22,99,65,109,55,45
第 2遍,3,22,23,89,74,99,65,109,55,45
第 3遍,3,22,23,89,74,99,65,109,55,45
第 4遍,3,22,23,45,74,99,65,109,55,89
第 5遍,3,22,23,45,55,99,65,109,74,89
第 6遍,3,22,23,45,55,65,99,109,74,89
第 7遍,3,22,23,45,55,65,74,109,99,89
第 8遍,3,22,23,45,55,65,74,89,99,109
第 9遍,3,22,23,45,55,65,74,89,99,109
返回算法的评价
算法的复杂性,是对算法计算所需的 时间和空间的一种度量。
算法的时间复杂性,是对算法计算所需 时间 的一种度量。
算法的空间复杂性,是对算法计算所需 空间 的一种度量。
复杂性度量函数,算法在求解一类问题的过程中随 问题规模 大小变化引起的算法中 抽象的基本运算执行的次数 或 存储空间量 的变化规律。
例如,f (n)=2n2+3n+1=O(n2),读作 n2阶,其中,n为问题规模 。 返回证比求易问题
三个中国人问题,洪加威,1980
国王：艾述，宰相：孔唤石，公主：秋碧贞楠求数 8770428644836899的一个真因子。
证明 23092871是 8770428644836899的一个真因子。
问题规模 17位，小因子不超过 9位顺序算法与并行算法
对偶性原理,在并行计算模型上，计算的时间与空间可以互换。
相似性原理,所有合理的、功能足够强的计算模型不仅可以相互模拟计算，而且它们相互模拟时，同时使用本质上相同的并行时间，本质上相同的空间，本质上相同的顺序时间。 返回
NP完全性问题
难解型问题,没有多项式时间复杂性算法的问题。
P类问题,存在图灵机可计算的多项式时间复杂性算法的问题。
NP问题,存在非确定图灵机可计算的多项式时间复杂性算法的问题。
NP完全性问题,NP问题中若有一个问题找到了多项式时间复杂性算法，这个类中的其它问题也可找到多项式时间复杂性算法，则 P=NP。 返回算法的概念
算法,一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列。此外，
算法的规则序列须满足如下五个重要条件：
1,有穷性,算法必须总是在执行有穷步之后结束；
2,确定性,算法的每一个步骤必须是确切地定义的；
3,输入,算法有零个或多个输入；
4,输出,算法有一个或多个输出；
5,能行性,算法中有待执行的运算和操作必须是相当基本的。 返回布尔代数
布尔,G,Boole,19世纪，英国，自学成才
集合代数：集合、集合的运算与性质集合 A,A的补集 A’，空集 Ф，全集 1，属于?,相等?，包含?，交?，并?
集合与命题
布尔代数实现了从 一组逻辑公理 出发，依靠 代数演算 来推导逻辑定律或定理，用数学的方法来研究人的思维结构。
语义推导与语法推导
布尔代数、数字逻辑与电子计算机 返回香侬 是现代信息论的著名创始人。 1938年，香侬在发表的论文中，
首次用布尔代数进行开关电路分析，并证明布尔代数的逻辑运算可以通过继电器电路来实现。
阿塔纳索夫 提出了计算机的三条原则：
1）以二进制的逻辑基础来实现数字运算，以保证精度；
2）利用电子技术来实现控制、逻辑运算和算术运算，以保证计算速度；
3）采用把计算功能和二进制数更新存储功能相分离的结构。
布尔代数与计算机
Claude Shannon
语义推导与语法推导定理,A?A=A（幂等律）。
集合代数中的 语义推导：
证明,1、设?x?A?A,则 x?A 且 x?A,
所以 x?A,故 A?A? A；
2、设?x?A,则 x?A 且 x?A,所以
x? A?A,故 A? A?A ；
所以,A?A=A □
逻辑代数中的 语法推导,返回逻辑代数中的 语法推导定理,A?A=A（幂等律）。
证明：因为：
A= A? 1 （ 1、）
= A? （ A? A’） （ 8、）
= （ A? A ）? （ A? A’） （ 5、）
= （ A? A ）? 0 （ 7、）
= A? A （ 2、）
所以,A?A=A □
布尔代数系统公理
1,A? 1 = A ；
2,A? 0 = A ；
3,A? B= B? A ；
4,A? B= B? A ；
5,A?（ B? C） = （ A? B）? （ A? C） ；
6,A?（ B? C） = （ A? B）? （ A? C） ；
7,A? A’= 0 ；
8,A? A’= 1 。
返回布尔代数系统公理
集合表示法,
设 k代表类,?是 集合的 包含关系符号，那么，系统的 公理为
1、如果 A? k 且 B? k,则 A? B?k ；
2、如果 A? k 且 B? k,则 A? B?k ；
3、存在?, k,使得对任意的 A，如果 A?k,则 A = A ；
4、存在?,k,使得对任意的 A，如果 A?k,则 A = A；
5,A? B= B? A,A?k,B? k ；
6,A? B= B? A,A?k,B? k ；
7,A? （ B? C） = （ A? B）?（ A? C）,A?k,B?k,C? k ；
8,A? （ B? C） = （ A? B）?（ A? C）,A?k,B?k,C? k ；
9、对任意的 A，存在一个 A’，使得 A?A’= k,A? A ’= Ф；
10、在类 k中至少存在两个不同的元素。
命题表示法,返回布尔代数系统公理命题表示法
1,A? 1 = A ；
2,A? 0 = A ；
3,A? B= B? A ；
4,A? B= B? A ；
5,A? （ B? C） = （ A? B）? （ A? C） ；
6,A? （ B? C） = （ A? B）? （ A? C） ；
7,A? A’= 0 ；
8,A? A’= 1 。 返回集合与命题
类,我们讨论的所有对象和事物的全体构成的论域。全集，
1。
命题,是指其含义确定，取值为,真,或,假,的断言。
1表示一种无论什么情况下都为,真,的恒真命题,?表示一种无论什么情况下都为,假,的恒假命题。因此 1也可看成由所有命题构成的类。例：西安是十一朝古都。
将集合看成命题,外延与内涵,040601班的全体学生
集合代数就可以看成是一种建立在命题表示基础上的 逻辑代数。
把,真,用 1表示，把,假,用 0表示，逻辑代数就可看成是所有命题只取 0,1二值的代数演算系统 —— 布尔代数 。
推理规则
等式的传递推导：如果已知 A=B,B=C，那么,A=C；
反证法：如果假定一个命题不成立，由此可以得出矛盾的结论，那么原命题得证；
代换推导：如果一个命题 A中的某一命题 B
用与它相等的命题 C代换之后得到命题 D，
那么,A=D ；
…… 返回数理逻辑与哥德尔定理
谓词演算,A=张山 是 040601班的学生 。040601（ 张山）? 040601（ x）x040601（ x） x 040601
（ x），皮尔斯和米切尔，哥德尔
数理逻辑,用数学方法研究推理的科学。
通用逻辑系统,从少数几条公理和推导规则出发，证明或发现和导出所有的未知定理。 希尔伯特 (Hilbert)
哥德尔定理,任一形式系统，它的一致性和完全性是不可兼得的。或者说，如果一个形式系统是一致的，
那么这个系统必然是不完全的。所谓不完全，就是指存在一个公式 A，使得 A和 A’在这个系统内都不可证。
返回计算模型与图灵机
图灵和他的时代同行
图灵机的直观描述
图灵机的形式描述
计算,x+1” 的图灵机
通用图灵机返回图灵和他的时代同行
可判定问题,能否找到一种有效的办法可以判断任意一个命题的真假?
20世纪 30年代,数理逻辑学家
计算模型,哥德尔 (K,G?del):递归函数 ;丘奇 (A,Church),?演算 ;图灵 (A.M,Turing):图灵机 ;波斯特
(E.l,Post):波斯特系统 — 等价
图灵,英国数学家,1936年，图灵机，
存储程序,1966年,ACM
（ Association for Computing
Machine),图灵奖计算机科学之父,阿伦 ·图灵图灵机的直观描述一条两端可无限延长的带子，一个读写头，一个控制器，带子由可擦写的小格组成，读写头可左右移动并读写，可写字符集
{0,1,b}，控制器有有穷个状态，一个开始状态，一个结束状态，控制器的命令为：
（状态，符号）?（写符号，移动，新状态）
图灵机从开始状态工作直到 结束状态停止，带上的内容就是计算结果。 返回图灵机的形式描述图灵机是一个五元组（ K,?,?,s,H），
其中：
K是有穷个状态的集合；
是字母表，即符号的集合；
是转移函数，即控制器的规则集合；
s? K 是初始状态；
H? K是停机状态的集合。 返回计算,x+1” 的图灵机图灵机
状态集合 K,{Start,Add,Carry,Noncarry,
Overflow,Return,Halt}；
字母表?,(0,1,*)；
规则集合?；
初始状态 s,Start；
停机状态集合 H,{Halt}。
例,当 x=5时,图灵机的工作过程 。 返回当 x=5时,图灵机 的工作过程状态 读写头位置
Start * 1 0 1 *
Add * 1 0 1 *
Carry * 1 0 0 *
Non- * 1 1 0 *
Non- * 1 1 0 *
Return * 1 1 0 *
… … … … … …
Halt * 1 1 0 *
通用图灵机
为,x+1” 图灵机编码 ；
多带 图灵机和单 带 图灵机是等价的；
三带图灵机 M；
图灵机 M与,x+1” 图灵机比较 ；
通用图灵机的重要意义：
1、把程序也作为数据；
2、存储程序和程序控制。
返回三带图灵机 M
第一条放输 x=5,即,*101*”,(00100001000000010010)
第二条放所有规则：
(Start,*,left,Add) (Add,0,1,Noncarry)
(Noncarry,1,left,Noncarry),(0101 0010 0011 0110
0110 0000 0001 1000 1000 0001 0011 1000)
第三条放初始状态,Start,0101
工作过程,1,扫描第三条获当前状态,Start,0101； 2、
扫描第一条获当前字符,*:0010； 3,扫描第二条获一个
16位字符串，前 4位为当前状态，第二个 4位串为当前字符，
则找到对应规则； 4,将第三条带上字符串改为该规则的第四个 4位串（新状态），并由第三个 4位串指挥第一条带上的动作； 5,若某一步在第二条带上找不到对应规则，则第三条带上为停机状态,M停机。 返回为,x+1” 图灵机编码
3个字母,2个动作,7个状态，共 12符号，需要 4位二进制码（ 24=16）：
为字母 编码,0:0000,1:0001,*:0010
为动作编码,left:0011,right:0100
为状态编码,Start:0101,Add:0110,Carry:0111，
Noncarry:1000,Overflow:1001,Return:1010,Halt:1011
为规则编码：
第一条 (Start,*,left,Add):(0101 0010 0011 0110)
第二条 (Add,0,1,left,Noncarry)? (Add,0,1,Noncarry),
(Noncarry,1,left,Noncarry)
(Add,0,1,Noncarry):(0110 0000 0001 1000),
(Noncarry,1,left,Noncarry):(1000 0001 0011 1000),
返回图灵机 M与,x+1” 图灵机比较
,x+1” 图灵机,输入 x，输出 x+1，功能固定的一个程序。
图灵机 M：输入为,x+1” 图灵机的编码,输出 x+1；若 输入换为其它图灵机的编码，则 M又能完成其它图灵机的功能 —— 通用图灵机 。
冯,诺依曼型计算机
冯,诺依曼和他的时代同行
存储程序式通用电子计算机组成
存储程序式通用电子计算机结构
图灵机与计算机的比较
计算机的更新换代
操作系统、进程与线程 返回冯,诺依曼和他的时代同行
冯,诺依曼 (Von Neumann),美藉匈牙利科学家，早期研究数理逻辑,1944
年夏天,参加 ENIAC的设计,1945年 3
月,提出第一台 存储程序式通用电子计算机 ──EDVAC的设计方案,1952年制造成功 。
冯,诺依曼和戈德斯坦
冯,诺依曼和 莫克利
冯,诺依曼和图灵计算机之父：
冯,诺依曼存储程序式通用电子计算机结构程序 由 指令组成，并和数据 一起存放在存储器中，机器一经启动，就能按照程序指定的逻辑顺序把指令从存储器中读出来逐条执行，自动完成指令规定的操作。
存储程序式通用电子计算机组成冯,诺依曼型计算机 五大 组成 部分,
运算器功能：算术运算和逻辑运算
控制器功能：使计算机能自动地执行程序，并使各部分协调工作
CPU=运算器 +控制器 =处理机存储器功能：用于保存程序和数据主存储器 (内部存储器 )存放当前所执行程序的指令和数据辅助存储器 (外部存储器 )存放暂不参加运算的程序的指令和数据
输入设备 用于程序和数据输入（标准设备：键盘）
输出设备 用于程序和数据输出（标准设备：显示器） 返回图灵机与计算机的比较
（ 1）、图灵机存储空间无限，计算机存储空间有限。
（ 2）、图灵机指令系统不定，计算机指令系统确定。
（ 3）、图灵机仅是理论模型，计算机是其物理实现。
所以，从理论上讲，图灵机的能力比计算机的能力强。 返回第一代
（ 1946~1956）
电子管
5千 ~4万（次 /秒）
第二代
（ 1957~1964）
晶体管几十万 ~百万（次 /秒）
第三代
（ 1965~1970）
集成电路百万 ~几百万（次 /秒）
第四代
（ 1971~90年代）
VLSI/LSI
几百万 ~几亿（次 /秒）
计算机发展的几个阶段摩尔定律 发展趋势晶体管数单位时间执行的指令数百万条/
每秒每 18个月芯片能力增长一倍。
计算机第一定律 —— 摩尔定律计算机的 发展趋势
微型化
巨型化,
世界上第一台超级计算机,1975年,,Cray-I”
超级计算机应用：天气预报、地震机理研究、石油和地质勘探，卫星图像处理等大量科学计算的高科技领域。
中国超级计算机：国防科技大学研制的,银河 1号,,
,银河 2号,和,银河 3号,,国家职能计算机中心推出的,曙光 1000”,,曙光 200I”和,曙光 3000”
网络化
智能化 返回操作系统、进程与线程
计算机操作方式的演变：
1、手工 2、批处理：单道与多道 3、联机：分时与实时
什么是操作系统？
操作系统的功能：
处理机管理、内存管理,I/O（输入输出）管理、
文件管理、作业管理
进程与线程
操作系统的分类：
批处理、分时、实时、网络、分布式 返回什么是操作系统操作系统是最基本的系统软件，其他的所有软件都是建立在操作系统的基础上。
操作 系统各种应 用程序
DOS
基础知识管家婆管理硬件资源协调后台工作服务生提供用户与计算机的交互接口进程与线程
并行：两个或两个以上的事件在同一时刻发生。
并发：两个或两个以上的事件在同一时间段内发生。
进程（ Process）,具有独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。
线程（ Thread）,进程内部的一个执行控制流程，
是系统进行处理机调度的最小单位。
进程状态的转换返回进程状态的转换返回计算机 网络与分层协议
计算机网络的概念,是计算机技术和通信技术发展的产物，是利用通信设备将多个计算机互联起来而形成的有机体，以实现计算机间的通信和资源共享。
计算机网络示意图
计算机网络组成
计算机网络的历史
计算机 网络体系结构
发展规律 与 广范应用返回高速通信线路主机终端通信子网通信控制处理机终端终端主机主机主机计算机网络示意图说明：通信子网 主要由通信线路和网络控制机组成，
负责网络通信和数据传送。
网络硬件：
网 络 系统 的 组 成
网络软件,
主机：连在网上的一台自主计算机。
传输介质：双绞线、同轴电缆、光纤、微波
网络连接设备：网卡、调制解调器、路由器
协议：是关于通信如何进行所制定的一系列标准。网络协议是指网络中通信各方事先约定的通信规则，计算机之间进行通信时必须使用相同的网络协议 。
例如,TCP/IP,HTTP等
操作系统：用以管理网络资源和通信。
应用软件：实现各种各样的网络应用 。
计算机网络一般由服务器、工作站、外围设备和通信协议组成。服务器是整个网络系统的核心，它为网络用户提供服务并管理整个网络。工作站（ Workstation）是指连接到网络上的计算机。
计算机网络发展历史回顾
七十年代的计算机网络
X.25 分组交换网：各国的电信部门建设运行
各种专用的网络体系结构,SNA,DNA
Internet 的前身 ARPANET进行实验运行
八十年代的计算机网络
标准化计算机网络体系结构,OSI
局域网络 LAN 技术空前发展
建成 NSFNET,Internet 初具规模
九十年代的计算机网络
Internet空前发展
Web技术在 Internet/Intranet 得到广泛应用 返回网络时代的三大基本定律摩尔定律,
CPU性能 18个月翻番,10年 100
倍。
所有电子系统
（包括电子通信系统，计算机）都适用光纤定律,
超摩尔定律，
骨干网带宽 9
个月 翻番,10
年 10000倍 。
带宽需求呈超高速增长的趋势联网 定律：
（迈特卡尔夫） 网络价值随用户数平方成正比。
未联网设备增加 N倍，效率增加 N倍。 联网设备增加 N倍，效率增加 N2倍网 络 体 系 结 构
体系结构,层和协议的集合 。
表示层会话层传输层网络层数据链路层物理层应用层表示层会话层传输层网络层物理层应用层数据链路层传输介质应用层协议表示层协议会话层协议传输层协议网络层协议链路层协议物理层协议
ISO
开放系统互联参考模 型
(OSI/RM) 返回
OSI参考模型各层功能
OSI (Open System Interconnection)
1.物理层（ The Physical Layer）
在物理线路上传输原始的二进制数据位（基本网络硬件）。
2.数据链路层（ The Data Link Layer）
在有差错的物理线路上提供无差错的数据传输（ Frame）。
3.网络层（ The Network Layer）
控制通信子网提供源点到目的点的数据传送（ Packet）。
4.运输层（ The Transport Layer）
为用户提供端到端的数据传送服务。
5.会话层（ The Session Layer）
为用户提供会话控制服务（安全认证）。 token management and
synchronization (insert checkpoints into the data stream)
6.表示层（ The Presentation Layer）
为用户提供数据转换和表示服务。
7.应用层（ The Application Layer）
为用户提供各种应用服务。 返回革命性的网络应用
开发今天 Internet没有，对国家重要的网络应用
健康保健：远程医疗、紧急医疗响应支持
教育：远程教育、数字图书馆
科学研究：能源、地理系统、气象、生物
国家安全：高性能全球通信、先进的信息传播
环境：监测、预测、警告、响应
政府：传递政府服务和信息给公民和企业
突发事件：灾难响应、危机管理
设计和制造：制造工程
主要策略：重点研究基础性应用
分布式计算应用、协同性应用 返回新型计算机
并行计算,多 CPU系统,多微处理器系统 (机群系统,高性能计算机系统 ),通道,SISD,SIMD,MISD,MIMD
分布式计算,多计算机系统,容错计算
非冯,诺依曼型计算机,非图灵计算模型,BSS机器 (实数域 ),
第五代计算机,日本,人工智能计算机,单调逻辑与非经典逻辑,智能的本质与模型
非电子计算机,金属互连电路的极限 (J.Coke),并行计算机系统的加速极限 (G,Amdahl),光子计算机,量子计算机,生物计算机
网格计算与 MAS(多代理系统 ),返回第二章作业
1、解释下列名词,① 集合与命题 ② 全集与类 ③ 计算与可计算性 ④ 算法与算法复杂性
2、给出,1”的至少三种以上含义。
3、直观分析哥德尔定理的正确性。
4、简述图灵机的直观组成与形式描述。
5、试分别描述当 x=011和 11时,x+1图灵机的工作过程。
6、简述计算机的组成、结构和工作过程。
7、简述操作系统的概念与功能，及其在计算机系统中的位置。
8、为什么要引入进程的概念？进程一般有哪些状态？
9、试述 计算机 网络的概念与组成。
10,ISO的 OSI/RM把网络体系结构分了哪七层？
11、试述计算机的划代与发展趋势。
12、试述 网络时代的三大基本定律。
13,用选择排序算法将 32,74,23,89,3,99,16,19,55,41十个数按从小到大的顺序排列，要求写出排序过程。 返回
理论计算机
冯,诺依曼型计算机
计算机网络
新型计算机
计算机发展反思,动力,社会需求 ;
目标,追求新型计算模型,制造先进计算机 ;
条件,理论指导,技术支持。
理论计算机
布尔代数
数理逻辑与哥德尔定理
计算模型与图灵机
可计算性,在有限步骤内可完成。
图灵机可计算性。
计算复杂性 返回计算复杂性
算法的概念
几个例子
算法的评价
证比求易问题
相似性原理
对偶性原理
NP完全性问题 返回几个例子
计算,x+1” 的图灵机
选择排序问题,将 3,74,23,89,22,99,65,109,55、
45十个数按从小到大的顺序排列。步骤：
1、取未排序的数中的第一个数，假设它是其中最小的数。
2、将它依次与其后的数相比较，若发现某个数更小，则目前为止发现的最小数是该数，并假设它是最小数，重复
2直到比较到最后一个数，此时，假设的最小数就是未排序的数中的最小数。
3、将该最小数与未排序的数中的第 1个数交换位置。回到
1，直到所有数都排序。
执行该步骤 1-3，产生以下的 排序过程,返回选择排序过程第 1遍,3,74,23,89,22,99,65,109,55,45
第 2遍,3,22,23,89,74,99,65,109,55,45
第 3遍,3,22,23,89,74,99,65,109,55,45
第 4遍,3,22,23,45,74,99,65,109,55,89
第 5遍,3,22,23,45,55,99,65,109,74,89
第 6遍,3,22,23,45,55,65,99,109,74,89
第 7遍,3,22,23,45,55,65,74,109,99,89
第 8遍,3,22,23,45,55,65,74,89,99,109
第 9遍,3,22,23,45,55,65,74,89,99,109
返回算法的评价
算法的复杂性,是对算法计算所需的 时间和空间的一种度量。
算法的时间复杂性,是对算法计算所需 时间 的一种度量。
算法的空间复杂性,是对算法计算所需 空间 的一种度量。
复杂性度量函数,算法在求解一类问题的过程中随 问题规模 大小变化引起的算法中 抽象的基本运算执行的次数 或 存储空间量 的变化规律。
例如,f (n)=2n2+3n+1=O(n2),读作 n2阶,其中,n为问题规模 。 返回证比求易问题
三个中国人问题,洪加威,1980
国王：艾述，宰相：孔唤石，公主：秋碧贞楠求数 8770428644836899的一个真因子。
证明 23092871是 8770428644836899的一个真因子。
问题规模 17位，小因子不超过 9位顺序算法与并行算法
对偶性原理,在并行计算模型上，计算的时间与空间可以互换。
相似性原理,所有合理的、功能足够强的计算模型不仅可以相互模拟计算，而且它们相互模拟时，同时使用本质上相同的并行时间，本质上相同的空间，本质上相同的顺序时间。 返回
NP完全性问题
难解型问题,没有多项式时间复杂性算法的问题。
P类问题,存在图灵机可计算的多项式时间复杂性算法的问题。
NP问题,存在非确定图灵机可计算的多项式时间复杂性算法的问题。
NP完全性问题,NP问题中若有一个问题找到了多项式时间复杂性算法，这个类中的其它问题也可找到多项式时间复杂性算法，则 P=NP。 返回算法的概念
算法,一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列。此外，
算法的规则序列须满足如下五个重要条件：
1,有穷性,算法必须总是在执行有穷步之后结束；
2,确定性,算法的每一个步骤必须是确切地定义的；
3,输入,算法有零个或多个输入；
4,输出,算法有一个或多个输出；
5,能行性,算法中有待执行的运算和操作必须是相当基本的。 返回布尔代数
布尔,G,Boole,19世纪，英国，自学成才
集合代数：集合、集合的运算与性质集合 A,A的补集 A’，空集 Ф，全集 1，属于?,相等?，包含?，交?，并?
集合与命题
布尔代数实现了从 一组逻辑公理 出发，依靠 代数演算 来推导逻辑定律或定理，用数学的方法来研究人的思维结构。
语义推导与语法推导
布尔代数、数字逻辑与电子计算机 返回香侬 是现代信息论的著名创始人。 1938年，香侬在发表的论文中，
首次用布尔代数进行开关电路分析，并证明布尔代数的逻辑运算可以通过继电器电路来实现。
阿塔纳索夫 提出了计算机的三条原则：
1）以二进制的逻辑基础来实现数字运算，以保证精度；
2）利用电子技术来实现控制、逻辑运算和算术运算，以保证计算速度；
3）采用把计算功能和二进制数更新存储功能相分离的结构。
布尔代数与计算机
Claude Shannon
语义推导与语法推导定理,A?A=A（幂等律）。
集合代数中的 语义推导：
证明,1、设?x?A?A,则 x?A 且 x?A,
所以 x?A,故 A?A? A；
2、设?x?A,则 x?A 且 x?A,所以
x? A?A,故 A? A?A ；
所以,A?A=A □
逻辑代数中的 语法推导,返回逻辑代数中的 语法推导定理,A?A=A（幂等律）。
证明：因为：
A= A? 1 （ 1、）
= A? （ A? A’） （ 8、）
= （ A? A ）? （ A? A’） （ 5、）
= （ A? A ）? 0 （ 7、）
= A? A （ 2、）
所以,A?A=A □
布尔代数系统公理
1,A? 1 = A ；
2,A? 0 = A ；
3,A? B= B? A ；
4,A? B= B? A ；
5,A?（ B? C） = （ A? B）? （ A? C） ；
6,A?（ B? C） = （ A? B）? （ A? C） ；
7,A? A’= 0 ；
8,A? A’= 1 。
返回布尔代数系统公理
集合表示法,
设 k代表类,?是 集合的 包含关系符号，那么，系统的 公理为
1、如果 A? k 且 B? k,则 A? B?k ；
2、如果 A? k 且 B? k,则 A? B?k ；
3、存在?, k,使得对任意的 A，如果 A?k,则 A = A ；
4、存在?,k,使得对任意的 A，如果 A?k,则 A = A；
5,A? B= B? A,A?k,B? k ；
6,A? B= B? A,A?k,B? k ；
7,A? （ B? C） = （ A? B）?（ A? C）,A?k,B?k,C? k ；
8,A? （ B? C） = （ A? B）?（ A? C）,A?k,B?k,C? k ；
9、对任意的 A，存在一个 A’，使得 A?A’= k,A? A ’= Ф；
10、在类 k中至少存在两个不同的元素。
命题表示法,返回布尔代数系统公理命题表示法
1,A? 1 = A ；
2,A? 0 = A ；
3,A? B= B? A ；
4,A? B= B? A ；
5,A? （ B? C） = （ A? B）? （ A? C） ；
6,A? （ B? C） = （ A? B）? （ A? C） ；
7,A? A’= 0 ；
8,A? A’= 1 。 返回集合与命题
类,我们讨论的所有对象和事物的全体构成的论域。全集，
1。
命题,是指其含义确定，取值为,真,或,假,的断言。
1表示一种无论什么情况下都为,真,的恒真命题,?表示一种无论什么情况下都为,假,的恒假命题。因此 1也可看成由所有命题构成的类。例：西安是十一朝古都。
将集合看成命题,外延与内涵,040601班的全体学生
集合代数就可以看成是一种建立在命题表示基础上的 逻辑代数。
把,真,用 1表示，把,假,用 0表示，逻辑代数就可看成是所有命题只取 0,1二值的代数演算系统 —— 布尔代数 。
推理规则
等式的传递推导：如果已知 A=B,B=C，那么,A=C；
反证法：如果假定一个命题不成立，由此可以得出矛盾的结论，那么原命题得证；
代换推导：如果一个命题 A中的某一命题 B
用与它相等的命题 C代换之后得到命题 D，
那么,A=D ；
…… 返回数理逻辑与哥德尔定理
谓词演算,A=张山 是 040601班的学生 。040601（ 张山）? 040601（ x）x040601（ x） x 040601
（ x），皮尔斯和米切尔，哥德尔
数理逻辑,用数学方法研究推理的科学。
通用逻辑系统,从少数几条公理和推导规则出发，证明或发现和导出所有的未知定理。 希尔伯特 (Hilbert)
哥德尔定理,任一形式系统，它的一致性和完全性是不可兼得的。或者说，如果一个形式系统是一致的，
那么这个系统必然是不完全的。所谓不完全，就是指存在一个公式 A，使得 A和 A’在这个系统内都不可证。
返回计算模型与图灵机
图灵和他的时代同行
图灵机的直观描述
图灵机的形式描述
计算,x+1” 的图灵机
通用图灵机返回图灵和他的时代同行
可判定问题,能否找到一种有效的办法可以判断任意一个命题的真假?
20世纪 30年代,数理逻辑学家
计算模型,哥德尔 (K,G?del):递归函数 ;丘奇 (A,Church),?演算 ;图灵 (A.M,Turing):图灵机 ;波斯特
(E.l,Post):波斯特系统 — 等价
图灵,英国数学家,1936年，图灵机，
存储程序,1966年,ACM
（ Association for Computing
Machine),图灵奖计算机科学之父,阿伦 ·图灵图灵机的直观描述一条两端可无限延长的带子，一个读写头，一个控制器，带子由可擦写的小格组成，读写头可左右移动并读写，可写字符集
{0,1,b}，控制器有有穷个状态，一个开始状态，一个结束状态，控制器的命令为：
（状态，符号）?（写符号，移动，新状态）
图灵机从开始状态工作直到 结束状态停止，带上的内容就是计算结果。 返回图灵机的形式描述图灵机是一个五元组（ K,?,?,s,H），
其中：
K是有穷个状态的集合；
是字母表，即符号的集合；
是转移函数，即控制器的规则集合；
s? K 是初始状态；
H? K是停机状态的集合。 返回计算,x+1” 的图灵机图灵机
状态集合 K,{Start,Add,Carry,Noncarry,
Overflow,Return,Halt}；
字母表?,(0,1,*)；
规则集合?；
初始状态 s,Start；
停机状态集合 H,{Halt}。
例,当 x=5时,图灵机的工作过程 。 返回当 x=5时,图灵机 的工作过程状态 读写头位置
Start * 1 0 1 *
Add * 1 0 1 *
Carry * 1 0 0 *
Non- * 1 1 0 *
Non- * 1 1 0 *
Return * 1 1 0 *
… … … … … …
Halt * 1 1 0 *
通用图灵机
为,x+1” 图灵机编码 ；
多带 图灵机和单 带 图灵机是等价的；
三带图灵机 M；
图灵机 M与,x+1” 图灵机比较 ；
通用图灵机的重要意义：
1、把程序也作为数据；
2、存储程序和程序控制。
返回三带图灵机 M
第一条放输 x=5,即,*101*”,(00100001000000010010)
第二条放所有规则：
(Start,*,left,Add) (Add,0,1,Noncarry)
(Noncarry,1,left,Noncarry),(0101 0010 0011 0110
0110 0000 0001 1000 1000 0001 0011 1000)
第三条放初始状态,Start,0101
工作过程,1,扫描第三条获当前状态,Start,0101； 2、
扫描第一条获当前字符,*:0010； 3,扫描第二条获一个
16位字符串，前 4位为当前状态，第二个 4位串为当前字符，
则找到对应规则； 4,将第三条带上字符串改为该规则的第四个 4位串（新状态），并由第三个 4位串指挥第一条带上的动作； 5,若某一步在第二条带上找不到对应规则，则第三条带上为停机状态,M停机。 返回为,x+1” 图灵机编码
3个字母,2个动作,7个状态，共 12符号，需要 4位二进制码（ 24=16）：
为字母 编码,0:0000,1:0001,*:0010
为动作编码,left:0011,right:0100
为状态编码,Start:0101,Add:0110,Carry:0111，
Noncarry:1000,Overflow:1001,Return:1010,Halt:1011
为规则编码：
第一条 (Start,*,left,Add):(0101 0010 0011 0110)
第二条 (Add,0,1,left,Noncarry)? (Add,0,1,Noncarry),
(Noncarry,1,left,Noncarry)
(Add,0,1,Noncarry):(0110 0000 0001 1000),
(Noncarry,1,left,Noncarry):(1000 0001 0011 1000),
返回图灵机 M与,x+1” 图灵机比较
,x+1” 图灵机,输入 x，输出 x+1，功能固定的一个程序。
图灵机 M：输入为,x+1” 图灵机的编码,输出 x+1；若 输入换为其它图灵机的编码，则 M又能完成其它图灵机的功能 —— 通用图灵机 。
冯,诺依曼型计算机
冯,诺依曼和他的时代同行
存储程序式通用电子计算机组成
存储程序式通用电子计算机结构
图灵机与计算机的比较
计算机的更新换代
操作系统、进程与线程 返回冯,诺依曼和他的时代同行
冯,诺依曼 (Von Neumann),美藉匈牙利科学家，早期研究数理逻辑,1944
年夏天,参加 ENIAC的设计,1945年 3
月,提出第一台 存储程序式通用电子计算机 ──EDVAC的设计方案,1952年制造成功 。
冯,诺依曼和戈德斯坦
冯,诺依曼和 莫克利
冯,诺依曼和图灵计算机之父：
冯,诺依曼存储程序式通用电子计算机结构程序 由 指令组成，并和数据 一起存放在存储器中，机器一经启动，就能按照程序指定的逻辑顺序把指令从存储器中读出来逐条执行，自动完成指令规定的操作。
存储程序式通用电子计算机组成冯,诺依曼型计算机 五大 组成 部分,
运算器功能：算术运算和逻辑运算
控制器功能：使计算机能自动地执行程序，并使各部分协调工作
CPU=运算器 +控制器 =处理机存储器功能：用于保存程序和数据主存储器 (内部存储器 )存放当前所执行程序的指令和数据辅助存储器 (外部存储器 )存放暂不参加运算的程序的指令和数据
输入设备 用于程序和数据输入（标准设备：键盘）
输出设备 用于程序和数据输出（标准设备：显示器） 返回图灵机与计算机的比较
（ 1）、图灵机存储空间无限，计算机存储空间有限。
（ 2）、图灵机指令系统不定，计算机指令系统确定。
（ 3）、图灵机仅是理论模型，计算机是其物理实现。
所以，从理论上讲，图灵机的能力比计算机的能力强。 返回第一代
（ 1946~1956）
电子管
5千 ~4万（次 /秒）
第二代
（ 1957~1964）
晶体管几十万 ~百万（次 /秒）
第三代
（ 1965~1970）
集成电路百万 ~几百万（次 /秒）
第四代
（ 1971~90年代）
VLSI/LSI
几百万 ~几亿（次 /秒）
计算机发展的几个阶段摩尔定律 发展趋势晶体管数单位时间执行的指令数百万条/
每秒每 18个月芯片能力增长一倍。
计算机第一定律 —— 摩尔定律计算机的 发展趋势
微型化
巨型化,
世界上第一台超级计算机,1975年,,Cray-I”
超级计算机应用：天气预报、地震机理研究、石油和地质勘探，卫星图像处理等大量科学计算的高科技领域。
中国超级计算机：国防科技大学研制的,银河 1号,,
,银河 2号,和,银河 3号,,国家职能计算机中心推出的,曙光 1000”,,曙光 200I”和,曙光 3000”
网络化
智能化 返回操作系统、进程与线程
计算机操作方式的演变：
1、手工 2、批处理：单道与多道 3、联机：分时与实时
什么是操作系统？
操作系统的功能：
处理机管理、内存管理,I/O（输入输出）管理、
文件管理、作业管理
进程与线程
操作系统的分类：
批处理、分时、实时、网络、分布式 返回什么是操作系统操作系统是最基本的系统软件，其他的所有软件都是建立在操作系统的基础上。
操作 系统各种应 用程序
DOS
基础知识管家婆管理硬件资源协调后台工作服务生提供用户与计算机的交互接口进程与线程
并行：两个或两个以上的事件在同一时刻发生。
并发：两个或两个以上的事件在同一时间段内发生。
进程（ Process）,具有独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。
线程（ Thread）,进程内部的一个执行控制流程，
是系统进行处理机调度的最小单位。
进程状态的转换返回进程状态的转换返回计算机 网络与分层协议
计算机网络的概念,是计算机技术和通信技术发展的产物，是利用通信设备将多个计算机互联起来而形成的有机体，以实现计算机间的通信和资源共享。
计算机网络示意图
计算机网络组成
计算机网络的历史
计算机 网络体系结构
发展规律 与 广范应用返回高速通信线路主机终端通信子网通信控制处理机终端终端主机主机主机计算机网络示意图说明：通信子网 主要由通信线路和网络控制机组成，
负责网络通信和数据传送。
网络硬件：
网 络 系统 的 组 成
网络软件,
主机：连在网上的一台自主计算机。
传输介质：双绞线、同轴电缆、光纤、微波
网络连接设备：网卡、调制解调器、路由器
协议：是关于通信如何进行所制定的一系列标准。网络协议是指网络中通信各方事先约定的通信规则，计算机之间进行通信时必须使用相同的网络协议 。
例如,TCP/IP,HTTP等
操作系统：用以管理网络资源和通信。
应用软件：实现各种各样的网络应用 。
计算机网络一般由服务器、工作站、外围设备和通信协议组成。服务器是整个网络系统的核心，它为网络用户提供服务并管理整个网络。工作站（ Workstation）是指连接到网络上的计算机。
计算机网络发展历史回顾
七十年代的计算机网络
X.25 分组交换网：各国的电信部门建设运行
各种专用的网络体系结构,SNA,DNA
Internet 的前身 ARPANET进行实验运行
八十年代的计算机网络
标准化计算机网络体系结构,OSI
局域网络 LAN 技术空前发展
建成 NSFNET,Internet 初具规模
九十年代的计算机网络
Internet空前发展
Web技术在 Internet/Intranet 得到广泛应用 返回网络时代的三大基本定律摩尔定律,
CPU性能 18个月翻番,10年 100
倍。
所有电子系统
（包括电子通信系统，计算机）都适用光纤定律,
超摩尔定律，
骨干网带宽 9
个月 翻番,10
年 10000倍 。
带宽需求呈超高速增长的趋势联网 定律：
（迈特卡尔夫） 网络价值随用户数平方成正比。
未联网设备增加 N倍，效率增加 N倍。 联网设备增加 N倍，效率增加 N2倍网 络 体 系 结 构
体系结构,层和协议的集合 。
表示层会话层传输层网络层数据链路层物理层应用层表示层会话层传输层网络层物理层应用层数据链路层传输介质应用层协议表示层协议会话层协议传输层协议网络层协议链路层协议物理层协议
ISO
开放系统互联参考模 型
(OSI/RM) 返回
OSI参考模型各层功能
OSI (Open System Interconnection)
1.物理层（ The Physical Layer）
在物理线路上传输原始的二进制数据位（基本网络硬件）。
2.数据链路层（ The Data Link Layer）
在有差错的物理线路上提供无差错的数据传输（ Frame）。
3.网络层（ The Network Layer）
控制通信子网提供源点到目的点的数据传送（ Packet）。
4.运输层（ The Transport Layer）
为用户提供端到端的数据传送服务。
5.会话层（ The Session Layer）
为用户提供会话控制服务（安全认证）。 token management and
synchronization (insert checkpoints into the data stream)
6.表示层（ The Presentation Layer）
为用户提供数据转换和表示服务。
7.应用层（ The Application Layer）
为用户提供各种应用服务。 返回革命性的网络应用
开发今天 Internet没有，对国家重要的网络应用
健康保健：远程医疗、紧急医疗响应支持
教育：远程教育、数字图书馆
科学研究：能源、地理系统、气象、生物
国家安全：高性能全球通信、先进的信息传播
环境：监测、预测、警告、响应
政府：传递政府服务和信息给公民和企业
突发事件：灾难响应、危机管理
设计和制造：制造工程
主要策略：重点研究基础性应用
分布式计算应用、协同性应用 返回新型计算机
并行计算,多 CPU系统,多微处理器系统 (机群系统,高性能计算机系统 ),通道,SISD,SIMD,MISD,MIMD
分布式计算,多计算机系统,容错计算
非冯,诺依曼型计算机,非图灵计算模型,BSS机器 (实数域 ),
第五代计算机,日本,人工智能计算机,单调逻辑与非经典逻辑,智能的本质与模型
非电子计算机,金属互连电路的极限 (J.Coke),并行计算机系统的加速极限 (G,Amdahl),光子计算机,量子计算机,生物计算机
网格计算与 MAS(多代理系统 ),返回第二章作业
1、解释下列名词,① 集合与命题 ② 全集与类 ③ 计算与可计算性 ④ 算法与算法复杂性
2、给出,1”的至少三种以上含义。
3、直观分析哥德尔定理的正确性。
4、简述图灵机的直观组成与形式描述。
5、试分别描述当 x=011和 11时,x+1图灵机的工作过程。
6、简述计算机的组成、结构和工作过程。
7、简述操作系统的概念与功能，及其在计算机系统中的位置。
8、为什么要引入进程的概念？进程一般有哪些状态？
9、试述 计算机 网络的概念与组成。
10,ISO的 OSI/RM把网络体系结构分了哪七层？
11、试述计算机的划代与发展趋势。
12、试述 网络时代的三大基本定律。
13,用选择排序算法将 32,74,23,89,3,99,16,19,55,41十个数按从小到大的顺序排列，要求写出排序过程。 返回
