“当按下电源后，x86 CPU 的 OS 是如何被启动的？”

x86 CPU 的 OS 启动流程

当 x86 CPU 电源联通后，它的 EIP (The Instruction Pointer) 被硬编码到地址 0xFFFFFFF0，即内存的最后 16 位。这时 CPU 是处于实模式 (Real Mode) 的，所以相当于从 0xFFFFFFF0 开始 CPU 可以执行一条命令。 实模式 (Real Mode) 和 保护模式 (Protected Mode) 是 CPU 的两种工作模式，实模式是早期 CPU 的工作模式，保护模式是现代 CPU 的工作模式。实模式出现在 8086 CPU 时代，运行的是 16 位指令。但 16 位 CPU 最多支持 1MB 的寻址（20 根地址线），所以后来内存越来越大后寄存器的位数就变成了 32 位。所以就引入了保护模式， 用来实现更大空间的，更…

Jul 22, 2020 ≈ 7 mins

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

Make your own memory allocator

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

Jul 18, 2020 ≈ 21 mins

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

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

Jun 28, 2020 ≈ 5 mins

“子图同构问题 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 个点可以…

Jun 27, 2020 ≈ 4 mins

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

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

Jun 26, 2020 ≈ 7 mins

“顶点覆盖问题 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 的正确性。显然这…

Jun 25, 2020 ≈ 7 mins

“分团问题 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 的正确性。显然该验证步骤是可以在多项式时间内完成的，所以分…

Jun 24, 2020 ≈ 6 mins

“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 与…

Jun 23, 2020 ≈ 5 mins

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

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

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

Jun 21, 2020 ≈ 7 mins

“证明 $$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 一定是也是某一个图灵机的…

Jun 21, 2020 ≈ 3 mins

Posts

Words

Tags

Portfolio

Viewers

FEATURED TAGS
普通の記事 remembered day summary raspberry 男默女泪 reproduce leetcode java algorithm C&C++ python CV jekyll Github 🔒 tensorflow deep learning js swift games CVE CS 🔧 Unity math tcs OS
ABOUT ME
avatar

“Only my Railgun”

FRIENDS
Blog Update Record