计算机保研专业课复习(简答)_北大计算机保研笔试内容

操作系统

1. 进程间的通信方式

1. 无名管道pipe：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
2. 命名管道FIFO：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
3. 消息队列MessageQueue：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
4. 共享存储SharedMemory：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
5. 信号量Semaphore：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
6. 套接字Socket：用于不同机器间进程的通信。
7. 信号 ( sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

2.进程有哪几种状态

创建态，就绪态，运行态，阻塞态，终止态。

3.进程状态之间的转化

4.有哪些页面置换算法

先进先出，最佳置换，最近最久未使用，时钟置换。

1. 最佳置换算法（OPT，Optimal）
   算法思想：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
   最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此，最佳置换算法是无法实现的。

2. 先进先出置换算法（FIFO）
   算法思想：每次选择淘汰的页面是最早进入内存的页面。
   当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为贝莱迪（Belay）异常。
   只有FIFO算法会产生Belay异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此，算法性能差。

3. 最近最久未使用置换算法（LRU，Least Recently Used）
   算法思想：每次淘汰的页面是最近最久未使用的页面。
   实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t最大的页面，即最近最久未使用。

4. 时钟置换算法
   简单CLOCK算法算法思想：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某个页被访问时，其访问位置1.当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）。

   ** 简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有淘汰的页面被修改过时，才需要写回外存**
   因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。
   改进型时钟置换算法的算法思想：在其他在条件相同时，应该优先淘汰没有被修改过的页面，从而来避免I/O操作。
   

5.死锁的概念和产生死锁的必要条件，死锁预防，死锁避免

死锁是指两个或多个进程在执行的过程中，因为竞争资源而造成互相等待的现象，若无外力作用，它们都无法推进下去。

产生死锁的四个必要条件：
1.互斥条件
一个资源每次只能被一个进程使用，即在一段时间内某资源仅为一个进程所使用。此时如果有其他进程请求该资源，则请求进程只能等待。
2.请求与保持条件
进程中已经保持了至少一个资源，但又提出了新的资源请求，而该资源已经被其他进程占有，此时请求进程被阻塞，但对自己已经获得资源保持不放。
3.不可剥夺条件
进程未使用完的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。
4.循环等待条件
若干进程间形成首尾相接循环等待资源的关系。在发生死锁时必然存在一个进程等待队列{P1，P2，…,Pn},其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路，环路中每一个进程所占有的资源同时被另一个申请。
注意：这四个条件是死锁的必然条件，只要系统发生死锁，这些条件必然成立。只要有上述条件有一条不满足，就不会发生死锁。

死锁的避免
基本思想：系统对进程发出每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，如果分配后系统可能发生死锁，则不予分配，否则分配。这是一种动态策略。典型的避免死锁的算法是银行家算法。

6.操作系统的功能

操作系统的基本功能是：1、进程管理。2、存储管理，可分为存储分配、存储共享、存储保护 、存储扩张。3、设备管理，可分为设备分配、设备传输控制 、设备独立性。4、文件管理。5、作业管理，负责处理用户提交的任何要求。

7.操作系统的四个特征，操作系统最基本的特征

并发，共享，虚拟，异步。




最基本的特征是 并发和共享。

8. 中断和系统调用

中断又叫硬中断，是指来自CPU执行指令以外的事件。系统调用是软中断的一种。系统调用，指的是操作系统提供给用户程序调用的一组特殊接口，用户程序可以根据这组接口获得操作系统内核的服务。

9、硬中断和软中断的区别

硬中断：硬中断是由硬件产生的，比如磁盘，网卡等。软中断是软件中断，进程产生。
软中断发生时间由程序控制，硬中断发生时间是随机的。软中断由程序调用引起，硬中断发生时间随机。硬中断可以屏蔽，软中断不可以屏蔽。硬中断的中断信号是由中断控制器控制的，软中断的中断信号由指令直接指出。

10.进程线程区别

进程：
是并发执行的程序在执行过程中分配和管理资源的基本单位，是一个动态概念，竞争计算机系统资源的基本单位。

线程：
是进程的一个执行单元。比进程更小的独立运行的基本单位。线程也被称为轻量级进程。

进程和线程的区别
地址空间：
线程共享本进程的地址空间，而进程之间是独立的地址空间。

资源：
线程共享本进程的资源如内存、I/O、cpu等，不利于资源的管理和保护，而进程之间的资源是独立的，能很好的进行资源管理和保护。

健壮性：
多进程要比多线程健壮，一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃整个进程都死掉。

执行过程：
每个独立的进程有一个程序运行的入口、顺序执行序列和程序入口，执行开销大。
但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制，执行开销小。

可并发性：
两者均可并发执行。

切换时：
进程切换时，消耗的资源大，效率高。所以涉及到频繁的切换时，使用线程要好于进程。同样如果要求同时进行并且又要共享某些变量的并发操作，只能用线程不能用进程。

其他：
线程是处理器调度的基本单位，但是进程不是。

11. 线程哪些资源共享，哪些资源不共享

共享的资源有：

堆。 由于堆是在进程空间中开辟出来的，所以它是理所当然地被共享的；因此new出来的都是共享的（16位平台上分全局堆和局部堆，局部堆是独享的）

全局变量 。它是与具体某一函数无关的，所以也与特定线程无关；因此也是共享的

静态变量。 虽然对于局部变量来说，它在代码中是“放”在某一函数中的，但是其存放位置和全局变量一样，存于堆中开辟的.bss和.data段，是共享的

文件等公用资源。 这个是共享的，使用这些公共资源的线程必须同步。Win32 提供了几种同步资源的方式，包括信号、临界区、事件和互斥体。

独享的资源有：

栈 。栈是独享的
寄存器 。 这个可能会误解，因为电脑的寄存器是物理的，每个线程去取值难道不一样吗？其实线程里存放的是副本，包括程序计数器PC

12. 如何预防死锁？

死锁的预防
我们可以通过破坏产生死锁的四个必要条件来预防死锁，由于资源互斥是固有特性无法改变的。
1.破坏“请求与保持”条件
方法一：静态分配，每个进程在开始执行时就申请他所需要的全部资源。
方法二：动态分配，每个进程在申请所需要的资源时他本身不占用系统资源。
2.破坏“不可剥夺”条件
一个进程不可获得其所需要的全部资源便处于等待状态，等待期间他占用的资源将被隐式的释放重新加入到系统的资源列表中，可以被其他进程使用，而等待的进程只有重新获得自己原有的资源以及新申请的资源才可以重新启动，执行。
3.破坏“循环等待”条件
采用资源有序分配的基本思想。将系统中的资源顺序进行编号

13. 简述银行家算法

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。

14. 介绍几种常见的进程调度算法

先来先服务 （FCFS，first come first served）
在所有调度算法中，最简单的是非抢占式的FCFS算法。
算法原理：进程按照它们请求CPU的顺序使用CPU.就像你买东西去排队，谁第一个排，谁就先被执行，在它执行的过程中，不会中断它。当其他人也想进入内存被执行，就要排队等着，如果在执行过程中出现一些事，他现在不想排队了，下一个排队的就补上。此时如果他又想排队了，只能站到队尾去。
算法优点：易于理解且实现简单，只需要一个队列(FIFO)，且相当公平
算法缺点：比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程

最短作业优先（SJF, Shortest Job First）
短作业优先（SJF, Shortest Job First）又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。
算法原理：对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。
算法优点：相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。
算法缺点：对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。

最高响应比优先法(HRRN，Highest Response Ratio Next)
最高响应比优先法(HRRN，Highest Response Ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。
算法原理：响应比R定义如下： R =(W+T)/T = 1+W/T
其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。
算法优点：由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRRN方式时其吞吐量将小于采用SJF 法时的吞吐量。
算法缺点：由于每次调度前要计算响应比，系统开销也要相应增加。

时间片轮转算法（RR，Round-Robin）
该算法采用剥夺策略。时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称RR调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
算法原理：让就绪进程以FCFS 的方式按时间片轮流使用CPU 的调度方式，即将系统中所有的就绪进程按照FCFS 原则，排成一个队列，每次调度时将CPU 分派给队首进程，让其执行一个时间片，时间片的长度从几个ms 到几百ms。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程，进程可以未使用完一个时间片，就出让CPU（如阻塞）。
算法优点：时间片轮转调度算法的特点是简单易行、平均响应时间短。
算法缺点：不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当
怎样确定时间片的大小：

时间片大小的确定
1.系统对响应时间的要求
2.就绪队列中进程的数目
3.系统的处理能力

多级反馈队列(Multilevel Feedback Queue)
多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。
多级反馈队列调度算法描述：
　　1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
　　2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
　　3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
　　4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。
　　在多级反馈队列调度算法中，如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能够较好的满足各种类型用户的需要。

15. 分页的作用的与好处，和分段有什么区别

分段和分页其实都是一种对地址的划分或者映射的方式。 两者的区别主要有以下几点：

1)页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；或者说，分页仅仅是由于系统管理的需要，而不是用户的需要（也是对用户透明的）。段是信息的逻辑单位，它含有一组其意义相对完整的信息（比如数据段、代码段和堆栈段等）。分段的目的是为了能更好的满足用户的需要（用户也是可以使用的）。

2)页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。段的长度却不固定，决定于用户所编写的程序，通常由编辑程序在对源程序进行编辑时，根据信息的性质来划分。

3)分页的作业地址空间是一维的，即单一的线性空间，程序员只须利用一个记忆符（线性地址的16进制表示），即可表示一地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名（比如数据段、代码段和堆栈段等），又需给出段内地址。

16. 线程的分类

内核级线程，用户级线程

17. 中断和异常

18. 中断处理流程

中断请求，中断判优，中断响应，中断服务，中断返回。
中断请求：内部中断不需要中断请求，外部中断请求由中断源提出。
中断判优：硬件软件都可实现
中断响应：CPU向中断源发出中断响应信号，同时保护硬件现场；关中断；保护断点；获得中断服务程序的入口地址。
中断服务：中断服务程序的一般结构：保护现场；开中断；中断服务；恢复现场；中断返回。
中断返回：中断响应的逆过程。

19. 进程和程序的区别，联系

区别：

1、进程是动态的，而程序是静态的；

2、进程有一定的生命期，而程序是指令的集合，本身无“运动”的含义。没有建立进程的程序不能作为一个独立单位得到操作系统的认可。

3、一个程序可以对应多个进程，但一个进程只能对应一个程序。

4、进程和程序的组成不同。从静态角度看，进程由程序、数据和进程控制块（PCB）三部分组成，而程序是一组有序的指令集合。

联系：

进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。

20、 处理机调度层次：高级调度，中级调度，低级调度

调度层次分为三种

高级调度 = 作业调度 = 长程调度
低级调度 = 进程调度 = 短程调度
中级调度 = 中程调度
作业调度往往是发生在一个作业运行完毕，退出系统，而需要重新调入一个(批)作业进入内存时，故作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。

进程调度的运行频率最高，在分时系统中通常是 10～100 ms 便进行一次进程调度，因此把它称为短程调度。为避免进程调度占用太多的CPU时间，进程调度算法不宜太复杂。
中级调度的运行频率基本上介于上述两种调度之间，因此把它称为中程调度。

高级调度的主要功能是根据某种算法，把外存上处于后被队列中的那些作业调入内存，也就是说它们的调度对象是作业。所以高级调度又称作业调度。
低级调度用于决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。
中级调度的主要目的是为了提高内存利用率和系统吞吐量。
为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。
当这些进程重又具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。

21. 临界资源，临界区

临界资源：一次仅允许一个进程使用的共享资源。
临界区：访问临界资源的那段代码

22. 同步和互斥

互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。
同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

23. 信号量

信号量多用于进程间的同步与互斥。
它允许多个线程同一时刻访问同一资源，但是需要限制同一时刻访问此资源的最大线程数目。
信号量的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。
信号量的值S与相应资源的使用情况有关。当S大于0时，表示当前可用资源的数量；当S小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值近能由PV操作来改变。
执行一次P操作意味着请求分配一个单位资源，因此S的值减一；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。
而执行一次V操作意味着释放一个单位资源，因此S的值加一；若S<=0。表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

24. 管程

管程是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这些操作能初始化并改变管程中的数据和同步进程。
在一个时刻只能有一个进程使用管程。

25. 程序的执行过程

编译，链接，装入。
编译：由编译程序将用户源代码编译成若干个目标模快。
链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块。
装入：由装入程序将装入模块装入内存运行

26. 程序的链接方式

静态链接，装入时动态链接，运行时动态链接

27. 程序的装入方式

绝对装入，可重定位装入，动态运行装入
绝对装入：在编译时就知道程序将要驻留在内存的物理地址，编译程序产生

28. 动态分区分配算法

动态分区分配算法又称可变分区分配。是内存连续分配的一种。（内存分配 分为内存连续分配和非连续分配。内存连续分配又分为单一连续分配，固定分区分配，动态分区分配。）
包括四种算法：

首次适应算法
算法思想：
每次都从低地址查找，找到第一个能满足大小的空闲分区。

如何实现：
空闲分区以地址递增的顺序排列
每次分配内存时从低地址顺序查找空闲分区链（空闲分区表）
找到大小能满足要求的第一个空闲分区
每次分配完成后修改空闲分区的大小
当找不到满足要求的空闲分区时，内存分配失败
优点：
优先利用内存中的低址部分，保留高址部分的大空闲区，为以后到达的大作业分配大的内存空间创造了条件
缺点：
低地址部分会产生大量的难以利用的碎片。

循环首次适应算法
与首次适应算法的不同：
在为进程寻找内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。
如果最后一个空闲分区不能满足要求，应返回到第一个空闲分区。
实现：
将空闲区链表首尾相连形成环形，每次查找从上一次停留的位置开始。

优点：
使内存中的空闲分区分布的更加均匀
缺点：
碎片仍没有得到解决
大的空闲区被分配，缺乏大的空闲分区

最佳适应算法
算法思想：
每次分配时优先使用最小的连续空闲区。

实现：
空闲分区按容量递增的次序链接
每次分配空闲分区时按顺序查找空闲分区链（空闲分区表）
找到满足大小要求的第一个空闲分区
空闲分区分配后要更新空闲分区连（空闲分区表），保持容量递增
缺点：
每次都选择最小空闲分区分配，因此会留下很多、很小、难以利用的内存块。

最坏适应算法
算法思想：
每次分配时优先使用最大的连续空闲区。

实现：
空闲分区按容量递减的顺序链接
每次分配内存时顺序查找空闲分区连（空闲分区表）
找到大小满足的第一个空闲分区。
空闲分区分配后要更新空闲分区连（空闲分区表），保持容量递减
缺点：
大的连续空闲分区被用完，以后的大作业没有分区使用
优点：
查询效率高

29、 库函数

把函数放到库里，供别人使用的一种方式。

30. 磁盘调度算法

先来先服务算法（FCFS）
算法思想：根据进程请求访问磁盘的先后顺序进行调度。

SSTF调度(最短寻道时间优先)
算法思想：优先处理的磁道是与当前磁头最近的磁道。可以保证每次寻道时间最短，但是不能保证总的寻道时间最短。（其实是贪心算法的思想，只是选择眼前最优，但是总体未必最优）。

扫描算法（SCAN）
一扫到底，然后依次扫回来

循环扫描算法
循环扫描（C-SCAN）调度是 SCAN 的一个变种，以提供更均匀的等待时间。像 SCAN 一样，C-SCAN 移动磁头从磁盘一端到磁盘另一端，并且处理行程上的请求。然而，当磁头到达另一端时，它立即返回到磁盘的开头，而并不处理任何回程上的请求。（一扫到底，然后迅速回到首柱面，再依次往后扫）

一扫到底，然后迅速回到首柱面，再依次往后扫

31. SPOOLing技术

多道程序技术将一台物理CPU虚拟为多台逻辑CPU，从而允许多个用户共享一台主机。通过SPOOLing技术可将一台物理IO设备虚拟为多态逻辑IO设备，同样允许多个用户共享一台物理IO设备。
SPOOLing技术就是利用多道程序中的一道程序来模拟脱机输入时外围控制机的功能，把低速IO设备上的数据传送到高速磁盘上；用另一道程序模拟脱机输出时外围控制机的功能把数据从磁盘传送到低速输出设备上。这样，便在主机的直接控制下，实现脱机输入，输出功能。此时的外围操作与CPU对数据的处理同时进行，这种在联机的情况下实现同时外围操作称为SPOOLing。

32. IO控制方式

1. 程序直接控制方式
   CPU反复读取IO状态，直到IO准备就绪。
2. 程序中断方式
   减少程序直接控制方式下CPU的等待时间以及提高系统的并行程度。
   CPU发出读写命令后，将等待IO的进程阻塞，先切换到别的进程执行。当IO完成后控制器会向IO发一个中断信号，CPU检测到中断以后，保存当前进程的运行环境信息，转去处理中断，这样CPU和IO设备就可以并行工作。
3. DMA方式
   直接存储器访问控制方式
   外部设备发出DMA请求，CPU同意后让出总线控制权，DMA控制器接管总线控制权之后开始进行外部设备和内存之间的直接数据交换，CPU不再作为中枢，适合大量数据的传输。
   DMA请求—>DMA响应—>数据传输—>DMA结束。
4. 通道控制方式
   通道是独立于CPU专门控制输入输出的处理机，他控制内存和设备直接进行数据交换。

数据结构

1. 红黑树的概念

是一种特殊的二叉查找树，最大深度小于最小深度的两倍。
顺口溜：根节点必黑，新增是红色，只能黑连黑，不能红连红，爸叔通红就变色，爸红叔黑就旋转，哪边黑往那边转。
红黑树必须存放在内存中，所以像数据库那样的大文件就不能用。
至于为啥要提出红黑树呢？
因为二叉搜索树可能退化成链表，而且平衡二叉树维护平衡的代价又太大。

2.KMP算法

根据模式串的特征计算next数组，防止主串指针回溯，提高效率。
算法流程
假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
如果当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
如果当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值，即移动的实际位数为：j - next[j]，且此值大于等于1。

KMP的next 数组相当于告诉我们：当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟文本串在i 处的字符匹配失配时，下一步用next [j] 处的字符继续跟文本串i 处的字符匹配，相当于模式串向右移动 j - next[j] 位。

3.拓扑排序

一个有向无环图所有顶点的线性序列。

4. 哈夫曼树和哈夫曼编码

哈夫曼树：带权路径长度最小的二叉树。

5. 判断链表是否有环

快慢指针

6. 二叉排序树

左孩子<根节点<右孩子
不允许出现值相同的元素。
构建，插入都是基于搜索。
删除结点要分为三种情况：1）删除叶子节点，直接删除。2）删除的结点仅有左/右子树，直接把他的左/右子树挪过去。3）删除的结点既有左子树又有右子树，用左子树最右结点和右子树最左节点代替。

7. 平衡二叉树

特殊的二叉排序树，任何一个节点的左右子树高度差的绝对值不大于1.
插入删除结点都要进行判断调整。

8. 哈希表的冲突解决办法

开放定址法：我们在遇到哈希冲突时，去寻找一个新的空闲的哈希地址。
1）线性探测法
当我们的所需要存放值的位置被占了，我们就往后面一直加1并对m取模直到存在一个空余的地址供我们存放值，取模是为了保证找到的位置在0~m-1的有效空间之中。
2）平方探测法（二次探测）
当我们的所需要存放值的位置被占了，会前后寻找而不是单独方向的寻找。

链地址法：将所有哈希地址相同的记录都链接在同一链表中。

9. B树（B-树）

B树是一种平衡的多路查找树。一个节点的查找路径不止有左右两个，而是有多个。

那为什么要使用 B-树呢（或者说为啥要有 B-树呢）？要解释清楚这一点，我们假设我们的数据量达到了亿级别，主存当中根本存储不下，我们只能以块的形式从磁盘读取数据，与主存的访问时间相比，磁盘的 I/O 操作相当耗时，而提出 B-树的主要目的就是减少磁盘的 I/O 操作。大多数平衡树的操作（查找、插入、删除，最大值、最小值等等）需要O(n)次磁盘访问操作，其中h是树的高度。但是对于 B-树而言，树的高度将不再是logn (其中n是树中的结点个数），而是一个我们可控的高度, 所以与 AVL 树和红黑树相比，B-树的磁盘访问时间将极大地降低。

10.B＋树

结点分为索引节点和叶子节点。B树的节点数据不会重复，B+树的节点数据会重复，所有数据都会在叶子节点再出现一遍

11. B树和B+树比较

B树离根节点近的元素查找会更加快速。B+树便于实现范围查找

12. 分治法和动态规划的联系和区别

分治法与动态规划
共同点 ：二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解.

不同点：
分治法将分解后的子问题看成相互独立的，通过用递归来做。

动态规划将分解后的子问题理解为相互间有联系, 有重叠部分，需要记忆，通常用迭代来做。

13. 插入排序

插入排序包括直接插入，折半插入，希尔排序。
插入排序可以理解为码扑克牌的过程，就便于理解记忆了，在无序的队列中拿一张，放到已经有序的队列中的相应位置。
希尔排序：把序列按照下标的一定增量分组，对每组使用直接插入排序，增量逐渐减少，直至被分为一组。
时复：平均O(nlogn)，最坏O(n2)。空复O(1)。不稳定。

这三种插入排序的比较：直接插入稳定，希尔排序不稳定。直接插入适合原始记录基本有序。希尔排序比较次数和移动次数少。直接插入排序适用于链式存储，希尔不适用。

14. 交换排序

冒泡和快排。
冒泡排序 平均时复：O(n2)，最坏：O(n2)，最好：O(n)。空复：O(1)。
冒泡稳定，快排不稳定。

15. 选择排序

简单选择排序，堆排序。

16. 基数排序

稳定

17. 归并排序

分治法的典型应用
O(nlogn)稳定

18. 邻接表和邻接矩阵

邻接表：对每一个顶点，创建一个表，链接其所有出边。
邻接矩阵：就是一个二维数组，大小为dis[n][n], 其中dis[i][j]表示顶点i到顶点j的距离.

19. 迪杰斯特拉

用来求单源最小路径

20. Floyd

可用于带负权值的边，但不允许包含负权值组成的回路。
采用了动态规划
网络层协议中，自治系统内部的路由选择协议：开放最短路径有限协议OSPF就是用的是这个。

21. 最小生成树的算法

在给定一张无向图，如果在它的子图中，任意两个顶点都是互相连通，并且是一个树结构，那么这棵树叫做生成树。当连接顶点之间的图有权重时，权重之和最小的树结构为最小生成树！
Kruskal算法（克鲁斯卡算法）
Kruskal算法是一种贪心算法，我们将图中的每个edge按照权重大小进行排序，每次从边集中取出权重最小且两个顶点都不在同一个集合的边加入生成树中！注意：如果这两个顶点都在同一集合内，说明已经通过其他边相连，因此如果将这个边添加到生成树中，那么就会形成环！这样反复做，直到所有的节点都连接成功！

Prim算法（普里姆算法）
Prim算法是另一种贪心算法，和Kuskral算法的贪心策略不同，Kuskral算法主要对边进行操作，而Prim算法则是对节点进行操作，每次遍历添加一个点，这时候我们就不需要使用并查集了。具体步骤为：

22. O(n)这个大O啥意思

O(n)这个大O表示的是最坏情况下的时间复杂度。

23. 线性存储结构和链式存储结构比较

24. 头指针和头结点的区别

25. 栈和队列的区别和内存结构

栈只允许在栈顶进行插入和删除，栈底不允许。
顺序栈的内存结构：数组，栈顶指针，最大容纳元素个数。
链式栈的内存结构，栈顶指针

队列：队首删除，队尾插入。
顺序存储结构：数组，头指针，尾指针。
链式队列：队首指针，队尾指针。

26、 有一个循环队列Q，里面编号0到n-1，头指针f，尾指针p,求Q中元素个数。

(p-f+n)%n
注：尾指针指向的可不是队尾元素，是队尾元素的下一个位置

27、区分循环队列是队空还是队满

两种方法：一是额外增加一个元素用来记录队列中已有元素的个数。二是放弃队尾的那个存储空间。

28. 堆，大顶堆，小顶堆的实现以及应用

用于堆排序

29. 哈希表的概念，构造方法，大戏冲突的解决办法

哈希表适合存储一些关键字和存储地址存在某种函数关系的数据
哈希函数的构造方法：直接定址法，除留余数法
哈希冲突解决：开放定址法，拉链法

30. 如何由遍历序列构造一棵二叉树？

中序加先序可以构造，中序加后序也可以，中序加层次遍历也可以

31、 介绍一下深度优先和广度优先如何实现的？

深度优先：一头扎到底，选择一条支路就不断的深入。
广度优先：一层一层的往外探索

32、为什么要稳定排序？

使得基于第一个关键字排序的结果服务于基于第二个关键字排序时相等的那些元素。

33. 为什么有了平衡二叉树还会出现B树，B+树，红黑树？

因为平衡二叉树要求太过严苛，每次插入删除都可能涉及到树的旋转。

34. 线索二叉树

遍历二叉树的其实就是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列。这些线性序列中的每一个元素都有且仅有一个前驱结点和后继结点。

但是当我们希望得到二叉树中某一个结点的前驱或者后继结点时，普通的二叉树是无法直接得到的，只能通过遍历一次二叉树得到。每当涉及到求解前驱或者后继就需要将二叉树遍历一次，非常不方便。
二叉树结构

观察二叉树的结构，我们发现指针域并没有充分的利用，有很多“NULL”，也就是存在很多空指针。

对于一个有n个结点的二叉链表，每个节点都有指向左右孩子的两个指针域，一共有2n个指针域。而n个结点的二叉树又有n-1条分支线数(除了头结点，每一条分支都指向一个结点)，也就是存在2n-(n-1)=n+1个空指针域。这些指针域只是白白的浪费空间。因此, 可以用空链域来存放结点的前驱和后继。线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。

如果只是在原二叉树的基础上利用空结点，那么就存在着这么一个问题：我们如何知道某一结点的lchild是指向他的左孩子还是指向前驱结点？rchild是指向右孩子还是后继结点？显然我们要对他的指向增设标志来加以区分。

35. 欧拉回路

包含图上所有边的回路。

计算机网络

1. OSI和TCP/IP模型各个层之间的功能

OSI：物理层，数据链路层，网络层，传输层，会话层，表示层，应用层。
TCP/IP：网络接口层，网际层，传输层，应用层。
物理层：考虑如何在传输媒体上传输比特流，尽可能屏蔽掉传输媒体和通信手段的差异，使数据链路层感受不到差异。
数据链路层：将数据包疯传唱歌和那个能够在不同网络上传输的帧，可以进行差错检测，但不能纠错。增大物理层传输原始比特流的能力。
网络层：进行路由选择和分组转发。
传输层：为应用进程间提供可靠和不可靠的数据传输服务，负责不同主机间进程的通信。
会话层：建立和管理会话。
表示层：进行数据压缩，数据加密，格式转换。
应用层：为用户提供接口，通过进程间的交互来完成特定的网络应用。

2. 计算机网络为什么要分层？优点

1）各层之间相互独立：高层是不需要知道底层的功能是采取硬件技术来实现的，它只需要知道通过与底层的接口就可以获得所需要的服务；
2）灵活性好：各层都可以采用最适当的技术来实现，例如某一层的实现技术发生了变化，用硬件代替了软件，只要这一层的功能与接口保持不变，实现技术的变化都并不会对其他各层以及整个系统的工作产生影响；
3）易于实现和标准化：由于采取了规范的层次结构去组织网络功能与协议，因此可以将计算机网络复杂的通信过程，划分为有序的连续动作与有序的交互过程，有利于将网络复杂的通信工作过程化解为一系列可以控制和实现的功能模块，使得复杂的计算机网络系统变得易于设计，实现和标准化

3. 简述一下层次路由的原理

Intermet网被分成多个自治系统或者多个域。一个域是一组主机和使用相同路由选择协议的路由器集合。
内部网关协议IGP:距离向量路由协议，链路状态路由协议
外部网关协议EGP

4. 网路协议三要素

语法，语义，时序。
语法：用来规定信息格式。
语义：用来说明通信双方应该怎么做
时序：详细说明事件的先后顺序

5. 香农公式

在带宽有限，有噪声的信道当中，为了不产生误差，信息的数据传输速率有上限值。
C=B*log(1+S/N)
C是信道容量，单位比特每秒，B是信道带宽，单位赫兹。

注：信道带宽单位是赫兹Hz，而我们平时所说的网络带宽单位是bit /s，是速率概念。信道带宽与我们的滤波器联系起来就很好理解，滤波器有“高通”、“低通”、"带通"之分，这里的通带概念就是能够通过的频率范围。硬件或通信系统一旦设计完成，那么这个硬件或通信系统所能通过的最大信道带宽就定了。
信道容量的单位是bit/s，和我们上面讲到的网络带宽单位是一样的，也是一个传输速率的概念。好了，这时我们就知道了平时我们说的网络带宽原来讲的就是信道的传输速率呀！信道容量也是讲的信道传输速率呀！！

那网络带宽与信道容量又有啥不一样呢？其实信道容量是指信道最大的数据传输速率，网络带宽指的是信道实际的数据传输速率。

6. 简述一下CSMA/CD协议

载波监听，多点接入，碰撞检测。
先听后发，边听边发，冲突停发，随机重发

MA: 多个站连接在一条总线上，竞争使用总线

7. TCP和UDP的异同点

相同点

TCP和UDP都是在网络层，都是传输层协议，都能都是保护网络层的传输，双方的通信都需要开放端口。

不同点

8. TCP三次握手建立连接

9. 为啥TCP不采用两次握手建立连接，四次呢

10 TCP四次挥手释放连接

11. UDP头部，TCP头部

UDP：源端口号，目的端口号，长度，检验和
TCP：源端口号，目的端口号，序号，确认号，ACK，FIN，SYN，窗口大小……

12. TCP如何保证可靠传输？

13. TCP的快速重传机制。

14. 流量控制和拥塞是什么关系

1.拥塞控制所要做的都有一个前提，就是网络能够承受现有的网络负荷。
2.拥塞控制是一个全局性的过程，涉及到所有的主机、所有的路由器，以及与降低网络传输性能有关的所有因素。
3.流量控制往往指在给定的发送端和接收端之间的点对点道信量的控制。
4.流量控制所要做的就是抑制发送端发送数据的速率，以便使接收端来得及接收。

15. ARP地址解析协议

16. 网卡是什么？功能

网卡是工作在链路层的网络组件，是局域网中连接计算机和传输介质的接口。
功能：实现局域网传输介质之间的物理连接和电信号匹配，还涉及帧的发送和接受，帧的封装与拆封等

17. 网络当中的主机通信流程。

18、 简述DNS域名解析的过程

19. 在浏览器输入一个网址，会发生什么？

20. IP地址和MAC地址有什么区别，有什么用途？

21. DHCP的作用

管理和分配IP地址
工作在局域网，用UDP

22. 能不能直接在应用层把数据交给网络层

23. 什么是socket

24. 协议和服务之间的联系和区别

25. 计算机网路常用的工作模式（端系统间的通信方式）

C/S, P2P

26. 物理层的主要设备

中继器，集线器

27. 物理层数据交换的方式

28. 为什么要进行流量控制？

29.组帧

组帧包括：帧定界，帧同步，透明传输

30、 组帧的方式

31、数据链路层的差错控制

检错，纠错
检错：奇偶校验，CRC
纠错：海明码

32. 滑动窗口流量控制的基本原理

33. 三种自动重传请求方式

34. 随机访问介质控制协议

ALOHA协议
CSMA协议
CSMA/CD协议
CSMA/CA协议

35. 数据链路层在广域网的协议

PPP,高级数据链路控制协议HDLC

36. 链路层设备

网桥，交换机

37.

数据库

1. 事务

事务是并发控制的基本单位，他是一个操作序列，这些操作要么都执行，要么都不执行，是一个不可分割的工作单位。事务是数据库维护一致性的单位，在每个事务结束时，都能保持数据一致性。

2. ACID（数据库事务正确执行的四个基本要素）

原子性atomicity，一致性consistency，隔离性isolation，持久性durability。
A，atomicity：原子性
事务必须是原子工作单元，对于数据的执行要不是全部执行，要不都不执行。如果只执行一个子集，可能会破坏事务的总体目标。

C，consistency：一致性
**事务将数据库从一种一致状态变为下一种一致状态。**如A账户转账给B账户，A账户减钱与B账户加钱必须是全做或全不做，即数据库必须处在一致状态。

I，isolation：隔离性
一个事务的执行不能被其它事物干扰。即一个事物的内部操作及使用的数据对其他并发事务是隔离的，并发执行的各个事物之间不能相互干扰。

D，durability：持久性
**事务完成之后，它对于系统的影响是永久性的。**该修改即使出现致命的系统故障也将一直保持。

3. 索引

(当表的数据量比较大时，查询操作会非常耗时，建立索引是加快查询速度的有效手段）

索引是对数据库表中一或多个列的值进行排序的结构，是帮助快速查询的。

4. 数据库创建索引的好处

1. 通过创建唯一性的索引，可以保证数据库表中每一行数据的唯一性。
2. 可以大大加快数据的检索速度，这也使创建索引的最主要的原因。
3. 可以加速表和表之间的连接，特别是在实现数据的参考完整性方面。
4. 在使用分组和排序子句进行数据检索时，同样可以显著的减少查询中分组和排序的时间。
5. 通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

5. 增加索引的不利的方面

1. 创建索引和维护索引需要消耗时间
2. 索引需要占用物理空间
3. 当对表中的数据进行增加，删除和修改的时候，索引也要动态地维护。

6. 哪些列应该创建索引

1. 作为主键的列上，强制该列的唯一性和组织表中数据的排列结构。
2. 在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度。
3. 在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的。
4. 在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间。
5. 在经常使用where子句中的列上面创建索引，加快条件的判断速度。

7. 哪些列不应该创建索引

1. 在查询中很少使用或者作为参考的列
2. 只有很少数据值的列，比如性别
3. 定义为text,image,bit的数据类型的列
4. 修改性能远远大于检索性能时，不应该创建索引，因为修改性能和检索性能是矛盾的。

8. 创建索引的方法

直接创建和间接创建（在表中定义主键约束或者唯一性约束时，同时也创建了索引）

9. 基本的索引类型

唯一性索引和复合索引

唯一性索引保证在索引列中的全部数据是唯一的，不会包含冗余数据。
复合索引就是一个索引创建在两个列或者多个列上，可以减少一在一个表中所创建的索引数量。

10、异常情况

丢失数据，读脏数据，非重复读，幻影读。
丢失数据：两个事务都对一个数据进行修改，一个先修改一个后修改

高数

1. 连续，可导，可微，可积的关系

一元函数：可导能推出可微，可微也能推出可导。两者都能推出连续。连续能推导出可积。
多元函数：偏导数连续能推出可微。可微能推出可偏导，也能推出连续。但是连续和可偏导不能相互推出。

2. 三个中值定理的区别

罗尔中值定理，拉格朗日中值定理，柯西中值定理

3. 偏导数，方向导数，梯度，梯度下降

偏导数：对于一个多元函数，选定一个自变量让其他自变量保持不变，只考察因变量与选定自变量的变化关系。
方向导数：多元函数在非坐标轴方向上也可以求导数
梯度：函数的所有偏导数组成的向量。梯度的方向即为函数值增长最快的方向。
梯度下降：沿着负梯度方向去减小函数值

4. 泰勒公式

用一个函数的信息描述其附近取值的公式。用一个多项式去逼近一个函数。
麦克劳林公式是泰勒公式的一种特殊情况，即x0=0的泰勒公式。

线代

1. 向量空间

2. 矩阵的秩

3. 特征值和特征向量

4. 相似矩阵

5. 正定矩阵

设A是n阶方阵，对任意的非零向量x，都有xTAx>0，则称A是正定矩阵。

6. 线性相关和线性无关

7. 正交矩阵

其转置等于其逆的矩阵。
正定向量：两个向量的内积如果是0，那么就说这两个向量是正交的。两个向量是正交的意味着他们是相互垂直的。

概率论

1. 古典概型，几何概型

古典概型：有限等可能。有限个可能事件，且每个事件等可能概率事件。
几何概型：无限等可能

2、条件概率

若P(B)>0，称在B发生的条件下，A发生的概率为条件概率，且P(A|B）=P(AB)/P(B)。

3. 全概率公式

若B1,B2,Bn是一个完备事件组，则对任一事件A，有P(A)=P(A|B1)+P(A|B2)+…+P(A|Bn)

4. 贝叶斯公式

在A事件发生的情况下，Bi事件发生的概率。
P(Bi/A)=P(A|Bi)P(Bi) / P(A|B1)+P(A|B2)+…+P(A|Bn)
举一个例子方便记忆全概率和贝叶斯。
比方说我今天去上课，走第一条路的概率是a,走第二条路的概率是b，走第一条路迟到的概率是c,走第二条路迟到的概率是d。那么全概率公式就是用来求我今天迟到的概率是多少，也就是ac+bd。贝叶斯公式就是用来求，我已经迟到了，那么我走第一条路的概率是多少？也就是ac/(ac+bd)。

5. 什么是先验概率？

事情没有发生，只根据以往的数据统计，分析事情发生的可能性，即先验概率。
先验概率是指根据以往经验和分析得到的概率，如全概率公式，他往往作为“由因求果”问题中的因出现。

6. 什么是后验概率？

事件已经发生，已经知道结果了。求引起这事发生的因素的可能性，由果求因，即后验概率。
后验概率是指依据得到的“结果”信息所计算出的最有可能是那种事件发生，如贝叶斯公式中的，是“执果寻因”问题中的因。

后验概率的计算，是以先验概率为前提条件。如果只知道事情结果，而没有以往数据统计，不知道先验概率的话，是没有办法计算后验概率的。

7. 离散型随机变量的常见分布。

8. 连续性随机变量的分布

9. 若干正态分布相加，相乘后得到的分布是什么

独立的前提下都服从正态分布。

10. 数学期望

随机变量的均值（不同于样本均值），大数定律指出，如果样本足够的话，样本均值会无限接近于数学期望。
数学期望（mean）是是试验中每次可能的结果的概率乘以其结果的总和，是最基本的数学特征之一。

11. 方差

方差是衡量数据和期望值相差的度量值。
D(X)=E(X2)-E2(X)
平方的期望减去期望的平方。

12. 协方差

X,Y的协方差等于每一个X减去X平均值乘上每一个Y减去Y平均值的乘积的和的平均数。从数值来看，协方差的数值越大，两个变量的同向程度也就越大。从直观上来看，协方差表示的是两个变量总体误差的期望。
如果两个变量的变化趋势一致，也就是说如果其中一个大于自身的期望值时另一个却小于自身的期望值，那么两个变量之间的协方差就是负值。

13. 相关系数

X,Y的相关系数就是X,Y的协方差除以X的标准差和Y的标准差。
相关系数也可以看成协方差：一种剔除了两个变量量纲影响，标准化后的特殊方差。他消除了两个变量变化幅度的影响。而只是单纯反应两个变量每单位变化时的相似程度。

14、相关系数或者协方差为0的时候能否说明两个分布无关？为什么？

只能说明不线性相关，不能说明无关。因为在数学期望存在的情况下，独立必不相关，不相关未必独立。

15、独立和互斥的关系？

互斥不独立，独立不互斥

16. 独立和不相关的区别

相关性描述的是两个变量是否有线性关系，独立性描述的是两个变量是否有关系。不相关表示两个变量没有线性关系，但还可以有其他关系，也就是不一定相互独立。独立就是互不相干没有关联。

17. 大数定律

答案一：
大数定律分为切比雪夫大数定律，辛钦大数定律，伯努利大数定律。
前两者：在试验次数足够多时，样本均值趋近于随机变量的数学期望。
伯努利大数定理：在试验次数足够多时，频率趋近于概率。

答案二：
随机变量的均值依概率收敛于自己的期望。
或者说在试验不变的条件下，重复试验多次，随机事件的频率近似于它的概率。

18. 中心极限定理

给定一个任意分布的总体，每次从这些总体中随机抽取n个抽样，一共抽取m次。然后把这m组抽样分别求出平均值。这些平均值的分布接近正态分布。

19. 大数定理和中心极限定理的区别

前者更关注样本均值，后者更关注样本均值的分布。

20. 最大似然估计是什么

是一种参数估计方法。
最大似然估计的目的是：利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值。

了解几个人工智能相关算法

1. 线性回归

线性回归（Linear Regression）可能是最流行的机器学习算法。线性回归就是要找一条直线，并且让这条直线尽可能地拟合散点图中的数据点。然后就可以用这条线来预测未来的值！这种算法最常用的技术是最小二乘法（Least of squares）。这个方法计算出最佳拟合线，以使得与直线上每个数据点的垂直距离最小。总距离是所有数据点的垂直距离（绿线）的平方和。其思想是通过最小化这个平方误差或距离来拟合模型。

2. 逻辑回归

逻辑回归（Logistic regression）与线性回归类似，但逻辑回归的结果只能有两个的值。如果说线性回归是在预测一个开放的数值，那逻辑回归更像是做一道是或不是的判断题。
逻辑函数中Y值的范围从 0 到 1，是一个概率值。逻辑函数通常呈S 型，曲线把图表分成两块区域，因此适合用于分类任务。

3. 决策树

如果说线性和逻辑回归都是把任务在一个回合内结束，那么决策树（Decision Trees）就是一个多步走的动作，它同样用于回归和分类任务中，不过场景通常更复杂且具体。
举个简单例子，老师面对一个班级的学生，哪些是好学生？如果简单判断考试90分就算好学生好像太粗暴了，不能唯分数论。那面对成绩不到90分的学生，我们可以从作业、出勤、提问等几个方面分开讨论。

以上就是一个决策树的图例，其中每一个有分叉的圈称为节点。在每个节点上，我们根据可用的特征询问有关数据的问题。左右分支代表可能的答案。最终节点（即叶节点）对应于一个预测值。

每个特征的重要性是通过自顶向下方法确定的。节点越高，其属性就越重要。比如在上面例子中的老师就认为出勤率比做作业重要，所以出勤率的节点就更高，当然分数的节点更高。

4. 支持向量机SVM

支持向量机（Support Vector Machine，SVM）是一种用于分类问题的监督算法。支持向量机试图在数据点之间绘制两条线，它们之间的边距最大。为此，我们将数据项绘制为 n 维空间中的点，其中，n 是输入特征的数量。在此基础上，支持向量机找到一个最优边界，称为超平面（Hyperplane），它通过类标签将可能的输出进行最佳分离。

超平面与最近的类点之间的距离称为边距。最优超平面具有最大的边界，可以对点进行分类，从而使最近的数据点与这两个类之间的距离最大化。

所以支持向量机想要解决的问题也就是如何把一堆数据做出区隔，它的主要应用场景有字符识别、面部识别、文本分类等各种识别。

5. K-近邻算法 KNN

是数据挖掘分类技术中最简单的方法之一。KNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

KNN分类示例

KNN理论简单，容易实现，可用于文本分类、模式识别、聚类分析等。

6. 降维

由于我们今天能够捕获的数据量之大，机器学习问题变得更加复杂。这就意味着训练极其缓慢，而且很难找到一个好的解决方案。这一问题，通常被称为“维数灾难”（Curse of dimensionality）。

降维（Dimensionality reduction）试图在不丢失最重要信息的情况下，通过将特定的特征组合成更高层次的特征来解决这个问题。**主成分分析（Principal Component Analysis，PCA）**是最流行的降维技术。

主成分分析通过将数据集压缩到低维线或超平面 / 子空间来降低数据集的维数。这尽可能地保留了原始数据的显著特征。

7. 人工神经网络ANN

人工神经网络（Artificial Neural Networks，ANN）可以处理大型复杂的机器学习任务。神经网络本质上是一组带有权值的边和节点组成的相互连接的层，称为神经元。在输入层和输出层之间，我们可以插入多个隐藏层。人工神经网络使用了两个隐藏层。除此之外，还需要处理深度学习。

人工神经网络的工作原理与大脑的结构类似。一组神经元被赋予一个随机权重，以确定神经元如何处理输入数据。通过对输入数据训练神经网络来学习输入和输出之间的关系。在训练阶段，系统可以访问正确的答案。

如果网络不能准确识别输入，系统就会调整权重。经过充分的训练后，它将始终如一地识别出正确的模式。

每个圆形节点表示一个人工神经元，箭头表示从一个人工神经元的输出到另一个人工神经元的输入的连接。

图像识别，就是神经网络中的一个著名应用。

8. 朴素贝叶斯分类

主要用来解决分类和回归问题。

具体应用有：
标记一个电子邮件为垃圾邮件或非垃圾邮件；
将新闻文章分为技术类、政治类或体育类；
检查一段文字表达积极的情绪，或消极的情绪；
用于人脸识别软件。

贝叶斯分类是一系列分类算法的总称，这类算法均以贝叶斯定理为基础，故统称为贝叶斯分类。朴素贝叶斯算法（Naive Bayesian) 是其中应用最为广泛的分类算法之一。朴素贝叶斯分类器基于一个简单的假定：给定目标值时属性之间相互条件独立。

上述人工智能算法来自链接：https://zhuanlan.zhihu.com/p/536818157

机器学习

机器学习根据训练方法大致可以分为3大类：
监督学习
非监督学习
强化学习

监督学习
监督学习是指我们给算法一个数据集，并且给定正确答案。机器通过数据来学习正确答案的计算方法。

这种通过大量人工打标签来帮助机器学习的方式就是监督学习。这种学习方式效果非常好，但是成本也非常高。

非监督学习
非监督学习中，给定的数据集没有“正确答案”，所有的数据都是一样的。无监督学习的任务是从给定的数据集中，挖掘出潜在的结构。

非监督学习中，虽然照片分为了猫和狗，但是机器并不知道哪个是猫，哪个是狗。对于机器来说，相当于分成了 A、B 两类。

** 强化学习**
强化学习更接近生物学习的本质，因此有望获得更高的智能。它关注的是智能体如何在环境中采取一系列行为，从而获得最大的累积回报。通过强化学习，一个智能体应该知道在什么状态下应该采取什么行为。

最典型的场景就是打游戏。

2019年1月25日，AlphaStar（Google 研发的人工智能程序，采用了强化学习的训练方式） 完虐星际争霸的职业选手职业选手“TLO”和“MANA”。

机器学习实操的7个步骤

1. 收集数据
2. 数据准备
3. 选择一个模型
4. 训练
5. 评估
6. 参数调整
7. 预测（开始使用）
   

15种经典机器学习算法

机器学习相关内容转自：https://easyai.tech/ai-definition/machine-learning/

深度学习

深度学习是机器学习的一个分支(最重要的分支)。目前表现最好的一些应用大部分都是深度学习。

深度学习的概念源于人工神经网络的研究，但是并不完全等于传统神经网络。不过在叫法上，很多深度学习算法中都会包含”神经网络”这个词，比如：卷积神经网络、循环神经网络。所以，深度学习可以说是在传统神经网络基础上的升级，约等于神经网络。

下面这个例子真的解释得非常好！！学到了！：
假设深度学习要处理的信息是“水流”，而处理数据的深度学习网络是一个由管道和阀门组成的巨大水管网络。网络的入口是若干管道开口，网络的出口也是若干管道开口。这个水管网络有许多层，每一层由许多个可以控制水流流向与流量的调节阀。根据不同任务的需要，水管网络的层数、每层的调节阀数量可以有不同的变化组合。对复杂任务来说，调节阀的总数可以成千上万甚至更多。水管网络中，每一层的每个调节阀都通过水管与下一层的所有调节阀连接起来，组成一个从前到后，逐层完全连通的水流系统。

那么，计算机该如何使用这个庞大的水管网络来学习识字呢？

比如，当计算机看到一张写有“田”字的图片，就简单将组成这张图片的所有数字（在计算机里，图片的每个颜色点都是用“0”和“1”组成的数字来表示的）全都变成信息的水流，从入口灌进水管网络。

我们预先在水管网络的每个出口都插一块字牌，对应于每一个我们想让计算机认识的汉字。这时，因为输入的是“田”这个汉字，等水流流过整个水管网络，计算机就会跑到管道出口位置去看一看，是不是标记由“田”字的管道出口流出来的水流最多。如果是这样，就说明这个管道网络符合要求。如果不是这样，就调节水管网络里的每一个流量调节阀，让“田”字出口“流出”的水最多。
这下，计算机要忙一阵了，要调节那么多阀门！好在计算机的速度快，暴力的计算加上算法的优化，总是可以很快给出一个解决方案，调好所有阀门，让出口处的流量符合要求。

下一步，学习“申”字时，我们就用类似的方法，把每一张写有“申”字的图片变成一大堆数字组成的水流，灌进水管网络，看一看，是不是写有“申”字的那个管道出口流水最多，如果不是，我们还得再调整所有的阀门。这一次，要既保证刚才学过的“田”字不受影响，也要保证新的“申”字可以被正确处理。

如此反复进行，知道所有汉字对应的水流都可以按照期望的方式流过整个水管网络。这时，我们就说，这个水管网络是一个训练好的深度学习模型了。当大量汉字被这个管道网络处理，所有阀门都调节到位后，整套水管网络就可以用来识别汉字了。这时，我们可以把调节好的所有阀门都“焊死”，静候新的水流到来。

与训练时做的事情类似，未知的图片会被计算机转变成数据的水流，灌入训练好的水管网络。这时，计算机只要观察一下，哪个出水口流出来的水流最多，这张图片写的就是哪个字。
深度学习大致就是这么一个用人类的数学知识与计算机算法构建起来的整体架构，再结合尽可能多的训练数据以及计算机的大规模运算能力去调节内部参数，尽可能逼近问题目标的半理论、半经验的建模方式。


卷积神经网络 – CNN
CNN 的价值：
能够将大数据量的图片有效的降维成小数据量(并不影响结果)
能够保留图片的特征，类似人类的视觉原理

CNN 的基本原理：
卷积层 – 主要作用是保留图片的特征
池化层 – 主要作用是把数据降维，可以有效的避免过拟合
全连接层 – 根据不同任务输出我们想要的结果

CNN 的实际应用：
图片分类、检索
目标定位检测
目标分割
人脸识别
骨骼识别

循环神经网络 – RNN
RNN 是一种能有效的处理序列数据的算法。比如：文章内容、语音音频、股票价格走势…

之所以他能处理序列数据，是因为在序列中前面的输入也会影响到后面的输出，相当于有了“记忆功能”。但是 RNN 存在严重的短期记忆问题，长期的数据影响很小（哪怕他是重要的信息）。

于是基于 RNN 出现了 LSTM 和 GRU 等变种算法。这些变种算法主要有几个特点：
长期信息可以有效的保留
挑选重要信息保留，不重要的信息会选择“遗忘”

RNN 几个典型的应用如下：
文本生成
语音识别
机器翻译
生成图像描述
视频标记

生成对抗网络 – GANs
假设一个城市治安混乱，很快，这个城市里就会出现无数的小偷。在这些小偷中，有的可能是盗窃高手，有的可能毫无技术可言。假如这个城市开始整饬其治安，突然开展一场打击犯罪的「运动」，警察们开始恢复城市中的巡逻，很快，一批「学艺不精」的小偷就被捉住了。之所以捉住的是那些没有技术含量的小偷，是因为警察们的技术也不行了，在捉住一批低端小偷后，城市的治安水平变得怎样倒还不好说，但很明显，城市里小偷们的平均水平已经大大提高了。

警察们开始继续训练自己的破案技术，开始抓住那些越来越狡猾的小偷。随着这些职业惯犯们的落网，警察们也练就了特别的本事，他们能很快能从一群人中发现可疑人员，于是上前盘查，并最终逮捕嫌犯；小偷们的日子也不好过了，因为警察们的水平大大提高，如果还想以前那样表现得鬼鬼祟祟，那么很快就会被警察捉住。为了避免被捕，小偷们努力表现得不那么「可疑」，而魔高一尺、道高一丈，警察也在不断提高自己的水平，争取将小偷和无辜的普通群众区分开。随着警察和小偷之间的这种「交流」与「切磋」，小偷们都变得非常谨慎，他们有着极高的偷窃技巧，表现得跟普通群众一模一样，而警察们都练就了「火眼金睛」，一旦发现可疑人员，就能马上发现并及时控制——最终，我们同时得到了最强的小偷和最强的警察。

深度强化学习 – RL
强化学习算法的思路非常简单，以游戏为例，如果在游戏中采取某种策略可以取得较高的得分，那么就进一步「强化」这种策略，以期继续取得较好的结果。这种策略与日常生活中的各种「绩效奖励」非常类似。我们平时也常常用这样的策略来提高自己的游戏水平。

在 Flappy bird 这个游戏中，我们需要简单的点击操作来控制小鸟，躲过各种水管，飞的越远越好，因为飞的越远就能获得更高的积分奖励。
这就是一个典型的强化学习场景：
机器有一个明确的小鸟角色——代理
需要控制小鸟飞的更远——目标
整个游戏过程中需要躲避各种水管——环境
躲避水管的方法是让小鸟用力飞一下——行动
飞的越远，就会获得越多的积分——奖励

你会发现，强化学习和监督学习、无监督学习 最大的不同就是不需要大量的“数据喂养”。而是通过自己不停的尝试来学会某些技能。
深度学习相关内容来自：https://easyai.tech/ai-definition/deep-learning/