计算机科学方法论

文坤梅博士讲师E-Mail:[e-mail]智能与分布计算实验室IntelligenceandDistributedComputingLab计算机科学与技术方法论—思想与方法2020/1/302关于本课程关于“四年之内学什么？”的课程学习方法老师：导读课堂学习与自学的结合要求到课，边看、边写、边思考课后看书消化理解不深入？放一放，四年内自然求解重点把握学科特点、学科形态、历史、发展趋势、方法、知识组织结构和分类体系等2020/1/303课程的目的对计算机科学的误解——这门学科的主要工作就是编程和游览网络本课程的目的——寻求一种统一的思想来认知计算机学科的本质对计算机学科进行系统化和科学化的描述关注在计算学科中具有共同的、本质特征的内容对将来四年学习内容有一个框架性的了解2020/1/3041.董荣胜、古天龙：计算机科学与技术方法论，人民邮电出版社，2002.92.黄德修主编(徐重阳、卢正鼎、朱光喜、孙德宝、张天序等参编)：信息科学导论，中国电力出版社，2001.53.赵致琢:计算科学导论(第三版),科学出版社,20044.(J.G.)(Brookshear)布鲁克希尔(美国)计算机科学概论.译本清华大学出版社(第9版),2007教材与参考:2020/1/305课程评分方法平时成绩+期末考试=总评开卷考试2020/1/306课程内容1.计算学科发展沿革及二维定义矩阵2.计算学科中的科学问题3.计算学科中的三个学科形态4.计算学科中的核心概念5.计算学科中的数学方法6.计算学科中的系统科学方法2020/1/307什么是计算学科？P22计算学科是对描述和变换信息的算法过程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。它来源于对算法理论、数理逻辑、计算模型、自动计算机器的研究，并与存储式电子计算机的发明一起形成于20世纪40年代初期。2020/1/308计算学科的研究包括从算法与可计算性的研究到根据可计算硬件和软件的实际实现问题的研究。科学与工程技术两方面，两者互为作用，高度融合。计算学科的根本问题是:什么能被(有效地)自动执行2020/1/309计算机的历史作用：•开辟了一个新时代——信息时代•孵化了一类新产业——信息产业•创立了一门新学科——计算机科学与技术•形成了一种新文化——计算机文化把人类社会从工业时代推向信息时代，从物质产业时代推向信息产业时代，将极为深刻地改变人们的生产方式、生活方式与学习方式。2020/1/3010第1章计算学科发展沿革及二维定义矩阵•追求一种会算、会听、会看、会说、会想的工具•计算学科的根本问题是：什么能被（有效地）自动执行•与理论、工业（制造水平）、商业（应用水平）的发展同步一、发展沿革2020/1/3011第1章计算学科发展沿革及二维定义矩阵1、计算机的发展线索（1623-1952）•手指、结绳、算筹、算盘•1623年，什卡尔特（Schikad），第一个演算机，加、乘法•1641年，帕斯卡（Pascal），齿轮，加、减法计算器•1672年，莱布尼兹（G.W.Leibniz），手摇计算机奠基•1820年，托马斯（C.Thomas），生产100台演算机•1842~1848年，巴贝奇（C.Babbage），差分机和解析机，提出程序控制计算的思想，助手Ada一、发展沿革2020/1/3012•1946年，宾夕法尼亚大学莫尔学院电工系，第一台通用电子数字计算机，ENIAC(ElectronicNumericalIntegratorAndCalculator)••占地170平米，重30吨，长30.48米，宽1米，30个操作台，约相当于10间普通房间的大小，耗电量150千瓦，造价48万美元•主要元器件：电子管（二极管和三极管），它包含了17,468真空管7,200水晶二极管,1,500中转,70,000电阻器,10,000电容器，1500继电器，6000多个开关•每秒执行5000次加法或400次乘法，是继电器计算机的1000倍、手工计算的20万倍缺点：未实现babbage关于“程序控制计算的思想”2020/1/3013•1945~1952年，冯·诺依曼（Von.Neuman），第一台存储程序的通用电子数字计算机EDVAC（ElectronicDiscretVariableAutomaticComputer）为现代计算机奠定了基础•1951年，威尔斯（M.V.Wilkes），批量生产EDSAC(ElectronicDelayStorageAutomaticComputer)，面包公司投资2020/1/3014•康托尔（G.Cantor,1845-1918）集合论P98•罗素（B.Russell）悖论：s={xxs}P19•布尔（G.Boole）代数P103•希尔伯特（D.Hilbert）纲领P20•图灵（A.M.Turing，1912-1954）机（20世纪30年代后期）P21P62可计算性=图灵可计算性任一过程是能行的（能够具体表现在一个计算中），当且仅当它能够被一台图灵机实现2、理论奠基2020/1/3015计算学科中的诺贝尔奖——图灵奖（1966）•1912年出生于英国伦敦，1954年去世•1936年发表论文“论可计算数及其在判定问题中的应用”，提出图灵机理论•1950年发表论文“计算机与智能”，阐述了计算机可以具有智能的想法，提出图灵测试•1966年为纪念图灵的杰出贡献，ACM设立图灵奖第一位华人图灵奖获得者——姚期智2020/1/30163、第一代——第四代计算机的主要特征第一代1946-1957第二代1957-1964第三代1964-1972第四代1972-至今逻辑元件电子管晶体管中小规模集成电路大规模与超大规模集成电路存储器延迟线、磁鼓、磁芯磁芯、磁带、磁盘磁芯、磁盘、磁带半导体、磁盘、光盘软件机器语言汇编语言高级语言管理程序操作系统结构化程序设计数据库、软件工程、程序设计自动化应用科学计算数据处理工业控制科学计算系统模拟系统设计大型科学计算科技工程各项域事务处理、智能模拟、大型科学计算，普及到社会生活的各方面年代特征项目2020/1/30174、新型计算机系统：•第五代计算机（人工智能计算机）•面向科学计算、工程设计、模拟仿真的SIMD、MISD、MIMD并行多机系统，高性能计算机•面向人工智能求解的LISP机、归约机、逻辑推理机•量子计算机•（分子计算机）、DNA芯片与生物计算机•光计算机2020/1/3018例：“深蓝”战胜卡斯帕罗夫•IBM，256（32node*8），2亿步/秒•1997.5.两胜一负三平•“深蓝”主管谭崇仁等.70万美元，卡40万，IBM5000万广告收益2020/1/3019计算思维美国卡内基梅隆大学（CMU）JeannetteM.Wing(周以真)教授的《ComputationalThinking（计算思维）》计算思维是建立在计算过程的能力和限制之上的，不管这些过程是由人还是由机器执行的。计算思维涉及运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为。计算思维涵盖了反映计算机科学之广泛性的一系列思维活动。把计算机这一从工具到思维的发展提炼到与“3R（读、写、算）”同等的高度和重要性，成为适合于每一个人的“一种普遍的认识和一类普适的技能”。“一个人可以主修计算机科学，接着从事医学、法律、商业、政治，以及任何类型的科学和工程，甚至是艺术工作。”2020/1/3020CDI简介“计算思维”这一概念在2006年3月提出后，引起美国科技界的高度重视，并得到美国国家科学基金会（NSF）重大基金资助计划CDI（Cyber-EnabledDiscoveryandInnovation，Cyber能够实现的科学发现与技术创新）的支持。该计划涉及NSF所有学科部门，强调以计算思维为核心，得到NSF所有学科部门理事会的赞同，任务书2007年9月28日公布，计划五年完成，支持额度为75000万美元，其中，2008年度预算经费为5200万美元，以后逐年增加。该计划旨在使用计算思维（特别是在该领域产生的新思想、新方法）促进美国自然科学和工程技术领域产生革命性的成果。而所谓的计算思维概括起来包括：计算的概念、方法、模型、算法和工具。计算思维正在深刻的影响美国创造新知识与应用新知识的能力，该计划通过“计算思维”在富有挑战性的自然科学与工程，以及教育等学科领域的应用来进一步扩大这种影响。最终CDI的研究成果，将使人们的思维方式产生转变，这种转变反映在对美国自然科学与工程，以及社会经济与技术等学科领域创新问题的理解上，这种变化的应用将进一步保持美国在自然科学与工程等领域所具有的世界领先地位，并进一步提高美国人民的生活质量。CDI网址：计算机模式的演进MainframeComputing（主机计算）Client/Server（C/S模式）Client/Browser/WebServer/DBserver（B/S模式）Client/Clusters（集群计算）Client/Networking（网络计算）MobileComputing（移动计算）2020/1/3022GridComputing（网格计算）Peertopeer（对等计算）WearableComputing（可穿戴计算）PervasiveComputing（普适计算）→Client/VirtualServerEnvironment（虚拟服务计算）Client→p4c(personal,computer,Communication,Customer,Control)SocialComputing（社会计算）CloudComputing（云计算）2020/1/3023对等计算P2P是peer-to-peer的缩写，P2P就是人可以直接连接到其他用户的计算机、交换文件，而不是像过去那样连接到服务器去浏览与下载。P2P另一个重要特点是改变互联网现在的以大网站为中心的状态、重返“非中心化”，并把权力交还给用户。2020/1/3024谁在“忽悠”谁？网格计算：学术界热、企业界不热云计算：企业界热、学术界不热2020/1/3025网格计算：依托专网或互联网，将处于不同地域、不同领域的多个计算机资源组织起来，统一调度，组成一台虚拟的“超级计算机”，完成一个共同的任务，如一个要求大量计算处理周期和大量数据的科学计算问题。Manyforone2020/1/3026云计算：互联网上某些节点强大的信息资源，包括存储资源、计算资源、软件资源、数据资源、管理资源，通过云计算以互联网上的服务方式，变成广大用户动态、可伸缩的虚拟资源，为用户所用。强调需求驱动、用户主导、按需服务，即用即付，用完即散，不对用户集中控制，用户不关心服务者在什么地方。Oneformany2020/1/3027云计算的应用网络环境下信息资源的感知、存储、处理、发布、传播和租用；网络化数据挖掘：用户主导、面向领域的跨系统、跨媒体、即时定制的服务或者服务组合。2020/1/3028资源共享虚拟计算网格计算和云计算的相同点2020/1/3029网格计算云计算并行计算为主：依托网络将跨地域的计算机组织起来并行作业，但需要通过调度系统将作业分解到各个不同的物理节点去。集群计算为主：节点自主、自治，节点之内常常是集群计算屏蔽异构：用中间件屏蔽异构系统，使用户面向同一环境，实现资源共享承认异构：承认节点在原理、规模、能力上的差异性，依靠互操作来实现节点之间的资源共享完成一次性特定任务：要完成的任务是预先设定的完成持久性多样化服务：中心提供计算、存储等资源，用户利用云计算按需聚合、柔性重组，获取持久、个性化服务，协作式运营：带宽保证、性能保障商业式运营：尽力而为的服务、按租使用，按用付费，多租赁，即用即散确定的交互：按规定要求和