导论课程第二讲2013-1-2修改.ppt

第二讲 Lecture Two 计算和信息本质 学思结合, 知行统一 专业导论 内容提要(outline) 计算机的史前史 计算的基本模型 计算机体系结构(第一台电子数字计算机的诞生) 再论计算学科的根本问题和定义 信息的本质和度量 计算本质的认识历史 算筹到算盘（中） 按口诀，“乘除不失，毫厘分明” “算法化”思想 1275,R.Lullus（西） “旋转玩具”的发明 计算机器制造的先河 1641,B.Pascal（法） 利用齿轮制成加法器 1673,G.W.V.Leibniz（德） 加减乘除计算机器 19世纪30年代，C.Babbage（英） 计算对数、三角函数 20世纪20年代，V.Bush (美） 解微分方程组的电子模拟计算机 专业导论 专业导论 计算本质的认识历史 康托尔的集合论 -1845-1918， 数学大厦的基石 罗素悖论 -1901， 理发师难题,引发第三次数学危机 布尔代数 -1854, 二值逻辑代数体系 希尔伯特纲领 20世纪初, 形式系统和形式理论 哥德尔 -1931， 形式系统的不完备定理 图灵 -20世纪30年代后期, 对计算本质的揭示 专业导论 计算的基本模型-图灵机 图灵（A.M.Turing) 从计算一个数一般过程入手对计算本质 进行研究,实现了对计算本质的真正认 识. 计算的基本模型（附页2-1-2图） 所谓计算就是计算者（人或机器）对一 条纸带上的0或1，经过有限步骤，最后 得到一个满足预先规定的符号串的变换 过程。 英国数学家图灵在1936 年发表的一篇论文“论 可计算数及其在判定问 题中的应用”奠定了现代 计算机的理论和模型的 基础 专业导论 计算的基本模型-图灵机 图灵机 (例) 专业导论 图灵对计算本质的揭示 可计算性=图灵可计算性。深刻揭示了计算所具有的“ 能行过程”的本质特征。 “算法”也称能行方法/过程，是对解题（计算）过程的 精确描述。由一组定义明确且能机械执行的规则（指 令、语句）组成。 计算机科学最高奖-图灵奖 专业导论 再谈计算学科的根本问题 计算学科的根本问题: 什么能被（有效地）自动 进行 注意：这里处理的都是离散对象，连续对象很难进行能行处理。 以离散变量为研究对象的离散数学(逻辑、集合、数列、关系和函 数、布尔代数、排列组合、图论等）对计算技术的发展起着十分 重要的作用, 例。 专业导论 第一台电子数字计算机的诞生 冯. 诺依曼(Von Neumann) - 计算机器之父 在电子计算装置逻辑结构设计报告中提出现代计算机 体系结构, 称为冯. 诺依曼体系结构: 由控制器、运算器 、存储器、输入和输出设备5部分组成（附页2-1-4） 提出二个重要概念: 保存程序和数据的存储器； 条件分支. 第一台电子计算机:1946.2.14, “埃尼阿克” ( ENIAC Electronic Numerical Integrator And Calculator,电子数 字积分计算机) 在宾夕法尼亚大学研制成功。 基于电子线路，冯. 诺依曼体系结构的全电子数字计算机 。 专业导论 计算本质的认识历史-小结 计算学科是对描述和变换信息的算法过程，包括 对其理论、分析、设计、效率、实现和应用等进 行的系统研究。 它来源于对算法理论、数理逻辑、计算模型、自动计算 机器的研究，并与存储式电子计算机的发明一起形成于 20世纪40年代初期。 从20世纪30年代到1989年，ACM和IEEE-CS 的计算作为 一门学科（Computing as a Discipline）的研究报告 ，确定了作为一个学科的地位和知识框架。 专业导论 计算本质的认识历史-小结 计算学科是以数学为基础的科学，其研究包括从算法与可计算 性的研究到根据可计算硬件和软件的实际实现问题的研究 计算机是一种能快速、高效、准确地进行信息处理的数字化电 子设备，它能按照人们事先编写的程序自动地对信息进行加工 和处理，输出人们所需要的结果。 中国学者：算盘到“吴方法” - 能行性到数学机械化 这座长算盘是在账房中供多人使用， 现藏于北京民俗博物馆（东岳庙） 吴文俊与“吴方法” 专业导论 信息本质的认识 科学史上三个基本概念 物质：指空间和质量的东西，物质不灭定律。 能量：E = mc2，能量守恒定律。 信息：不是物质也不是能量？ 关于信息的传输、控制和处理的三位奠基人 香农(Shannon) ：信息论 维纳（Wiener) ：控制论 冯. 诺依曼(Von Neumann)：计算机 40年代中分别在通信、控制和计算机领域工作，奠定了信息论 、控制论和计算机的基础。 专业导论 信息及其度量 信息熵(Entropy) 香农（1916-2001）被称为是“信息论之父” 。 通常将香农于1948年10月发表于贝尔系统技术学 报上的论文”通信的数学原理”作为现代信息论 研究的开端。在文中，香农给出了信息熵的定义. 信息熵的定义： 表明某些物质系统状态的一种量度或说明其可能出 现的程度。在信息理论中的一个基本量。是利用统 计方法求得信息源中包含的平均信息量。 专业导论 信息及其度量 信息熵“形式化”和“概率论”公式表示如下： 如果有一个系统S内存在多个事件S = E1,.,En, 每个事件的概率分布 P = p1, ., pn，则每个 事件本身的信息为: Ie = log2pi （对数以2为底，单位是比特） 整个系统的平均信息量为 这个平均信息量就是信息熵，例 专业导论 信息的本质 信息 是由特定的物质过程产生、发送、接受和利用的， 是质-能的一种属性，不能离开物质或能量单独存 在。 有三个层次的载体 物质材料存储载体 物质-能量的波动信号载体 符号载体。 信息的本质 香农提出“信息的核心本质是一个数学分支，是一 个严密的演绎系统。” 专业导论 信息的属性 事实性 l 最基本的 扩散性 l 是本性，传播和保密 传输性 l 优于其它物质和能源 共享性 l 可共享但不能交换 增值性 l 随时间推移 不完全性 l 不能完全得到，也无必 要 等级性 l 信息是分级的 滞后性 l 数据-信息-决策-结果 l 办公自动化系统（OA