内容简介(摘选)
本书是大学计算机专业的基础课教材,涉及计算机科学的各个方面.本书着重讲解基本概念而不是数学模型和技术细节,通过大量的图表和演示范例讲解计算机科学的基础知识.
本书既适合作为高等院校计算机专业学生的基础课教材,又可作为一般的计算机基础入门读物.
以下是我在阅读过程中的笔记,大概记了下所讲述的东西
可以先大概浏览下,如果感兴趣的话,再看原书
算是一篇读后感
正如作者的内容简介一样,这本书非常基础,讲的东西也很浅,很多东西都点到即止,
适合零基础的,看完后对整个计算机体系的相关概念有一个了解
2.数字系统
3.数据存储
4.数据运算
5.计算机组成
6.计算机网络
7.操作系统
8.算法
9.程序设计语言
10.软件工程
11.数据结构
12.抽象数据类型(ADT)
13.文件结构
14.数据库
15.数据压缩
16.安全
...
1.绪论
图灵模型
图灵机:设想所有的计算都可能在一种特殊的机器上执行
数据处理器:接收数据->处理->输出数据
可编程数据处理器:基于图灵模型的计算机
冯-诺依曼模型
图灵机中数据存储在存储器中,该模型认为程序也能存储在计算机的存储器中
存储器,算术逻辑单元,控制单元,输入输出单元
2.数字系统
数字系统定义了如何用独特的符号表示一个数字.
位置化数字系统:在数字中符号占据的位置决定了其表示的值
十六,八,二,十进制等互相转换
3.数据存储
位:bit 表示一个开关的开0或者合1
存储无符号整数:转换成进制,不够的位数左边补0,最左位表示正0负1
二进制补码表示法存储负数
浮点表示法,科学计数法
余码系统 所有数加7,余7码系统 所有数都可以用正数表示
(三四十页的篇幅讲解各种存储的进制表示法...)
音频:
存储一个音频信号的密度,每隔一段时间来自麦克风的信号,模拟数据
采样:在模拟信号上选择点记录 一般每秒40000个样本点
每样本位:8,16,32,64位
位率:每样本位没秒样本数 4000016=640000b/s=640KB/s
图像:
光栅图:样本称为像素
矢量图:数学表达式
视频:
图像在时间上的表示
4.数据运算
逻辑运算,移位运算,算术运算
逻辑运算讲一些与或非异或之类的运算
移位运算移到模式中的位
算术运算就是加减乘除
5.计算机组成
三个:CPU(算术逻辑单元,控制单元,寄存器),存储器,输入输出器
存储:磁盘:一点有磁性1无磁性0
CD: 凸起,反射层;激光扫描凸起或者可反射层
(然后就是二三十页的对三个系统合在一起,即程序流程的介绍,计算机怎么工作的...)
6.计算机网络
网络:由两个或两个以上通过链路连接的设备构成
链路:数据从一个设备传输到另一个设备的通信通道
物理拓扑:网络在物理上的布置方式,一个或多个链路形成拓扑
分三类:局域网(LAN),广域网(WAN),城域网(MAN)
互联网:能够相互通信的两个或多个网络
因特网:是最著名的互联网,很难给出准确表示,它是不断变化的
协议:因特网创建的一组规则,分解完成任务所需的服务
这些协议允许使用不同技术的LAN 和 WAN 互相连接到一起,控制因特网的一组协议称为 TCP/IP 协议族
物理层->数据链路层->网路层->传输层->应用层
应用层:
负责向用户提供服务,允许用户访问网络
客户/服务器体系结构:即分为一直运行的服务器端,需要时运行的客户端
应用层地址:不是用来发消息的,只是帮助客户找到服务器的实际地址
传输层:
整个消息的进程到进程的传输,负责客户和服务器进程间的消息的逻辑传输
传输层的地址:端口号 8000
1 多路复用和解多路复用:发送和接收信息
2 拥塞控制:
物理上传送数据包的下层网络可能发生交通拥塞,这可能引起网络丢弃一些数据包(丢包),有些协议为每个进程使用缓冲区,消息在发送前存储在缓冲区中,如果传输层监测到网络上有拥塞,就暂缓发送
3 流量控制:
监控接收端传输层,检查接收者接收的数据包是否过量
4 差错控制:
确保消息被目的传输层正确接收,如果未确认包无损坏到达和次序正确的确认,就提取缓冲区中保存的副本重新发送数据包
传输层协议: UDP,TCP,SCTP
UDP: 用户数据报协议,无连接协议
接收者不会通知发送者重新发送,只是默默丢掉
优点是效率高,速度快,适合用在及时性比准确性更重要的应用中,比如视频,音频
TCP: 传输控制协议,面向连接的协议
完美的传输层协议,包括所有4点,还使用了序号,确认号,检验和,缓冲区
如果数据包错误,就需要重新发送
SCTP: 流控制传输协议
结合了 UDP 和 TCP 提供4点,还适合视频音频的传输,如因特网电话和视频流
网络层:
负责单个数据包从计算机到计算机的发送
路由选择:
确定数据包的部分或全部路径
网络层协议:
主协议:IP(因特网协议)
数据链路层:
从一个节点(计算机或路由器)到另一个节点传送数据
数据链路层地址:
也叫物理地址或者MAC地址 -> 07:01:02:11:2C:5B
差错控制和流量控制:
只在节点发出点和节点到达点间实现
物理层:
负责组成帧的单个二进制位从一个节点到另一个节点的传送
物理层不需要地址,广播方式传播
应用层:进程交换消息
传输层:数据单元被称为段(TCP),用户数据报(UDP),包(SCTP)
网络层:数据报
数据链路层:帧
物理层:二进制位
电子邮件的运行流程
文件传输协议(FTP)
远程登录
7.操作系统
是计算机硬件和用户的一个接口,它使得其他程序更加方便有效地运行,并能方便地对计算机硬件和软件资源进行访问
计算机开机通电后,ROM自举程序加载操作系统至RAM内存,CPU的程序计数器设置为ROM的开始处
操作系统的发展历程:
批处理系统(人)->分时系统(多进程)->个人系统->并行系统(多CPU)->分布式系统(多计算机)
组成部分:
内存管理器:单道程序,多道程序
多道程序:
分区调度:给内存分区,每个区保存一个程序
分页调度:给内存分的区大小相等,称为帧,程序也分为与帧大小相等的页,提高了效率
请求分页调度:内存可以同时加载多个程序的页
请求分段调度:把程序分为主程序和子程序
进程管理器:
程序:一组存在硬盘上的稳定的指令
作业:程序被执行到结束的过程
进程:一个执行中的程序,在内存中运行的作业
死锁,饿死
8.算法
算法是一种逐步解决问题或完成任务的方法
算法是一组明确步骤的有序集合,它产生结果并在有限的时间内终止
选择排序:
把数据分为两个子列表及中间的一堵墙,找到未排序子列表中最小的元素,把它和未排序数据中第一个元素进行交换,经过每次选择和交换,两个子列表间假想的墙向前移动一个元素
冒泡排序:
就不说了
插入排序:
把数据分为两个子列表,未排序子列表中第一个元素被取出,然后转换到已排序的子列表中,插入到合适的位置(打扑克)
顺序查找:
从头开始挨个比较查找,最笨的方法
折半查找:
先排序再折半查找,就不说了
子算法:
结构化编程的原则是将算法分成几个单元
9.程序设计语言
机器语言:二进制代码
汇编语言:用符号或助记符的指令和地址
高级语言:可以通过翻译转化为机器语言
翻译:包括编译和解释
通过词法分析器,语法分析器,语义分析器,代码分析器将源文件翻译成目标文件
模式是一种计算机语言看待要解决问题的方式
(然后就是大篇幅的解释语言模式,面向过程与面向对象语言等)
10.软件工程
开发过程模型:
瀑布模型:开发过程只有一个方向的流动,前一个阶段不结束,后一个阶段不能开始
增量模型:首先完成整个系统的简化版本,不包含具体的细节,一点点增加功能
模块化,低耦合,高内聚
(然后十几页的说明一个好的系统需要的优点,比如可操作性,可维护性,可迁移性...)
测试阶段:分为白盒测试(玻璃盒测试),黑盒测试
白盒测试:
基于知道软件内部结构的,知道有关软件的一切
1>基本路径测试
在软件中每条语句至少被执行一次的方法,找到必须被走过的独立路径
2>控制结构测试
分为条件测试(检查模块中的任何条件,关系表达式是否被正确设置)
数据流测试(基于通过模块的数据流的)
循环测试(检查循环条件的正确性)
黑盒测试:
在不知道程序的内部也不知道程序是如何工作的情况下测试程序(按照软件完成的功能来测试软件,如数据的输入输出)
穷尽测试,随机测试,边界值测试
11.数据结构
数组
域(字典)
链表:
介绍了链表的基本特性,基本操作,增删改查
链表是一个有序数据的集合,每个元素包含下一个元素的地址,即每个元素包含两部分:数据和链.
搜索链表:只能是顺序查找,数组可以折半查找
开始处插入节点:新节点成为原先第一节点的前驱,新连接的节点成为第一个节点
开始删除节点:把第二个节点与表指针连接在一起
末尾处插入节点:新节点与原先最末节点连接在一起,新连接的节点变成最末节点
中间插入节点:把新节点与它的后继连接在一起,把新节点与它的前驱连接在一起
删除中间/末尾节点:把后继节点与前驱节点连接在一起
遍历链表:用一个步行指针,当元素被处理,从一个节点移到另一个节点,开始时,步行指针指向链表中的首节点,然后循环,指向下一个节点
12.抽象数据类型(ADT)
ADT包含了一组允许程序员使用的操作的定义,而且这些操作的实现是隐藏的,用户不用关心任务是如何完成的,而是关心能做什么,对外暴露API
限制线性表:
1>栈:只能在顶部插入删除,后进先出
没有细讲如何实现的,只是给了API,建栈,入栈,出栈,空栈,用来描述ADT的
应用:
倒转数据:先入栈再出栈
配对数据:算术符号的优先级
数据延迟使用,回溯步骤
2>队列:在尾部一端插入,在头部一端删除,先进先出
同样API分为建队列,入列,出列,空
应用:调节和建立数据的快速生成和数据缓慢消费间的平衡,组织数据库等
广义线性表:
插入和删除等操作可以在其中任何地方进行的表,可以在表头,表中间,表尾
树:就讲解了下定义,很浅,说研究的超出了本书的范围是什么鬼...
二叉树:
二叉树是一棵空树或由一个根结点和两棵子树构成,每棵子树也是二叉树
说建树,插入,删除,检索,空超出了本书范围...
遍历:
深度优先遍历:前序(根->左子树->右子树)中序(左子树->根->右子树)后序(左子树->右子树->根)
广度优先遍历:层序(从根开始从左到右一层一层)
二叉搜索树:(BST)
是一种具有额外特性的二叉树,每个结点的关键字值大于左子树中的所有结点的关键字值,而小于右子树中所有结点的关键字值
所以中序遍历创建了一个升序列表
图:一笔带过...
13.文件结构
顺序文件:记录只能按照顺序从头到尾一个接一个地进行存取
应用于需要从头到尾存取记录的应用,例如月底打印工资
更新顺序文件:事务文件+旧主文件=新主文件/错误报告文件
索引文件:索引将键映射到地址
散列文件:用一个函数来完成映射(哈希表)
直接散列法:键是未经算法处理的文件地址,直接拿来用
求模法:用文件大小除键后余数加1作为文件地址
数字析取法:选择从键中提取的数字作为文件地址
除了直接法,其他方法都可能发生地址冲突(相同)
开放寻址解决法:当一个冲突发生时,主区地址将查找开放的或空闲的地址来用于存放新数据,简单的策略就是把该数据存在起始地址的下一个地址中
链表解决法:第一条记录存储在起始地址,包含一个指向下一条记录的指针
桶散列法:一个结点能装多个记录
14.数据库
一个组织内被应用程序使用的逻辑相一致的相关数据的集合
层次模型,网状模型,关系模型,现在只剩最后一种
SQL:
一种描述性的语言,用于关系数据库上的标准化语言
插入,删除,更新,
选择:产生另外一个新关系,从原表中选择部分元组(行变少)
投影:产生另外一个新关系,新关系中的属性减少(列变少)
连接:基于共有的属性,把两个关系组合起来(行数相同,增加列)
并:把两个有相同属性的关系组合,成为一个新的关系(列数相同,增加行)
交:把两个有相同属性的关系组合,只留下相同的属性(列数相同,减少行)
差:把两个有相同属性的关系组合,只留下一个组合中有,另个一组合中没有的
15.数据压缩
无损数据压缩:
1>游程长度编码
将数据中连续重复出现的符号用一个字符和这个字符重复的次数来代替
比如aaaaaa->a06
2>赫夫曼编码
根据字符出现的频率构成赫夫曼树(大顶堆二叉树)然后根据路径给字符编码
3>Lempel Ziv编码
基于字典的编码,接收和发送双方都有一个字典,字符串由字典中的索引代替
建立字典索引(1,2,3),把单个数据按照索引排列(1->a,2->b),然后用排列好的索引代替数据(ab->1b->3,abb->3b->4),构成压缩后的数据串(abababb->a,b,1b,3b)
解码时用前两位拼接后面的数据去
有损数据压缩:
介绍了图像压缩(JEPG),视频压缩(MPEG),音频压缩本质...
16.安全
安全目标:机密性,完整性,可用性
攻击机密性:
嗅探:对数据的非授权访问和侦听数据
流量分析:通过在线流量监控收集其他类型的信息
威胁完整性:
修改,假冒,回放(发两次验证短信),否认
威胁可用性:
拒绝服务(DoS):减慢或完全中断系统的服务
实现安全目标:
密码术:对称密匙密码,非对称密匙密码,散列
隐写术:在原先的信息上加上别的信息,插到数据中
传统密码:
替换密码:用一个符号替代另一个符号,字母移位
置换密码:重新排序
现代对称密匙密码:
DES(数据加密标准):56位密匙
AES(高级加密标准):密匙更长了128,256
密匙用KDC管理(可信任第三方)
非对称密匙密码:
用接收者的公钥加密,接收者用私钥解密
RSA算法(三个发明者命名的)
密匙用CA管理(可信任第三方)
散列:
修改检测码(MDC):保证完整性与不被修改性,用一个密码散列函数,建立消息的消息摘要,用来检查
消息验证码(MAC):保证信息的起源是正确的,包含了接收方与发送方的秘密
数字签名:发送者使用签名算法来签署信息,接收者用验证算法来验证签名,为真接收消息
密码系统使用接收者的私钥和公钥,数字签名使用发送者的私钥和公钥
17.计算理论
介绍了简单语言(递增,递减,循环语句构成),图灵机(磁带,控制器,读/写)
邱奇图灵论题:如果存在一个能完成一个符号操纵任务的算法,那么也存在一台完成这个任务的图灵机
哥德尔数:一个无符号数能被分配给任何用特定语言编写的程序
停机问题:能否构造一个可以预言另一程序是否会结束的程序
停机问题不可解,是不存在的
18.人工智能
对人工智能做了简单的介绍
人工智能是对程序系统的研究,该程序系统在一定程度上能模仿人类的活动,如感知,思考,学习和反应
图灵测试:一个询问者对计算机和人类都提出一组问题,得到答案后不能肯定地说出哪一组来自人类,哪一组来自计算机,那么计算机就通过了具有智能行为的图灵测试
智能体:一个能够智能地感知环境,从环境中学习并与环境进行交互的系统
简单介绍了语义网,框架,谓词逻辑(一种表示逻辑的语言),基于规则的系统(使用一组规则来表示知识)
简单介绍了神经元网络
附录:
介绍了一些零散的知识点,比如ASCII码,
统一建模语言UML:用来进行分析和设计的图形化语言,可以用标准的图形概念来说明,可视化,构造和用文档说明软件和硬件系统
伪代码
结构图
布尔代数和逻辑电路:只有0或1两种值的变量和常量
还复习了下基础的数学知识:
指数函数:底为x的指数函数定义为x^n
对数函数:对数函数和指数函数互为倒数 y = x² <-> 2 = logxy
以e为底的对数写成ln,以10为底的写成log
