2-Spin System Quick Notes
SettingConfiguration : A configuration of graph is a map such as:
\begin{aligned}
\sigma: V &\to 2^V\\
u&\mapsto \{+,-\}
\end{aligned}Partition Function: For graph , define its partition function as
Z_G(\beta, \gamma, \lambda) = \sum_{\sigma} \beta^{m_{++}}\gamma^{m_{--}}\lambda^{n_+}where is the number of edges between two vertices pinned to , is the number of vertices pinned to , and we sum over all possible configurations.
Initially, we wonder when there exsits a polynomial time ...
数理逻辑速通笔记
命题演算系统谓词演算系统
浅谈 SAT 问题与 SAT-Solver
通过 Hackergame 比赛滑水知道了有 SAT-Solver 这个东西（其实是先知道了 SMT-Solver 然后再知道了 SAT-Solver），遂花了点时间去研究了一下。
这篇文章的前半部分是 SAT 相关的一些常识的回顾，后半部分开始介绍求解一般 SAT 问题的算法。
笔者计划在24春系统学习形式化方法入门内容，在那之后会进一步整理更多内容。
SAT 备件简述SAT 问题与 CNF 格式SAT 问题即可满足性问题 (Satisfiability Problem)：一般被定义为布尔可满足行问题或命题可满足性问题，即：
布尔可满足性问题 (Boolean Satisfiability Problem) ：给定布尔表达式 (由 AND, OR, NOT, 变量, 和括号构成), 是否存在对变量 TRUE 或 FALSE 的赋值, 使得整个表达式真。例如
(x + y\neg z)(x + y + z)(\neg y + \neg z)
以及：
命题可满足性问题 (Propositional satisfiability problem) :给定命题逻辑公式, 命题是否可满 ...
Dancing Links X 算法学习笔记
在 Hackergame 赛后自己去补了点基础，现在写一点 Dancing Links X 算法的学习笔记
算法原理算法原理参见 Dancing Links - OI Wiki 。
这个算法的原理已经在各种文章中被重述了 114514 次，我并没有信心讲得比他们好，不过还是简要描述一下。
代码实现代码内包含大量注释（代码基本就是 OI Wiki 的）
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485struct DLX { static const int MAXSIZE = 1e5 + 10; int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10]; int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZ ...
对Stone-Weierstrass定理的简单讨论
对Stone-Weierstrass定理的简单讨论Weierstrass逼近
如果 是 上的一个连续实函数，那么便有实多项式 的序列使得
\lim\limits_{n\to \infty} P_n(x) = f(x)在 上一致地成立，对于连续复函数也可以用复多项式逼近
这是 最早发现的逼近定理的形式。
证明 : 不失一般性地假定 并且假设 ，否则令
g(x) = f(x) - f(0) - x[f(1)-f(0)]\quad (0\le x\le 1)我们再补充定义 在 以外地区间上取 那么该函数在实轴上一致连续。
取
Q_n(x) = \frac{(1-x^2)^n}{\int_{-1}^1 (1 - x^2)^n \,\mathrm{d}x}现在令
P_n(x) = \int_{0}^1 f(t) Q_n(t-x) \,\mathrm{d}t注意到这样构造出来的 是关于 多项式。虽然这是一个显然的结论，但是对卷积不熟悉的人可能会产生一定的困惑，所以这里详细展开一下：事实上注意到 是变量，所以把 写成关于 的多项式：
\begin{alig ...
分析原理 - 基础拓扑题选
分析原理 - 基础拓扑题选摆烂太久了于是昨天久违地读了点闲书
前面省略了一点基本定理, 基本是在做题, 有错误欢迎指正
感觉 远不如 好使 但是后者不方便传b乎
对于 证明以下三个条件是等价的
是有界闭集
是紧集
的任意无限子集在 内有极限点
由定理 紧集的闭子集是紧的 以及 方格是紧集 直接得出
若 在 内无极限点, 则 存在 使之含有至多一个 中的点
于是 是一个 的覆盖, 然而其任意子覆盖不是有限的, 这与紧性矛盾
若不有界则可取一列 , 满足 此时显然 在 内无极限点
若不是闭集设 是 的一个极限点但 则取一列 满足
则由假设 存在一个不同与 的极限点 , 则除去有限个 有
\begin{aligned}
|x_n - y| &\ge |y - x _0| - |x_n - x_0|\\
&\ge |x_0 - y| - \frac 1n \\
&\ge \frac 12 |x_0 - y|
\end{aligned}这就导出了矛盾
需要注意的是在任意度量空间中, 与 是等价的, 这一点将在后 ...
子群格基本算法
子群格基本算法子群格与子群层级
定义 一个群的子群格是由其所有子群和子群间的包含关系构成的二元组
实际上就是子群所构成的偏序集
定义 子群格中的元素地层数 定义为子群阶数中素因子指数的和
于是我们自然地想到，可以按照层数以此构造出一个群的全体子群
循环扩张基础算法 是一个 层的子群的一个充分不必要条件是存在一个 层子群 和一个元素 使得
使用这种方法我们可以从由一层的子群构造出下一层的子群（注意到这个方法并不永远能构造出全部的子群，在一个群没有完全子群的情况下这是可以的）
接下来遇到的一个问题是，如何保证加入第 层的子群与之前的子群不重合呢？
事实上会发生重合的情况只有以下两种
是第 层子群中的元素
是已经加入第 层的子群中的元素
于是我们给出一个简单的算法
算法 1
12345678910111213for U_{i-1} in the layer[i-1]: Gamma := G - U_{i-1} for W in the layer[i]: if U_{i-1} is contained in W: Gamma -= W whi ...
随便聊聊(2) - 有限群结构简单结论 续
随便聊聊(2) - 有限群结构简单结论 续10/6
近日试图整理本人平日里自学抽象代数时的一点浅薄的思考（因而并不是知识体系的全面总结），大多是一些令我惊叹的题目和证明，但也不乏大量琐碎的小结论。
上篇文章中结论过于浅显小清新，这一篇中会有大量内容是 抄书/习题。另一方面感觉把每个小结论拆开来整理不是很好，这次稍微调整一下笔记结构。
写笔记于我而言无非是一种督促我自己读书的手段，也只有在这个过程中我会静下心阅读各种各样的资料，拿起笔喝着咖啡悠闲地推推公式。发布笔记对我学习带来的正反馈作用无疑是远远高于写作业考试拿学分的，这个过程确实让我感觉痛并快乐着，而不是只有被内卷的气氛裹挟的反胃。
文章在发布后也会不定期往里面添加内容。
有限群结构相关小结论
是有限 群，其中心 包含任何一个 阶正规子群
这里并不直接证明这个结论，而是分别给出其两个方向上的推论及证明。其中第一个给出了 群的重要性质，另一个则给出了对同态核与自同构群的精妙运用。
是有限 群，其中心 与任意正规子群有非平凡交（这给出中心本身非平凡）
考虑正规子群 ，考虑使 通过共轭作用作用在其上，其作用 ...
随便聊聊(1) - 有限群结构简单结论
随便聊聊(1) - 有限群结构简单结论近日试图整理本人平日里自学抽象代数时的一点浅薄的思考（因而并不是知识体系的全面总结），大多是一些令我惊叹的题目和证明，但也不乏大量琐碎的小结论。
文章在发布后也会不定期往里面添加内容。
有限群结构相关小结论本文是关于有限群结构的简单结论。
若，则中存在二阶元
考虑 中的不动点数量其必然为偶数（因变换中轨道大小为），由单位元存在可得二阶元存在。
若满足，则
由陪集性质，注意到左陪集与右陪集相等
若，则中有大小为的正规子群
由 得，G中二阶元存在，随后考虑给出的群的置换表示（注意到在这样的置换表示中，不可能存在一阶轮换，除非该元素为单位元）， 的置换表示完全由 个 轮换组成。因而是一个奇置换，由奇偶置换的基本性质得知， 由奇偶置换各半组成，取出其中所有偶置换得到一个正规子群。(这给出一个简单的推论：这样阶数的单群不存在)
若，且 中存在 阶元 ，则 中一切奇数阶元构成正规子群
显然对 使用数学归纳法。考虑证明考虑证明 就是一个奇置换。
事实上 给出的置换群具有很强的性质， 阶元素的置换表示为 个 轮换 ...