计算机科学与技术方法论ch01

计算机科学与技术方法论主讲教师：董荣胜、钟艳如、陈光喜、李凤英专题讲座：古天龙桂林电子科技大学“计算机科学与技术方法论”课程组前言对计算机科学的误解——这门学科的主要工作就是编程和游览网络本课程的目的——寻求一种统一的思想来认知计算机学科的本质；对计算机学科进行系统化和科学化的描述关注在计算学科中具有共同的、本质特征的内容上。第1章绪论要解决学科的认知问题，必须有一套科学的方法——有助于人们对学科认识的逻辑化、程序化、理性化和具体化。1984年7月——美国计算机科学与工程博士单位评审部的领导们，在犹他州会议上对计算认知问题进行了讨论。促使ACM和IEEE-CS联合攻关组，开始用新的思维方式来理解计算学科。计算机科学与技术方法论的建立——借鉴了数学的公理化思想1.1方法论产生的历史背景1943年——英国的一台名叫“巨人”（Colossus）的计算机就投入了运行，用于译解德国密码，1970年之前一直保密1946.2.14——美国宾夕法尼亚大学研制成功的ENIAC（ElectronicNumericalIntegratorandCalculator，电子数字积分器和计算器）是世界第一台多功能、全电子数字计算机。早期关于“计算机科学”名称的争论最早的计算机科学学位课程——美国普渡大学于1962年开设的斯坦福大学——开设了同样的学位课程。计算机科学——这一名称，在当时引起了激烈的争论。当时的计算机主要用于数值计算，使用计算机仅仅是编程问题，没有必要设立学位很多人还认为，计算机从本质上说是一种职业而非学科。ComputingasaDiscipline的主要成果第一个重大问题第一次给出了计算学科一个透彻的定义(ExistenceProof)第二个重大问题未来计算教育问题，整个学科核心课程详细设计第三个重大问题整个学科综述性导引（导论）课程的构建另外给出了计算学科二维定义矩阵的定义及相关研究内容ComputingasaDiscipline的局限性报告选择了抽象、理论和设计3个过程的内容作为“新的思想方法”报告在强调3个过程是错综复杂地缠绕在一起的时候，忽视了3个过程的内在联系“新的思想方法”是对计算领域几十年来的概括和总结，其目标就是构建起计算学科自己的方法论（但是报告没有认识到这一点）CC1991的主要成果提取了计算学科中反复出现的（具有方法论性质的）12个核心概念。“社会的、道德的和职业的问题”主领域的提出，使计算学科方法论的研究更加完备。由于CC1991没有解决计算教育中的第二和第三个重大问题，CC1991教学计划的执行远没有达到它的预期目标。但使一些学者开始考虑如何构建计算学科方法论的问题。CC2001的主要成果任务组将CC1991报告划分的11个主领域扩展为14个主领域，提出了计算机科学知识体的新概念，并从领域、单元和主题三个不同的层次给出了知识体的内容，为整个学科核心课程的详细设计奠定了基础。CC1991教学计划的执行并没有达到预期的效果，主要是缺乏更详细的课程指导。整个学科大量内容的罗列，有可能使学生们只见树木，不见森林——对新教学计划的争论仍将继续下去。解决计算教育3个重大问题的意义第一个重大问题对学科的发展至关重要第二个重大问题为高校制定计算机教学计划奠定基础第三个重大问题使人们对整个计算学科的认知科学化、系统化和逻辑化。计算机科学与技术方法论的提出2001年7月，在上海召开的CC2001工作研讨会上，本书作者提交的《计算机科学与技术方法论》大会论文引起了IEEE-CS教育委员会副主席、CC2001工作组负责人Carl.Chang教授（美籍华人）的注意，并在大会特邀报告中肯定了该论文所具有的批判性。2001年8月1日，在网上公布的CC2001报告（草案），增加了作者充分肯定的原《计算作为一门学科》报告和CC1991报告中具有方法论性质的抽象、理论和设计三个过程，以及计算学科中反复出现的12个核心概念的内容，同时，还第一次增加了要求学生更多地了解方法论的内容。1.2计算机科学与技术方法论的建立计算学科认知问题的大量研究成果《计算作为一门学科》报告CC1991报告CC2001报告著名计算机科学家、图灵奖获得者戴克斯特拉（E.W.Dijkstra）教授“关于真正讲授计算科学的严酷性”（OntheCrueltyofReallyTeachingComputingScience）及其争论，计算教育哲学、计算机科学与技术方法论等方面的研究成果研究成果——促进了计算学科认知领域的发展，为计算机科学与技术方法论的建立奠定了基础。计算机科学与技术方法论的定义在计算领域中，“认识”指的是抽象过程（感性认识）和理论过程（理性认识），“实践”指的是学科中的设计过程。抽象、理论和设计是具有方法论意义的3个过程，这3个过程是计算机科学与技术方法论中最重要的研究内容。计算机科学与技术方法论是对计算领域认识和实践过程中一般方法及其性质、特点、内在联系和变化发展进行系统研究的学问。计算机科学与技术方法论是认知计算学科的方法和工具，也是计算学科认知领域的理论体系。1.2.2计算学科二维定义矩阵知识框架《计算作为一门学科》报告遵循了一般科学技术方法论的思想，它给出了计算学科二维定义矩阵（简称定义矩阵）的概念并细化了其内容。定义矩阵的一维是“3个过程”（抽象、理论和设计）另一维是主领域。特别当主领域仅为计算学科时，定义矩阵便是《计算作为一门学科》报告中所指的“知识框架”。二维定义矩阵“知识框架”反映了计算领域中人们的认识是从感性认识（抽象）到理性认识（理论），再由理性认识（理论）回到实践（设计）中来的科学思维方法。“知识框架”是对计算学科总的概括，它是稳定的；“知识框架”的内容（值），即各主领域及其“3个过程”的内容，则随计算技术的发展而变化。计算学科分支领域的划分当前的计算学科已成为一门范围极为宽广的学科，将整个学科划分为若干分支领域有助于我们对计算学科的理解。分支领域的划分一般遵循以下4个原则：科目内容基础的协调一致；实质性的理论部分；有意义的抽象；重要的设计和实现。计算学科是“工科”还是“理科”？《计算作为一门学科》报告给出了一个计算学科的二维定义矩阵，使得学科各主领域中有关抽象、理论和设计3个形态的核心内容完整地呈现出来，该二维定义矩阵是对学科的一个高度概括和总结。3个学科形态的内容以及学科的根本问题都清楚地表明：计算机科学和计算机工程在本质上没有区别，学科中的抽象、理论和设计要解决的都是计算中的“能行性”和“有效性”的问题。计算机科学注重理论和抽象计算机工程注重抽象和设计计算机科学与技术则居中计算学科是“工科”还是“理科”？因此，不能简单地将计算学科归属于“理科”还是“工科”，在统一认识之后，ACM和IEEE-CS任务组将计算机科学、计算机工程、计算机科学和工程、计算机信息学以及其他类似名称的专业及其研究范畴统称为计算学科计算学科的本质问题归约为定义矩阵本质问题的说明要把握定义矩阵的本质，就是要分别把握定义矩阵的“横向”（抽象、理论和设计3个过程）以及“纵向”（各主领域）共有的、能反映各主领域内在联系的思想和方法的本质。抽象、理论和设计3个过程的内在联系与发展规律的内容，是计算机科学与技术方法论中最重要的内容。3个过程之间的相互作用，推动了计算学科及其分支领域的发展。“纵向”关系的内容，即各分支领域中所具有的共同的能反映学科某一方面本质特征的内容，既有助于我们认知计算学科，又有助于我们更好地运用方法论中的思想从事计算领域的工作，它是方法论中仅次于科学问题与“3个过程”的重要内容。14个主领域的主要内容离散结构——主要内容集合论、数理逻辑、近世代数、图论以及组合数学等。该领域与计算学科各主领域有着紧密的联系，CC2001为了强调它的重要性，特意将它列为计算学科的第一个主领域。该主领域以抽象和理论两个学科形态出现在计算学科中，它为计算学科各分支领域解决其基本问题提供了强有力的数学工具。1.离散结构——基本内容(43个核心小时)DS1.函数，关系，和集合论(6)DS2.基本逻辑(10)DS3.证明方法(12)DS4.计算基础(5)DS5.图和树(4)DS6.离散概率(6)注：核心学时是CC2001任务组推荐的一个相对授课学时，若将它视为课内学时时，则应有3倍的课外学时与之配套。2.程序设计基础(38个核心小时)主要内容PF1.基本的程序设计结构(9)PF2.算法和问题求解(6)PF3.基本数据结构(14)PF4.递归(5)PF5.事件驱动和并行程序设计(4)程序设计基础基本问题对给定的问题，如何进行有效的描述并给出算法？如何正确选择数据结构？如何进行设计、编码、测试和调试程序？3.算法与复杂性(31个核心小时)主要内容AL1.基本的算法分析(4)AL2.算法策略(6)AL3.基本的计算方法(12)AL4.分布式算法(3)AL5.基本可计算性理论(6)AL6.P和NP复杂类；AL7.自动机理论AL8.高级算法分析；AL9.加密算法AL10.几何算法；AL11.并行算法算法与复杂性基本问题对于给定的问题类，最好的算法是什么？要求的存储空间和计算时间有多少？空间和时间如何折衷？访问数据的最好方法是什么？算法最好和最坏的情况是什么？算法的平均性能如何？算法的通用性如何？4.体系结构(36个核心小时)主要内容AR1.数字逻辑和数字系统(6)AR2.数据的机器表示(3)AR3.汇编级机器组织(9)AR4.存储器系统组织和体系结构(5)AR5.接口和通信(3)AR6.功能的组织(7)AR7.多道处理和预备体系结构(3)AR8.性能提高AR9.网络和分布式系统的体系结构体系结构基本问题实现处理器、内存和机内通信的方法是什么？如何设计和控制大型计算系统，而且使其令人相信，尽管存在错误和失败，但它仍然是按照我们的意图工作的？哪种类型的体系结构能够有效地包含许多在一个计算中能够并行工作的处理元素？如何度量性能？5.操作系统(18个核心小时)主要内容OS1.操作系统概述(2)OS2.操作系统原理(2)OS3.并发(6)OS4.调度和分派(3)OS5.存储管理(5)OS6.设备管理；OS7.安全和保护OS8.文件系统；OS9.实时和嵌入系统OS10.容错；OS11.系统性能评价OS12.脚本操作系统基本问题在计算机系统操作的每一个级别上，可见的对象和允许进行的操作各是什么？对于每一类资源，能够对其进行有效利用的最小操作集是什么？如何组织接口才能使得用户只需与抽象的资源而非硬件的物理细节打交道？作业调度、内存管理、通信、软件资源访问、并发任务间的通信以及可靠性与安全的控制策略是什么通过少数构造规则的重复使用进行系统功能扩展的原则是什么？6.网络计算(15个核心小时)主要内容NC1.网络计算引导(2)NC2.通信和组网(7)NC3.网络安全(3)NC4.顾客-服务器计算的一个实例：web(3)NC5.建立网络应用；NC6.网络管理NC7.压缩和解压；NC8.多媒体数据技术NC9.无线和移动计算网络计算基本问题网络中的数据如何进行交换？网络协议如何验证？如何保证网络的安全？分布式计算的性能如何评价？分布式计算如何组织才能够使通过通信网连接在一起的自主计算机参加到一项计算中，而网络协议、主机地址、带宽和资源则具有透明性？7.程序设计语言(21个核心小时)主要内容PL1.程序设计语言概述(2)PL2.虚拟机(1)PL3.语言翻译导引(2)PL4.声明和类型（3）PL5.抽象机制（3）PL6.面向对象的程序设计（10）PL7.函数式程序设计PL8.语言翻译系统；PL9.类型系统PL10.程序设计语言语义学；PL11.程序设计语言的设计程序设计语言基本问题