计算导论


计算导论

第一次数学危机

  • 毕达哥拉斯学派(公元前500年)
    • 数是万物本原,事物的性质是由某种数量关系决定的,万物按照一定数量的比例构成和谐的秩序
    • 一切数均可以表示成整数或整数比
    • 毕达哥拉斯证明了勾股定理,同时发现直角三角形的三边比不能用整数表达。他的学生,希帕索斯考虑了一个问题:边长为1的正方形其对角线长度是多少?无理数的出现挑战了人们的信仰,希帕索斯被处死。
  • 两百年后欧多克索斯建立了一套完整的比例论,巧妙的避开了无理数,缓解了数学危机,推动了几何学的发展
  • 19世纪下半叶,实数理论正式确立后猜得到解决。

第二次数学危机

  • 17世纪,牛顿和莱布尼茨各自独立发现了微积分,但两人理论都是建立在无穷小的分析之上。贝克莱提出质疑,无穷小有时为0,有时又不为0。是怎么回事。
  • 19世纪实数理论的提出,引出极限理论
  • 19世纪下半叶,康托尔创立了著名的集合论
  • 伯特兰罗素,讲了一个故事,质疑了集合论:

塞尔维亚有一位理发师:他只给所有不给自己理发的人理发,不给那些给自己理发的人理发。问:他要不要给自己理发?

  • 罗素悖论:s由一切不是自身元素的集合所组成,罗素问:s是否属于s呢?。证明集合论存在问题。
  • 1931年哥德尔不完备性定理:

任何一个数学系统,只要它是从有限的公理和基本概念中推导出来的,并且从中能推证出自然数系统,就可以在其中找到一个命题,对于它我们既没办法证明,也没办法推翻

哥德尔不完全定理的证明结束了关于数学基础的争论,宣告了把数学彻底形式化的愿望是不可能的

可计算问题

那么对于一个系统中的可证问题和不可证问题的边界在哪里呢?

  • 设函数f的定义域是D,值域是R,如果存在一种算法,对D中任意给定的x都能计算出f(x),则称函数是可计算的。

  • 研究思路

    • 为计算建立一个数学模型,称为计算建模,然后证明,凡是这个计算模型能够完成的任务,就是可计算任务。

图灵机

  • 1936年,图灵在其著名的论文《论可计算数在判定问题中的应用》一文种提出了一种理想的计算机数学模型,图灵机
  • 美国计算机协会ACM于1966年设立图灵奖
  • 图灵机的构成
    • 一条存储带
      • 双向无限延长
      • 上有一个个小方格
      • 每个小方格可存储一个数字/字母
    • 一个控制器
      • 包含一个读写头,可以读写,更改存储带上
      • 可以接受设定好的程序语句
      • 可以改变自身的状态
      • 可以沿着存储带一格一格的左移右移

image

  • 图灵机的工作准备:
    • 存储带上符号初始化
    • 控制器设置好自身的状态
    • 控制器位于起始位置
    • 准备好工作程序
  • 图灵机的工作步骤
    • 读写头读出存储带上当前方格中的字符/数字
    • 根据自身状态和读入的字符,找到响应的程序语句
    • 根据响应的程序,做三个动作:
      • 在当前存储带放个上写入一个相应的字母/数字
      • 变更自身状态至新状态
      • 读写头向左,或向右移动一步
  • 图灵机停机
    • 标识计算完毕,表示当前存储带上保留的是计算结果,停机意味着计算得出结果
    • 也就是说:
      • 对于一个问题的输入A,能否推证出B,如果能找到一个个图灵机并得到B,那么A到B就是可计算的。
  • 图灵机收到重视:
    • 简单
    • 强大
    • 可实现:http://aturingmachine.com
  • 图灵机的意义:
    • 可计算性的判定
    • 给出了一个通用的计算模型
    • 引入了通过读写符号和状态改变来进行运算的思想
    • 实现了基于简单的字母表,完成复杂运算的能力
    • 引入了存储器,程序,控制器等概念的原型

计算机为什么能计算

  • “数”在计算机种如何表示?

    • 字母表中的符号越多,读入移动次数减少,但程序数量就越多
    • 字母表中符号越少,程序量会减少,但读入移动次数就越多
    • 字母表中符号的最优数量,可能是欧拉常数e(2.7182818284590...)取整后为3。
    • 与具有两个状态的电子元件相比,具有三个状态的电子元件在制造上更困难,可靠性更低。
  • 逻辑上“数”是如何计算的?

    • 布尔代数
      • 1854年,布尔发表<思维规律的研究——逻辑与概率的数学理论基础>,并综合其另一篇文章《逻辑的数学分析》,创立了一门全新的学科——布尔代数。

      • 为计算机的电路设计提供了重要的数学方法和理论基础。
      • 基本的逻辑运算: 与或非
      • 符合逻辑运算:同或,异或,与非,或非,与或非
    • 用二进制实现加法
      • 本位:A和B的亦或运算
      • 进位: A和B的与运算
    • 所有基本的逻辑运算都可以用电路表示,与门,非门,或门,与或门。。。

    • 结论:
      • 参与运算的数可以转换为 二进制
      • 二进制的运算可以用布尔运算实现
      • 基本的布尔运算都可以由电路实现

计算机的历史与未来

历史

  • 手工计算器, 1200年 ~ 1600年
    • 算盘
    • Oughtred计算尺,1621
    • Napier乘除器 ,1617
  • 机械计算器,1600年 ~ 1930年
    • 帕斯卡加法器(1642)
      • 齿轮组成装置,依靠发条转动,用铁笔拨动转轮输入数字
      • 6位加减法
    • 契克卡德(1623)
      • 德国科学家,天文学,数学
      • 1623年为开普勒制作计算机
      • 6位加减法
    • 莱布尼茨(1646-1716)
      • 德国伟大数学家,提出”二进制”概念
      • 1673年改进帕斯卡加法器,进行四则运算
      • 16位加减法
  • 计算机原型,1937年 ~ 1946年
    • 巴贝奇差分机(1822年)
      • 处理3个不同的5位数
      • 计算精度达到6位小数
    • 巴贝奇分析机(1834年)
      • 堆栈,运算器,控制器
      • 计算用的程序和数据存储于穿孔卡片上
    • Ada Augusta
      • 分析编制了人类历史上第一批计算机程序
    • Hollerith
      • 统计学家,Founder of IBM
      • 人口普查
        • 1880年人口普查1887年才完成,1890年的可能需要1900年完成
        • 发明”制表机”,6个月完成1890年人口普查
      • 1896年成立”计算制表记录公司”,1924年改名”国际商用机器公司”
      • 1935年: IBM制造了IBM601穿孔卡片式计算机,一秒内计算乘法
    • ENIAC(Electronic Numeric Integrator and Computer)电子数字积分计算机
      • 宾西法尼亚大学摩尔学院,J. Mauchly, J.Eckert
      • 1943年~1945年研制。1946年2月14日正式启动
      • 17468只电子管,7200个二极管,7000多个电阻器,10000多只电容和6000只继电器;174000W功耗
      • 30米长,3米高,30吨重,占地面积170平方米
      • 10位数乘法,5000次加法在3/1000秒内完成
      • 和Atansasoff有专利之争,到底谁发明了第一台计算机。
        • 1941年6月, Mauchly拜访了Atanasoff并参观了已经接近完成的ABC
      • 缺点:
        • ENIAC还不是存储程序计算机
        • 编程是通过手工接线的方式进行
    • EDVAC(Electronic Discrete Varable Automatic Computer)电子离散变量计算机
      • 1945年3月冯.诺依曼(John von Neumann)同J. Mauchly, J.Eckert在摩尔学院进行两天讨论,指定了存储式计算机的方案。于1945年6月发表——存储程序控制原理
      • EDVAC于1952年制造完成
      • EDVAC是第一套存储程式计算机
      • 是现代计算机的原型和范本
  • 现代计算机
    • 电子管计算机,1946年
      • 使用真空管存储数据
        • 真空管是一种控制真空中电子流动的电子装置
        • 两个电极表示0/1
        • 体积大,能耗高,易烧坏
          • ENIAC有18000个真空管,第一年运行就替换了19000个
      • 只能用0/1进行编程
    • 晶体管计算机,20世纪50年代后期
      • 贝尔实验室1947年发明晶体管
        • 更小,更便宜,功耗低,可靠
      • 产生操作系统
        • 标准化的硬件资源管理
        • 不可移植
      • 产生高级编程语言
        • Fortran
        • Cobol
    • 集成电路计算机,1965年
      • 使用集成电路,1958年德州仪器发明
      • 操作系统可移植
      • C语言
    • 超大规模集成电路,20世纪70年代早起
      • 超大规模集成电路
      • 第一块CPU,1971年Intel 4004
        • 2400个晶体管,计算能力与ENIAC相当
        • 尺寸:3mmx2mm
      • 计算机发展出现瓶颈
      • 摩尔定律
        • 1965年Intel创始人之一,Moore提出
          • 芯片密度每18个月增加1倍
          • CPU性能价格比大约18个月翻一番

未来

  • 摩尔定律的挑战
    • 晶体管大小限制
      • 晶体管持续变小很快会达到原子大小,任何纳米管和传统工艺都无法解决这种情况
      • 1999年 180nm,2011年 22nm
    • 电泄漏
      • 随着晶体管体积不断缩小,电泄漏的情形也不断增加
    • 散热
      • 晶体管密度与速度的增加导致芯片消耗更多的电力产生更多的热能
        • Intel CTO Partric Gelsinger
          • 2005年一个高端处理器每平方厘米散热量和一个核反应堆外壳持平
          • 2010年和火箭助推器相提并论
          • 2015年太阳表面温度
  • 量子计算机
    • 1982年物理学家Richard Feynman提出”利用量子理论进行通用计算”
      • 使用现有计算机去模拟计算量子运动计算量太大
      • 使用一个已有的可控的量子系统(比如一台量子计算机)去计算另一个感兴趣的量子系统(如宇宙)会很高效
    • 量子计算机原理
      • 存储方面
        • 经典存储:一个晶体管某一个时刻只能表示一个比特,0或1
          • 2个比特,某一个时刻,只能存储1对0或1,只能表示1个数
          • N个比特,某一个时刻,只能存储2的N次方个数中的某一个
        • 量子存储:一个量子比特可以同时保持多种状态
          • 2个量子比特,某一个时刻,能同时存储4对0或1,能表示4个数
          • N个量子比特,某时刻可以同时存储2的N次方个二进制数
      • 计算方面
        • 经典计算:
          • 输入N个二进制数,输出一个结果
        • 量子计算
          • 输入N个二进制数,输出2的N次方个结果,类似并行计算
    • 挑战
      • 量子状态不稳定
        • 300个量子比特能承载的数据是2的300次方,超过全宇宙的原子数量总和。现实中,需要1000个物理量子比特来保证足够数量的逻辑量子比特
      • 量子与外界环境隔离才能保持良好的相干性,但作为计算机,需要观察量子的状态,这回带来与量子的耦合,因此是一对矛盾
    • 当前成就
      • 2009年11月美国NIST研制一台2个量子比特的计算机
        • 2个镁离子+2个铍离子被限定在3.5mm长200微米宽的离子井中
        • 铍离子用于存储量子比特,镁离子做稳定剂,使用激光脉冲量子逻辑门对量子比特进行操作
        • 每个量子逻辑门准确率达到90%以上,但整体准确率仅为79%
        • 只有准确率达到99.999%以上才能商用
      • 2011年11月IBM组建团队,5年研究计划
        • 使用”金属超导性原理”制作量子bit
          • 在硅基质上使用铝和铌合成的金属冷却到非常低的温度,他们表现出零电阻
          • 构建循环闭合电路,同一时间电流可以流向两个方向,顺时针为1,逆时针为0
        • 同年,基于金属超导性原理,加拿大公司生产D-Wave
          • 有争议,不是真正意义的量子计算机

程序运行原理

思路整理

  • 电路可以完成运算,但是通用性没法保证,对于各种运算没法定义统一的电路。
  • ENIAC通过插拔电路来实现不同的运算
  • 冯诺依曼,提出了新的思路:
    • 通过命令来控制计算机
    • 命令可以存放在计算机
    • 修改命令,功能就改了
    • 制造新计算机EDVAC

什么是存储程序计算机

  • 冯诺依曼EDVAC:
    • 输入输出设备
    • 总线
    • 运算器
    • 控制器
    • 存储器
  • 工作过程
    • 在控制器的指挥下,从存储器上取出指令
    • 分析指令,得到计算命令和待操作数
    • 从存储器上取出待计算得数放入运算器
    • 运算器计算结果
    • 输出到存储器或者输出设备

存储

  • 寄存器
    • CPU内部,用于存放操作数和结果
    • 工作速度与CPU运算节拍保持一致
    • 一次存取数据大约花费0.x纳秒
    • 寄存器与运算部件直接连接,运算部件直接对寄存器进行读写操作
    • 寄存器制作成本高,一般CPU芯片中通常只有少数寄存器
  • 高速缓存
    • 可以在CPU内部,用作数据缓冲区
    • 也可以在CPU外部
    • 通常分为多级,不同级之间的工作频率不同
    • 一般在纳秒内读写一次
    • 容量大小不同(nK-nM)
  • 内存
    • CPU里想放但是放不下的
    • 工作频率越来越接近CPU频率,但仍有差距
    • RAM
      • DRAM:可随机存取,但必须周期性的刷新以保持存储内容
        • SDRAM: 工作在CPU外部总线频率上,与CPU的时钟保持同步
        • DDR SDRAM:从理论上讲 ,可以把RAM的速度提升一倍,它在始终的上升沿和下降沿都可以读取数据。
        • DDR2 电压1.8v,高端频率可达1000MHz
        • DDR3 电压1.5v,频率可达2000MHZ 8bit预读
        • DDR4 电压1.2v,数据传输速率3.2GT/s
  • 外存

  • 存储的原理是什么?

原理:

  • T1和T2组成一个双稳态触发器,用于保存数据。T3,T4为负载管
  • 如A点为高电平,则B点为低电平
  • 行选择有效电平时,AB处的数据信息通过门控管T5,T6送至C,D点
  • 列选择有效电平时,CD处的数据信息通过门控管T7,T8送至芯片数据引脚I/O

CPU指令的执行

  • 问题?
    • CPU能够识别正确的程序吗
    • 指令是什么?
    • 指令如何执行的
  • 指令集
    • CPU中能够执行指令的集合
    • 在CPU设计时就先定义好的
    • Intel X86指令集
    • ARM 指令集
  • 指令
    • 表现形式都是二进制码
    • 长度随CPU类型不同而不同
    • 包含一个或多个字节
    • 包含指令码和操作数: ADD 1 2
  • CPU工作方式
    • 运算器ALU
      • 专门进行算术和逻辑运算的电路
      • 寄存器
        • 累加器AC:暂时存放计算结果
        • 状态寄存器PSR:ALU运算结果,系统工作状态信息
        • 数据寄存器MAR:数据缓存
    • 控制器
      • 程序计数器PC:保存下一条指令的地址
      • 指令寄存器IR:存放当前正在执行的指令
      • 地址寄存器MAR:存放要访问的主存地址
  • 指令执行过程:

程序

-结论: - 程序必须要经过编译才转换成CPU所能接手的指令 - 一句程序有可能转换为多句指令 - 在控制器的协调下连续,依次进行相应的指令 - 程序执行过程是在内存中完成的 - 程序在执行过程中,在内存中的不同区域,存放代码和相关数据

语言

语言分类

  • 低级语言 之 机器语言
    • 00000001000000001000:将数据装入寄存器
  • 低级语言之汇编语言
    • load 0 a:将数据装入寄存器0
    • mult 0 1:将数据装入寄存器1
  • 高级语言之C
    • d = a*b+c

语言历史

  • Fortran
    • 1954 - 1956 年IBM的 John Backus和他的研究小组开发了FORTRAN(FORmula TRANslation)
  • Algol 60
    • 1960年1月,Alan J. Perlis发表《算法语言Algol60》(A语言)
    • 计算科学里程碑
  • BCPL
    • 1963年剑桥大学在ALGOL 60的基础上推出了CPL,但是规模较大,难以实现
    • 1967年剑桥大学的Martin Richards对CPL进行了简化,推出了BCPL
  • C
    • 1970年贝尔实验室,Ken Thompson在PDP-7上写操作系统,缺乏语言,于是他简化了BCPL,发明了B语言,同时用B语言写出了UNIX
    • 1972-1973,Dennis Ritchie加入,在B语言上完善出C语言,并重写了UNIX

语言构成

  • 数据
    • 数据类型
  • 运算
    • 运算符号
    • 运算规则
  • 控制
    • 条件控制语句
  • IO
    • 输入输出

资料