群环模域

群是一个集合与一个运算符构成的结构，要满足四点： 闭合性，结合律，幺元，有逆元

半群： 闭合行，结合律

幺半群（monoid)：闭合性，结合律，幺元 阿贝尔群： 交换群，满足交换律

环

环就是在其上定义了两种二元运算”"，“+”， 关于"+"满足是阿贝尔群。 关于”*“是幺半群，即满足结合律，有幺元。 “+”，““两种运算还满足分配律。 环是一类包含两个二元运算 的代数系统。

域

域是在其上满足下列条件的环： “+"运算的幺元与”*“运算的幺元是不同的 域如果去掉了0元后关于"“运算不再仅仅是幺半群，而是一个群。 “*“满足交换律。

向量空间

给定域F，向量空间V记为F-向量空间。其二元运算：

向量加法：+ : V × V → V 记作 v + w, ∃ v, w ∈ V 标量乘法：·: F × V → V 记作 a v, ∃a ∈ F 且 v ∈ V 并且满足如下8条公理[10]： 向量加法结合律：u + (v + w) = (u + v) + w 向量加法的单位元：V存在零向量的0，∀ v ∈ V , v + 0 = v 向量加法的逆元素：∀v∈V, ∃w∈V，使得 v + w = 0 向量加法交换律：v + w = w + v 标量乘法与域乘法兼容性(compatibility): a(b v) = (ab)v 标量乘法有单位元: 1 v = v, 1指域F的乘法单位元 标量乘法对于向量加法满足分配律：a(v + w) = a v + a w 标量乘法对于域加法满足分配律: (a + b)v = a v + b v 另，若F是实数域ℝ，则V称为实数向量空间；若F是复数域ℂ，则V称为复数向量空间；若F是有限域，则V称为有限域向量空间。

模

一个域作用于另一个群，向量空间就是一种模。

小结

比如整数集，实数集，有理数集都是关于加法的阿贝尔群。 环是在群的基础上又加了一种二元运算，并且满足交换律。 域的条件比环更强，除了0元都可逆。 向量空间条件更加严格，是一个域域群的相互作用。

以上主要讲了群论中的一些概念，群论比较适合做一些定性和方向性的分析。

解决一个具体的算法问题，通常只会遇到群论的一些小结论。或者把大的研究对象看作群，得到一些大的数学原则。

旋转矩阵

  1. 矩阵与向量空间与线性空间之间并不能直接等同，虽然向量经常可以用矩阵形式表示。

  2. 反比例函数旋转可以得到一种特殊的双曲线（渐进性为y=x,y=-x); 这种旋转操作，可以用一个旋转矩阵表示。 $$ \left[ \begin{matrix} \cos (\theta) & - \sin (\theta)\
    \sin (\theta) & \cos (\theta)\
    \end{matrix} \right] $$

  3. 对于旋转操作而言，用复数形式来推导更合理，简单推导过程：

设复数为： cos(t) + i*sin(t)
旋转角度t，相当于乘以该复数; 设点（x，y）在复数坐标系中，旋转后：
[x + i*y][cost + i*sint] 
= cos(t)*x + i*y*cost +i*x*sint -y * sint
= [cos(t)*x - y *sin(t)] + i*[sin(t)*x+cos(t)*y]
设旋转后得到的点为(x‘，y’)所以有线性方程组
cos(t)*x - sin(t)*y = x'
sin(t)*x + cos(t)*y = y'
将系数表示为行矩阵形式，即可得到旋转向量

  1. 逆时针旋转45度的旋转向量为：

    $$

    \left[ \begin{matrix} \cos (\frac{\pi}{4}) & - \sin (\frac{\pi}{4})\
    \sin (\frac{\pi}{4}) & \cos (\frac{\pi}{4})\
    \end{matrix} \right] = \left[ \begin{matrix} \frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2}\
    \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{matrix} \right]

    \newline (x, y) 旋转后得到（x’,y’)\
    x’ = \frac{\sqrt{2}}{2} x -\frac{\sqrt{2}}{2} y\
    y’ = \frac{\sqrt{2}}{2} x +\frac{\sqrt{2}}{2} y \
    假设旋转满足： y’ = a/x’ 代入，则:\
    \frac{\sqrt{2}}{2}(x+y)=\frac{a}{\frac{\sqrt{2}}{2}(x-y)} \
    化简得 x^2 - y^2 = 2a 满足双曲线方程

    $$

单纯形法与最小二乘法

  1. 矩阵的秩，就是矩阵经过高斯变换化简为阶梯矩阵后，非零行的行数，代表了矩阵的维数。
  2. 向量的点乘，相当于投影，而矩阵的乘法本身，相当于向量在系数矩阵上的投影，向量与投影点之间的距离是最短距离
  3. 最小二乘法的英文表示是least squre method，直译过来应该是最小平方根法
  4. 理解向量最小二乘法的核心，在于把Ax=b中的A看成一组基，并由法向量与基垂直，得到$A^T * (Ax’-b)=0$
  5. 向量的最小二乘法，与统计线性拟合是同样的问题，并且可以推广到多项式拟合。拟合也可以称之为插值，英文是Interpolation
  6. 线性规划中的单纯形法不是最小二乘法，两者有区别。线性规划是一种优化算法，英文是optimization。
  7. 单纯形法中重要的是迭代过程，域牛顿迭代法求多项式方程的根有相似之处，与gcd迭代求最大公约数也有相似之处。
  8. 线性规划中用的非常普遍的是单纯形法，提出一种迭代方法，可以通过代数方法遍历解可行域的顶点，得到最优解。
  9. 单纯形法的核心方法是引入更多的自由变量，并通过换基来遍历顶点，单纯形法有解的前提是最优解在顶点处取得。

image-20220913102206024

傅里叶变换

傅立叶变换，源头是傅立叶级数展开； 是一种基于微分和正弦函数的展开，非常适合于信号处理。

傅里叶变换也可以用于计算大数乘法，比多项式乘法效率更高。

蒙特卡洛算法

蒙特卡洛算法是一类算法的总称，基本原理是通过随机过程，对结果进行随机选取并打分，通过反复迭代，得到较优解。

其核心也在于迭代方式，每次迭代使用的是在一定取值空间内的随机值。

图算法与加解密

现代计算机领域最核心的算法，如分治法，fft，单纯形，图算法，压缩算法，加解密算法等；

构成了计算机领域计算，存储，网络等功能的基础，算法的种类还是很多的。

大的算法分类可以参考wiki百科：https://en.wikipedia.org/wiki/List_of_algorithms