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 ...
数学分析 A3 备忘录
备忘录是考试导向的，由于大部分内容都很简单但是需要记忆的结论比较琐碎所以几乎不会有证明，并且很多内容会用感性语言而不是数学语言叙述，毕竟你是为了拿分不是为了学习。
本文适用人群应当满足如下条件：整个学期没听课也没学习，并且只有预留了几个小时的复习时间
对应到的教材是史济怀的数学分析教程 14-18 章节，对应肥科数学分析 A3 课程。
[TOC]
1.无穷级数问题正项级数比较判别法及其常见形式：极限形式和比值形式（导出的等价量判别法）
比较判别法的推论：
Cauchy 根值判别法（单项开根上极限）
d’Alembert 判别法（前后项比值）
Raabe 判别法（处理 d’Alembert 比值趋近 1 的情况）
Bertrand判别法（处理 Raabe 比值趋近于 1 的情况）
Gause 判别法（综合以上三种判别法）
一般项级数引入绝对收敛的概念（这是自然的）
Leibniz 判别法（交错级数单项收敛于 0）
乘积 Dirichlet 判别法（Abel 变换的推论，其中某项单调收敛到 0，另一侧部分和有界）
乘积 Abel 判别法（Abel 变换的推论，其中某项单调有界，另一 ...
Hackergame 2023 游记
开赛第四天看到 qq 空间转发抽奖才知道有这个比赛，没有任何基础和经验上场被薄纱，好几个有思路的题做不出来太遗憾了。这比赛真挺好玩的，玩得很开心，明年还来。
自己只会做简单题，接下来陆陆续续写一些复盘发上来。想看比较有价值内容的可以直接跳到第二部分。
比赛网站 hack.lug.ustc.edu.cn 会持续开放几个月的时间。
参赛题解虽然写成题解都挺简单只有一两行，但实际做着还是有点折磨在的
Hackergame 启动很简单的修改 URL 的事情。
猫咪小测第一问：科大图书馆网站第二问：直接在 arxiv 上面搜就能搜到第三问：问一问 ChatGPT 就知道了，很直接的问题第四问：具体过程忘记了，反正也是一连串的搜索引擎使用，先找到论文本身，再从论文搜到会议
深邃黑暗直接读 HTML 源代码即可。
旅行照片第 1/2 问：东大诺贝尔奖得主最年轻的是梶田隆章，通过拉面馆合照中的 STATPHYS28 得知日期。
博物馆直接找错了，我看题目里面“学校里面的博物馆”，自然认为是东大本乡总合研究博物馆，没想到是对面的东京都国立博物馆…这个真的算是在学校里面吗？
虫从题目描述中知道是无线电图 ...
一道出现在线代课后习题的组合矩阵论入门题
题目出处：王新茂《线性代数讲义》 第二章第四节习题16由于王老师的讲义版本更新极快，这里放上本文参考的的版本是 2023-4-23版本 （讲义和源码都是开源的，因此我在个人网站内存了一份）最新版本的pdf和源代码均可以在王老师的个人主页上找到（需接入USTC校园网）。
题目先给出几个定义：
对于任意 , 若存在置换方阵 使得 , 其中 都是阶数 的方阵, 则 称为可约的, 否则 称为不可约的.
若 的元素都 , 则 称为非负矩阵.
对于非负矩阵 , 若存在正整数 使得 的元素都 , 则 称为本原的, 否则 称为非本原的.
设 是非负矩阵. 证明:
是不可约的 存在正整数 使得 的元素都是正实数 存在正实数 使得 的元素都是正实数.
存在置换方阵 使得 是准上三角方阵, 其中每个准对角块都是不可约方阵.
若 是本原的, 则 是不可约的.
若 是非本原且不可约的, 则存在正整数 和置换方阵 , 使得
P^T A P=\left(\begin{array}{cccc}
O & A_1 & & \\
& O & \ddots & \\
...
对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 ...
讨论几道有趣的定积分上手题
讨论几道有趣的定积分上手题2/18
马上要开学期末考，做几个有趣的题练练手. 这几天凉宫春日看的很开心, 好久没看到这种作品了, 于是一改之前用来自深渊头图的习惯. 试用 Zhihu on VSCode 感觉很爽.
设 在区间 上二阶可微，且 ，对正整数 定义
B_n= \int_0^1 f(x) \mathrm dx - \frac 1n \sum\limits_{k=1}^n f(\frac{2k - 1}{2n})证明
这一道题来自数学分析习题课讲义，意在证明对积分区间 等分数值积分，取区间中点估计的情况下误差项的级别是 。而这一题的前导问题则证明了取区间断点估计的情况下误差级别是 ，使用同样的方法我们可以证明本题。
解法 1 :
B_n =\sum\limits _{k = 1} ^n \int_{\frac{k - 1}n}^{\frac kn} f(x) - f(\frac{2k-1}{2n}) \mathrm dx于是乎我们先考虑证明一个引理：
\begin{aligned}
\int_{a}^{b} \left(f(x) - f(\frac{a ...
分析原理 - 基础拓扑题选
分析原理 - 基础拓扑题选摆烂太久了于是昨天久违地读了点闲书
前面省略了一点基本定理, 基本是在做题, 有错误欢迎指正
感觉 远不如 好使 但是后者不方便传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}这就导出了矛盾
需要注意的是在任意度量空间中, 与 是等价的, 这一点将在后 ...