CS学习update
摘要
在被浙江大学计算机学院拟录取之后, 我现阶段的两个任务是:
- 完成本科土木工程的学业,主要是毕业设计
- 弥补计算机科学的基础知识和素养,并向研究方向靠拢
为了能循序渐进的奠定计算机科学的基础,在此记录学习的内容和自己的收获总结.文章更新周期为一周一次, 每周全面的总结一周七天后写成.文章格式为问答式,提出问题并自己解答,以此自检.
周期1: 已学总结与学习计划
时间: 2017/03/20 - 2017/04/01
Q1: 我已学过的计算机科学的专题有哪些?
数学和物理: 微积分, 线性代数, 概率论, 大学物理(电路)
计算机: C/Python, 算法与数据结构,操作系统,网络,组成原理,
下面分别概括各科的情况并确定加强的方向:
1. 微积分
以离散的数列和连续的函数为核心,用极限和微分/积分为基础工具,微积分使我学习到严格的推导过程和缜密的计算流程,同时,有两个基本的解决问题的思路:
a. 如何通过离散的角度(数列极限)考察连续的函数.
例如:考虑函数在一个点(x,y)是否是连续的,这里有三个量:点(x,y)的函数值f(x),左侧无限逼近x的离散的自变量序列{An},和右侧的序列{Bn}.左右两侧对应无穷数列的极限和f(x)相等则证明该点连续.公式如下:
$$f(x)=\lim_{x \to x-}f(x)=\lim_{x \to x+}f(x)$$
b. 如何利用连续的概念解决离散的问题.
例如: 在数列极限难以求解的问题中,采用连续化为函数的方法,适用范围内,数列极限等于函数极限.公式如下:
$$\lim_{n \to \infty}a_n=\lim_{x \to x_0}f(x)$$
微积分对概率论中的连续随机变量,以及任何形式的函数关系(数据科学领域)打下坚实的基础.但考虑到计算机本质上是一个离散的系统,虽然微积分中连续的概念可以指导计算机中离散对连续变量的模拟,但我认为离散数学应该更能奠定计算机的数学基础.加强方向: 离散数学课程 MIT
2. 线性代数:
本科学习的核心概念包括:行列式,矩阵,线性方程组,相似及二次型,向量,线性空间.
向量和矩阵作为一个离散的概念,十分适合描述一个系统的信息,例如如何定量的描述一个网站的信息?定义一个向量对应网页,向量的每一个元素定义为网页的特征,如关键词,词频,访问量等可定量的特征,如此,所有网页对应的向量构成的矩阵就可以描述该网站,基于矩阵的运算理论则使整个网站参与运算,用于如搜索网站的排名,推荐系统等等.用矩阵来思考内存的组织是很形象生动,加深对内存空间的理解的.
线性方程组的理论,我认为可以用以理解其他线性代数中的概念,并作为一种基础工具来求解其它问题.矩阵运算有时很难思考对应的实际意义,那么将其看成线性方程组的求解,看矩阵的行向量代表的含义,则能很好的和实际应用联系起来.方程组理论中的有解,有非零解,解空间的理论贯穿在整个线性代数中,例如行列式是否为零,矩阵是否奇异,特征向量都可以通过方程组来解决.
遗憾的是没有深入学习线性空间,我认为这是线性代数最能推而广之解决一般性问题的方法,用线性系统的观点来建模实际的问题.因此我计划在这方面重点加强课程 MIT Linear Algebra
3. 概率论与数理统计:
概率论中的核心概念是:概率与分布(离散型,连续型), 数字特征(均值,方差).
概率是定量化的可能性,记录事件发生的可能,是对世界的最真实的描述.概率基于对已发生事件的频率, 描述可重复事件的可能,例如科研中的可重复的大量实验,在得到很多实验数据后,如何根据数据调整实验参数.一个很好的例子是贝叶斯公式:
$$P(A|B) = \frac {P(B|A) \times P(A)}{P(B)}$$
基于已知的事件的可能性{P(A)P(B)}和过去的{经验P(B|A)},推断事件{P(B|A)}发生的可能性,这是预测的基本的方式.
我认为,数理统计将会是与计算机科学以及研究生阶段关联最紧密的主题.例如:课题项目的实验获取的大量数据如何处理?计算均值,方差,做回归分析,建立统计模型,验证模型,反馈调整实验参数…做科研的一个基本能力是数据分析能力,也离不开对数理统计的扎实掌握.我计划在这个主题加强课程 MIT
4. 物理
大学物理课与计算机科学相关的主要是电路,加上自学{CODE},对逻辑电路有了基本的理解.二进制与开关的闭合对应的关系,正是Shannon在他的论文确定的计算机用电路实现的基础.与门,非们,或们,触发器实现的时序电路构成内存,寄存器+加法器+控制逻辑构成基本的ALU,组合逻辑电路构成完整的CPU.
另外,物理课与实验密切结合,如何实验验证假设,如何控制变量,处理数据,得到结论,物理课训练我用一个正确的实验过程是怎样的实现的.
5. C
C的核心概念:强类型, 数组与指针, 函数与递归,预处理和宏.
即使加上C标准库,C仍然是一门简洁清晰的编程语言:C结构清晰,以main()函数为入口,调用其他函数,声明和定义时要求类型定义;面向过程编程,抽象机制明确,过程抽象的语法是函数func(),数据抽象的语法是结构体struct;有指针pointer这个强力工具,连接计算机的底层,实现地址的操纵(&和*操作符)和内存的管理(malloc()等函数);项目组织有.h头文件和.c源文件,make控制编译.
有内存管理和地址操纵这些底层功能,加上编译优化后高效的运行性能,使得C成为操作系统kernel,编译器complier,数据库database等的核心语言,尤其长于系统和硬件编程,我计划在学习这几个主题实现对应project的过程中,努力进阶C的编程能力.
C中指针是个强大的概念，从最简单的交换两个变量值swap(),到函数指针func,内存管理的返回值类型void*,指针发挥了传递对象首地址而不是拷贝对象的作用.另外,基于指针的线性表-链表,具有了数组没有的易动态变化(增删)的优点,也使得树和图结构的实现更容易.
但相比与其他高级语言如Java/Python,C不支持面向对象的特性,难以直接进行面向对象的程序设计.除去标准库/GNU-lib,同时没有相对丰富的库支持,不适合high-level(如GUI)的编程.但是,有了gcc,make等toolchain的支持,C仍然适合大型/要求性能/系统底层的开发工作,这也是我C加强的方向.
6. 算法与数据结构, 操作系统最近正在学习,见下面的问题.
7. 组成原理
相比较与计算机体系机构注重在不同硬件平台上的具体实现，即一台RISC计算机内部结构是怎样的,指令系统是如何实现的,组成原理重点关注一般的计算机内部具有哪些通用的基本的结构,整个计算机的结构是如何联系起来共同工作的,而不在意具体的实现形式.
计算机基本的冯诺依曼架构, CPU(运算器ALU, 控制器CU), 内存Mem, 输入输出I/O,以及串联所有构件的总线BUS.在CPU内部,运算由基本的加法器实现,通过控制部件用加法器实现减法,乘法和除法;数据由二进制表示,可以编码为原码/补码/反码/移码,浮点数由IEEE745标准规定;CU控制指令的执行过程,PC确定下一条指令的地址,一个完整的指令周期包括取指/译码/执行,以及取指/取数过程中的间指,以及处理外部产生的中断;一个指令的基本结构是{指令地址;操作码;操作数},由硬布线组合逻辑或微程序设计实现.
存储的架构 CPU内部register - 缓存cache - 主存memory - 外存(硬盘,闪存),有ROM, RAM, FLASH等具体实现方式.
输入输出I/O的结构: CPU or mem - I/O接口 - I/O设备.CPU通过程序查询(轮询)或中断和设备进行信息传递, mem可采用DMA方式直接与高速外设交换数据.
总线可采用单/双/多总线结构,有基本的数据/地址/控制/控制等总线分类,主要解决的问题是总线仲裁和判优,针对不同的结构连接采用不同的总线标准,如ISA/PCI/USB.
组成原理站在硬件角度考察计算机的结构性,注重计算机构件及其连接的原理,从整体的角度思考为什么硬件要这样组合,出现的问题如何解决?例如要使加法器实现加减乘除四种运算,首先要用补码编码,这样很容易就解决了加减统一的问题,乘除时符号位在运算中得出,基本的实现是循环(Booth算法);又比如如何提高指令执行的效率这一问题,除过对指令进行优化, 最佳的解决方案就是提高指令执行的并行性,流水线将指令划分为多个阶段,不同指令不同的周期并行,最大限度的提高部件的使用率,另外采用多核结构,直接实现程序的并行执行,提高计算机的吞吐率.
对组成原理主题的加强,我认为可以通过实现软件与硬件的接口Computer Orgianization and Design.
8. 网络
计算机网络最大的特点是层次化设计,分布式解决.
TCP/IP四层协议和OSI七层协议,清晰的罗列网络的分级,也正是因为网络的复杂性,所以只有通过层次结构,一层一层的抽象分工,才能有效的解决不同计算机通信的问题.
考虑一条链路上两个节点的通信,在底层物理的线路上封装比特流有物理层实现,比特流打包为数据帧保证数据不出错由链路层实现,数据包从哪里出发目的地是哪里由网络(iP)层实现,数据包传输的是面向连接还是无连接/是否保证无差错送达/解决网络的拥塞问题由传输层(TCP/UDP)实现,用户的不同的应用如何通信由应用层实现.
分层明确,各司其职.下层通过访问服务点SAP为上层提供服务,对等层peer之间实现相同的协议,下层的抽象使得对等层似乎在直接通信.通过学习计算机网络,主要明确一个复杂的系统如何通过抽象分层,把大型的复杂的问题化为小问题来分析,然后通过层级架构之间的交互组合成大问题的解决方案,这样的思路在计算机科学是一种普遍的思维方式,例如操作系统位于用户层和硬件层之间,解决硬件的管理和对用户提供舒适的服务又比如算法中递归将问题向下分解为一层层的子问题(递归式),最终化为直接解决的简单问题(递归基base case),向上合并为要求解的问题.抽象和分层在网络中发挥了巨大的威力.
分布式是指不同的计算机有不同的结构,不同的网络有不同的组织(异构网络),如何有效的利用这些资源?不同的网络直连时如何解决不兼容的问题?这都是分布式的概念.网络之间通过节点(网桥,路由器)和相关算法(如OSPF,BGP)实现异构网络之间的通信和同步,而不是各自为政,无法协调.
网络这个主题我的实践还很少,努力加强的方向是linux环境下的网络编程.
Q2:周期1内我学习的内容有哪些?
周期1内我主要学习的是:算法与数据结构, 操作系统
下面分别详述:
1. 算法与数据结构
算法主题我采用的教材是MIT的introduction to algorithms以及配套的课程.下面是我的学习笔记:
算法主题可以分为三个方向:算法的数学理论,算法的设计分析,算法的应用.算法导论主要包括强两个方面的内容, 尤其注重算法的推导和证明.
算法的定义为将输入转换为输出的计算步骤序列(An algorithm is thus a sequence of computational steps that transform the input into the output.),有确定的输入,和明确实现实现的步骤,以及满足要求的输出.在用编程语言实现算法的过程中,清晰性(无歧义)/可实现/有穷性是算法的基本的要求.
面对的具体的问题,有不同的算法,对应着不同的性能.我们主要考虑这样几个问题:空间复杂度, 时间复杂度,可扩展性等等.该算法在运行时是否要求额外的内存,需要多少空间?最坏/最好/平均的数据分布情况下,消耗多少时间?在解决特定规模的问题后,是否能扩展到一般的更大规模的问题?算法分析时考量这几个主要特征.
已排序算法为例,基本的排序算法有插入排序(直接插入,折半插入,希尔排序), 选择排序(选择排序,堆排序),交换排序(冒泡,快排),归并排序,基数排序.排序算法的基本特征是复杂度(空间,时间),稳定性(关键字相同的数据排序前后相对顺序不变).
从平均时间复杂度讲快排/堆排序/归并排序是O(nlogn),快排在基本有序的情况下退化为O(n^2),归并排序需要额外的O(n)的空间,堆排序在任何情况下都是很优秀的O(nlogn);选择/冒泡/直接插入是O(n^2);基数排序为O(d(n+radix)),可以达到接近线性O(n)的性能,但依赖与基数和位数的多少.
当数据排序时要求有多个关键字时(关键字A相同的按关键字B排序),要求排序的稳定性,冒泡/选择/插入/归并/基数排序是稳定的,快速/希尔/堆是不稳定的.
当数据量较大,内存无法一次放下,需要从外存调入数据,归并排序则是最佳的选择.归并将数据分段,然后构造归并树由叶子节点向上归并到根节点,非常符合外部排序的要求.另外,归并排序既可以用递归(递归排序前一半数据,递归排序后一半数据,归并前后两段)实现,极好的体现了问题分解为子问题,逐个击破的递归特点;也可以用迭代实现,将序列分为两个数据一组,从两个开始归并直到合成总的有序序列.与此类似的还有快速排序的分割思想,用key将序列分解为小于key和大于key的序列.
从归并的递归和迭代实现可以看到,这是两种解决算法问题的思路:递归top-down,将问题分解为相似的子问题,divide and conquer,逐个解决;迭代bottom-up,从基本的最小问题开始,构造出求解的大问题.
mit课程中第一节课讲到了peek-problem,搜索数据意义上的极大值.从一维序列的角度讲, 序列$ [a_1, a_2, a_3, \ldots, a_n]$的peek $a_i$满足条件$ a_i > a_{i-1} \, and \, a_i > a_{i+1}$ ．
线性算法O(n)遍历序列可以寻找peek,是否有更好的算法呢?运用二分的思想, 如下
$$\begin{align}
if \, a_{n/2} < a_{n/2-1}, peek \, in \, [a_1, a_2, \ldots, a_{n/2-1}]\\
if \, a_{n/2} < a_{n/2+1}, peek \, in \, [a_{n/2+1}, \ldots, a_{n-1}, a_n]\\
else \, a_{n/2} \, is \,peek
\end{align}$$
可以得到O(logn)的结果.
解决一位的问题后推广到二维(m*n),线性遍历O(mn)仍然是适用的,但二分不能解决问题.是否可以采用优化后的二分思想解决问题?将二维问题看成一个由列向量构成的矩阵,增加一个函数max(),求解列向量的最大值及其位置,然后由最大值作为一列的代表运用二分的思想得到O(mlogn)的算法.
从解决peek-problem的过程中,我学到的的是如何正确的求解一个算法问题:首先选择规模最小,最简单的问题形式(如一维),是提出最直观的暴力解法{如线性的遍历,O(n^2)的筛选},虽然能解决问题但往往性能是很差;然后寻找优化的方向{如二分的O(logn), 归并的O(nlogn)};接下来向一般的/更复杂的情况(如二维,多变量)推广,考察一维的方法是否仍然适用,如果不适用是什么原因导致的,能否改进调整.我认为对比解决同一问题的不同算法, 泛化到一般情况是学好算法的好标准.
2. 操作系统
操作系统采用的教材是Operating System Concepts,配套实验是MIT xv6.下面是我的学习笔记:
操作系统课程我在考研时学习了理论的知识,但学习是有不完整/系统的,因此需要重点弥补理论的部分和动手实践的能力.
从最初的解决批处理的问题,到分时给不同的用户交互,再到实时系统要求的快速反馈/高稳定性,到现在分布式系统的同步/网络系统的通信.我认为始终有两个核心内容贯穿其间:一是如何实现对计算机资源的管理,尤其是独占资源(CPU的计算,内存的储存,外设);二是如何实现与用户的交互,操作系统归根到底是要为用户服务的,用户的应用如何通过操作系统得到资源.
操作系统位于中间层,介于计算机资源与用户应用之间,向上提供服务,向下管理资源,是一个大型的系统软件.就上述两个主题来详述:
一台主机要向多个用户提供分时服务就在同一主机上产了不同的用户程序,或者同一用户有不同的应用需求(如在编辑文档时听音乐/访问网络),因此产生了进程的概念:”一组数据集在程序上的动态运行”.进程要使用CPU/mem等有限的独占资源,在时间上是交错开使用这些资源的,产生了诸多关键问题:
进程:
1. 进程之间如何切换?产生了进程调度算法(先来先服务,时间片轮转,优先级,响应比,多级反馈队列);
2. 进程切换十分消耗资源,是否有更好的方法?共享进程空间,切换代价很小的线程
3. 不同进程在占用资源时是否有先后顺序,之间是否有前后依赖关系?要求进程的同步和互斥(信号量机制及其解决的经典同步问题,管程,原语的原子性)
4. 进程使用资源顺序不当时,如何防止产生死锁,产生后死锁如何解决?破坏死所的四个必要条件来预防,银行家算法来避免死锁,化简资源分配图来检测死锁,终止进程来解决死锁.
内存:
1. 程序是如何运行的?程序的编译,链接与装载,地址空间的映射,内存保护.
2. 多组程序和数据存储在内存,如何管理?交换与覆盖技术,静态分页与分段.
3. 内存不够使用,如何扩展内存?用外存扩展,虚拟内存技术(请求分页,页面置换
文件:
1. 站在用户角度,如何更好的使用文件?文件系统接口(FCB,文件的逻辑实现,目录的结构,文件共享和保护)
2. 站在计算机的角度,如何管理文件?文件系统实现(分配硬盘空间, 管理空闲磁盘快, 目录实现)
3. 硬件层面如何管理磁盘?磁盘结构,调度,管理磁盘(格式化,引导)
设备:
1. 用户如何使用设备,设备如何与CPU/mem实现信息传递?I/O设备管理器与接口,轮询/中断/DMA
2. 计算机如何实现对设备的管理?I/O子系统(缓冲机制,SPOOLING, 内核管理设备的数据结构)
除过上面的问题，还有一个核心问题是用户的应用如何使用计算机的资源？通过系统调用(system call)，从用户态切换到内核态，由内核执行系统调用子程序，返回用户想要的结果．
以上是我对操作系统理论的基本认识，还有待扩展细化，并且和MIT xv6操作系统实验结合起来．MIT实验笔记正在总结，另外写一个update.
最后完成日期：2017-04-02