一、计算机科学概论
第一部分：基础
第一章：全景
计算系统、计算机硬件、计算机软件
计算系统的六层（由内向外）：信息-->硬件-->程序设计-->操作系统-->应用程序-->通信
四大技巧
算法思想：能够用按部就班的过程表示问题，从而解决问题
表示法：用能被有效处理的方式存储数据
程序设计：把算法思想和表示法阻止在计算机软件中
设计：是软件满足一种用途，实现特定的功能
计算学科主题领域（1989年）
算法与数据结构
操作系统
人工智能与机器人技术
编程语言
软件方法学与工程学
人机交互
计算机体系结构
数据库与信息检索
图形学
第二部分：信息层
第二章：信息层
数学方面：二进制、八进制、、十进制、十六进制
计算机中使用二进制来存储信息的原因是：计算机硬件中的存储为只有高电平和低电平两种信号，所以用二进制很符合逻辑。
我们可以把低电平信号看做是0，高电平信号看做是1，注意存储位的状态不能为空，必须是0或1中的一个。
名词
二进制数字（binary digit）：二进制技术系统中的一位数字，可以说0或1
位（bit）：二进制数字的简称
字节（byte）：八个二进制位
字（word）：一个或多个字节，字中的位数称为计算机的字长
第三章：数据表示法
3.1 数据与计算机
没有数据，计算机就没有意义
数据类型：数字、文本、音频、图像和图形、视频，这些都被存储为二进制数字，每个文档、图像和音频都将被表示为由0和1组成的字符串。
不讨论数据压缩，就不能讨论数据表示法
名词
多媒体（multimedia）：几种不同的媒体类型
数据压缩（data compression）：减少存储一段数据所需的空间
带宽（bandwidth）：在固定时间内从一个地点传输到另一个地点的最大位数或字节数
压缩率（compression ratio）：指压缩的程度，是压缩后的数据大小除以原始数据大小的值
无损压缩（lossless compression）：不会丢失信息的数据压缩技术
有损压缩（lossy compression）：会丢失信息的数据压缩技术
用有限的机器表示无限的世界，是不可能的
模拟数据（analog data）：用连续形式表示的信息
数字数据（digital data）：用离散形式表示的信息
举例：温度计可以显示当时的温度，但实际的温度可能是42.156978°，温度计的刻度对应的也是这个温度，但是我们永远无法读出这个数据
模拟数据完全对应于我们周围连续无限的世界，这是计算机不能处理的，因此需要数字化数据，把信息分割成片段并单独表示每个片段。
数字化（digitize）：把信息分割成离散的片段
计算机中采用二进制而不是其他进制的原因还包括电信号的问题，模拟信号和数字信号（此处不懂）
脉冲编码调制（pluse-code modulation）：电信号在两个极端之间跳跃的变化
重新计时（reclock）：在信号降级太多之前将它重置为原始状态的行为
二进制表示法
如果我们想要表示两种状态，那么只需要一位（0,1）就足够了；四种状态（00,01,10,11），两位也足够了。但随着状态的增加，位数也会增加，而每增加一位，能够表示的状态就会增加一倍，这就会导致空余的情况，比如想要表示25种状态，我们至少要5位，而5位可以表示的状态数是32，其中7种组合并没有用到。
一般来说，我们会多分配一些位数来表示状态，即便可能用不到。计算机体系结构一次能够寻址和移动的位数有一个最小值，通常是2的幂，比如8、16、32等，因此分配给任何类型数据的最小存储量通常是2的幂的倍数。
3.2 数字数据表示法
负数表示法
符号数值表示法（signed-magnitude representation）：符号表示数所属的分类（正数或负数）、值表示数的量值的数字表示法
十进制补码（tens's complement）：用10的k次幂减I来表示负数的方法
二进制补码
假如我们用八位来表示数字，一位表示符号，七位表示数字，那
最左边的一位表示符号，0为正，1为负，所以是对的
更简单的方法是将二进制先取反再加一
数字溢出
溢出（overflow）：给结果预留的位数存不下计算出的值的状况
实数表示法
小数点（radix point）：在计数系统中，把一个实数分割成整数部分和小数部分的点
浮点表示法（floating point）：标明了符号、尾数和指数的实数表示法
3.3 文本表示法
字符集（character set）：字符和表示它们的代码的清单
ASCII字符集：
Unicode字符集：utf-8是Unicode的一种实现方式
文本压缩（便于在不同的计算机间传递）
关键词编码（keyword encoding）：用单个字符代替常用的单词 缺点：用于编码的字符不能出现在原文中，限制了编码
行程长度编码（run-length encoding）：把一系列重复字符替换为它们重复出现的次数，又被称为迭代编码
霍夫曼编码（Huffman encoding）：用变长的二进制串表示字符串，使常用的字符具有较短的编码
解决解码的方式是用于解释一个字符的位串不会是其他字符的前缀
3.4 音频数据表示法
采样：周期性地测量信号的电压，并记录合适的数值
塑胶唱片、光盘CD
音频格式：WAV、AU、AIFF、VQF、MP3
MP3盛行的主要原因是它的压缩率比同时期的其他格式的压缩率高
3.5 图像与图形表示法
颜色表示法
RGB（red-green-blue）：
色深度：用于表示颜色的数据量
增强彩色：16位，RGB各5位，一位表示透明度
zhencaise：24位，RGB各8位
数字化图像和图形
像素（pixel）：用于表示图像的独立点，代表图像的元素
分辨率（resolution）：用于表示图像的像素个数
光栅图形格式（raster-graphics format）：逐个像素存储图像信息的格式，包括位图（BMP），gif，JPEG
位图文件：只包括图像像素的颜色值
GIF（Graphics Interchang Format）：只有256种颜色，适合用于表示颜色较少的情况，最适合表示图形，
JPEG：利用人眼的特性，存储照片颜色图像的首选格式
PNG（Portable Network Graphics）：不支持动画，本用来取代GIF
图形的矢量表示法
矢量图形（vector graphics）：用线段和几何形表示图像的方法
SVG（Scalable Vector Graphics）
3.6 视频表示法
视频被分割成一系列表示为图像的静态图像
编译码器（ codec）：包括压缩器和解压缩器（COmpressor/DECompressor）
视频编译码器（video codec）：用于缩减电影大小的方法
时间压缩
空间压缩
PS：ACM（Association of Computing Machinery）、IEEE（Institute of Electrical and Electronics Engineers）
第三部分：硬件层
第四章：门与电路
4.1 计算机与电学
门（gate）：对电信号执行基本运算的设备，接收一个或多个输入信号，生成一个输出信号
电路（circuit）：相互关联的门的组合，用于实现特定的逻辑函数
门和电路的表示方法
布尔代数（Boolean algebra）：表示二值逻辑函数的数学表示法
逻辑框图（logic diagram）：电路的图形化表示，每种类型的门都有特定的符号
真值表（truth table）：列出了所有可能的输入值和输出值的表
4.2 门
非（NOT）
与（AND）
或（OR）
异或（XOR）：不同才输出1
与非（NAND）：与的相反
或非（NOR）：或的相反
4.3 门的构造
晶体管（transistor）：作为导线或电阻器的设备，由输入信号的电平决定它的作用（如何由晶体管构建门？）
半导体（semiconductor）：
4.4 电路
组合电路（combinational circuit）：输出仅由输入决定的电路
时序电路（sequential circuit）：输出是输入值和电路当前状态的函数的电路
电路等价（circuit equivalence）：对应每个输入值的组合，两个电路都生成完全一样的输出
加法器（adder）：对二进制值执行加法运算的电路
半加器（half adder）：计算两个数位的和并生成正确的进位的电路
全加器（full adder）：计算两个数位的和并考虑进位输入的电路
多路复用器（multiplexer）：使用一些输入控制信号来选择哪一条输入数据线发出输出信号的电路
多路分配器：只有一个输入，分配多个输出
4.5 存储器电路
S-R锁存器：
4.6 集成电路
集成电路（integrated circuit）：芯片（chip），嵌入了多个门的硅片
4.7 CPU芯片
第五章：计算部件
5.1 独立的计算机部件
中央处理器：如 Intel Core2 Duo（2.66GHz/1066MHz FSB/6MB cache ），其中 Duo是指双核，2.66GHz是指处理器的处理速度（G为10亿），也就是处理中的时钟在发出的脉冲的频率；1066MHz FSB，这是指处理器与外界总线的通信频率；6MB cache是指处理器内部的缓存的大小，处理器优要处理的数据很多都放在缓存中，只有缓存中没有的时候才与外界通信（总结就是：时钟、前端总线、缓存空间）
显示器：
图形处理器GPU：
主存储器RAM：
硬盘驱动器：在被固态硬盘取代
5.2 存储结构的概念
冯诺依曼体系结构
存放数据和指令的内存单元
对数据进行算术和逻辑运算的算术逻辑单元
把数据从外部世界转移到计算机内的输入单元
把结果从计算机内部转移到外部世界的输出单元
确保其他部件都参与了表演的控制单元
内存
物理地址是如何保存的？
可编址性（addressability）：内存中每个可编址位置存储的位数
算术逻辑单元
算术逻辑单元（Arithmetic/Logic Unit, ALU）：执行算术运算和逻辑运算的计算机部件
寄存器（register）：CPU中的一小块存储区域，用于存储中间值或特殊数据
寄存器就是CPU中的缓存空间吗？
输入/输出单元
输入：
输出：
控制单元
控制单元（control unit）：控制其他部件的动作，从而执行指令序列的计算机部件
指令寄存器（Instruction Register， IR）：存放当前正在执行指令的寄存器
程序计数器（Programma Center，PC）：存放下一条要执行指令的地址的寄存器
中央处理器（Central Processing Unit, CPU）：控制单元和算数逻辑单元的组合
总线宽度：
缓存：
流水线：
读取-执行周期
读取下一条指令
破译指令
如果需要，获取数据
执行指令
RAM和ROM
可修改和不可修改
二级存储设备（跳过）
触摸屏
电阻式：
电容式：
红外触摸屏：
表面声波：
5.3 嵌入式系统
5.4 并行体系结构
比特级
指令级
数量级
任务级
第四部分：程序设计层
第六章：低级程序设计语言与伪代码
机器语言（machine language）：由计算机直接使用的二进制编码指令构成的语言
虚拟机（virtual computer）：为了模拟真实机器的重要特征而设计的假象机器
（跳过）
第七章 ：问题求解与算法设计
第八章：抽象数据类型和子程序
第九章：面向对象设计与高级程序设计语言
Last updated
Was this helpful?