学计算机基础课件分解

1、Chapter 9高 级 主 题CS, ZJU10/11/2022Chapter 9高 级 主 题CS, ZJUOverview高性能计算人工智能虚拟现实自动机理论可计算理论信息安全信息社会Overview高性能计算9.1 高性能计算高性能计算HPC ，High Performance Computing是计算机科学的一个分支，旨在研究复杂体系结构、算法和开发相关软件，致力于开发高性能计算机并行计算分布式计算集群计算云计算9.1 高性能计算高性能计算HPC ，High Perfor1.并行计算并行计算（Parallel Computing）传统意义上是指计算资源应包括一台配有多处理机（并行处理

2、）的计算机具有超级计算能力的计算机系统，这是获得高性能计算的重要手段今天，并行计算也是指一个通过网络连接的计算机群，或者两者结合使用在过去很长一段时间内，并行计算几乎就是HPC的代名词 1.并行计算并行计算（Parallel Computing）并行计算1980年代，并行计算机系统（多处理器同时对一组数据进行同一个操作）达到了鼎盛时期90年代，超大规模并行计算（Massively Parallel Processing，MPP）开始占主导地位对称多处理器（Symmetric Multi-Processor，SMP）结构的并行系统1993年成立的Top500机构开始进行全球高性能计算机系统排名并

3、行计算1980年代，并行计算机系统（多处理器同时对一组数据并行计算据2005年11月Top500公布的数据排名第一的Blue Gene /L系统IBM公司处理速度达到280.6 TFlop/s（每秒万亿次浮点运算），系统有131,072个处理器我国曙光公司生产的曙光4000A超级计算机，在2004年Top500中跻身前十名，标志着我国高性能计算进入世界先进水平中国联想集团生产的深腾6800高性能计算机系统也达到了10TFlop/s级并行计算据2005年11月Top500公布的数据曙光5超级计算机 百万亿次/秒曙光5超级计算机 百万亿次/秒%中国天河计算机日本“京”计算机%中国天河计算机日本“京

4、”计算机世界超级计算机排名据国外媒体报道，在两年一次的世界上最强力的超级计算机排名中,中国仍然占据着榜首排名中的所有500台超级计算机，总的计算能力达到每秒250千万亿次的浮点运算速度，其中排名前17的超级计算机的计算能力就占了一半，并且有31台超级计算机的计算速度达到了1千万亿次以上世界超级计算机排名据国外媒体报道，在两年一次的世界上最强力的天河二号2013.11.20：“天河二号”超级计算机的每秒33.86千万亿次的浮点计算能力，是第二名美国泰坦超级计算机接近2倍遗憾只有18的CPU是自主知识产权（超算CPU非常多）其余的是购买的进口产品，但是值得关注的是采用了国产麒麟系统天河二号2013

5、.11.20：“天河二号”超级计算机的每秒3天河二号天河二号IBM公司64枚处理器芯片的计算机主板IBM公司64枚处理器芯片的计算机主板2.分布式计算 分布式系统研究组件的异构性、开放性、安全性和可伸缩性、并发性、透明性及故障处理分布式计算的主题是多种多样的，包括分布式硬件结构和分布式软件设计一个分布式系统是为解决单个问题而紧密结合在一起工作的多处理机的集合Or，一个分布式系统可能意味着一个由地理上分散的、各自独立的计算机组成的网络，这些计算机连接在一起以实现对不同资源的共享2.分布式计算 分布式系统研究组件的异构性、开放性、安全分布式计算分布式系统这个词义方面的混乱源于对物理的分布和逻辑的分

6、布的区分分布式技术和网络技术之间的相互渗透和交融更多的观点认为，分布式系统：逻辑或物理分布的部件或机器，以网络连接的形式组成的一个（计算机）系统并行意义的根本是将两台以上的机器（处理器）连接起来解决一些计算问题 分布式计算分布式系统这个词义方面的混乱3.集群计算集群计算（Cluster Computing）也是基于并行系统和网络的它作为并行计算和网络技术在高性能计算机体系结构中最为成功的集成和运用，也是目前性价比最好的系统在2005年11月的Top500中，集群系统占到了70以上3.集群计算集群计算（Cluster Computing）集群系统集群系统是以高速网络（如光缆局域网）连接起来的高性

7、能工作站或微机组成集群系统在运行中像一个统一的整合资源，所有节点使用单一的界面本质上说，集群是一种并行或者分布式系统 集群的同义词是工作站网络（Network of Workstation，NOW） 集群系统集群系统是以高速网络（如光缆局域网）连接起来的高集群系统集群系统最廉价的高性能计算机系统主要原因：（1）微机或工作站的性能越来越强（2）LAN特别是高速光纤LAN延迟越来越小，网络带宽增加（3）工作站网络易于集成，和现有的网络更容易整合（4）相比大型并行系统，微机或工作站的开发工具更成熟，而且更易于被大批专业人员掌握（5）工作站和微机系统标准化程度高（6）集群系统采用的平台便宜而且易于获得

8、，如Unix、Linux和Windows Server都可以作为集群系统的平台集群系统集群系统最廉价的高性能计算机系统4.云计算分布式计算、网格计算、普适计算发展而来云计算（无处不在的计算）云因特网效用计算计费，像电网的用电付费云产业（云软件、云平台、云设备）计算机基础科学184.云计算分布式计算、网格计算、普适计算发展而来云计算（9.2人工智能人工智能作为计算机研究的重要领域，已经成为计算机科学和技术发展的一个目标。图灵测试-计算机能够象人一样思考吗 ？中国屋思考实验-反驳图灵测试推理：知识表达语义网络搜索树-深蓝9.2人工智能人工智能作为计算机研究的重要领域，已经成为1.图灵测试:“计算机

9、能够象人一样思考吗？”图灵测试黑盒测试测试者和被测者之间用幕布隔开，发问者不知道对面回答问题的人是谁图灵测试本身也被人提出了疑问 中国屋思考试验塞尔认为：机器不能思考，它只是一个工具，符号识别不能够满足语义，只有大脑能引起思考 现在还没有机器通过图灵测试，关于机器思考的争论还在持续，但计算机科学家并没有停止或者放弃对AI的研究，相反地这种争论促进了AI的研究进展1.图灵测试:“计算机能够象人一样思考吗？”图灵测试黑盒学计算机基础课件分解2. 推理：知识表达人工智能一直在研究计算机的推理能力 人类智能是基于行为的进化而不是复杂程序的执行 解决问题需要有效信息，有效信息还需要有效表达 计算机使用符

10、号语言科学家们试图在人类的自然语言和机器的符号处理之间找到一种关系，使得机器能够具有人类的推理能力语义网络是一种知识表达法定义它非常困难相比语义网络，搜索树易于实现 2. 推理：知识表达人工智能一直在研究计算机的推理能力 3.专家系统一种智能计算机软件系统，像领域专家那样向用户提供解决问题的方法四个要素：应用于某专门领域 拥有专家级知识 能模拟专家的思维 能达到专家级水平 3.专家系统一种智能计算机软件系统，像领域专家那样向用户提供4.神经网络由大量处理单元（神经元、处理元件、电子元件、光电元件等）广泛互连的网络高度非线性的超大规模的连续时间动力系统具有大规模并行分布处理及学习能力具有非线性动

11、力系统的共性具有不可预测性、吸引性、耗散性、不可逆性、高维性、广泛连接性和自适应性等特点4.神经网络由大量处理单元（神经元、处理元件、电子元件、光电神经网络25人工神经元模型 其中： xi为输入信号，ui表示神经元的内部状态，i为阈值。si为外部输入信号，si可对神经元ui进行控制 神经网络25人工神经元模型 其中： xi为输入信号，ui表示5.机器人综合了人和机器特长的一种拟人化的电子机械装置，它既有人对环境状态的快速反应和分析判断能力，又有机器可长时间持续工作、精确度高、抗恶劣环境的能力“大脑”：嵌入式处理器机器人视觉系统接近觉传感器机器人语言265.机器人综合了人和机器特长的一种拟人化的

12、电子机械装置，它既Robot机器人装有所需要的传感器视觉传感器，为机器人移动进行导航接近觉系统，探测自身与周围物体之间相对位置和距离的传感器机器人语言 ，实现与人的联系智能机器人在研究阶段 Robot机器人装有所需要的传感器6.自然语言处理语音识别自然语言理解语音合成最新的进展：IBM公司的智能计算机“沃森”6.自然语言处理语音识别自然语言处理尝试使用自然语言和计算机对话IBM的Voice系统 依据规则进行处理 最困难的是自然语言的理解 自然语言特有的二义性 理解单词的意义需要根据上下文 理解自然语言，人类需要依赖他们所具有的知识和联想记忆力 自然语言理解需要进行语法分析、语义分析和上下文分析

13、自然语言处理研究的另一个方面是整个文件而不是一个句子 机器翻译 ？自然语言处理尝试使用自然语言和计算机对话学计算机基础课件分解7.人工智能的研究困难图灵机的启示计算机博奕的困难 自动定理证明及其局限 模式识别的困惑 自动程序设计的困难 317.人工智能的研究困难图灵机的启示319.3虚拟现实虚拟现实（VR）或称虚拟环境（VE） ：由计算机生成的、使人具有身临其境感觉的计算机模拟环境，它是一种全新的人机交互系统虚拟环境能对介入者人产生各种感官刺激，如视觉、听觉、触觉、嗅觉等，同时人能以自然方式与虚拟环境进行交互操作VR强调作为介入者人的亲身体验，要求虚拟环境是可信的，即虚拟环境与人对其理解相一致

14、9.3虚拟现实虚拟现实（VR）或称虚拟环境（VE） ：由虚拟现实虚拟现实的概念模型可看做“显示检测”模型显示是指虚拟环境系统向用户提供各种感官刺激信号，包括光、声、力、嗅、味等各种刺激信号检测是指虚拟环境系统监视用户的各种动作，检测并辨识用户的视点变化，头、手、肢体和身躯的动作虚拟现实虚拟现实的概念模型可看做“显示检测”模型9.4自动机理论自动机理论是对抽象（计算）机和它们能解决的问题的研究。多种自动机模型：有限自动机：基于离散系统的抽象数据模型图灵机：图灵提出的一个自动机模型，用于解释机器的计算能力及其局限性。是算法研究的重要工具细胞自动机：离散模型，在自动机理论、数学及理论生物学方面有其研

15、究和应用。源于科学家对生物细胞的自我复制的模仿，冯诺依曼提出。9.4自动机理论自动机理论是对抽象（计算）机和它们能解决的有限自动机基于离散系统的抽象数据模型计算机中的加法器、计数器、操作系统等活动过程都是离散系统的实例有限自动机主要研究系统的综合和分析，给出具体的功能要求，设计能够实现其功能的有限自动机，分析有限自动机的功能描述、时间复杂性和故障传播与检测等有限自动机基于离散系统的抽象数据模型9.5可计算理论可计算问题计算机能做什么，计算机不能做什么？可计算函数哥德尔数计算复杂性停机问题9.5可计算理论可计算问题1.可计算函数计算是与算法关联的，可计算理论算法理论算法实质的研究对算法概念的精确

16、化研究把计算机看作抽象的机器，算法就是执行的程序可计算问题能够被抽象计算机计算其值的问题可计算函数是其中研究的一个方面如果函数能够通过算法得到函数值，则称函数是可计算的(Computable)1.可计算函数计算是与算法关联的，可计算理论算法理论2.哥德尔数哥德尔（Kurt Godel）是继牛顿之后的最伟大的数学家和逻辑学家哥德尔不完备定理哥德尔数程序设计语言的符号被能够分配一个对应的无符号数，这个数就是哥德尔数计算机语言是复杂的，已经证明：只要简单的3条语句就可以描述所有的程序Incr(加1运算)、decr(减1运算)、while(循环)转换：程序哥德尔数2.哥德尔数哥德尔（Kurt Gode

17、l）是继牛顿之后的最伟哥德尔数 程序设计语言的符号能够被分配一个对应的无符号数符号十六进制数符号十六进制数符号十六进制数符号十六进制数004488whileC115599D2266incrAE3377decrBXF1程序转换为哥德尔数 例：incr(X) incrX AFH 175 2哥德尔数转换为程序 例：3058 BF2H decrX2 decr(X2) 哥德尔数 程序设计语言的符号能够被分配一个对应的无符号数符哥德尔数 P.1831程序转换为哥德尔数 while x1 /如果x1不等于0，则执行下面的循环decr x1 incr x2 CF1DBF1AF2EH14232916700974

18、2哥德尔数转换为程序 例：13622270CFDBFEH while xdecr x / 将变量x置0哥德尔数 P.1831程序转换为哥德尔数阿克曼函数递归函数，计算机中许多算法都可以归结为递归问题原始递归函数可以通过有限次的、可计算的函数，在原始递归函数和某些程序设计语言之间存在对应关系.阿克曼函数是一种非原始递归函数，使用两个自然数作为输入值，输出也是一个自然数，输出值随着输入值增大而急剧增大。 n+1 若m=0A(m,n)= A(m-1,1) 若m0且n=0 A(m-1,A(m,n-1) 若m0且n0双重递归阿克曼函数递归函数，计算机中许多算法都可以归结为递归问题3.计算复杂性复杂性的度

19、量定量描述算法的复杂程度完成计算（算法）所需要的时间和存储器资源大O表示法：主要考虑其数量级而不是精确值对于n个输入的算法 C，复杂性表示为： f(n,C)=n2+2n当n足够大时2n可忽略O(n)表示有n个输入的算法，执行 n 次运算O(n2)表示有n个输入的算法，执行 n2 次运算3.计算复杂性复杂性的度量计算复杂性大O表示法选择法排序，复杂度 O(n2) n个数排序的次数为 n(n-1)/2，即0.5n2-0.5n快速排序法，复杂度为 O(nlogn)比较 n=1 000 000，使用运算速度为每秒100万次的计算机O(logn)O(n)O(n2)Times: 6 s Times: 1

20、000 000 s Times: 1012 s 1s277h计算复杂性大O表示法Times: 6 s 1s277h计算复杂性在计算机科学领域，将问题分为：不可解问题的确无解，如停机问题虽然有解，但时间复杂度很高可解问题P问题（多项式问题）NP问题（非确定性多项式问题）计算复杂性在计算机科学领域，将问题分为：计算复杂性P问题有多项式的时间解可在多项式表达的有限时间内解决算法的复杂度大O值是输入数量n的多项式如：O(n2) O(nlogn)P问题包含大量的已知的自然问题如：判断素数、计算最大公约数、计算PI值、计算e值、排序问题、二维匹配问题P问题是是可解的，是区别问题是否可以被计算机求解的一个重

21、要标志计算复杂性P问题计算复杂性P问题算法的复杂度不能使用确定的多项式来表示通常它们的时间复杂度是指数变量如：O(10n)O(n!)最短路径问题，O(2n)，n是途经城市的数量通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解(Intractable)的问题计算复杂性P问题4.停机问题（Halting problem）停机问题：是否有一个程序T能够预测任何一个程序的执行是否会停机结论：没有一个程序T能够测试用哥德尔数表示的程序是否会终止，也就是说，预测程序是否被终止是不可能的停机问题是不可计算的while x incr x;如果存在一个停机函数，那么这个函数是不可计算的4.停机问题

22、（Halting problem）停机问题：是否9.6 信息安全信息安全工程 研究各种防止安全事故的发生和各种攻击、入侵事件的发生。前者需要的是一种有效的组织管理进制，而后者的主要研究内容是安全协议。 核心：安全协议的研究建立有效的组织机制9.6 信息安全信息安全工程计算机与安全威胁计算机安全的主要因素：灾难系统缺陷病毒黑客攻击等 计算机与安全威胁计算机安全的主要因素：1.计算机安全工程计算机和网络安全所依赖的技术基础主要是密码学、可靠性技术、安全印刷和认证、审计等 安全工程的本质在于了解系统的潜在威胁，然后选择适当的措施来控制这些威胁因素 安全工程的核心是安全协议的研究计算机安全工程中的重要

23、基础是口令 1.计算机安全工程计算机和网络安全所依赖的技术基础计算机系统风险硬件风险容错的计算机系统Fault-tolerant Computer System软件风险软件测试Software Testing计算机系统风险硬件风险2.计算机病毒计算机病毒(Computer Virus) “编制或者在计算机程序中插入的破坏计算机功能或者破坏数据，影响计算机使用并且能够自我复制的一组计算机指令或者程序代码。” 中华人民共和国计算机信息系统安全保护条例这种程序代码或指令段具有传染性、破坏性、潜伏性以及自我复制能力，类似于微生物学中的病毒故而得名。2.计算机病毒计算机病毒(Computer Virus

24、) 病毒种类常见的计算机病毒：宏病毒一种寄存在文档或模板的宏中的计算机病毒 寄生型病毒一种感染可执行文件的程序 蠕虫病毒能够自我复制的计算机程序，虽然它并不感染其他文件，通过分布式网络来扩散传播特定的信息或错误，使网络流量大大增加进而造成网络服务遭到拒绝并发生死锁黑客病毒一种能够散布病毒蠕虫或其他恶意程序的计算机程序。 25/53病毒种类常见的计算机病毒：25/533.反病毒软件的机制反病毒软件发展历程：简单的病毒扫描（Scan）程序启发式的扫描程序行为陷阱全方位的保护主要技术：寻找病毒的特征码 3.反病毒软件的机制反病毒软件发展历程：4.黑客现在黑客常指专门利用计算机犯罪的人防御手段：实体安

25、全防范，包括机房、网络服务器、线路和主机等对系统进行全天候的动态监控加强基础安全防范，主要包括授权认证、数据加密和信息传输加密，防火墙设置等4.黑客现在黑客常指专门利用计算机犯罪的人5.防火墙为了防止非法访问而设置的“屏障”；通过硬件实现；通过软件实现；5.防火墙为了防止非法访问而设置的“屏障”；9.7 信息社会社会影响自第一台计算机诞生至今，它为社会带来了巨大的经济效益，同时也给人类社会生活带拉了现实的和潜在的问题。9.7 信息社会社会影响1.社会问题对于个人隐私的威胁计算机安全与计算机犯罪知识产权保护自动化威胁传统就业信息时代的贫富差距依赖复杂技术带来的社会不安全因素1.社会问题对于个人隐

26、私的威胁2.计算机与法律计算机犯罪因计算机技术和知识起了基本作用而产生的非法行为（美国司法部）在自动数据处理过程中任何非法的违反职业道德的未经批准的行为（欧洲经济合作与发展组织）2.计算机与法律计算机犯罪计算机犯罪与法律 我国刑法认定的几类计算机犯罪包括以下几种（1）违反国家规定，侵入国家事务、国防建设、尖端科学技术领域的计算机信息的行为；（2）违反国家规定，对计算机信息系统功能进行删除、修改、增加、干扰，造成计算机信息系统不能正常运行；（3）违反国家规定， 对计算机信息系统中存储处理或者传输的数据和应用程序进行删除、修改、增加操作；（4）故意制作和传播计算机病毒等破坏性程序，影响计算机系统正

27、常运行计算机犯罪与法律 我国刑法认定的几类计算机犯罪包括以下几种3.隐私保护隐私权是指公民享有的个人生活不被干扰的权利和个人资料的支配控制权在信息网络时代，个人隐私权侵犯六种情形侵害个人通信内容收集他人私人资料赚钱散播侵害隐私权的软件侵入他人系统以获取资料不当泄露他人资料网上有害信息3.隐私保护隐私权是指公民享有的个人生活不被干扰的权利和个人软件版权和自由软件知识产权（Intellectual Property）是指由个人或组织创造的无形资产，依法享有专有权利盗版软件的非法复制版权的合理性自由软件使用者可以自由的运用，拷贝，分发，学习，改变改善该软件 共享软件 软件版权和自由软件知识产权（In

28、tellectual Pr1.软件版权及其保护盗版软件的非法复制会受到法律诉讼“软件版权”赋予一个程序作者唯一享有复制、发布、出售、更改软件等诸多权利许可证（License）保护：软件许可证是一种具有法律效力的合同商业软件版权保护享有许可证保护1.软件版权及其保护盗版软件的非法复制2.自由软件软件版权合理吗？最早的软件“随机销售”，不存在版权FreeBSD最早的自由软件伯克利发布第一个免费的Unix版本又叫“源代码开放软件”，GUN/Linux全球前500名超级计算机中，有91%运行Linux自由软件和LINUX无处不在2.自由软件软件版权合理吗？自由软件和LINUX无处不在3.共享软件又叫“试用软件”，微软最早提出介于商业软件和自由软件之间的一种形式也受著作权保护发行方式：复制品可以通过网络在线服务、BBS或者从一个用户传给另一个用户等途径自由传播测试