liuqinh2s' blog

公司安排了一次新人技术分享，我分享的主题是：自制 json 解析器

图灵机

图灵机（Turing Machine）是 英国数学家艾伦·图灵 在 1936 年发表的 "On Computable Numbers, with an Application to the Entscheidungsproblem"（《论可计算数及其在判定性问题上的应用》）中提出的数学模型。在文章中图灵描述了它是什么，并且证明了，只要图灵机可以被实现，就可以用来解决任何可计算问题。

历史

• 妈咪说：图灵
• 模仿游戏

冯·诺依曼结构

冯·诺伊曼结构与 存储程序型计算机 是互相通用的名词

哈佛结构 是一种将程序数据与普通数据分开存储的设计概念，可以说是冯·诺依曼结构的一种。

存储程序计算机在体系结构上主要特点有：

• 以运算单元为中心
• 采用存储程序原理
• 存储器是按地址访问、线性编址的空间
• 控制流由指令流产生
• 指令由 操作码 和 地址码 组成
• 数据以二进制编码

五个组成部分：

• 存储器
• 控制器
• 运算器（算术逻辑单元）
• 输入
• 输出

文本文件中，为了让比特表示文字，我们发明了字符集，让特定的比特序列对应特定的字符。

常见的字符集有：

• ASCII
• EASCII
• GB2312
• GBK
• Unicode
• UTF-8 （严格来说 UTF-8 只是 Unicode 的一种编码方式）
• ANSI 编码

信息的本质

信息的本质是消除不确定性：我们抛掷一枚硬币，然后用手盖住，出现正面朝上和反面朝上的概率都是二分之一。当我们偷看了结果，确定了是正面还是反面朝上，也就获得了信息。在这个例子中，我们消除的不确定性是一个二分之一的概率。在 香农 划时代的论文 通信的数学原理 中，首次提出了信息是可量化的，以及如何量化信息。我们以 bit 为信息的度量单位，一个 bit 可以是 0 或者 1，我们每获得一个 bit 的信息，就会消除一个二分之一的不确定性。

小思考题：如果我们抛掷的是一个骰子呢，当我们确定了一次投掷结果，我们获得多少信息（用 bit 为单位衡量）？
我们都知道，骰子有 6 个面，分别刻有 1~6，我们有六分之一的概率得到其中任意一个面朝上。那么我们获得的信息应该是： ${\log }_{2}6$ 。