“编写你自己的内存分配器”

Make your own memory allocator

在这篇文章中我将带着大家实现一个自己的内存分配器。这个内存分配器 十分简单 ,它旨用于帮助大家对操作系统内部的内存分配过程有更深的理解。所以它并不会很高效。简单的说,这个内存分配器 只是能用 ( Just works )。 我们主要会使用 C 语言来进行编程。但在编程前,我们首先要对我们操作系统的内存存储方式有一定的了解。 操作系统的内存存储 我们的操作系统的内存中,主要存在着 5 个部分。这 5 个部分分别是: kernel: 存储着我们的操作系统的…

“反馈边问题 NP-Complete 证明”

反馈边 (Feedback Arc Set)问题的描述如下。给定一个有向图 G ,问是否可以移除小于等于 k 条边使得 G 中没有循环。首先这个问题显然是 NP 问题。即给定移除的 k 条边,我只需要先把这 k 条边移除,然后判断剩下的图中是否有循环就可以了。判断循环的方法为从一个点出发,记录经过的点,判断当前点是否已经走过,若走过即存在循环。而这个操作是显然可以在多项式时间内完成的。 现在,我们把顶点覆盖问题归约到反馈边问题来证明反馈边问题是 NP 难的…

“子图同构问题 NP-Complete 证明”

子图同构(Subgraph isomorphism problem)问题的描述如下。给定两个图 G_1 G_2 ,判断 G_1 是否与 G_2 的一个子图同构。首先假如我们得到了 G_1 G_2 和对应的解(即 G_2 的子图 G_s 使得 G_s G_1 同构),我们只需要遍历解中的点和每一个与这个点相连接的边,检查是否与 G_1 对应即可验证解的正确性。所以这个问题首先显然是一个 NP 问题。 为了证明这个问题同时也是一个 NP 难问题,我们将 分团问题 规约到 子图同构问题上来。具体地,假设我们现在有一个有解的分团问题 % <![CDATA[ <G,k> %]]> ,即 G 中存在 k 个点可以…

“3 色问题的 NP-Complete 证明”

3 色问题 (3-Color) 的描述如下:给定一个图 G ,为 G 中每一个顶点涂色,要求每两个相邻的顶点颜色不一致。问是否可以用 3 种颜色完成上面的要求。 首先我们证明这个问题是 NP 问题。显然,若给定一个解,我们只需要遍历每一个节点,检查其与其相临节点的颜色是否一致,即可判断解是否正确。这个操作显然是可以在多项式时间内完成的,所以 3 色问题是 NP 问题。 接下来我们通过将 SAT 转换到 3 色问题来证明 3 色问题是 NP 难问题。即任意给定一个 SAT ,我可以…

“顶点覆盖问题 NP-Complete 证明”

顶点覆盖问题(Vertex Cover)的描述如下:给定 % <![CDATA[ <G,k> %]]> ,其中 G 是一个无向图,问图中是否存在点集 V % <![CDATA[ \lvert V \rvert <= k %]]> , 使得 V 中的每一个顶点覆盖 G 中所有的边。即 G 中每一条边的起点或终点都为 V 中的一个点。以下图为例, % <![CDATA[ <A,B> %]]> 就是一个符合条件的点集,因为图中的 4 条边,每一条边都连接了 % <![CDATA[ <A,B> %]]> 中至少一个点。 为了证明其 NP 完全,我们首先还是证明其是 NP 问题。给定一个 G 和一个 V ,我们只需要遍历 G 中的每一个边,检查其是否与 V 中一个点相连,即可判定 V 的正确性。显然这…

“分团问题 NP-Complete 证明”

分团问题(Clique Problem) 的描述如下:给定 % <![CDATA[ <G, k> %]]> ,其中 G 是一个无向图,问图中是否存在点集 V 组成一个团,且 % <![CDATA[ \lvert V \rvert <= k %]]> 。即 V 中的点相互连接?以下图为例。 % <![CDATA[ <B,C,D,E> %]]> 就是符合条件的一个点集,因为这四个点相互连接,即可以构成一个团。 首先我们为了真证明其 NP 完全,我们还是要先证明其是一个 NP 问题。若给定一个点集 V ,其中 % <![CDATA[ \lvert V \rvert <= k %]]> 。那么我只需要检查每一个 V 中的点是否与其他点相连,即可验证 V 的正确性。显然该验证步骤是可以在多项式时间内完成的,所以分

“3-SAT NP-Complete 证明”

阅读本篇需要先理解 SAT 问题是 NP 完全的,其主要由 Cook–Levin theorem 证明。有很多非常优秀的资源都对 SAT 的 NP 完全性作了证明,但这里就先省略掉了,还请读者自己参考。以后有时间的话我会补一个我理解的 SAT 证明问题。 3-SAT (3-CNF-SAT)的描述为:判断是否存在一个布尔表达式 C = C_1 \cap C_2 \cap \cdots \cap C_n ,其中 C_i = x_a \cup x_b \cup x_c ,使得 C = 1 。即判断是否存在布尔表达式 C = (x_a^1 \cup x_b^1 \cup x_c^1) \cap (x_a^2 \cup x_b^2 \cup x_c^2) \cap \cdots \cap (x_a^n \cup x_b^n \cup x_c^n) 为真。 为了证明 3-SAT 的 NP 完全性,我们需要 1) 证明它是 NP 问题。 2)证明它 NP 难(NP-Hard)。 3-SAT 与…

“$$L_u$$ 问题不可判定性的证明”

将 $$L_d$$ 归约到 $$L_u$$

现在我们已经知道了 L_d 问题是不可判定的了,那么我们应该如何使用类似 L_d 这样的我们已经知道是不可判定了的问题呢?答案是:我们通过他们来证明更多问题的不可判定性。在这个过程中我们要使用一种叫做归约 (Reduce) 的方法。 规约简单的说,就是一个偷懒的过程,一个化简问题的过程。例如你已经知道了如何计算一个圆的面积,那如何来计算两个圆的面积呢?答案是将「计算两个圆的面积」这个我们未知的、高难度的问题化简到「做两…

“证明 $$L_d$$ 的不可判定性”

图灵机的可判定性问题

L_d 问题是一个非常基本的不可判定问题,我们可以非常方便得将 L_d 问题规约到其他问题来证明其他问题的不可判定性。 L_d 的一般数学表达为:给定一个语言 L_d 满足: L_d=\{w_i \mid w_i \in L(TM_i)\} 判断 L_d 是否可决定 (decidable)。 w_i TM_i 分别指第 i 个字符串和第 i 个图灵机。换一句话说,判定一个图灵机是否可以停机接受它自己的编码。 为了证明 L_d 的不可判定性,我们这样思考: 我们假设 L_d 是可判定的,由于 L_d 一定是一个定义在 \{0, 1\} 上的语言,所以 L_d 一定是也是某一个图灵机的…

“矩阵求导”

分母布局

矩阵求导(Matrix Derivative)也称作矩阵微分(Matrix Differential),在机器学习、图像处理、最优化等领域的公式推导中经常用到。矩阵求导实际上是多元变量的微积分问题,只是应用在矩阵空间上而已,即为标量求导的一个推广,他的定义为将自变量中的每一个数与因变量中的每一个数求导。 具体地,假设存在 A_{m \times n} B_{p \times q} ,则 \frac{\partial A}{\partial B} 会将 A 中的每一个值对 B 中的每一个值求导,最后一共会得到 m \times n \times p \times q 个导数值。这么多的导数值,最后是排布成一个 m \times (n \times p \times q) 的矩阵…