Coursera课程笔记----计算导论与C语言基础----Week 1

时间:2023-12-09 18:40:31

计算机的基本原理(Week 1)

第一次数学危机

公元前500年,毕达哥拉斯学派,他们相信数是万物的本源:一切数均可表示成整数或者整数之比

然而毕达哥拉斯证明了勾股定理,某些直角三角形的三边比不能用整数表达

希帕索斯悖论:边长为1的正方形,对角线?

危机的缓解:比例论,使用几何方法避开无理数

危机的解决:实数理论的建立

第二次数学危机

微积分:牛顿和莱布尼兹,建立在**无穷小****分析之上

贝克莱悖论:无穷小一会儿是0,一会儿不是0,像一个幽灵~

危机的缓解:重建实数理论

新的问题:魏尔斯特拉斯给出了一个处处不可微的连续函数➡直观&几何思考不可靠

第三次数学危机

集合论:康托尔建立,一切数学成果可建立在集合论基础上

罗素悖论:S由一切不是自身元素的集合所组成,S是否属于S?

哥德尔不完备性定理:把数学彻底形式化的愿望是不可实现的

问题:如何判断问题可计算or不可计算?

解决思路:为计算建立一个数学模型(计算模型),它能够完成的就是可计算的——图灵机

图灵与图灵机

1936年,《论可计算数在判定问题中的应用》提出了理想的计算机数学模型——图灵机(Turing Machine)

图灵机的构成

一条存储带:其上有一个个小方格,可存储一个数字or字母

一个控制器:包含一个读写头(读or写or改),可接受程序语句,可存储&改变自身状态,可沿着存储带移动

图灵机如何工作

准备:存储带初始化、控制器置于起始并设置好自身状态、准备好程序

执行过程:读字母or数字、根据状态字符找到对应的程序语句、执行三个动作(写入字母or数字、变更自身状态、左右移)

停机:表示计算完毕,存储带上即为计算结果

图灵机的理论意义

特点:简单,强大,可实现

意义:可实现的通用计算模型,引入了通过读写符号状态改变进行运算的思想,证实了基于简单字母表完成复杂运算的能力,引入了存储区程序控制器等概念的原型

计算机为什么能计算

计算机中数的表示——二进制

十进制转为二进制:除以二的商取余数,”触底反弹“

二进制转为八进制和十六进制:卡3位/4位

计算机中数的计算——布尔运算

基本逻辑运算:与、或、非

复合逻辑运算:同或、异或等

二进制加法:本位是异或运算,进位是与运算——半加器

半加器进行组合,一个半加器的输出作为另一个半加器的输入——全加器

布尔运算的实现——电路

结论——电路能够实现计算