自学(4)：杂项
大二下学期的自学笔记，由图形学、CSAPP、随机过程、博弈论、微分几何、金融数学组成。
一、GAMES 101
1. 变换
- $\vec{a}\times \vec{b}=A*\vec{b}=\begin{bmatrix}0 & -a_z & a_y\\a_z & 0 & -a_x\\-a_y & a_x & 0\end{bmatrix}\vec{b}$，用于判断左右、内外
- 仿射坐标：点 $(x,y,z,1)$，向量 $(x,y,z,0)$
- 交比：直线上四点 $A,B,C,D$，$(A,B;C,D)=\frac{\vec{AC}/\vec{CB}}{\vec{AD}/\vec{DB}}$，射影变换前后保持不变
- 欧拉角：绕 $x,y,z$ 轴旋转 $\alpha,\beta,\gamma$ 角，$R=R_z(\gamma)R_y(\beta)R_x(\alpha)$
- 绕 $\vec{n}$ 轴旋转 $\alpha$ 角：$R(\vec{n},\alpha)=\cos\alpha I+(1-\cos\alpha)\vec{n}\vec{n}^T+\sin\alpha \begin{bmatrix}0 & -n_z & n_y\\n_z & 0 & -n_x\\-n_y & n_x & 0\end{bmatrix}$
- 视角变换：把摄像机移动到原点，$y$ 轴向上，看向 $-z$
- 正交投影：把长方体变换到 $[-1,1]^3$
- 透视投影：把视锥压缩成长方体再正交投影，前平面不变，后平面压缩且中心点不变
2. 几何
- 隐式表示：$f(x,y,z)=0$、几何体加减、距离函数（可用于插值）、水平集
- 显示表示：$(u,v)\to (x,y,z)$、点云、多边形网格
- 贝塞尔曲线：三阶 $b_0^3(t)=(1-t)^3 b_0+3(1-t)^2tb_1+3(1-t)t^2b_2+t^3b_3$，为保证 $\mathbb{C}^1$ 连续需连接点处平分控制点
- 贝塞尔曲面：16 个控制点，先沿 $u$ 求四条曲线，再对每个 $v$ 以四条曲线为控制点
- 曲面细分：Loop 细分（三角形加三个中点，一拆四）、Catmull-Clark 细分（加边中点、面中心）
- 曲面简化：边收缩，使用二次度量误差建优先队列，贪心收缩
- 曲线坐标：切线（方向变化快慢为曲率）、法线（切向量导数）、副法线（叉乘，方向变化快慢为挠率）
- 曲面第一基本形式：$I=E\mathrm{d}u^2+2F\mathrm{d}u\mathrm{d}v+G\mathrm{d}v^2,E=\vec{r_u}\cdot \vec{r_u},F=\vec{r_u}\cdot \vec{r_v},G=\vec{r_v}\cdot \vec{r_v}$，切向量 $\vec{r_u},\vec{r}_v$，法向量 $\vec{n}$
- 曲面第二基本形式：$II=L\mathrm{d}u^2+2M\mathrm{d}u\mathrm{d}v+N\mathrm{d}v^2,L=\vec{n}\cdot \vec{r_{uu}},M=\vec{n}\cdot \vec{r_{uv}},N=\vec{n}\cdot \vec{r_{vv}}$，$r_uv$ 为二阶导数
- 曲率：法曲率（沿切平面中某方向截曲面得平面曲线的曲率）$\kappa_n=\frac{II}{I}$，主曲率（法曲率最大最小值）$\kappa_1,\kappa_2$，平均曲率 $H=\frac{\kappa_1+\kappa_2}{2}$，高斯曲率 $K=\kappa_1\kappa_2$ 与曲面在 $\mathbb{R}^3$ 中的嵌入无关
- 双曲几何：直线为与单位圆正交的圆弧，平行线有无数条
3. 摄影
- 视场：传感器大小、焦距，等效焦距为 35mm 传感器时
- 曝光：光圈直径、快门时间、ISO 倍数
- 景深：对焦距离附近的清晰区间，焦距越长、光圈越大、对焦距离越近景深越浅
- 光场：前后平面共四维，同物体不同角度、同角度不同物体
- 光场相机：微透镜阵列，每一角度对应普通相机一张图，可后期调整焦距、光圈等
- 颜色：光谱与视锥细胞响应函数乘积，有同色异谱
- 加色系统：sRGB（用三纯色调出纯频率，再调出光谱）、XYZ（人为定义，Y 代表亮度）、HSV（色调、饱和度、明度）、Lab（亮度、绿红轴、蓝黄轴，互补色原理）
- 色彩空间：XYZ，固定 Y，$(x,y,z)=\frac{(X,Y,Z)}{X+Y+Z}$，$sRGB$ 为三角形
- 减色系统：CMYK（品红黄青黑，印刷用）
4. 光栅化
- 三角形：判断像素中心是否在内部，可用先模糊或多重采样（MSAA）反走样
- 反走样原理：采样等于时域上乘积等于频域上卷积（重复），高低频信号混叠，模糊等于低通滤波
- 深度缓冲：逐像素记录最近深度
- 着色模型：Blinn-Phong，环境光常数、漫反射（系数、平方反比、余弦）、高光（系数、平方反比、半程向量余弦幂）
- 着色频率：逐平面、平面内插值顶点着色、平面内插值顶点法线
- 插值方法：重心坐标（用三顶点坐标表示平面内点）、双线性（先 u 再 v，解决纹理过小）、Mipmap（预先计算指数级不同分辨率纹理，解决纹理过大），各向异性过滤（存长方形纹理）
- 渲染管线：几何 $\to$ 纹理 $\to$ 着色 $\to$ 变换 $\to$ 光栅化
- 高级纹理：环境光贴图、法线贴图、位移贴图
- 阴影贴图：从光源视角渲染深度图，像素在深度图中对应位置深度小于等于该值则有光照
5. 光线追踪
- 传统方法：从视角发射光线，每次与场景相交时计算着色和反射折射，着色递归相加
- 求交：$f(\vec{o}+t\vec{d})=0$，三角形先计算平面交点再判断内外或直接套公式
- 加速结构：轴对齐包围盒、均匀网格、空间切分（KD 树、层次包围体）
- 辐射度量学：立体角（单位球上的面积）、Irradiance（单位面积上接收的功率）、Radiance（单位面积单位立体角上接收的功率）
- 渲染方程：$L_o(p,\omega_o)=L_e(p,\omega_o)+\int_{\Omega^+} f_r(p,\omega_i,\omega_o)L_i(p,\omega_i)(\vec{n}\cdot \omega_i)\mathrm{d}\omega_i$
- 蒙特卡洛积分：$\int_a^b f(x)\mathrm{d}x\approx \frac{b-a}{N}\sum_{i=1}^N f(x_i)$
- 路径追踪：对不遮挡光源换元到光源上积分，对物体只取一根光线递归（以概率继续）
- 改进：双向路径追踪、Markov 链采样、次表面散射（不在原地出射）
- 微表面材质：法线分布函数、菲涅尔项（反射率，与入射角正相关）、微遮挡项
6. 动画
- 基本方法：关键帧插值、物理模拟（质量弹簧、有限元、质点系统、逆运动学）、动捕
- 质量弹簧系统：弹力、阻尼（相对速度在连线上的投影），可模拟布料（对角网格加跳连）
- ODE 求解：欧拉法 $x^{t+\delta t}=x^t+\dot{x}^t\delta t$，中点法 $x^{t+\delta t}=x^t+\dot{x}_{\mathrm{mid}}\delta t$，隐式欧拉法 $x^{t+\delta t}=x^t+\dot{x}^{t+\delta t}\delta t$（逆向优化求解），四阶 Runge-Kutta 法
- 流体模拟：质点位置基方法，分质点法（拉格朗日）、格点法（欧拉）、物质点法（混合）
二、CSAPP 后半部分
1. 链接
- 编译过程：.c $\to$ 预处理 $\to$ .i $\to$ 编译 $\to$ .s $\to$ 汇编 $\to$ .o $\to$ 链接 $\to$ .exe
- 可重定位目标文件 .o：代码 .text，数据 .rodata/.data/.bss（只读/已初始化/未初始化），符号表 .symtab，重定位表 .rel.text/.rel.data
- 库：静态库 .a（多个 .o 文件打包，链接时提取需要的 .o 文件）、动态库 .so/.dll（链接时记录库名和符号表，运行时加载）
- 链接过程：符号解析确定所需 .o 再合并，重定位引用地址
2. 异常控制流
- 异常：中断（异步 I/O）、陷阱（系统调用）、故障（可恢复错误）、终止（不可恢复错误）
- 进程：虚拟内存空间（代码、数据、栈）、寄存器、文件描述符表
- 信号：类似异常，接收后内核将控制流转移到信号处理程序再返回
3. 虚拟内存
- 正常流程：MMU 接收虚拟地址向内存中页表请求查询物理页号，再将物理页号和虚拟页偏移量组合成物理地址向内存请求访问
- 缺页：MMU 发现物理页号首位无效（地址指向初始磁盘位置），触发缺页异常将磁盘复制到内存，更新页表后重试访问
- 加速：TLB 页表缓存、多级页表、和高速缓存联用
4. 系统级 I/O
- 共享文件：描述符表进程独立，打开文件表和 v-node 表进程共享
- 打开同一文件两次：描述符表中两条，指向打开文件表中不同条，指向同一 v-node 表条
- 父子进程：复制描述符表，对应条指向同一打开文件表条，指向同一 v-node 表条
- 重定向：将描述符表条重新指向其他打开文件表条（可用于 stdin/out/err）
5. 网络编程
- 端口：客户端由内核自动分配临时端口，服务器为固定端口，服务器内核监听到端口请求后将控制流转移到对应程序
- URL：通用资源定位符，用于静态内容在服务器磁盘上查找
- CGI ：通用网关接口，用于动态内容传递运行参数，用？分隔文件名和参数，用&分隔参数
6. 并发编程
- 并发方式：进程式（遇请求后 fork）、事件式（遇请求后转移控制流）、多线程
- 线程：栈（同一虚拟内存空间的不同区间）、寄存器，共享虚拟内存空间、文件描述符
- 信号量：P（减一，阻塞直到非负）、V（加一，唤醒一个等待线程），用于互斥锁
- 死锁：等待永远不为真的条件，如 PV 顺序不一致导致的禁止区域左下角
三、随机过程
1. 离散时间 Markov 链
- 停时：事件发生与否仅和历史状态有关
- 周期：所有 $p^n(x,x)>0$ 的 $n$ 的最大公约数，1 为非周期
- 正常返：$P_x(T_x<\infty)=1,E_x(T_x)<\infty$，否则为零常返
- 平稳分布：$\pi_y=\frac{1}{E_y(T_y)}$，需要存在正常返状态（无限不一定）
- 细致平衡：$\pi_x p(x,y) = \pi_y p(y,x)$（两两平衡，强于平稳分布）
- 循环把戏：$\mu_x(y)=\sum_{n=0}^\infty P_x(X_n=y,T_x>n)$ 为平稳测度
- 双吸收态概率：$h(a)=1,h(b)=0,h(x)=\sum_y p(x,y)h(y)=P_x(T_a<T_b)$
- 吸收时间：$E_x(T_A)=1+\sum_{y\notin A} p(x,y)E_y(T_A)$
2. 连续时间 Markov 链
- 定义：$\forall 0\le s_0\lt \cdots\lt s_n\lt s,\forall i_0,\cdots,i_n,i,j,P(X_{t+s}=j|X_{s_0}=i_0,\cdots,X_{s_n}=i_n,X_s=i)=P(X_{t}=j|X_0=i)$
- 转移概率：$p_t(i,j)=P(X_t=j|X_0=i)$
- 转移速率：$q(i,j)=\lim_{t\to 0}\frac{p_t(i,j)}{t}$
- 转移速率矩阵：$Q(i,j)=\begin{cases}q(i,j) & i\neq j\\-\sum_{k\neq i} q(i,k) & i=j\end{cases}$
- Kolmogorov 方程：$p^\prime_t=Qp_t=p_tQ,p_t=e^{Qt}$
- 不可约：任意两状态可达，即 $\exists k_0=i,k_1,\cdots,k_n=j$ 使 $q(k_{l-1},k_l)>0$
- 平稳分布：$\forall t\geq 0,\pi p_t=\pi$，当且仅当 $\pi Q=0,\pi(j)=\lim_{t\to\infty} p_t(i,j)$
- 细致平衡：$\forall j\neq k,\pi(k)q(k,j)=\pi(j)q(j,k)$，强于平稳分布
- 嵌入链：记录原连续时间链跳转状态的离散时间链，每个状态停留一单位时间，转移概率为 $r(i,j)=\frac{q(i,j)}{\lambda_i},\lambda_i=\sum_{j\neq i} q(i,j)$
- 离出分布：令 $V_A=\min{t:X_t\in A}$，$h(i)=P_i(X_{V_A}=a)$，则 $h(a)=1,h(b)=0,b\in A-{a},h(i)=\sum_j r(i,j)h(j)$
- 首达时刻：停留时间加转移，$E_iV_A=\frac{1}{\lambda_i}+\sum_{j} r(i,j)E_jV_A$
3. 鞅
- Poisson 过程：事件发生间隔为指数分布
- 更新过程：Poisson 过程的推广，事件发生间隔为独立同分布的随机变量
- 鞅：$E[M_{n+1}|X_0,\cdots,X_n]=M_n$，上鞅 $\leq$
- 判定定理：$f(x,n)=\sum_y p(x,y)f(y,n+1)$，则 $f(X_n)$ 是鞅
- $M_{T\wedge n}=\begin{cases}M_n & n\leq T\\M_T & n>T\end{cases}$
- 连续时间：$\forall 0\leq s\leq t,E[M_t|\mathcal{F}_s]=M_s$，其中 $\mathcal{F}_s$ 是 $s$ 时刻之前不可数多个事件的集合
- 半鞅：$X_t=M_t+A_t$，$M_t$ 为局部鞅，$A_t$ 为有限变差过程
- 局部鞅：如三维 Brown 运动倒数为上鞅，但存在停时序列使其为鞅，非负局部鞅是上鞅
- 有限变差过程：$\sum_{i=1}^n |A_{t_i}-A_{t_{i-1}}|$ 对所有分割有界，可定义 Stieltjes 积分 $\int_0^t f(s)\mathrm{d}A_s$
- 二次变差：$\langle M,M\rangle_t=\lim_{|\pi|\to 0} \sum_{i=1}^n (M_{t_i}-M_{t_{i-1}})^2,\langle M,N\rangle_t=\frac{1}{2}(\langle M+N,M+N\rangle_t-\langle M,M\rangle_t-\langle N,N\rangle_t)$，有限变差为零
4. 随机积分
- 定义：$\int_0^t H_s\mathrm{d}X_s=\lim_{|\pi|\to 0} \sum_{i=1}^n H_{t_{i-1}}(X_{t_i}-X_{t_{i-1}})$
- 二次变差规则：$\langle\int_0^\cdot H_s\mathrm{d}M_s,\int_0^\cdot K_s\mathrm{d}N_s\rangle_t=\int_0^t H_sK_s\mathrm{d}\langle M,N\rangle_s$
- Itô 公式积分形式：$f(X_t)=f(X_0)+\int_0^t f^\prime(X_s)\mathrm{d}X_s+\frac{1}{2}\int_0^t f^{\prime\prime}(X_s)\mathrm{d}\langle X,X\rangle_s$
- Itô 公式微分形式：$\mathrm{d}f(X_t)=f^\prime(X_t)\mathrm{d}X_t+\frac{1}{2}f^{\prime\prime}(X_t)\mathrm{d}\langle X,X\rangle_t$
- Lévy 定理：Brown 运动为二次变差正好等于时间的连续局部鞅
- Dambis–Dubins–Schwarz 定理：任意连续局部鞅都可看作变速 Brown 运动
- 鞅表示定理：相对 Brown 运动滤过的局部鞅可表示为 Brown 运动的随机积分
- Girsanov 定理：改变路径权重可在无漂移 Brown 运动和有漂移 Brown 运动之间切换
5. 随机微分方程
- 微分形式：$\mathrm{d}X_t=f(t,X_t)\mathrm{d}t+g(t,X_t)\mathrm{d}B_t$
- 积分形式：$X_t=X_0+\int_0^t f(s,X_s)\mathrm{d}s+\int_0^t g(s,X_s)\mathrm{d}B_s$
- 齐次方程：$f,g$ 不显含 $t$，有 Markov 性
- Euler-Maruyama 方法：$X_{t+\delta t}=X_t+f(t,X_t)\delta t+g(t,X_t)\sqrt{\delta t}Z$，$Z\sim N(0,1)$
四、博弈论
- 核心：自身的策略要最大化对方的策略可能带来的最小收益
- 序贯行动博弈：博弈树逆向归纳求解
- 纳什均衡/鞍点：每个参与者的策略在给定其他参与者策略的情况下都是最优的
- 连续型策略：最优反应曲线（对方每一个纯策略的最优策略）的交点为纳什均衡
- 混合策略：最大化对方选择每一个纯策略所带来的最小期望收益
- 最大最小值定理：零和博弈两个混合策略线性规划互为对偶，最优值相等（对偶定理）
- 非常和博弈：纯策略或混合策略纳什均衡一定存在，但不一定是帕累托最优
- 囚徒困境解法：有限重复（会坍缩）、无限重复、冷酷策略、以牙还牙、惩罚、领导
五、微分几何
六、金融数学
自学(4)：杂项
https://sqzr2319.github.io/CSDIY/CSDIY-4/