计算机科学导论-计算思维程序实践 课件汇 扩展第1-5讲-计算与社会-机器是怎样表示文字声音图像的-编码与解码

扩展第1讲计算与社会哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣计算与社会变革计算的发展与社会计算与学科与各行业计算与学生未来本讲讲什么内容提要第一次工业革命第二次工业革命第三次工业革命第四次工业革命第一次信息技术革命第二次信息技术革命计算与工业革命信息工业：新一轮大国竞争的焦点计算引发的个人改变吃-穿-住-行-用-工作-娱乐软件正在占领全世界from马克.安德森--前Netscape公司创始人计算引发的社会变革计算思维是人类应具备的第三种思维实验思维:实验观察发现、推断与总结.---观察与归纳理论思维:假设/预设定义/性质/定理证明.---推理和演绎计算思维:设计,构造与计算.---设计与构造计算思维关注的是人类思维中有关可行性、可构造性和可评价性的部分当前环境下，理论与实验手段在面临大规模数据的情况下，不可避免地要用计算手段来辅助进行计算引发的科研变革计算科学与信息探索科学已成为科学创新的重要方面世界上最小台式电脑----如同拇指大小智能手机

可嵌入、可携带计算微型化与社会人体芯片人体芯片IBM-BlueGene(蓝色基因):MilestoneofanIntelligentMachineAmassivelyparallelsupercomputerusingtensofthousandsofembeddedPowerPCprocessorssupportingalargememoryspaceWithstandardcompilersandmessagepassingenvironment

大规模、复杂计算计算大型化与社会InternetofServicesInternetofNetworksInternetofThingsInternetof3DWorldsForpeopleandenterprises“未来互联网”-FutureInternet机-机相联，物-物相联，物-人相联，人-人相联，人-机-物互联人-机-物互联的世界计算网络化与社会理解自然语言，具有自适应性，自主完成复杂功能计算智能化与社会IBM：SmartPlanetInstrumentedInterconnectIntelligent计算技术的发展促进了计算与社会/自然的深度融合冯.诺依曼计算机云计算环境并行分布计算环境复杂系统，（技术与应用）双轮驱动，交叉融合计算与社会/自然融合环境计算与各行各业高端机械机械的“计算/自动控制”部件数字化

计算化/自动化

智能化互联网+高端机械(群)计算+：数字数据采集与控制互联网+：互联互通互控数据+：数据分析与应用机械材料化工数理制造医学计算机+(计算思维)(系统能力)(智能机械)(智能制造)(计算数理)(材料计算)(计算化学)（智能化工）(智慧医疗)社会学/经济学(计算社会学/计算经济学)文学/艺术(数字艺术/计算人文)电器/仪器(智能电器/智能仪器)管理(管理信息系统)建筑/能源(智能建筑/智慧能源)交通/市政(智能交通/智慧城市)新工科的内涵之一核心思维之一是计算思维核心能力之一是系统能力

需要计算思维与系统能力，而不仅仅是应用计算机。各学科+计算机与“计算机+”深度融合

各学科的高端研究：

计算化/自动化

网络化

智能化

新工科：国家战略计算机+各学科计算+、互联网+、大数据

信息+、（人工）智能+

计算(机)与社会/自然(各学科)深度融合计算与学科计算+、互联网+、大数据、人工智能+当现实世界的领导者融合了计算思维以后…真实世界复杂系统(包括人系统)分工：独立管理分工：独立管理分工：独立管理合作-协同：联合管理如何理解复杂系统，如何求解复杂系统？分工-合作-协同化复杂为简单操作系统—不仅仅是应用领导者/总控：完成宏观任务的各种资源协调者

复杂任务：分工-合作-协同资源体系：不同性能资源的组合运用资源管理：化整为零与还零为整-效率资源调度：分时-并行-分布现实世界：领导者操作系统：完成大(宏观)任务的计算资源协调者

程序执行：分工-合作-协同存储体系：不同性能资源的组合运用

磁盘管理/网络传输：化整为零与还零为整-效率CPU调度：分时-并行-分布互联网世界：管理者与执行者【示例】以计算系统的计算思维，训练学生的管理思维和领导思维计算与未来的领导者专业密切相关专业相关跨各专业从学生发展角度：计算思维对各学科学生未来创新都将会产生重要影响设计/构造…计算/仿真系统应用…计算/仿真系统进行学科问题研究未来能做出未来能应用毕业生新生1st迭代2nd迭代3rd迭代要素层面理解计算系统思维层面理解计算系统设计与构造计算系统1st迭代2nd迭代理论与方法层面理解计算思维层面理解计算系统【大学计算机-计算思维导论/计算思维与计算系统导论】【计算科学】各学科计算系统/工具【计算概论/计算机科学导论/计算机类专业导论】机器结构/计算机系统、软件构造、算法与数据结构等本学科计算系统/工具计算与学生未来复杂性思维教学是一种挑战，计算思维是一种高阶复杂性思维技能，是复杂性思维能力培养的重要支撑，强调计算思维教育，可以帮助学习者解读真实世界的系统并解决全球范围的复杂问题。

From2015地平线报告。

计算思维是新时代人才应具备的11种思维能力之一。制造、发现、人际交往技能、个体技能与态度、创造性思维、系统性思维、批判与元认知、分析性思维、计算思维、实验性思维及人本主义思维。FromMIT.诺贝尔化学奖：1998年和2013年两度授予计算工具的研究者说明计算思维与各学科融合创新的重要性。J.A.Pople把计算机应用于量子化学，设计了一套基函数程序，并把计算方法从描述比较简单的平衡状态的分子的电子结构推广到对化学反应途径和过渡态的研究，使全世界的量子化学工作者都在用他的程序研究化学问题。2013年，马丁·卡普拉斯、迈克尔·莱维特和阿里耶·瓦谢勒，因开发多尺度复杂化学系统模型及其计算工具所做的贡献而获得诺贝尔化学奖。国家推行了一系列信息技术引领的行动计划，如【互联网+行动计划】、【新一代人工智能发展规划】等，其关键和基础是要培养一批具有“互联网+”思维、“大数据”思维、“人工智能”思维的人才。“思维有多远，就能走多远”，思维是创新的源头。国家层面/社会层面对计算思维的重视？未来需要拥有计算思维结论：计算思维很重要！要学习并掌握计算思维！扩展第2讲大学计算思维教育空间—计算之树?战德臣哈尔滨工业大学计算学部教学委员会主任国家教学名师从计算之树看大学计算思维教育空间递归程序0和1树根：奠基性思维递归程序0和1“0和1”思维--符号化

计算化

自动化

0和1是实现任何计算的基础；社会/自然与计算融合的基本手段；0和1是连接硬件与软件的纽带；0/1是最基本的抽象与自动化机制。“程序”思维--千变万化复杂功能的构造、表达与执行计算机是能够执行程序的软件或硬件程序是基本动作(指令)的各种组合，是控制计算系统的基本手段“递归”思维--无限事物及重复过程的表达与执行方法递归是最典型的构造程序的手段，是可以表达让机器大量重复动作的构造手段；递归函数是可计算函数的精确的数学描述；递归函数是研究计算学科理论问题的基础树根：奠基性思维递归程序0和1云计算环境并行分布环境个人计算环境冯.诺依曼机树干：通用计算环境演变递归程序0和1云计算环境并行分布环境个人计算环境冯.诺依曼机树干：通用计算环境演变个人计算机冯.诺依曼计算机云计算环境并行分布计算环境思维的变化

计算环境的变化

思维的进一步变化看似不可能，其实很可能递归程序0和1云计算环境并行分布环境个人计算环境冯.诺依曼机算法系统两色树枝：问题求解的两种手段-算法与系统递归程序0和1云计算环境并行分布环境个人计算环境冯.诺依曼机算法系统两色树枝：问题求解的两种手段-算法与系统“算法”：问题求解的一种手段—构造与设计算法算法是计算的灵魂；算法强调数学建模；算法考虑的是可计算性与计算复杂性；算法研究通常被认为是计算学科的理论研究。“系统”：问题求解的另一种手段—构造与设计系统系统是改造自然的手段；系统还强调非数学建模；系统考虑的是如何化复杂为简单(使其能够被做出来)；系统还强调结构性、可靠性、安全性等。系统是龙，算法是睛，画龙要点睛。递归程序0和1云计算环境并行分布环境个人计算环境冯.诺依曼机算法系统社会/自然的计算化计算/求解的自然化抽象量子计算/光子计算移动计算生物计算计算生物学计算物理学计算化学计算经济学计算统计学计算金融学企业计算计算工程学服务计算云计算社会计算计算广告学媒体计算纳米计算智能计算计算语言学神经计算自然现象的计算的表达与推演用社会/自然所接受的形式体现计算及结果自动化各树枝：计算与社会/自然的融合递归程序0和1云计算环境并行分布环境个人计算环境冯.诺依曼机算法系统社会/自然的计算化计算/求解的自然化抽象量子计算/光子计算移动计算生物计算计算生物学计算物理学计算化学计算经济学计算统计学计算金融学企业计算计算工程学服务计算云计算社会计算计算广告学媒体计算纳米计算智能计算计算语言学神经计算自然现象的计算的表达与推演用社会/自然所接受的形式体现计算及结果自动化模型语言协议系统编译器编解码器业务-计算人-计算机机-机，物-物三个层面的融合机制-抽象与自动化递归程序0和1云计算环境并行分布环境个人计算环境冯.诺依曼机算法系统社会/自然的计算化计算/求解的自然化抽象量子计算/光子计算移动计算生物计算计算生物学计算物理学计算化学计算经济学计算统计学计算金融学企业计算计算工程学服务计算云计算社会计算计算广告学媒体计算纳米计算智能计算计算语言学神经计算自然现象的计算的表达与推演用社会/自然所接受的形式体现计算及结果自动化模型语言协议系统编译器编解码器业务-计算人-计算机机-机，物-物局域网/广域网：机器网络互联网：信息网络/广义资源网络物联网;知识网;服务网;社会网网络化网络化思维递归程序0和1云计算环境并行分布环境个人计算环境冯.诺依曼机算法系统社会/自然的计算化计算/求解的自然化抽象量子计算/光子计算移动计算生物计算计算生物学计算物理学计算化学计算经济学计算统计学计算金融学企业计算计算工程学服务计算云计算社会计算计算广告学媒体计算纳米计算智能计算计算语言学神经计算自然现象的计算的表达与推演用社会/自然所接受的形式体现计算及结果自动化模型语言协议系统编译器编解码器业务-计算人-计算机机-机，物-物局域网/广域网：机器网络互联网：信息网络/广义资源网络物联网;知识网;服务网;社会网网络化事务管理与数据库数据分析与数据仓库数据聚集与大数据数据化数据化思维智能化思维递归程序0和1云计算环境并行分布环境个人计算环境冯.诺依曼机算法系统社会/自然的计算化计算/求解的自然化抽象量子计算/光子计算移动计算生物计算计算生物学计算物理学计算化学计算经济学计算统计学计算金融学企业计算计算工程学服务计算云计算社会计算计算广告学媒体计算纳米计算智能计算计算语言学神经计算自然现象的计算的表达与推演用社会/自然所接受的形式体现计算及结果自动化模型语言协议系统编译器编解码器业务-计算人-计算机机-机，物-物局域网/广域网：机器网络互联网：信息网络/广义资源网络物联网;知识网;服务网;社会网网络化事务管理与数据库数据分析与数据仓库数据聚集与大数据数据化智能化机器学习自适应优化“知识/术语”随着“思维”的学习而展开，“思维”随着“知识”的贯通而形成，“能力”随着“思维”的理解而提高。从问题分析着手，强化如何进行抽象，如何将现实问题抽象为一个数学问题或者一个形式化问题，提高问题表述及问题求解的严谨性。通过图示化方法来展现复杂的思维可以一目了然；通过规模较小的问题求解示例来理解复杂问题的求解方法；通过从社会/自然等人们身边的问题理解到计算科学家是如何进行问题求解。追求“问题”及问题的讨论，通过逐步地提出问题，使自己从一个较浅的理解层次逐步过渡到较深入的理解层次，通过不同视角和递阶的讨论，使自己理解和确定前行的方向。宽度与深度相结合，从宽度学习开始，深度学习结束，既能够使自己理解相关的思维与知识，还能够有助于建立起较为科学的研究习惯与研究方法。思维蕴含在案例中，案例蕴含着思维。从计算之树看大学计算思维教育空间怎样学习计算思维扩展第3讲

计算机的理论模型-图灵机战德臣哈尔滨工业大学计算学部教学委员会主任国家教学名师理解图灵机模型

图灵机与算法和可计算性的关系图灵机模型对现代计算机的启示图灵机的一个重要应用—形式语言及其识别本讲讲什么内容提要图灵(AlanTuring,1912~1954)，出生于英国伦敦，19岁入剑桥皇家学院，22岁当选为皇家学会会员。1937年，发表了论文《论可计算数及其在判定问题中的应用》，提出了图灵机模型，后来，冯·诺依曼根据这个模型设计出历史上第一台电子计算机。1950年，发表了划时代的文章：《机器能思考吗?》,成为了人工智能的开山之作。计算机界于1966年设立了最高荣誉奖：ACM图灵奖。图灵是谁图灵及其贡献图灵的贡献重要在哪里呢？你能查阅一下哪些人获得图灵奖了吗？因为什么贡献而获奖呢？所谓计算就是计算者(人或机器)对一条两端可无限延长的纸带上的一串0或1，执行指令一步一步地改变纸带上的0或1，经过有限步骤最后得到一个满足预先规定的符号串的变换过程。…10001110110011010110001…0110101由“程序”控制，一步步将输入“转换”为输出输入输出程序通用机器图灵机的基本思想什么是计算—图灵的观点关于数据、指令、程序及程序/指令自动执行的基本思想。输入被制成一串0和1的纸带，送入机器中----数据。如00010000100011…机器可对输入纸带执行的基本动作包括：“翻转0为1”，或“翻转1为0”,“前移一位”,“停止”。对基本动作的控制----指令，机器是按照指令的控制选择执行哪一个动作，指令也可以用0和1来表示：01表示“翻转0为1”(当输入为1时不变)，10表示“翻转1为0”(当输入0时不变),11表示“前移一位”,00表示“停止”。输入如何变为输出的控制可以用指令编写一个程序来完成,如:011110110111011100…

机器能够读取程序，按程序中的指令顺序读取指令，读一条指令执行一条指令。由此实现自动计算。图灵机的基本思想什么是计算—图灵的观点基本的图灵机模型为一个七元组,如右图几点结论:(1)图灵机是一种思想模型，它由一个控制器(有限状态转换器)，一条可无限延伸的带子和一个在带子上可完成读写的读写头构成，纸带可以向右或向左移动，或者说，读写头可以向左或向右移动。(2)

一个图灵机就是一个程序。程序是五元组<q,X,Y,R(或L或N),p>形式的指令集。其定义了机器在一个特定状态q下从方格中读入一个特定字符X时所采取的动作为在该方格中写入符号Y,然后纸带向右移一格R(或向左移一格L或不移动N),同时将机器状态设为p供后续操作使用。图灵机模型图灵机是什么M=（Q，

，

，

，S，B，F）其中：Q:状态的有穷集合

：输入字母表

：带符号表

S:开始状态F：终止状态集合B或b:空白符号

：移动函数，&(q,X)=(p,Y,R或L或N)表示M在状态q时读入符号X,则将状态改为p,并在X所在的带方格中印刷符号Y，然后将纸带向右/向左移动一格或者不动；（注：也可定义读写头向右/向左移动一格。读写头向右移动即纸带向左移动。这里定义是纸带向右/向左移动，便于后续示例一致性）…bb11100bb…状态qi控制器(有限状态转换器)读写头一个具体的图灵机示例(q1,0,0,L,q1)(q1,1,1,L,q2)(q2,1,1,L,q2)(q2,0,1,R,q3)(q3,1,1,R,q3)(q3,0,0,N,q4)q1q2q3q41,1,L1,1,L0,1,R1,1,R0,0,NQ={q1,q2,q3,q4}其中q1：开始状态q2：右移状态q3：左移状态q4：停机状态

={0,1}

带字符集={0,1,b}S={q1}F={q4}B/b空白字符&--移动函数/指令集0,0,L理解图灵机模型图灵机【示例1】指令集（移动函数）状态图（或状态输入转换图）

(注:(q,X,Y,L,p),状态图中圆圈内的是状态，箭线上的是<X,Y,L>,表示读出X时则写入Y并向左移动。L位置也可以是R(向右移动)或N(不动))。M=（Q，

，

，

，S，B，F）与通常【程序】（一条接一条执行的指令集合）的差异依据【当前状态】和【输入】决定执行哪条指令功能：将一串连续1的后面再加一位1001111000控制器q1q2q3q41,1,L1,1,L0,1,R1,1,R0,0,N0,0,L001100011你能否用另一个输入模拟一下这个程序的执行呢?001111000001111000(q1,0,0,L,q1)(q1,1,1,L,q2)001111000(q2,1,1,L,q2)001111000(q2,0,1,R,q3)001111100(q3,1,1,R,q3)001111100(q3,0,0,N,q4)理解图灵机模型图灵机计算过程【示例1】纸带向左移，读写头向右移该图灵机能处理完给定的输入吗？后面再讨论图灵机模型示例另一个示例（空白输入开始）0101

0101

1101

1001

1011

1010(q1,b,b,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)q1q2q3b,b,L1,0,Lb,b,N1,0,R0,1,R0,1,L注：纸带的左移(相当于读写头的右移)，纸带的右移(相当于读写头的左移)。状态图中标示的是纸带的移动.(q1,1,0,R,q1)(q1,0,1,R,q2)(q1,b,b,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)图灵机模型示例另一个示例（从纸带1处开始）q1q2q3b,b,L1,0,Lb,b,N1,0,R0,1,R0,1,L注：纸带的左移(相当于读写头的右移)，纸带的右移(相当于读写头的左移)。状态图中标示的是纸带的移动.(q1,1,0,R,q1)(q1,0,1,R,q2)(q1,b,b,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)1101

1001

0001

0001

1001

110111111110(q1,1,0,R,q1)(q1,1,0,R,q1)(q1,b,b,L,q2)(q2,0,1,L,q2)(q2,0,1,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)图灵机模型示例另一个示例（从纸带0处开始）q1q2q3b,b,L1,0,Lb,b,N1,0,R0,1,R0,1,L注：纸带的左移(相当于读写头的右移)，纸带的右移(相当于读写头的左移)。状态图中标示的是纸带的移动.(q1,1,0,R,q1)(q1,0,1,R,q2)(q1,b,b,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)1100111011111111110111100(q1,0,1,R,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)图灵机模型被认为是计算机的基本理论模型图灵机从初始状态开始对纸带上的输入符号进行处理，如果能够到达终止状态，则被认为是成功地完成一次计算，此时纸带上的符号就是输出。

当图灵机的输入纸带为X，运行指令集，如果能够到达终止状态且输出纸带变为期望的M(X)，则说图灵机求解了X。有一类特殊的问题，其输入为X，而输出是1（接受）或0（拒绝），则被称为【判定问题】。例如输入一个字符串，如果输出为1表明该字符串是可接受的符合规则的字符串，否则为不可接受的或者说不符合规则的字符串。图灵机从初始状态开始对纸带上的输入符号进行处理，如果输入处理完毕，且能够到达{接受、拒绝}等某一终止状态，则被认为是成功地完成了一次判定：输入被接受，或者输入被拒绝。图灵机是一种离散的、有穷的、构造性的问题求解思路，一个问题的求解可以通过构造其图灵机(即程序或算法)来解决。计算机是使用相应的程序或算法来完成任何设定好的任务。图灵可计算性继续看图灵机是什么q1q2q3b,b,L1,0,Lb,b,N1,0,R0,1,R0,1,L图灵机怎样才算结束并给出答案图灵可计算问题

一个问题“能否由A计算出B？”，利用图灵机做一个判定，即：如果能在A与B之间找到或设计出一个图灵机，使输入A停机得到的结果是B，就说明这个问题可解；否则就说明这个问题不可解。

图灵机根据指令集对输入进行处理，有的输入（初始状态与初始输入）可能导致停机（即能够到达某一终止状态）。有的输入则可能导致无限的执行序列（即不能够到达任一终止状态或停留在非终止状态）。【停机问题】：是否存在一个算法，对于任意给定的图灵机都能判定任意的【初始状态+初始输入】是否会导致停机。已经证明，这样的算法是不存在的，即停机问题是不可判定的。假设纸带上的符号串为与自然数n相关的编码。如果机器以此为输入，到达终止状态时，纸带上的符号串已改造为m相关的编码，则称机器计算了函数f(n)=m。如果一个函数以自然数为值域和定义域，并且有一个图灵机计算它，则称此函数为“可计算函数“。已有的关于可计算函数的另一些定义，如递归函数、λ可定义函数等，都等价于图灵机定义的可计算函数（为什么？同学可继续学习相关课程来回答）凡是能用算法方法解决的问题也一定能用图灵机解决;凡是图灵机解决不了的问题任何算法也解决不了。（为什么？同学可继续学习相关课程来回答）图灵可计算性继续看图灵机是什么q1q2q3b,b,L1,0,Lb,b,N1,0,R0,1,R0,1,L图灵机一定能停机吗？能否判定按计算规则(程序)对输入进行变换得到输出输入程序&指令(计算规则)输入/输出都是0和1的形式表达输出程序和指令也是0和1的形式表达程序可用状态转换图来表达图灵机模型对现代计算机的启示现代计算机的基本思想是否是图灵机的思想呢？图灵机模型对现代计算机的启示冯.诺依曼计算机:思想与构成M=（Q，

，

，

，S，B，F）其中：Q:状态的有穷集合

：输入字母表

：带符号表

S:开始状态F：终止状态集合B或b:空白符号

：移动函数，&(q,X)=(p,Y,R或L或N)表示M在状态q时读入符号X,则将状态改为p,并在X所在的带方格中印刷符号Y，然后将纸带向右/向左移动一格或者不动；（注：也可定义读写头向右/向左移动一格。读写头向右移动即纸带向左移动。这里定义是纸带向右/向左移动，便于后续示例一致性）…bb11100bb…状态qi控制器(有限状态转换器)读写头【存储程序】怎样能看出图灵机的影子呢计算机的基本部件CPU：中央处理单元(CentralProcessUnit)，将运算器和控制器集成在一块芯片上，形成微处理器。CPU、主存储器、I/O设备及总线成为现代计算机的四大核心部件。总线现代计算机里面，一个微处理器(芯片)可能包含多个CPU，即多核.图灵机模型对现代计算机的启示现代计算机运算器中央处理单元CPU控制器(主或内)存储器程序数据程序与数据的保存程序执行与数据计算图灵机模型对现代计算机的启示计算机非常简单：数据与程序，存储器与CPU形式计算理论课程：形式语言与自动机形式计算的基础是符号化和语言。形式语言与自动机是研究符号化表达(即形式语言)以及符号化识别与处理(即自动机)的理论。形式语言：字母表∑上满足一定条件的字符串的集合L，称为∑上的一种语言。例如，若是由26个英文字母(包括大小写)、标点符号和空格组成的字母表，则∑上那些符合英文单词组成规则和句子生成规则的字符串的集合，便是英语。再如，全部二进制整数也可看作一种语言，它是字母表{0，1}上所有字符串的集合。文法：文法是一类语言发生器。从一个文法G可以产生出一个语言L的各个句子，这些句子实际上是字符串。文法即是形式语言定义中需要满足的“条件”，即按文法产生的字符串(或说句子)才是该语言的字符串。自动机：自动机是一种符号处理系统，或者说语言识别器，即它能识别出符合一个语言文法的各个字符串(句子)。它根据状态、输入和规则决定下一个状态和输出。即：状态＋输入＋规则

状态迁移

+输出。典型系列课程介绍

计算机数学理论系列课程图灵机的重要作用—形式语言及其识别形式语言与自动机“模式”化语句的识别(形式语言的识别-符合一定文法的字符串的识别)V=C+C;标识符=常量+常量(形式语言的文法规则)S1S2S3S4V,V,R空格,null,R=,=,RC,C,RS5S6+,+,R空格,null,R空格,null,R空格,null,R空格,null,RS7;,null,NC,C,R空格,null,R;,null,N能识别两种模式“V=C;”和“V=C+C;”并能去除空格的图灵机示意图字母表{V，C，=，+，空格,;}；S1起始状态；S7终止状态；null表示什么也不写回。Result=7+10;(V,1)=(C,1)+(C,2);(V,2)=(C,3)+(C,4);图灵机的重要作用—形式语言及其识别语句模式的识别M=（Q，

，

，

，S，B，F）Value=8+20;形式计算理论课程：形式语言与自动机(Cont.1)典型系列课程介绍

计算机数学理论系列课程2型文法上下文无关语言1型文法上下文相关语言3型文法正则语言0型文法递归可枚举语言图灵机线性界限自动机下推自动机有限自动机语言规则语言识别和计算状态变换与控制图灵机的重要作用—形式语言及其识别形式语言的类别与识别机器【图灵机】是有更少约束的自动机理解图灵机模型

图灵机与算法和可计算性的关系图灵机模型对现代计算机的启示图灵机的一个重要应用—形式语言及其识别计算机的理论模型-图灵机为什么图灵机是计算机的理论模型你理解得怎么样呢？形式语言与自动机可计算性-计算理论设计语言并识别语言问题可计算性判断与算法需进一步学习扩展第4讲机器是怎样处理符号与小数点的？--机器数与定浮点数哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣信息表示[T]数值信息表示[T]非数值信息表示[K]进位制[K]机器数(有符号与无符号数)

[K]浮点数(小数)

[K]二进制/十进制/十六进制[K]进制转换[K]机器字长[ETP]减法转加法[K]机器数0的编码[QT]机器数的范围[EK]溢出及其逻辑判断[K]不同类型整数[EK]符号-阶码-尾数[QT]精度与范围[K]单精度与双精度[K]字符编码ASCII[EK]汉字编码[EK]内码(存储)[EK]外码(输入)[EK]字形码(输出)[ET]汉字处理过程[QT]不同编码的异同[K]Unicode[K]等长编码和变长编码[T]万事万物信息表示[KT]采样-量化-编码[T]语音信号编码[T]图像信号编码[K]位图[K]压缩编码[T]编码器（感知器）[T]编码(压缩)-解码(还原)信息变换(程序与算法)

[T]编码效率[K]压缩：有损与无损[T]视频信号编码[T]解码器（显示&输出）[EK]原码与补码[K]编码[K]知识

[T]思维

[S箭头]次序[Q]问题

[E]示例

[P]练习信息在计算机中的基本表示方法概览二进制十六进制十进制有0,1,2,3,4,5,6,7,8,9共十个数码数码的位置规定了数码的等级“权/数位”：10i逢十进一、借一当十。高数位的1相当于低数位的10表示法：128、(128)十、(128)D有0,1共两个数码数码的位置规定了数码的等级“权/数位”：2i逢二进一、借一当二。高数位的1相当于低数位的2表示法：(01001000)二、(01001000)B有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个数码数码的位置规定了数码的等级“权/数位”：16i逢十六进一、借一当十六。高数位的1相当于低数位的16与二进制转换简单：小数点开始向左向右分别处理，1位十六进制数对应为4位二进制数，或4位二进制数对应1位十六进制数。表示法：(15FE)十六、15FEH、0x15FE

0001010111111110日常使用机器内部使用辅助阅读机器数据计数制十进制、二进制、十六进制要熟悉和习惯二进制和十六进制【机器字长】是指机器内部进行数据处理、信息传输等的基本单元所包含的二进制位数，通常是8位、16位、32位、64位等。例：（78）十

转换成二进制数。不同字长的表示，结果是不同的

（1）（78）十

=（1001110）二

（2）（78）十

=（01001110）二

（3）（78）十

=（0000000001001110）二

（4）（78）十

=（00000000000000000000000001001110）二

溢出数的表示范围机器字长未考虑机器字长8位机器字长16位机器字长32位机器字长数值性信息与机器数机器数：机器字长假设：16位机器字长有符号数无符号数无符号机器数的表示范围：0

X<216，即0至65,535（0000000000000000）二

（1111111111111111）二

数的符号也用0和1表达，0表“+”号，1表“-”号（0000000000000000）二

（0111111111111111）二

（1000000000000000）二

（1111111111111111）二

有符号数的表示范围？有符号数的大小？数值性信息与机器数机器数：有符号数和无符号数有符号机器数的表示范围：-215<

X<215，即-32,767至+32,767+244+

111101000

11110100-244-

111101001

111101000

111101001

000010110

111101001

00001100十进制数二进制数机器数-原码机器数-反码机器数-补码加

00000001负数正数不同的机器数表示方法带符号的机器数：原码、反码和补码负数正数原码、反码和补码是一样的原码、反码和补码是不同的表示原码、反码和补码的表示范围也是不同的不同的机器数表示方法机器数：原码、反码和补码为什么要有补码:(1)0只有一种表示，可多表示一个数；(2)运算时符号位可一起参与运算;(3)减法可当作加法进行01010+)1110111100(10)+(-3)=(7)00111+)0001101010(+7)+(+3)=(+10)11001+)1010010110(-7)+(-12)=溢出11011+)1100100101(-5)+(-7)=(-12)5位机器字长（1位符号位，4位数值位）补码再求补即为原码受字长限制自动舍弃减法可用加法实现补码的加减法：符号位与数值位一起参与运算(+245.25)十+11110101.0100011110101.01000111101010100小数点默认在此位置(无需用符号表示)，机器中全部是小数0111101010100小数点默认在此位置(无需用符号表示)，机器中全部是整数定点数小数点的处理定点数：纯小数vs.纯整数(+245.25)十=0.24525103+11110101.0100011110101.0100浮点数00.1111010101002+800.111101010100

20100000

1000111101010100尾数?多少位;?精度指数/阶码?多少位；?数的范围符号小数点的处理浮点数：小数点位置的处理浮点数的指数又被称为阶码小数点如何处理(4)浮点数示例?-0.11101

2-1001

-1.1101

2-1010

S指数(8位)尾数(后23位)

-1.1101*2-1010

11010000000000000000000011101011加(27-1)后得到默认存在，但不存储(-127)+-01111111(-0,+0)+00000000(+127)++01111111+127(0)+00000000(127)+01111111(254)+11111110(-10)+-00001010(117)+01110101小数点的处理浮点数：是否还能提高精度S指数(8位)尾数(后23位)0-127+1270+127+254带正负号的指数不带正负号的指数将指数平移（均加上27-1）：-127--+127的范围，变为0—254，避免指数符号与整个数符号的混淆能否去掉指数的符号是否可多表示1位尾数？尾数(后52位)S指数(11位)S指数(8位)尾数(后23位)浮点数，32位表示单精度数(相当于科学计数法1.x×2y)(S为符号位，x为23位尾数,y为8位指数/阶码)浮点数，64位表示双精度数(相当于科学计数法1.x×2y)(S为符号位，x为52位尾数,y为11位指数/阶码)0-127+1270+127+254带正负号的指数不带正负号的指数小数点如何处理(3)单精度数/双精度数将指数平移：-127---+127的范围，变为0—254，避免指数符号与整个数符号的混淆小数点的处理浮点数：单精度数vs.双精度数数值的小数点的处理：定点数与浮点数小数点如何处理(5)小结?小数点的处理浮点数：小结—同学仍需要延展学习与思考一下深入：单精度和双精度数的表示范围与表示精度究竟是多少？深入：浮点数的0真的是0吗？例如“x==0”是真还是假？IEEE754有很多设计特色与细节细节：指数值全0或全1时表示什么含义（同学自主学习）小数点如何处理(5)小结?数值性信息表示为什么要学习数值性信息表示？高级语言编程时，为什么要声明变量的类型？例如：C语言占用存储单元数目-机器字长。不同类型的字长是不同的数值的表示方法，不同类型的数值表示是不同的不同类型的变量在处理时会有一些约束（例如与0比较时）

基本类型数值类型字符类型char整型浮点型短整型short整型int长整型long单精度型float双精度型double编程序时是否要注意这个问题呢？扩展第5讲机器是怎样表示文字声音与图像的

-编码与解码战德臣哈尔滨工业大学计算学部教学委员会主任国家教学名师信息表示[T]数值信息表示[T]非数值信息表示[K]进位制[K]机器数(有符号与无符号数)

[K]浮点数(小数)

[K]二进制/十进制/十六进制[K]进制转换[K]机器字长[ETP]减法转加法[K]机器数0的编码[QT]机器数的范围[EK]溢出及其逻辑判断[K]不同类型整数[EK]符号-阶码-尾数[QT]精度与范围[K]单精度与双精度[K]字符编码ASCII[EK]汉字编码[EK]内码(存储)[EK]外码(输入)[EK]字形码(输出)[ET]汉字处理过程[QT]不同编码的异同[K]Unicode[K]等长编码和变长编码[T]万事万物信息表示[KT]采样-量化-编码[T]语音信号编码[T]图像信号编码[K]位图[K]压缩编码[T]编码器（感知器）[T]编码(压缩)-解码(还原)信息变换(程序与算法)

[T]编码效率[K]压缩：有损与无损[T]视频信号编码[T]解码器（显示&输出）[EK]原码与补码[K]编码[K]知识

[T]思维

[S箭头]次序[Q]问题

[E]示例

[P]练习信息在计算机中的基本表示方法概览非数值性信息可以用编码表示编码：编码是以若干位数码或符号的不同组合来表示非数值性信息的方法，它是人为地将若干位数码或符号的每一种组合指定一种唯一的含义。例如：0----男，1----女再如：001--星期一；010--星期二；011--星期三；100--星期四；101--星期五；110--星期六；000--星期日编码的主要特征：

唯一性：每一种组合都有确定的唯一性的含义公共性：所有相关者都认同、遵守、使用这种编码

(人使用编码)：易于记忆/便于识认

(机器使用编码)：(1)有一定规律，便于机器解读；(2)利用0-1编码；(3)效率：存储效率(以最少的位数来编码最多的信息，最少的位数即占用最少的存储空间)和编码/解码算法的效率(编码存储与解码还原的效率)。

编码是典型的计算思维，利用0-1编码求解问题。为什么需要编码非数值性信息的表达手段--编码【示例】有一位雇主，雇佣一位员工为自己完成一项7天能够完成的任务。雇主答应总计支付一根金条作为报酬，员工要求每天支付1/7的工资，雇主答应了。问：雇主怎样在金条上切两刀，保证每天正好能支付员工1/7的工资。为什么需要编码编码是典型的计算思维22

21

207654

3

2

1D7D6D5D4

D3D2

D1111110101100011010001二进制编码求解问题是一种基本思维【思维】（1）切两刀，形成3块，即3个数字（3个数字都必须是1/7的倍数）（2）3个数字通过组合能否组合出1-7的每一个。（3）按2的幂次方来切：三块分别为20,21,22。（4）由2的幂次方可组合出1-7的每一个。ASCII码汉字编码Unicode编码关于编码先看几种常规的等长编码ASCII码是英文字母与符号的0-1型编码方法，是用7位0和１的不同组合来表示10个数字、26个英文大写字母、26个英文小写字母及其一些特殊符号的编码方法，是信息交换的标准编码。为处理方便，通常采用8位0和1编码，其中最高位为0。ASCII码：AmericanStandardCodeforInformationInterchange

B7B6B5B4B3B2B1B0

0xxxxxxx

00110001

01001110“1”“N”ASCII码英文字母符号编码--ASCII码ASCII码为什么要用8位来编码呢？每8位为一个字符，最高位为041H~5AH:“A”~“Z”61H~7AH:“a”~“z”30H~39H:“0”~“9”0AH:

换行符号LF0DH:

回车符号CRB6B5B4B3B2B1B0【1】字符发生器；【2】光栅/点阵-显示用内存编码与解码示例：键盘-ASCII-显示/输出

由ASCII码看键盘与显示器八位0/1码绑定语义：一个字母或数字信息表示规范/标准：ASCII码解码器：读取文件,8位分隔一个字符,将8位ASCII码转换成字符字型码送显示器显示信息采集:键盘(通过按键位置识别出所按的符号)编码器:将符号转换成ASCII码存储/8位一个字符信息：ASCII码0/1存储的文件(.txt)信息显示/打印A信息存储解析规则Wearestudents0101011101100101001000000110000101110010011001010010000001110011011101000111010101100100011001010110111001110100011100110/1串按8位分隔一个字符，查找ASCII码表映射成相应符号键盘的实现机理是怎样的？显示的实现机理是怎样的？应用程序接收的是操作系统传递过来的ASCII码“大”汉字在计算机内部采用汉字内码存储，汉字内码是一两字节且最高位均为1的0-1型编码。计算机内部由外到内由内到外b7

b6b5b4b3b2b1b0

b7

b6b5b4b3b2b1b0

用0和1编码汉字,每个汉字在计算机内部由2个字节表示00110100

01110111国标码1011010011110111(机)内码汉字内码汉字在机器内部的存储—汉字内码单字节操作系统—西文操作系统两字节操作系统—中文操作系统两字节能编码多少个汉字，够用吗？怎样区分一个字节是ASCII码还是汉字编码？汉字编码标准GB2312-80GBK-95GB18030-2000GB18030-2005怎样方便人们记忆？“型”输入码有若干：拼音码、字型码、区位码……拼音码：xing双拼码：x；其中,‘x’表声母x,而‘；’表韵母ing五笔字型码：gajf其中,g表字根“-”,a表开下的草字头,j表右侧立刀,f表下面土字计算机内部由外到内由内到外汉字外码是用键盘上的字母符号编码每一汉字的编码,

它使人们通过键入字母符号代替键入汉字汉字外码/输入码汉字如何输入到计算机中—汉字输入码/外码为什么会有那么多种汉字编码?汉字外码编码要解决什么问题?一个编码能否唯一对应一个汉字？怎样减少汉字输入的按键次数？“大”用0和1编码无亮点和有亮点形成字形信息,便于显示……汉字字形码是一种字模点阵码。也有不同的处理汉字点阵信息的编码，如向量编码等oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11ooooo1oo1111111111111111oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo111oooooooooooo11oo1oooooooooo11oooo1oooooooo11ooooo11ooooooo1ooooooo11ooooo1ooooooooo111o

11ooooooooooo1oo计算机内部由外到内由内到外大汉字字形码是用0和1编码无亮点和有亮点像素,形成汉字字形的一种编码,依据字形码通过显示器或打印机输出汉字。汉字字形码汉字如何显示和打印—汉字字形码怎样编码汉字的字形？字模点阵码汉字向量码/矢量码Unicode是可以容纳世界上所有文字和符号的字符编码方案，用数字0到0x10FFFF的范围来映射所有的字符。具体处理时，将前述唯一确定的码位按照不同的编码方案映射为相应的编码，有UTF-8、UTF-16、UTF-32等几种编码方案。Unicode：b15b14b13b12b11b10b9b8b7b6b5b4b3b2b1b0【UTF-8】是以字节（8位比特）为单位对Unicode字符进行编码，对不同范围的字符使用不同长度的编码：（1）0x000000至0x00007F区间的符号（此区间的字符为标准的ASCII码字符），用一字节编码，即0x00至0x7F，将高位的0均省略，与标准的ASCII码完全相同。（2）0x000080至0x0007FF区间的符号，用两字节编码，即110xxxxx10xxxxxx。（3）0x000800至00FFFF区间的符号(中文汉字通常位于此区间),用三字节编码1110b15b14b13b1210b11b10b9b8b7b6

10b5b4b3b2b1b0。（4）其它区间则用四字节编码。【UTF-16】是以字（16位比特）为单位对Unicode字符进行编码，在0x000000至0x00FFFF区间的符号（国标汉字和ASCII码字符通常位于此区间）其后16位就是其UTF-16编码。【UTF-32】是以双字（32位比特）为单位对Unicode字符进行编码。

“大”的Unicode码为0101100100100111。则： “大”的UTF-8编码为111001011010010010100111，即0xE5A4A7。

“大”的UTF-16编码为0101100100100111，即0x5927。

“灯”的Unicode码为0111000001101111。则：

“灯”的UTF-8编码为111001111000000110101111，即0xE781AF。

“灯”的UTF-16编码为0111000001101111，即0x706F。Unicode编码世界所有字符/文字的统一编码：UnicodeGB18030和Unicode能对应吗？怎样对应？关于编码再看一种不等长编码（霍夫曼编码）—如何提高编码效率霍夫曼编码是依据对象出现的概率分布来确定对象编码长度的一种变长编码方式，在保证编码不存在二义性的前提下，实现总体编码长度的最小化。对出现概率大的对象赋予较短的编码，而对出现概率小的对象赋予较长的编码。采00芣010苡011薄100言101之110掇11100袺11110有11111捋111010襭111011采0000芣0001苡0010薄0011言0100之0101掇0110袺0111有1000捋1001襭1010采采芣苡薄言采之采采芣苡薄言有之

采采芣苡薄言掇之采采芣苡薄言捋之

采采芣苡薄言袺之采采芣苡薄言襭之等长编码：全诗共48字，不重复汉字有11个，需采用4位二进制编码，总长度为4×48=192比特。不等长编码(霍夫曼编码)：全诗48字可用143个比特完成编码，平均码长为

2.979。这个编码是怎样产生的呢？霍夫曼编码【示例】关于编码采采芣苡薄言采之采采芣苡薄言有之

采采芣苡薄言掇之采采芣苡薄言捋之

采采芣苡薄言袺之采采芣苡薄言襭之霍夫曼编码：(1)计算每个汉字出现的概率。(2)按照如下规则进行合并相加：即不断将全表中尚未使用的最小的两个概率数字求和归并，直到得到100%。(3)反向依据归并路径编码。从右往左，蓝色路径编码0，红色路径编码1，走完路径即可得到每一个汉字的编码。00000000001111111111是否还能提高编码效率—压缩编码关于编码采采芣苡薄言采之采采芣苡薄言有之

采采芣苡薄言掇之采采芣苡薄言捋之

采采芣苡薄言袺之采采芣苡薄言襭之等长编码需4位编码总计需192比特霍夫曼不等长编码总计需143比特是否还能更少？重复短语，若建立字典：Ａ：采采芣苡

薄言Ｂ：采Ｃ：之

采采芣苡

薄言D：

有

Ｅ：掇Ｆ：捋Ｇ：袺Ｈ：襭Ｉ：之则全诗可以从48个汉字字符压缩为13个英文字符：ＡＢＣＤＣＥＣＦＣＧＣＨＩ再用霍夫曼编码存储，则仅需要

37个比特0000

0001

1

0010

1

0011

1

0100

1

0101

1

0110

0111信息绑定

协议

协议编码器/协议解码器(研究对象的)信息绑定语义的方法：0/1码绑定或字母符号绑定--何种语义。一般而言，“协议”是为交流信息的双方(计算机)能够正确实现信息交流而建立的一套规则、标准或约定。(研究对象的)协议/语言/标准编译器