一 导入
逻辑重要性: 排中律、统一律、充足理由律
算法形式和架构:
1.1 算法工程化
算法工程化步骤包括：
- 问题分析
- 数学建模
- 算法设计
- 算法说明（算法证明）
- 算法程序实现
- 算法分析
1.2 操作系统经典算法
进程调度算法
1、时间片轮转调度算法
2、先来先服务调度算法
3、优先级调度算法
4、多级反馈队列调度算法
5、高响应比优先调度算法
全局页面替换策略
1、最佳页面替换算法
2、先进先出页面替换算法
3、最近最少使用页面替换算法
4、第二次机会页面替换算法
5、时钟页面替换算法
可变分区存储管理算法
1、最先适应分配算法
2、下次适应分配算法
3、最优适应分配算法
4、最坏适应分配算法
5、快速适应分配算法
局部页面替换算法
1、局部最佳页面替换算法
2、工作集置换算法
3、模拟工作集替换算法
4、缺页频率替换算法。
磁道（柱面）的搜索定位算法
1、先来先服务算法
2、最短查找时间优先算法
3、扫描算法
4、分步扫描算法
5、电梯调度算法
1.2.1 时间片轮转调度算法
在操作系统中多进程运行的次序是不一样的，这时就需要选择执行的顺序。在分时系统中多采用循环轮转调度算法，系统规定一个时间片，每个进程被调度时分得一个时间片，当这一时间片用完时，该进程转为就绪态并进入就绪队列末尾。
当CPU空闲时，选取就绪队列首元素，赋予时间片。当进程时间片用完时，就释放CPU控制权，进入就绪队列末尾，CPU控制权给下一个处于就绪队列首元素。状态图如下：
操作系统为每个进程都维护了一个进程控制块PCB，用于保存该进程的有关的各种状态信息。一个进程存在则必定会有一个PCB，PCB是进程存在的唯一的标志，如果进程消失，则对应PCB也随之消失。
PCB是进程实体的一部分，是操作系统中最重要的记录型数据结构，作用是使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，成为能与其它进程并发执行的进程。OS是根据PCB对并发执行的进程进行控制和管理。
PCB中的信息包括：
- 进程标识符(PID)
- 上下文数据
- 进程调度信息
- 进程控制信息
- I/O 状态信息
PCB组织方式：
链表：
同一状态的进程其PCB连成一个链表, 多个状态对应多个不同的链表
如 : 就绪链表, 阻塞链表, 运行链表
索引：
同一个状态的进程归入一个index表, 由index指向PCB , 多个状态对应多个不同的index表
算法实现思路
考虑用循环链表来存放数据。循环列表和一般链表唯一一个区别就是最后一个结点本来是p->next=NULL，现在就把头结点和尾结点相连就行，即p->next=head
下面是结构体的里面的内容，放入进程的名字以及需要运行的时间和等待时间:
struct pcb { char name[10]; //进程名称int need, turn; //进程运行时间和已等待时间 struct pcb *next; };
在计算运行时间时，
1.比如说第一个进程的运行时间小于或等于时间片的长度，所以就把时间加上去，并将每个进程的等待时间都加上这个进程的运行时间。并且将正在运行的进程的need赋值为0。这样是为了将need标记为已经运行完的了，以后若再碰到就跳过这个结点。
2.再比如说第一个进程的运行时间大于时间片的长度，就将该进程的need减去一个时间片的长度，并且将指针移到下个结点，相当于把这个结点放到队列尾部。再把各个进程的等待时间加上一个时间片的长度。就这样反复的循环，知道所有结点的need全部变为0的时候就跳出来。
1.3 网络经典算法
TCP拥塞控制算法
组播树生成算法
Bellman-Ford算法
距离向量（D-V）算法
路径选择算法（Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法、A*算法、SPFA算法、）
贪心算法证明：
线性相关的两个性质
拟阵