最小生成树如果图中有权值，称为网，仅在无向图中考虑这些问题，生成树指删去一些边变为树 kruskal算法这个也被称为加边法， 把图中所有边按权值从小到大排序 把图中n个点看为n个独立的连通块 选择端点分属两个联通块且权值最小的边，若可选择的边有多条，任选其中一条即可 重复三，直至只剩一个连通块 如何存边？ 12345678struct node{ int u,v,w; f

定义图灵机是一个七元组(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}$： 拒绝状态 简单

引例活动选择问题 假设n个活动集合S，这些活动使用同一个资源。这个资源在某一时刻只能供一个活动使用，每个活动都有一个开始时间和一个结束时间。 我们想选出时间不重叠的数量最多的活动集（假设活动按照结束时间单调递增排序）。 这个问题可以写出最优解的表达式但是求解的时候比较麻烦。 我们是否可以这样考虑，我们每次都挑选最早结束的活动，这样就算有活动比他早开始，但是因为比他晚结束，所以同样是一个活动还是早

误差来源 模型误差： 将实际问题时出现的误差。因为实际问题转化为数学模型时会省略很多东西，因此难免会有误差。 观测误差： 在测量一些物理量（长度等）时产生的误差。 截断误差： 求近似解产生的误差。例如泰勒公式使用若干项进行求解就会舍去后面的项 舍入误差： 使用计算机计算时，由于计算机表达位数有限，因此会产生舍入误差 误差和有效数字假设x为准确值， $x^$为x的一个近似值，$e^ = x^ -

基础概念首先需要知道积分的含义： 在二重积分中，积分可以粗略的认为是求面积。由于我们是离散的点，因此常见的做法是使用矩形或梯形来逼近这块面积，如果采样点无限多，那么通过这种方法得出的结果就是精确的。 但是这种方法计算代价过大，我们可以利用这些点做插值来拟合曲线，再对插值函数进行积分得到更好的结果。 代数精度定义： 如果某个求积公式对于次数不超过m的多项式均能准确的成立，但对于m+1次的多项式不能准

上下文无关文法 上下文无关文法(CFG)是一个四元组(V, $\sum$, R, S) V是变元 $\sum$是终结符 R: 规则，每条规则都由左边的变元和右边变元和终结符组成的字符串构成 S： 起始节点 例如： S -> aSb | SS | $\varepsilon$ 二义性二义性指的是一个字符串可能有多种解析方式 . 导致二义性的原因： 解析顺序不同，可能最后生成的解析树是相同的。

三维观察是将一个三维物体投影到二维平面上的过程。一般需要经过建模变换、观察变换、投影变换、规范化变换和裁剪、视口变换 观察变换 观察坐标就是人眼观察事物的坐标，我们可以使用n作为z轴正向向量，v作为眼睛上方向量也就是y，u是视线的右方也就是x。 观察变换的目的就是把物体从世界坐标系转换到观察坐标系 可以进行如下两个步骤实现转换 将世界坐标的参考原点由世界坐标系原点平移到相机坐标系原点 进行旋

引入空间角度的图像增强是非常直观且符合我们认知的，但是图像如何引入频率呢？ 在图像中频率可以看成是图像变换速率。频率越大图像强度（亮度/灰度）变换越快，因此有日常所说的高频信息和低频信息。 傅里叶变换傅里叶变换可以将空间上的信息转化为频率上的信息，也就是他可以捕获变化的剧烈程度。 连续变换及反变换公式： 可以得出离散形式的变换和反变换公式： 根据欧拉公式$e^{ix} = cos(x) +

定义系统中有若干个状态S1, S2, …, Sn. 随着时间推移，系统会从一个状态转移到另一个状态，马尔可夫模型认为后一个状态和前面若干个状态有关系。 例如天气和前面若干天的天气之间有关系，假如近两天天晴明天天晴的可能性就比较大。 形式化描述： 马尔可夫模型可以表示为一个五元组$\lambda = (S, O, A, B, \pi)$ 状态集合S: S = {S1, S2, S3} 描述了模

概念 节点： 运行链路层协议的设备，例如主机、路由器等 链路： 将信息传输到相邻节点的通信信道 链路层帧： 数据报封装在链路层帧中 链路层提供的服务有： 链路接入： 媒体访问控制（MAC）协议规定了帧在链路上的传输规则，还协调了多个节点共享当个链路时的问题。 可靠交付： 和TCP协议一样，这里的可靠交付也是通过差错检测和重发保证的。 差错检测 链路层的主题是在网络适配器中实现的，也叫网络接口