有限自动机
基础概念
集合： 一群无序对象
序列(sequence): 以某种顺序排布的有序列表
元组(tuple): 有限序列称为元组
字母表： 字母表是任何非空有限集合，例如{a, b, c}
字符串： 字符串是在字母表中的字符组成成的有限序列,如abcac
语言： 字典序的一组字符串。例如{0, 1}组成的一个语言为{0, 1, 01, 10, 11, 000}.也就是说1比0更大，先比较长度，长度相同从高位向低位比较
语言的拼接： 定义两个语言L1, L2， 他们的拼接L1L2 = {xy | $x \in L_1, y \in L_2$}。类似于分配率
设L1 = {ab, ba, bb} L2 = {00, 11}, L1L2 = {ab00, ab11, ba00, ba11, bb00, bb11}
语言的闭包：
$L^* = L^+ \cup {\xi}$
例如， $\sum = {0, 1}$ L = {01, 10} $L^0 = {\xi}, L^1 = L = {01, 10}, L^2 = L * L = {0101, 0110, 1001, 1010} ...
线和面的表示
线的表示定义： P1(x1, y1, z1) P2(x2, y2, z2)是空间中的两点，两点之间线段的表示为;
P(t) = (1-t) \times P1 + t \times P2 \quad t \in [0, 1]这种表示方法的优点在于他只有一个变量，并且范围始终在[0, 1]。这也使得我们可以通过改变线的大小方便的得到不同的点从而在计算机中绘制出这条线。
一般式:
P(t) = (X(t), Y(t))二维线画图元生成直线段生成DDA算法
依据：y = m * x + b
其中 $m = \frac{y_2 - y_1 }{x_2 - x_1 }, b = y_1 - m * x_1$
现在需要从(x1, y1)到(x2, y2)间画线
算法步骤：
划分区间[x1, x2] x1, x2, …, xi, …, xn 其中$x_{i+1} = x_i + 1$
计算每个点的纵坐标,通过下面的方法可以让原来的乘法计算变为加法，增快速度。其中$m \in [0, 1]$
\begin{aligned}
y_{i+1} =& m * x_{i+1} + ...
文件系统
文件文件的结构和类型文件在系统中其实就是一串二进制数，结尾有特殊的符号标识，而他的入口处由操作系统管理。
在linux系统中，文件的类型有目录文件，一般文件和特殊文件（如设备文件）等，这些文件在内容组织上各不相同，但是他们的基础构成还是上面说的。
查找文件首先在linux中文件通过树形结构进行组织，在找到对应目录下的文件后就要打开文件了。linux目录中存放的i节点表，i节点中存放着一些文件的信息和文件的入口地址。
如图就是一些文件的属性，操作系统会根据自身需要选取某些属性。
这个图中就是i节点的结构，注意Point to Block data就是在磁盘中的位置
文件在磁盘中的储存
第一种方法时每个文件在磁盘中有固定的位置，当然这种方法是不可行的，因为这样必须事先分配好大小，如果达到了事先分配的最大值后就无法继续增大。
第二种方法是通过一个链表组织。这种方法中链表在磁盘的前几个字节，然后i节点指向入口地址。它的缺点是如果想访问后面的节点必须把前面节点都扫一遍，并且因为他在磁盘中占有了位置，所以现在磁盘中所能容纳的文件字节数减少了，需要重新考虑对齐的问题。
第三种方法是在i节点中增加15 ...
文本聚类
层次聚类层次聚类可以表示为树图的形式。
单/全连通聚类寻找两个集合之间最相似样本之间的相似度。
算法过程：
初始每一个节点为一类，计算每两类中最近节点的距离，并选取距离最小的进行合并。
如图，第一回合聚类结果为{a, b}, {c, d}, {e, f}, {g, h}。第二回合聚类结果为{a, b, c, d}, {e, f, g, h}
但是a和d之间的距离实际上比a和e之间的距离要大，因此这种算法可能会导致拉长聚类区域。
全连通聚类
全连通聚类考虑的是最不相近样本之间的聚类，然后选取这些距离中最小的进行聚类。
平均连通聚类
平均连通聚类定义了一个相似度$S(Cj ) = \frac{1}{|c_j |(|c_j |-1)}\sum{\vec{x} \in cj}\sum{\vec{x} != \vec{y} \in c_j} sim(\vec{x}, \vec{y})$
我们需要计算S($c_u \cup c_j$)，并且合并结果最大的两个集合
\vec{s}(c_j ) = \sum_{\vec{x} \in c_j}\vec{x}
非层次聚类k-means算法
网络流
AOV网络aov网络指的是用顶点表示活动的网络。讲个例子吧
例如学习课程有个前后顺序，前面一门课没有学完后面一门课动不了手。这样就可以用顶点表示课程，然后用有向箭头表示学习的次序，这样就是一种AOV网络。并且显然每个点都要走，因为每门课都要学。
检测有向环可以用对AOV网络构造拓扑序列。构造方法等会讲，如果有环，那么就会出现永远都有入度的情况，就说明有环。
构造过程
就拿上面一个图来说吧。必须先要学完c1，c2才可以学c3.学了c1又可以学c8，按照这样的顺序就可以得出学习顺序是C1C2C3C5C4C8C9C7C6。当然，还有许多其他的次序。
从中我们可以发现一个规律，假如每当我们学一门课就删去这些边，那么我们可以学习一个课程时入度一定为0.例如我们学完1和2后3入度就是0所以现在我们可以学了。如果入度不为0说明我们还有前置知识我们没有掌握，就不能学。
总结：找出入度为0的点，删去与之相邻的边，然后找新的入度为0的点，重复上述过程。
下面给出模板：
#include<iostream>using namespace std;struct edge{ int ...
网络层
基础概念在应用层和运输层已经将数据封装好了，网络层所做的工作就是把数据尽可能传输过去，其中的难点在于选择传输的路径。有些传输算法可能导致需要经过4个路由器，而有的只需要两个。
转发： 从输入接口转移到输出接口，是路由器内部过程。路由器本身有许多个接口，可能要从一个接口输入再从另一个接口输出。
路由选择： 选择从源到目的地的路径。
路由器中的一个关键元素就是转发表，它决定了这个路由器可以传输到哪些路由器，
路由器工作原理路由器的组件有：
输入端口： 输入端口负责接收数据和查找。查找指的是通过转发表找到输出端口。这里的端口并不是逻辑端口（如计算机上的端口）而是交换机上实实在在的端口。
交换结构： 将输入端口连接到输出端口
输出端口：
路由选择处理器： 它是操作转发表的结构。它通过路由选择协议来改变维护转发表
输入端口处理例如：
目的地址范围
链路接口
0xC8171000 - 0xC81717FF
0
0xC8171800 - 0xC81718FF
1
0xC8171900 - 0xC8171FFF
2
其他
3
可以看到他们的范围中前缀都是一样 ...
图论基础
最小生成树如果图中有权值，称为网，仅在无向图中考虑这些问题，生成树指删去一些边变为树
kruskal算法这个也被称为加边法，
把图中所有边按权值从小到大排序
把图中n个点看为n个独立的连通块
选择端点分属两个联通块且权值最小的边，若可选择的边有多条，任选其中一条即可
重复三，直至只剩一个连通块
如何存边？
struct node{ int u,v,w; friend operator <(const node &x,const node& y) { return x.w<y.w; }}e[maxm];
其中u代表起点v代表终点，而w代表权值
采用了并查集的思想
怎么看加边后是否会变成环？只需要查找u，v的根节点，如果根节点相同则说明加边后 会变成环
模板，n个点m条边，找最小生成树
#include<iostream>#include<vector>#define MAXN 1000using namespace std;struct node{ ...
图灵机概述
定义图灵机是一个七元组(Q, $\sum , \tau , \delta , q0 , q{accept} , q_{reject}$}
Q： 状态集
$\sum$: 输入字母表
$\tau$: 纸带字母表 $\sqcup$是空白符
$\delta$: $Q \times \tau -> Q \times \tau \times {L, R}$
$q_{reject}$： 拒绝状态
简单来说图灵机有一个纸带，并且有一个探头可以读取纸带中任意位置的数据，并且可以修改纸带中任意位置的值，纸带的初始内容就是输入的字符串，纸带上最后一个字符后的字符都是空白符。
纸带的格局（当前状态的内容）：
纸带的格局由三部分内容组成，他可以使用uqv表示，其中q是读写头，uv是纸带内容
当前状态： q
当前纸带内容： uv
读写头当前位置： v的第一个字符
从当前格局跳转到下一个格局的形式化定义为：
a, b $\in \tau$, u, v $\in tau^*$, $q_i , q_j \in Q$
ua$q_i$bv 产生 u$q_j$acv 如果存在$\delta(q_i , b) ...
贪心与k-优化
引例活动选择问题
假设n个活动集合S，这些活动使用同一个资源。这个资源在某一时刻只能供一个活动使用，每个活动都有一个开始时间和一个结束时间。 我们想选出时间不重叠的数量最多的活动集（假设活动按照结束时间单调递增排序）。
这个问题可以写出最优解的表达式但是求解的时候比较麻烦。
我们是否可以这样考虑，我们每次都挑选最早结束的活动，这样就算有活动比他早开始，但是因为比他晚结束，所以同样是一个活动还是早结束的活动更优。
代码比较简单，就不打了
原理 性质： 我们通过局部最优解构造全局最优解。也就是我们可以考虑当前问题最优的选择，而不比考虑子问题的解。
如果一个问题最优解包含子问题最优解，称此问题有最优子结构性质。
每个小问题的解可由贪心选择获得，则称这个问题具有贪心选择性质。
k-优化算法
这里的k-优化是拿背包问题进行说明的，其他某些问题也可以使用。
大致过程：
首先按密度进行排序
先拿取k件物品，如果重量大于背包重量c，则放弃这个选择（具体请看下面例子）
对其余物品使用贪心算法
进行$C_n^k$次上述过程找出贪心最优解
k-优化算法的优点是它将贪心算法与最优算法的偏差 ...
数值计算的误差
误差来源
模型误差： 将实际问题时出现的误差。因为实际问题转化为数学模型时会省略很多东西，因此难免会有误差。
观测误差： 在测量一些物理量（长度等）时产生的误差。
截断误差： 求近似解产生的误差。例如泰勒公式使用若干项进行求解就会舍去后面的项
舍入误差： 使用计算机计算时，由于计算机表达位数有限，因此会产生舍入误差
误差和有效数字假设x为准确值， $x^$为x的一个近似值，$e^ = x^ - x$为近似值的*绝对误差，简称误差。
通常我们不知道准确值，但是我们有时候我们可以估计出一个上限，记作$\varepsilon^$，称为*误差限
即 $|x^ - x| \le \varepsilon^$
相对误差： 绝对误差与真实值的比值,记作$e_r^*$
e_r^* = \frac{e^*}{x^*} = \frac{x^* - x}{x}通常情况下我们无法获得x，因此相对误差可以写成$\frac{x^ - x}{x^ }$
相对误差也有误差限，记作$\varepsilon_r^$,即$\varepsilon_r^ = \frac{\varepsilon^}{x^}$
有效数字定义 ...