计算概论关键词.docx
- 文档编号:14590608
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:15
- 大小:34.82KB
计算概论关键词.docx
《计算概论关键词.docx》由会员分享,可在线阅读,更多相关《计算概论关键词.docx(15页珍藏版)》请在冰点文库上搜索。
计算概论关键词
计算概论关键词
计算原理部分
//无穷
潜无穷:
作为永远延续的过程的无穷
如自然数数列1,2,3,4,5,……
实无穷:
作为已完成的整体的无穷
如全体自然数的集合{1,2,3,4,5,…n,…}
亚里士多德(Aristotle,B.C.384-322)最先提出要区分潜无穷和实无穷,并认为只存在潜无穷,实无穷即无穷集合是不存在的,因为无穷多个事物不能构成一个固定的整体。
无穷计算造成了困扰
无穷数列的求和(收敛和发散)
无穷集合的性质被陆续发现,虽然人们不承认无限集合的存在
普罗克拉斯(Proclus,410-485)在研究直径分圆的问题时发现直径数量和将圆分成部分的数量有一一对应的关系,由于直径的数量是无穷的,所以表明直径的数量集合{1,2,3,…n,…}和圆被分成部分数量集合{2,4,6,…2n,…}之间存在一一对应的关系
伽利略(G.Galileo,1564-1642)也发现不等长线段上的点可以构成一一对应关系。
数字计算与模拟计算
·离散和连续(数字与模拟)
··基于不同数系的计算
···自然数(整数、有理数)
···实数
··两种不同形式的计算
···面向有限序列计数的计算
简单的四则运算
···面向物理量测量的计算
复杂的开方、对数、指数、三角函数等需要无穷计算的运算
电子计算(模拟与数字)
模拟电路基于电路的电气特性,模拟运算速度快,容易实现复杂运算,但限制较大,精确度低
数字电路基于分立单元的组合,结构简单,过程清晰,结果精确
电子管
晶体管
集成电路
大规模集成电路
//半加法和全加法器
半加法器:
不考虑低位的进位全加法器:
考虑低位的进位。
可并联成多位的加法。
//计算的概念
从已知的条件出发
根据既定的规则(算法!
)对表示问题的符号进行变换
(经过有限的变换步骤,)得到表示解的符号
图灵机基本结构和计算规则
一条分格的无限长的纸带,每格可容纳一个字符
一个读写头,可以在纸带上移动,读出当前格子的字符,重写格子上的内容,改变自己的内部状态
一系列关于读写头动作的规则(程序)
纸带上的内容(包括空白B)是计算前的输入和计算完成后的输出
计算从读写头的初始状态s0、初始位置和输入的纸带格局开始
按照规则进行读写头的移动、纸带字符的修改,直到进入停机状态(SH/SY/SN)
在停机状态时纸带的内容就是输出
规则q={si,ak,al,sj,d},si,sj∈S(内部状态),ak,al∈A(纸带字符),d∈{L,R,N}(左移,右移,不动)
表示如果读写头当前状态为si,读到当前格子字符为ak,则:
改写格子内容为al
转变状态为sj
进行d指定的动作(读写头左移、右移或不动)
限制:
有限条规则
任意两条规则前两项不能相同:
动作的确定性
没有规则第一项是SH/SY/SN:
保证这三个状态是停机状态
✹表示自然数
✹用n+1个连续的1表示自然数n
✹0=1,1=11,2=111,3=1111……
✹表示二元参数
✹两个输入的自然数之间用B隔开
✹0,2=1B111
✹f(m,n)=m+n:
即字符串的连接操作
✹f(m,n)=m*n:
即将m重复copyn次
计算机器的一般结构
输入数据程序计算输出结果
中间结果
通用计算机
✹“计算机的计算机”:
实现一套通用的指令
✹可以用来模拟算法和程序实现
✹同样的输入产生同样的输出
✹将算法和程序独立出来
✹将程序如数据一样存储可变
✹不同的程序实现不同的功能
用通用指令集来描述算法和程序
//冯诺伊曼结构
✹运算器和存储器分离
✹程序和数据混合存储
✹指令和数据宽度相同(位数相同)
✹指令的自修改问题
✹将程序指令作为数据看待
✹编译器:
由高级语言的源代码产生机器指令
·运算器[算术逻辑单元]ALU
算术逻辑位移运算[除法、浮点运算一般不在这中实现]
·控制器CU
保存机器状态:
寄存器[运算的临时结果,调取堆栈]
从内存中调取指令,转化为控制信号传递给ALU执行
计算结果写回内存
·时钟控制的机器周期
1指令周期和执行周期2流水线操作
·存储器Mem指令+数据
可以存放数据或者指令
存放地址线性编制
读出内容/写入内容
·输入输出设备I/O
与外界的接口实现数据交换
在CU/ALU支配下,与内存交换数据
DMA直接内存访问方式
·总线Bus
信号传输通道
连接控制器、运算器、输入输出设备、存储器,传递数据、控制命令、程序指令
由时钟协调占用次序
CPU=ALU+CU
冯诺依曼瓶颈
由于CU和ALU分离,高速的ALU不得不等待低速的CU传递数据[用高速缓存来解决]
指令的恶意或错误自我修改导致功能混乱或系统崩溃
计算机运行过程
1.程序和指令存储在内存
2.控制器的程序计数器PC指向存储在内存中的第一条指令
3.CU调取被存中的第一条指令,转化为控制信号传导到ALU
4.ALU根据控制信号进行计算,结果写回内存
5.控制器中的状态改变
6.程序计数器按照指令的后果改变,指向下一条命令[程序顺行,条件跳转,无条件跳转,程序块调用和返回]
7.returnto2
信息技术原理部分
概述
///信息系统构成
硬件:
信息系统的物理基础
软件:
实现信息处理的过程
数据:
用来表示信息,被软件处理
用户:
与信息系统交互,实现输入输出和信息的理解
信息的定义
一种消息,通常以文字、声音或者图形的方式来表现,是数据按有意义的关联排列的结果。
包括:
符号[形式和载体]和意义[内容和本质]
信息的表示
二进制、十六进制、八进制之间的转换
·二进制数字用(1001)b表示
十进制用d,八进制o,十六进制h
··6转换为二进制?
6÷2=3余0
3÷2=1余1
剩得数1
6=(110)d
··2倍即加0
··1后面全零的,几个零就是2的几次方
记住常用的2次方,便于估计
256,512,1,024(1K~1千)
65,536,1,048,576(1M~1百万)
1,073,741,824(1G~10亿)
32次方~40亿
·十六进制
每位有16种符号:
0~9,A~F
和二进制之间的转换相当容易
从低位开始每四位二进制数一组转到十六进制
反之亦然
10100111b=A7h
·八进制
每位有8种符号:
0~7
每三位一组计算J
101010b=52o=2Ah
bit,byte,word
·位bit:
0、1
·字节byte:
8bits
·字word:
一般是4bytes,32bits
//补码
·补码表示负数
·正数的补码等于自身,最高位为0;
·N位二进制表示负数即加上2N;
·负数的补码最高位为1;
·能表示的最大正数减半
·如:
-1补=256+(-1)=255=11111111b
·a-b=a+(-b)补
定点数和浮点数(了解IEEE754)
·定点数fixedpoint
固定总位数,固定小数点后的位数
如:
decimal(4,2):
4位,小数点后2位
表示范围和表示精度限制较大
·科学记数法
用基数和进制的指数表示小数:
1.2234E7
·浮点数floatpoint
采用科学记数法,记录规格化的基数和指数
规格化normalized:
小数点左边恰为一位非零数
指数:
一个整数
固定有效数字,小数点位置浮动
IEEE754
定义了四种格式
最常用:
单精度浮点数32bits,双精度浮点数64bits
扩展单精度和扩展双精度
字节序问题
出现在多字节表示整数时
高位高地址vs高位低地址
字节序变换问题常见于网络通信[跨平台]
结构化数据
由简单类型数据组合成的结构
数字图像
图像作为像素的矩阵
像素:
规则排列的图像单元,具有颜色和位置的属性
RGB颜色模型
✹三原色模型RGB
✹用三元数表示红、绿、蓝的颜色强度
✹更多的位数可以表示更多的颜色
✹8位、16位
✹24位(真彩色)、32位(增加了透明度)
空间数据的表示
·空间数据:
描述与地球表面有关的信息
·以几何形状和属性表示的空间数据
✹几何形状描述占据的空间位置和范围
✹结构化数据描述内在的属性
✹通过几何计算获得信息和知识
·以数字图像表示的空间数据
✹遥感:
拍摄“地球的照片”(数字图像)
✹每个像素代表地面的一块区域,颜色值告诉我们
✹通过数字图像处理获得信息和知识
·空间数据的处理:
非结构化数据
信息的获取
信息获取的过程
✹能量转换:
各种形式外部信息转换为电信号
✹数字化:
模拟电信号转换为数字信号
✹输入接口:
数字信号编码进入存储器
✹后期处理:
处理原始数据得到目标信息
采样,采样精度和采样频率
采样:
在指定的时间点上获得的测量值
分辨率:
一个范围内可区分的不同值数目
采样精度:
从最低幅度到最高幅度所分的级数
采样频率:
两次采样之间的时间间隔。
[若要完整采样,那么采样频率至少为原频率的两倍]
//串行接口和并行接口
·串行接口
每个时钟节拍传输1bit
传输线简单,距离长,抗干扰能力强
目前的高速接口趋势
·并行接口
每个时钟节拍同时传输多个bits
传输线复杂,距离短,抗干扰能力差
早期的高速接口
信息的存储
存储器分级体系
从内到外,从快到慢,从小到大的存储器分级体系
基本存储器:
寄存器[register]高速缓冲存储器[cache]主存储器
联机存储器:
快闪存储器硬盘存储器
脱机存储器:
光盘存储器磁带存储器
信息冗余(目的、基本方法)
电气干扰和许多偶然因素会引起数据的丢失和篡改
将数据作双份保存[镜像],则如果镜像不同出现错误,镜像相同暂时正确
奇偶校验循环冗余校验简单校验和散列函数海明码独立磁盘冗余阵列
数据压缩(目的、基本方法)
按照一定的规则重新编码,以达到减小数据量的目的
无损压缩
压缩数据解压缩后与原数据完全一致
游程编码字典编码Huffman编码[基于概率统计]线性预测编码
有损压缩
在允许失真的前提下,可大幅削减数据量,并尽量维持接近原视听效果
降低分辨率正交变换
信息安全
数据加密的主要要素
机密性[任何未授权者都无法理解经过加密的消息]
完整性[可以检测存储介质或传输过程中对加密消息的任何更改或讹误]
不可抵赖性[发送方不能抵赖先前生成或发送了加密消息]
身份验证[发送方和接收方能够彼此确认对方的身份以及消息的来源和目的地]
加密解密的流程
明文---[密钥]加密算法----密文----[密钥]解密算法-----明文
密钥的概念和种类
加密时的附加信息,由加密者和解密者掌握
对称密钥:
加密和解密使用一个密钥
公开密钥:
加密解密使用不同的密钥,一个称为公开密钥,另一个称为私有密钥
数据隐藏(目的、基本方法)
隐藏传递信息,数字作品的版权保护[数字水印],对加密的有效补充
将需要隐藏的数据嵌入另一个称作宿主[载体]的数据中
保证嵌入后宿主不会出现外观上的变化;最好具有强健性,对宿主进行一定修改也不影响隐藏的数据。
数据隐藏的一般流程
载体---[秘密数据+隐写密钥]嵌入算法-----隐写载体----解密算法[隐写密钥]-----秘密数据
身份认证的一般种类
基于签名认证
基于口令认证
基于公开密钥加密的认证
[数字证书:
用认证权威实体的私钥加密的个人信息,可以通过此权威实体公布的公钥来解密验证]
基于生物特征识别的认证
信息传输
Internet结构
用户/服务器---路由器---路由器---用户/服务器
Internet地址和域名
域名:
层次化名称,分配给各级用户
IP地址:
层次化的4字节整数地址,分配给计算机或者路由器
IPv6:
下一代互联网协议
路由和路由器
路由:
为数据从远端传送到目的端选择通路
路由器:
为通过自己的数据选择一条通路;搜集统计数据;记录并选择最佳路径;防止网络拥塞
IPv6概念
采样128位地址;适用更高速网络和增强的网络安全;更强的自动配置,支持“永远在线”特性
Internet传输级别的服务
面向连接的可靠传输;无连接的不可靠传输[最基本]
//协议
定义了两个通讯实体之间的交换信息的次序和格式,以及就接收和发送信息所采取的格式
网络协议的层次
应用层[软件]---运输层[IP协议数据包]----网络层[IP地址]---链路层[光电信号]---物理层[网卡]
HTML
超文本描述语言
HTTP
超文本传输协议
信息组织和检索
线性组织、顺序检索、二分查找法
·数据的相继排列,称为线性表
··信息组织的最基本方式,符合存储器的排列特征
·顺序检索:
最基本的检索方式
从第一个数据开始依次查找
最好情况一次对比找到
最坏情况N次对比找到,平均N/2
·二分查找法
和我们查英汉词典的方法相同
需要查找的值和中间的元素对比,如果后者大,则在线性表的前半部继续用相同的方法查找,反之则在后半部查找,直到找到所需的值,最多查找log2N次
树结构、树的遍历、排序树的查找
·非线性的层次化组织方式
·有一个数据称为“树根(根节点)”,树根有若干下级数据(子节点),每个下级数据又各自有若干下下级数据
·树的遍历
深度优先;广度优先
·查找
从顶层开始,逐层向下,快速缩小搜索空间
网状组织(基本元素、类型)
元素:
节点;连接节点的边
类型:
有向网;无向网
节点可达性、连通和最佳路径选择
可达性:
从一个节点是否可以沿着边到达另一个节点
连通:
任意两个节点之间都是可达的
最佳路径选择:
两个节点间的若干通路之间选择一最短的通路。
用结构化数据表示实体和关系
简单数据表示属性;简单数据的组合体用来表示实体和关系
面向问题和面向过程的解决方案
面向问题:
用适当的语言描述清楚要解决的问题
面向过程:
用适当的语言描述清楚解决问题的过程
SQL的特点
结构化查询语言
更贴近自然语言的语法
面向一个信息集合处理,而不是一个个单条信息
非过程化的检索方式
可以完成信息结构定义,信息操纵,检索,完整性保证,权限控制等功能
关键字检索的基本原理
保持信息原始状态,由计算机按关键字自动进行组织
从精确描述问题到辅助用户精确描述问题
1维护一个关键词表,记录关键词和关键词之间的相关程度
2对所有信息文件进行内容扫描,记录每个关键词在信息文件中的存在性、相关性和位置
3当文件加入、改变、删除时,相应修正上述的记录
4用户输入关键词进行检索时,根据关键词匹配和相关度给出相关的信息文件的列表
5指引用户缩小搜索范围,搜索相关内容
基于内容多媒体检索的三个层次
原始数据
统计特性
语义特征
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 概论 关键词