Keep Coding

本文是我学习在 Coursera 上北京大学开设的程序设计与算法专项课程的相关笔记。

Coursera 链接:https://www.coursera.org/specializations/biancheng-suanfa

你也可以在国内的网站上找到这套课程的相关资料:

比如哔哩哔哩:程序设计与算法

感谢 Coursera 提供的奖学金!

从数学危机到图灵机

第一次数学危机(公元前500年)

毕达哥拉斯学派:数是万物的本原、一切数均可表成整数与整数之比。–> 西帕索斯悖论

危机的缓解:欧多克索斯建立完整的比例论,避开无理数。

第二次数学危机

微积分:牛顿和莱布尼茨各自独立发现了微积分,两人的理论都建立在无穷小分析之上。–> 贝克莱悖论

危机的缓解:十九世纪七十年代实数理论

第三次数学危机

集合论:十九世纪下半叶,康托尔创立。从自然数与康托尔集合论出发可建立起整个数学大厦 –> 罗素悖论

1931年歌德尔不完备性定理结束关于数学基础的争论

图灵与图灵机

图灵(Alan Mathison Turing)(1912——1954)

英国数学家、逻辑学家,1936年提出图灵机。

图灵机的基本构成

构成

如何工作

  1. 准备
    1. 存储带上符号初始化
    2. 控制器设置好自身当前状态
    3. 控制器置于起始位置
    4. 准备好工作程序
  2. 反复执行以下工作直到停机
    1. 读写头读入
    2. 根据 自身状态 和 所读到的字符,找到对应程序语句
    3. 根据程序语句,做三个动作
      1. 写入相应字母/数字
      2. 变更自身至新状态
      3. 读写头左移或右移

图灵机的运行机理

图灵机特性:简单、强大、可实现

停机

“停机”表示计算完毕,表示当前存储带上保留的,是计算结果。

也就是说:

对于一个问题输入 A,问:

A 能否 推证出 B?

如果能找到一个图灵机,得出对应符号序列 B,那么从 A 到 B 就是可计算的,否则问题不可计算。

图灵机的意义

数的二进制表示

计数符号:0,1

基数:2

$10010=12^4+02^3+12^2+02^0$

十进制 转换为 二进制

除以二取余(取整)

将123转换为二进制:

$123/2=61……1$

$61/2=30……1$

$30/2=15……0$

$15/2=7……1$

$7/2=3……1$

$3/2=1……1$

$1/2=0……1$

123的二进制就是:1111011

二进制 转换为 八进制、十六进制

从二进制 到 八进制

从右向左,每三位进行一次转换,即从二进制数的值转换成等值的八进制数字

1111011–> 173

从 二进制 到 十六进制

从右向左,每四位进行一次转换,即从二进制数的值转换成等值的十六进制数字

1111011 –> 7B

二进制数的布尔运算

计算机中数的逻辑运算方法

英国数学家布尔(G.Boole),1854年创立布尔代数

与、或、非,异或、同或

计算方法

半加器 –> 串联 –> 全加器