计算机科学导论课件第2章 认识计算学科

第2章认识计算学科教学要求掌握计算学科的基本概念；熟悉计算学科的知识体系、学科特性以及中国计算机科学与技术学科概况；了解计算学科的根本问题、学科形态和计算学科的典型问题.问题引出从原始的计算工具到现代的电子计算机，已发展成为一门新兴学科——计算学科。那么，作为一门新兴的综合性学科，它是怎样形成的？其根本问题是什么？具有哪些基本特性？计算学科包括哪些知识领域和研究范畴？这就是本章所要讨论的问题.

教学重点本章主要讨论计算学科的形成、计算学科的根本问题、主要特点、计算学科的3个形态；中国计算机科学与技术学科的专业设置、课程体系；计算学科中的经典问题等。

§2.1计算学科的基本概念

§2.4计算机软件系统

§2.2计算学科的知识体系认识计算学科

§2.3计算机科学与技术学科本章教学内容§2.1计算学科的基本概念

1、什么是计算学科

《辞海》对学科的定义是：“①学术的分类。指一定科学领域或一门科学的分支，如自然科学中的物理学、生物学等，社会科学中的史学、教育学等；②教学的科目。指学校教学内容的基本单位，如中、小学的政治、语文、数学、外语等。”

2、计算学科的定义1985年春美国计算机学会（AssociationforComputingMachinery，ACM）和国际电子电气工程师协会计算机学会（InstituteofElectricalandElectronicsEngineers-ComputerSociety，IEEE-CS）联合组成攻关组，开始了对“计算作为一门学科”的存在性证明。通过4年的研究，1989年提出了报告。2.1.1计算作为一门学科

(1)计算作为一门学科的存在性证明：在这份报告中，第一次对计算学科及其核心问题给出了定义：计算学科是对信息描述和变换的算法过程（包括对其理论分析、设计、效率分析、实现和应用等）进行的系统研究。美国计算科学鉴定委员会（CSAB）发布的报告摘录中强调了计算学科的广泛性：“计算学科的研究，包括了从算法与可计算性的研究以及可计算硬件和软件的实际实现问题的研究。这样，计算学科不但包括从总体上对算法和信息处理过程进行研究的内容，也包括满足给定规格要求的有效而可靠的软硬件设计，包括所有科目的理论、研究、实验方法和工程设计。”2.1.1计算作为一门学科

(2)整个学科核心课程详细设计：报告《计算作为一门学科》勾画出了计算学科的知识框架，给出了计算学科中二维定义矩阵的定义及其相关研究内容,从而将学科的主题领域与学科的3个学科形态（抽象、理论和设计）有机地联系在一起。它通过主题领域划分的方式为计算学科课程体系建设提供了基础的指导思想，从而为科学制订教学计划奠定了基础，避免了教学计划设计中的随意性。

(3)强调整个学科综述性引导课程的构建：提出并解决了未来计算学科教育必须解决的整个学科核心课程问题以及整个学科综述性引导(导论)课程的构建问题。使人们对整个学科认知科学化、系统化和逻辑化，有力促进对计算学科方法论的研究，推动计算学科的快速发展。

2.1.1计算作为一门学科

3、计算学科教程

《计算作为一门学科》报告对计算学科的发展起到了极大的推动作用。1991年，在该报告的基础上，提交了关于计算学科的计算教程(ComputingCurricula1991,CC1991)报告。随后相继发表了CC2001、CC2004、CC2005等，形成了不同时期的“计算教程”。CC2004在原有的4个专业方向：

计算机科学、计算机工程、软件工程、信息系统的基础上，添加了信息技术专业方向。其中，CC2001提出了许多新的概念和主题领域新的划分，为新学科教程的形成起到了承前启后的重要作用。计算学科的二维定义矩阵如表2-1所示。2.1.1计算作为一门学科表2-1计算学科的二维定义矩阵三个过程学科主领域抽象理论设计1.离散结构（DS）集合论；数理逻辑；近世代数；图论；组合数学等2.程序设计基础（PF）程序设计结构；算法和问题求解；数据结构等3.算法与复杂性（AL）算法设计策略；算法分析；并行算法；分布式算法等。可计算性理论；计算复杂性理论；并行计算理论；密码学等。算法及组合问题启发式算法的选择、实现和测试；密码协议等4.体系结构（AR）布尔代数模型；电路模型；有限状态机；硬件可靠性等。布尔代数；开关理论；编码理论；有限自动机理论等。硬件单元；指令集的实现；差错处理；故障诊断；机器实现等5.操作系统（OS）用户可察觉对象与、内部计算机结构的绑定；子问题模型；安全计算模型等。并发理论；调度理论；程序行为和存储管理的理论；性能模型化与分析等。分时系统；自动存储分配；多级湿度；内存管理；文件管理；构建OS技术等。6.网络计算（NC）分布式计算模型；组网;协议；网络安全模型等。数据通信理论；排队理论；密码学；协议的形式化验证等。排队网络建模；系统性能评估；网络体系结构；协议技术等。7.程序设计语言（PL）基于各种标准的语言分类；语义模型；编译器组件等。形式语言与自动机；图灵机；形式语义学；近世代数等。特定程序设计语言；程序设计环境；翻译技术；统计处理等。8.人机交互（HC）人的表现模型；原型化；交互对象的描述；人机通信等认知心理学；人机工程学；社会交互科学；人机界面等交互设备；图形专用语言；交互技术；用户接口；评价标准等。9.图形学与可视化计算(GV)显示图像算法；实体对象的计算机表示；图像处理方法等。二维和多维几何；颜色理论；认知心理学；傅立叶分析等。图形算法的实现；图形库和图形包；图像增强系统等。10.智能系统（IS）知识表示；推理与学习模型；自然语言理解；自动学习等。逻辑；概念依赖性；认知心理学；相关支持领域等。逻辑程序设计语言；定理证明；专家系统；弈棋程序；机器人等。11.信息管理（IM）数据模型；文件表示；数据库查询语言；超媒体模型等.关系代数；关系演算；数据依赖理论；并发理论；统计推理等。数据库设计；数据库安全；磁盘映射；人机接口等。12.软件工程（SE）归约方法；方法学；软件工具与环境；系统评价；生命周期等程序验证与证明；时态逻辑；可靠性理论；认知心理学等归约语言；配置管理；软件开发方法；工程管理；软件工具等13.社会和职业问题（SP）价值观；道德观；知识产权；美学问题等。14.科学计算（CN）数学模型；有限元模型；连续问题的离散化技术等。数论；线性代数；数值分析；其他支持领域等有限元算法映射到特定结构的方法；标准程序库和软件包等。表2-1计算学科的二维定义矩阵2.1.2计算学科的三个形态1、抽象形态抽象是指在思维中对同类事物去除其现象的、次要的方面,抽取其共同的、主要的方面，从而做到从个别中把握一般，从现象中把握本质的认知过程和思维方法。抽象形态表明，基于计算学科的实验科学方法，广泛采用实验物理学的研究方法。抽象的结果是概念、符号、模型。按照对客观现象和规律的实验研究过程包括以下4个步骤：①对研究对象的概念抽象(定义)；②假设对象的基本性质和对象之间可能存在的关系；③确定这些性质和关系是否正确(证明)；④解释结果(与计算机系统或研究对象形成对应)。抽象形态的基本特征是其研究内容的构造性数学特征，是区别于更广泛的数学科学学科形态的典型特征。2.1.2计算学科的三个形态2、理论形态科学认识由感性阶段上升为理性阶段就形成了科学理论。理论形态表明，基于计算科学的数学基础和计算科学理论，广泛采用数学的研究方法。按照统一、合理的理论发展过程，包含以下4个步骤：①表述研究对象的特征(定义和公理)；②假设对象之间的基本性质和对象之间可能存在的关系；③确定这些性质和关系是否正确(证明)；④分析结果(与计算机系统或研究对象形成对应)。这个形态主要出现在计算科学中与硬件设计和实验有关的研究之中。当计算科学理论比较深奥，理解较为困难时，不少科研人员在大致了解理论、方法和技术的情况下，基于经验和技能常以这种学科形态方式开展工作。2.1.2计算学科的三个形态3、设计形态设计用来开发求解给定问题的系统和设备，主要要素为：需求说明、规格说明、设计和实现方法、测试和分析。设计形态表明，基于计算学科的工程设计，广泛采用工程科学的研究方法。按照为解决某个问题构造系统或装置的过程，包含以下4个步骤：①进行需求分析；②给定技术条件，建立规格说明；③设计并实现该系统或装置；④对系统进行测试分析、修改完善。这个形态广泛出现在计算科学中与硬件、软件、应用有关的设计和实现之中。2.1.3计算学科的根本问题计算学科的根本问题是讨论“计算过程的能行性”，而凡是与“能行性”有关的讨论，都是处理离散对象，因为非离散对象，即连续对象是很难进行“能行性”处理的。因此“能行性”决定了计算机本身的结构和它处理对象的离散特性，决定了以离散数学为代表的应用数学是描述计算学科的理论、方法和技术的主要工具。

1、计算过程的能行性对计算学科根本问题的认识与对计算过程的认识是紧密联系在一起的。远古时期我国学者就认为，对于一个数学问题，只有当确定了可用算盘求解的规则时，例如“三下五去二”、“四下五去一”等)，这个问题才是可解的，这就是最初的“算法化”思想，它蕰涵了中国古代对计算根本问题——“能行性”的理解。2.1.3计算学科的根本问题

20世纪30年代，图灵用形式化的方法成功地表述了计算过程的本质，证明了某些数学问题不能用任何机械过程来解决，深刻地揭示了计算所具有的“能行过程”的本质特征：

一个计算过程是能行的，当且仅当它能够被图灵机实现。

2、计算的本质

计算的本质问题是可计算性。可计算性决定了计算机的体系结构和计算机所处理的对象都只能是离散型的，因为连续对象(即非离散对象)）是很难进行计算处理的，必须在转化为离散型问题以后才能被计算机处理。例如，计算定积分就是把它变成离散量，再用分段求解的方法来处理的。尽管计算学科已成为一个极为宽广的学科，但计算学科所有分支领域的根本任务就是进行计算，其实质就是符号的变换。

1严谨：计算机硬件系统的设计和软件的开发都必须十分严谨，尤其是软件开发，严谨的逻辑思维能力是相当重要的。2学科知识体系庞大：该学科从算法与可计算性研究到根据可计算硬件和软件实现问题的研究，其知识体系庞大。3抽象：是计算学科的三个基本学科形态(抽象、理论、设计)之一。例如计算机中的文件管理、设备管理等都归为操作系统。

4实践性强：计算学科是在数学和电子学基础上发展起来的，它不仅是一门理论性很强的学科,而且是一门实践性很强的学科。5与其它学科关联紧密：如逻辑学、微电子科学、光电子科学、遗传学和神经生理学、物理和化学科学中的精细材料科学等。2.1.4计算学科的主要特点

1计算机科学：程序设计、离散结构、算法、数据结构、组成原理计算机网络、操作系统、数据库、编译、软件工程等15门.2计算机工程：程序设计、离散结构、算法、数据结构、组成原理网络、操作系统、数据库、编译、软件工程、数字逻辑等16门。3软件工程：程序设计、离散结构、算法、数据结构、组成原理、网络、操作系统、数据库、编译、软件工程、软件测试等24门。4信息技术：信息技术导论、数据结构与算法、数据库与信息管理计算机系统平台、应用集成、互联网络、信息工程等15门。§2.2

计算学科的知识体系2.2.1计算学科的知识领域5信息系统：关系数据库、数据查询、数据模型、信息系统、信息存储、多媒体信息、事务处理、超文本和超媒体等15门。

1计算机离散数学：研究数理逻辑、集合论、近世代数和图论等,计算机所处理的对象是离散型的，它是计算机科学的理论基础.2算法分析理论：研究算法设计和分析中的数学方法与理论，如组合数学、概率论、数理统计等。3形式语言与自动机理论：研究程序设计语言及自然语言的形式化定义、分类、结构,研究识别各类语言的自动机模型及相互关系.4程序设计方法学：研究编制高质量程序的各种程序设计规范化方法，程序正确性证明理论等。5程序设计语言理论：运用数学和计算机科学理论研究程序设计语言的基本规律。如代数语义、公理语义、操纵语义等。2.2.2计算学科的研究范畴1、计算机理论的研究内容

1元器件与存储介质：研究构成计算机硬件的各类电子的、磁性的、机械的、超导的元器件和存储介质。2微电子技术：研究构成计算机硬件的各类集成电路、大规模集成电路、超大规模集成电路芯片的结构和制造技术等。3计算机组成原理：研究通用计算机的硬件组成结构以及运算器、控制器、存储器、输入/输出设备等各部件的构成和工作原理。4微型计算机技术：研究使用最广泛的微型计算机的组成原理、结构、芯片、接口电路及其应用技术。5计算机体系结构：研究计算机软硬件的总体结构、各种新型体系结构以及进一步提高计算机性能的各种新技术。2.2.2计算学科的研究范畴2、计算机硬件的研究内容

1程序设计语言：研究数据类型、操作、控制结构、引进新类型和操作机制。根据实际需求选择合适、新颖的程序设计语言。2算法设计：研究计算机领域及其它相关领域中的常用算法的设计方法并分析其时间复杂度和空间复杂度，以评价算法的优劣。3数据结构：研究数据在计算机中的表示和存储方法、抽象的逻辑结构及其定义的各种基本操作。4编译原理：研究程序设计语言中的词法分析、语法分析、中间代码优化、目标代码生成和编译程序开发。2.2.2计算学科的研究范畴3、计算机软件的研究内容

数据库管理系统：研究数据库基础理论、数据库安全保护、数据库模型、数据设计与应用和数据库标准语言等。6软件工程学：研究软件过程、软件需求与规格说明、软件设计、软件验证、软件演化、软件项目管理、软件开发工具与环境、形式化方法、软件可靠性、专用系统开发。7可视化技术：研究如何用图形和图像来直观地表征数据，它不仅要求计算结果的可视化，而且要求计算过程的可视化。2.2.2计算学科的研究范畴操作系统：研究操作系统的逻辑结构、并发处理、资源分配与调度、存储管理、设备管理、文件系统等。85

1网络组成：研究局域网、广域网、Internet、Intranet等各种类型网络的拓扑结构、构成方法和接入方式。2数据通信：研究连接在网络上的计算机进行数据通信的介质、传输原理、调制与编码技术、数据交换技术和差错控制技术等。3体系结构：研究网络通信双方必须共同遵守的协议和网络系统中各层的功能、结构、技术和方法等。4网络安全：研究计算机网络的设备安全、软件安全、信息安全以及病毒防治等技术，以提高计算机网络的可靠性和安全性。5网络服务：研究如何为计算机网络的用户提供方便的远程登录、文件传输、电子邮件、信息浏览等服务。2.2.2计算学科的研究范畴4、计算机网络的研究内容

1软件开发工具：研究软件开发工具的有关技术,如程序调试技术、代码优化技术、代码重用技术等。2完善现有的应用系统：根据新的技术平台和实际情况对已有的应用系统进行升级、改造，使其功能更强大，更加便于使用。3开拓新的应用领域：研究如何打破计算机传统的应用领域，扩大计算机在国民经济以及社会生活中的应用范畴。4人一机交互：研究人与计算机的交互和协同技术，如图形用户接口设计、多媒体系统的人机接口等，为用户提供更加友好界面。2.2.2计算学科的研究范畴5、计算机应用的研究内容在这些研究领域中，有些方面已研究得比较透彻并取得了许多成果，也有些方面还不够成熟和完备，需要进一步去探索、研究、完善和发展。

1信息、管理与决策系统：涵盖数据库设计与数据管理技术、数据表示与存储、多媒体技术、数据与信息检索、管理信息系统、计算机辅助系统、数字仿真、决策系统等方向。3计算可视化：涵盖科学计算、计算机图形学、计算几何、模式识别与图形图像处理等方向。4人工智能应用与系统：涵盖人工智能、机器人、神经元计算、知识工程、自然语言处理与机器翻译、自动推理等方向。2.2.3计算学科的知识结构

计算学科经过了半个多世纪的迅猛发展，已经成为一个相对比较完备的学科体系，衍生了许多相对独立的方向和分支。从学科体系的角度，可将计算学科的内容划分为3个层面。1、应用层

1软件开发方法学：涵盖顺序、并行与分布式软件开发方法学，如软件工程技术、软件开发工具和环境等方向。2计算机网络与通信技术：涵盖计算机网络、网络互联技术、数据通信技术以及信息保密与安全技术等方向。3程序设计科学：涵盖数据结构、数值与符号计算、算法设计与分析、程序设计语言、程序设计方法学、程序理论等方向。4计算机系统基础：涵盖电路基础、数字逻辑技术、计算机组成原理、计算机体系结构、操作系统、编译技术、数据库系统实现技术、容错技术、故障诊断与器件测试技术等方向。2、专业基础层2.2.3计算学科的知识结构

1计算理论：涵盖了可计算性（递归论）与计算复杂性理论、形式语言与自动机理论、形式语义学、Petri网理论等方向。2高等逻辑：涵盖模型论、各种非经典逻辑与公理集合论等方向。3、专业理论基础层

上述三个层面的划分，有利于不同类型人才的培养。在人才培养规格上，可分划为三种类型。

●科学型人才：强调基础理论知识的掌握和创新能力的培养，要求掌握计算机科学理论和应用知识，具备较强的创新能力和实践能力。

●工程型人才：强调解决实际工程问题能力的培养，要求掌握计算机理论和应用知识，具备较强的工程实践能力。

●应用型人才：强调应用知识的掌握和组织协调能力的培养，要求掌握计算机科学及计算机应用知识，具备较强的实践能力和动手能力。2.2.3计算学科的知识结构2.2.4计算学科与其它学科的关系1、计算学科与数学方法计算学科对数学具有很大的依赖性，数学不仅是计算机系统设计、算法设计的基础，而且为计算学科提了最重要的学科思想和学科的方法论基础。2、计算学科与电子学计算机硬件的发展与电子技术的发展紧密相关，每当电子技术有突破性的进展，就会导致计算机的一次重大变革。未来计算机的发展，将会与微电子学和光电子学密切相关。

3、计算学科与新兴技术计算学科的发展正在更多地依赖新兴技术的发展。对计算学科能产生重大影响的学科有：光学、材料科学、科学哲学、生物化学、脑科学与神经生理学、构造性数学、行为科学等。§2.3

中国计算机与技术学科2.3.1CCC2002与专业规范

1、中国计算机教程2002我国的计算机专业本科教育始于1956年哈尔滨工业大学等学校开设的“计算装置与仪器”专业，后经历了多种名称变化，于1998年教育部进行本科专业目录调整，计算机类专业名称统一为计算机科学与技术专业。从2001年开始，增设了软件工程专业和网络工程专业。为了与国外先进课程体系接轨，2001年3月成立了《中国计算机科学与技术学科教程2002》（ChinaComputingCurricula2002，CCC2002）项目研究组，希望通过对CC2001的跟踪、分析和研究，并结合我国计算学科的发展状况，提出一个适应我国本科教学要求的教学计划，2002年4月提交了研究报告，并通过了教育部组织的专家评审，且于同年9月出版发行。2.3.1CCC2002与专业规范

2、中国计算机专业规范

2006年6月24日，教育部颁布了计算机科学与技术专业发展规范，主要内容为：①在计算机科学与技术专业名称下，鼓励不同的学校根据社会需求和自身实际情况，为学生提供不同人才培养类型的教学计划和培养方案。②将人才培养的规格归纳为三种类型、4个专业方向：科学型(计算机科学专业方向)、工程型(计算机工程专业方向、软件工程专业方向)、应用型(信息技术专业方向)。③给出了4个专业方向的专业规范,，并将CC2004中的“信息系统(InformationSystem,IS）”专业方向划归管理科学，因此在《研究报告暨专业规范》中没有该专业方向的内容。2.3.2计算机科学与技术学科的专业设置

1、计算机科学与技术学科体系

20世纪90年代我国对计算机科学与技术学科与专业设置做了重大改革，本科专业按一级学科培养，统一为计算机科学与技术专业；研究生按二级学科培养，统一为计算机软件与理论、计算机系统结构和计算机应用技术3个专业,如图2-2所示。图2-2计算机科学与技术学科结构三个二级学科计算机系统结构计算机软件与理论计算机应用技术一个一级学科计算机科学与技术2.3.2计算机科学与技术学科的专业设置

2、计算机科学与技术学科结构

(1)计算机系统结构学科：是计算机科学与技术的支柱学科和基础学科,它研究计算机硬件与软件的功能分配、软硬件界面的划分、硬件结构、组成与实现的方法与技术。

(2)计算机软件与理论学科：是计算机科学与技术的核心与灵魂,它研究系统软件、软件自动化、程序设计语言、数据库系统、软件工程与软件复用技术、并行处理与高性能计算、智能软件、理论计算机科学、人工智能、计算机科学基础理论等。

(3)计算机应用技术学科：是计算机科学与技术学科服务于国民经济、国防建设、社会生活的钥匙与纽带,它研究计算机各类应用中具有共性的理论、技术和方法,以及各种前沿性、创新性、跨学科、跨领域的计算机新应用，包括科学问题的计算、数据的自动处理、各种对象的过程控制等。2.3.3计算机科学与技术学科的知识体系

1、离散结构8、人机交互

2、程序设计基础9、图形学与可视化计算3、算法与复杂性10、信息管理

4、体系结构与组织11、信息管理

5、操作系统12、软件工程

6、网络及其计算13、计算科学与数字方法

7、程序设计语言14、社会与职业问题

在上述核心课程中，计算机科学导论是学习计算机科学技术的入门课程、是计算机专业完整的知识体系概论，是计算机科学与技术专业课程体系中的通识课程。该课程在整个知识体系中，起到承前启后的作用，并对整个学习过程起导航作用。在人类进行科学探索与科学研究的过程中，曾经提出过许多对科学发展具有重要影响和深远意义的科学问题，如哥德巴赫猜想、四色定理、哥尼斯堡七桥等著名问题。这些经典问题的提出，对计算学科及其分支领域的形成与发展起了重要推进作用。了解这些经典问题，不仅有助于我们深刻理解计算学科中一些关键问题的本质，而且对学科的深入研究具有十分重要的促进作用。为了便于讨论，我们将其归类为：图论问题、算法复杂性问题、机器智能问题、并发访问控制问题。

通过对这些经典问题的介绍，希望能激发出同学们的学习热情和研究兴趣，为计算机科学与技术的研究和进步做出贡献。§2.4

计算学科的经典问题2.4.1图论问题

1、哥尼斯堡18世纪中叶,俄罗斯有一座哥尼斯堡城，城中有一条贯穿全市的流河,河中央有座岛，河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，由７座桥将４个城区连起来，如图2-3所示。图2-3哥尼斯堡七桥问题人们常通过这７座桥到各城区游玩，于是产生了一个有趣的问题:一个人怎样不重复地走完7座桥，最后回到出发地点？这就是著名的“哥尼斯堡七桥问题”。为了解决哥尼斯堡七桥问题，欧拉用4个字母A、B、C、D代表4个城区，并用7条边表示7座桥，如图2-4所示。欧拉不仅给出了哥尼斯堡七桥问题的证明，还将问题进行了一般化处理，即对给定的任意一个河流图与任意多座桥，判定是否存在每座桥恰好走过一次的路径(不一定回到原出发点),并用数学方法给出了三条判定规则,人们将其规则图称为欧拉图。图2-４哥尼斯堡问题七桥抽象图2.4.1图论问题

2、哈密尔顿回路问题1857年爱尔兰物理学家和数学家威廉·哈密尔顿提出的一个数学问题，也有人将它称为周游世界的数学游戏。游戏的规则是：设有一个如图2-7所示的正十二面体，它有20个顶点，把每个顶点看作一个城市,把正十二面体的30条边看成连接这些城市的路。找一条从某城市出发,经过每个城市恰好一次,并且最后回到出发点的路径,人们把这种路径称为哈密顿回路。把正十二面体投影到平面上，如图2-8所示。图中标出了一种走法,且从城市1出发，经过2、3、…、20，最后回到1。

2.4.1图论问题2.4.1图论问题图2-7正十二面体图2-8周游世界游戏示意图

对一个图是否存在“欧拉回路”前面已给出充分必要条件，而对一个图是否存在哈密顿回路至今仍未找到充分必要条件。

3、中国邮路问题我国数学家管梅谷教授1960年也提出了一个有重要理论意义和广泛应用背景的问题，当时称为“最短投递路线问题”，国际上称为中国邮路问题：一个邮递员应如何选择一条路线，使他能够从邮局出发，走遍他负责送信的所有街道，最后回到邮局，并且所走的路程最短。该问题归结为图论问题，对问题的求解是：给定一个连通无向图(没有孤立顶点)，每条边都有非负的确定长度,求该图的一条经过每条边至少一次的最短回路。对于有欧拉回路的欧拉图，找到一条欧拉回路即可。对于不存在欧拉回路的非欧拉图，才是中国邮路问题的重点。管梅谷教授及国内外学者给出了一些解决该问题及推广与变形问题的算法，研究成果除用于邮政部门外，还用于扫雪车路线、洒水车路线、警车巡逻路线的最优设计等。2.4.1图论问题

4、旅行商问题旅行商问题（TravelingSalesmanProblem，TSP）是哈密顿和英国数学家柯克曼于19世纪初提出的一个数学问题。其基本含义是，有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发，必须经过每一个城市且只能在每个城市停留一次，最后回到原出发城市。要解决的问题是：如何事先确定好一条路程最短的旅行路径呢？人们思考解决这个问题时首先想到的基本方法是：对给定的城市进行排列组合，列出每一条可供选择的路径，然后计算出每条路径的总里程，最后从所有可能的路径中选出一条路程最短的路径。假设给定有4个城市，分别为C1、C2、C3和C4，各城市之间的距离是确定的值，城市间的交通如图2-9所示。2.4.1图论问题2.4.1图论问题图2-9城市交通问题示意图图2-10组合路径图从图中可以看到，从城市Cl出发，最后再回到Cl城市，可供选择的路径共有6条，括号中为路径长度，如图2-10所示。

Cl→C2→C3→C4→C1（20），Cl→C2→C4→C3→C1（29）Cl→C3→C2→C4→C1（23），Cl→C3→C4→C2→C1（29）Cl→C4→C3→C2→C1（20），Cl→C4→C2→C3→C1（23）从中很快可以选出一条总路程最短的路径

Cl→C2→C3→C4→C1或Cl→C4→C3→C2→C1若设城市的数目为n时，则组合路径数为（n-1）!。显然，当城市数目不多时，要找到最短距离的路径并不难，但随着城市数目的不断增多，组合路径数将呈指数规律急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题”。假设城市的数目为20，组合路径数则为(20-1)!≈1.216×1017，如此巨大的组合数目，若计算机每秒能计算出1000万条路径的速度计算，计算完所有路径的需要386年的时间,这样的算法是没有实际意义的。2.4.1图论问题据报导，1998年，科学家们成功地解决了美国13509个城市之间的TSP问题，2001年又解决了德国15112个城市之间的TSP问题，但这一工程代价也是巨大的。据报道，解决15112个城市之间的TSP问题，共使用了美国赖斯大学和普林斯顿大学之间网络互联的、由速度为500MHz的CompaqEV6Alpha处理器组成的110台计算机，所有计算机花费的实践总和为22.6年。TSP是最有代表性的优化组合问题之一，它的应用已逐渐渗透到各个技术领域和我们的日常生活中。在大规模生产过程中，寻找最短路径能有效地减低成本。事实上，这类问题的解决还可以延伸到其它行业领域中。由于TSP会产生组合爆炸问题，为此人们提出了一些求近似解的算法，即找出的路径不一定是最短路径，而是比较短的路径，但求解问题的时间复杂度大大降低了，因而是可行的实用算法，包括最近邻算法、抄近路算法等。2.4.1图论问题所谓“计算复杂性”，就是利用计算机求解问题的难易程度。它包括两个方面：一是计算所需的步数或指令条数，称为时间复杂度（TimeComplexity）；二是计算所需的存储单元数量，称为空间复杂度（SpaceComplexity）。下面列举算法复杂性的4个著名实例。

1、Hanoi（汉诺塔）问题Hanoi问题源于印度神话传说。传说古代教的天神在创造世界时，建造了一座称作为贝拿勒斯的神庙，神庙里安放了一个黄铜座，座上竖有三根宝石柱子。在第一根宝石柱上按照从小到大、自上而下的顺序放有64个直径大小不一的金盘子形成一座金塔，如图2-11所示。

2.4.2算法复杂性问题天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，同时定下三条规则：①每次只能移动一个盘子；③盘子只能在三根柱子上来回移动，而不能放在它处；③在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。2.4.2算法复杂性问题

ABC图2-11汉诺塔问题示意图64个盘子天神说,当这64个盘子全部移到第三根柱子上后,世界末日就要到了。事实上，如果每秒移动一次，一年有31536000秒,僧侣们一刻不停地来回搬动,也需要花费大约5849亿年的时间。假定计算机以每秒10000万个盘子的速度进行搬迁,则需要花费大约58490年的时间。通过这一例子我们可以了解到，理论上可以计算的问题，实际上并不一定能实现。Hanoi塔是一个典型的只有用递归方法才能解决的问题。所谓递归，就是将一个较大的问题规约为一个或多个相对简单的子问题的求解方法。而这些子问题比原问题简单，且在结构上与原问题相同。

Hanoi塔是一个看似简单，而实际处理却很复杂，这一类问题称为难解性问题，它包括时间的复杂性和空间的复杂性。2.4.2算法复杂性问题

2、NP问题

在采用图灵机作为标准的计算工具的情况下，可以非形式化地定义如下几类计算问题。(1)NP类问题：就是在算法的时间复杂性分析和研究中，将所有可以在多项式(如T(n2))时间内验证的问题称为多项式复杂程度的非确定性类问题。NP问题是至今没有找到多项式时间算法解的一类问题，因此，NP类问题采用的是非确定性算法。

(2)NP完全问题：在NP类问题中某些问题的复杂性与整个类的复杂性有关，如果这些问题中的任意一个能在多项式的时间内求解，则所有NP类问题都能在多项式时间内求解，这些NP类问题称为NP完全问题或NP难问题。求总路程小于B的路径的旅行商问题是NP完全问题，求哈密顿回路也是NP完全问题。2.4.2算法复杂性问题2.4.2算法复杂性问题

3、36军官问题36军官问题是18世纪由欧拉作为一个数学游戏提出来的。设有分别来自6个军团共有6种不同军衔的36名军官他们能否排成6行6列的编队使得每行每列都有各种军衔的军官1名，并且每行和每列上的不同军衔的6名军官还分别来自不同的军团？如果将一个军官用一个序偶(i，j)表示，其中i表示该军官的军衔(i＝1,2,…,6)，而j表示他所在的军团(j＝1,2,…,6)。于是这个问题又可以变成：36个序偶(i，j)(i＝1,2,…,6；j＝1,2,…,6)能否排成6×6阵列，使得在每行和每列这6个整数1,2,…,6都能以某种顺序出现在序偶第一个元素的位置上，并以某种顺序出现在序偶第二个元素的位置上？2.4.2算法复杂性问题36军官问题提出后的很长一段时间没有得到解决，直到20世纪初才被证明这样的方队是排不起来的。将36军官问题中的军团数和军阶数推广到一般的n的情况,相应的满足条件的方队被称为n阶欧拉方。经过多次尝试，欧拉猜测：对任何非负整数k,n＝4k＋2阶欧拉方都是不存在的。1901年,法国数学家塔里(G.Tarry，1843～1913)用穷举法证明了欧拉猜想对于n＝6是成立的；大约在1960年,三位统计学家R.C.Bose、E.T.Parke和S.S.Shrikhande）成功地证明了欧拉猜想对于所有的n＞6都是不成立的，也就是说，n＝4k＋2(k≥2)阶欧拉方是不存在的。2.4.2算法复杂性问题

4、四色问题四色问题又称为四色猜想或四色定理，1852年首先由英国的一位大学生古思里(F.Guthrie)提出来的。古思里在给一幅英国地图着色时发现，只要4种颜色就可以使任何相邻的两个郡不同色。他推断任何地图的着色也只需要4种颜色就够了，但他未能给出证明。1878年，英国数学家凯利(A.Cayley，1821～1895)对此问题进行了认真分析，认为这是一个不可忽视的问题，他正式向伦敦数学学会提出这个问题，于是四色猜想成了世界数学界关注的问题，世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1879年，英国律师兼数学家肯普(1849～1922)发表了证明四色猜想的论文，宣布证明了四色定理。11年后，即1890年，年轻的数学家赫伍德(1861～1955)以自己的精确计算指出肯普的证明有误。2.4.2算法复杂性问题赫伍德一生坚持研究四色问题，但始终未能证明这一定理。但赫伍德在肯普的方法的基础上证明了用5种颜色对任何地图着色都是足够的，即“地图五色定理”是成立的。进入20世纪以后，科学家们对四色猜想的证明基本上是按照肯普的想法进行的。有些数学家对平面图形的可约性进行了深入分析。1969年德国数学家希斯第一次提出了一种具有可行的寻找不可避免可约图的算法，开创了研究的新思路。1970年，美国伊利诺伊大学的数学教授哈肯与阿佩尔合作从事这一问题研究。1976年6月哈肯和阿佩尔终于获得成功：一组不可避免的可约图终于找到了，这组图一共有2000多个，即证明了任意平面地图都能够用4种颜色着色。他们的证明需要在计算机上计算1200小时，程序先后修改了500多次。2.4.3计算机智能问题计算机智能是20世纪中叶兴起的一个新的科学技术领域，是目前计算机领域的热点研究问题，也是计算机的一个重要发展趋势。下面是计算机智能问题中的3个著名实例。

1、图灵测试在计算机科学诞生后，为解决人工智能中一些激烈争论的问题，图灵和西尔勒分别提出了能够反映人工智能本质特征的两个著名的哲学问题，即图灵测试和西尔勒的中文小屋。经过多年的研究，人们在人工智能领域取得了长足的进展。图灵在1950年英国《Mind》杂志上发表了题为《计算机器和智能》的论文。论文中提出了“机器能思维吗?”这一问题，在定义了“智能”和“思维”的术语之后，最终他得出的结论是我们能够创造出可以思考的计算机。2.4.3计算机智能问题同时，他还提出了另一个问题：“如何才知道何时是成功了呢？并给出了一个判断机器是否具有智能功能的方法，这就是被后人称之为图灵测试的模拟游戏，测试方法和过程如下：该游戏由一个男人(A)、一个女人(B)和一个性别不限的提问者(C)来完成。提问者(C)待在与两个回答者相隔离的房间里，如图2-12所示。图2-12图灵测试示意图回答者B回答者A提问者2.4.3计算机智能问题游戏的目标是让提问者通过对两个回答者的提问来鉴别其中哪个是男人，哪个是女人。为了避免提问者通过回答者的声音、语调轻易地做出判断，在提问者和回答者之间通过计算机键盘。提问者只被告知两个人的代号为X和Y，游戏的最后提问者要做出“X是A，Y是B”或“X是B，Y是A”的判断。现在，把上面这个游戏中的男人(A)换成一部机器来扮演，如果提问者在与机器、女人的游戏中做出的错误判断与在男人、女人之间的游戏中做出错误判断的次数是相同或更多，那么就可以判定这部机器是能够思维的。这时机器在提问者的提问上所体现出的智能(思维能力)与人没有什么区别。根据图灵当时的预测，到2000年，能有机器通过这样的测试。有人认为，在1997年战胜国际象棋大师卡斯帕罗夫的“深蓝”计算机就可以看作通过了图灵测试。2.4.3计算机智能问题

2、西尔勒中文小屋与人工智能有关的另一个著名的实验是“中文小屋”。1980年美国哲学家西尔勒在杂志上发表了“心、脑和程序”的论文，文中他以自己为主角设计了一个假想实验：假设西尔勒被关在一个小屋中，屋子里有序地堆放着足够的中文字符，而他对中文一窍不通。这时屋外的人递进一串中文字符，同时还附有一本用英文编写的处理中文字符的规则（作为美国人，西尔勒对英语是熟悉的），这些规则将递进来的字符和小屋中的字符之间的转换作了形式化的规定，西尔勒按照规则对这些字符进行处理后，将一串新的中文字符送出屋外。事实上，他根本不知道送进来的字符串就是屋外人提出的“问题”，也不知道送出去的字符串就是所提出问题的“答案”。2.4.3计算机智能问题又假设西尔勒很擅长按照规则熟练地处理一些中文字符，而程序员（编写规则的人）又擅长编写程序（规则），那么，西尔勒“给出”的答案将会与一个熟悉中文的中国人给出的答案没有什么不同。但是，能说西尔勒真的懂中文吗？真的理解以中文字符串表示的屋外人递进来的“问题”和自己给出的“答案”吗？西尔勒借用语言学的术语非常形象地揭示了“中文小屋”的深刻含义：形式化的计算机仅有语法，没有语义，只是按规则办事，并不理解规则的含义及自己在做什么。图灵认为，不要求机器与人脑在构造上一样，只要与人脑有相同的功能就认为机器有思维。西尔勒认为，机器没有什么智能，只是按照人们编写好的形式化的程序来完成一项任务，机器本身未必清楚自己在做什么。这种对同一问题的不同认识代表了目前人们在计算机智能或人工智能上的争议。2.4.3计算机智能问题

3、博弈问题人们把诸如下棋、打牌、战争等一类竞争性的智能活动称为博弈。人工智能研究博弈的目的并不是为了让计算机与人进行下棋、打牌之类的游戏，而是通过对博弈的研究来检验某些人工智能技术是否能达到对人类智能的模拟，因为博弈是一种智能性很强的竞争活动。另外，通过对博弈过程的模拟可以促进人工智能技术更深一步的研究。IBM研制的超级计算机“深蓝”于1997年5月，与当时蝉联12年世界冠军的国际象棋大师—白俄罗斯的卡斯帕罗夫对弈，最终“深蓝”以3.5比2.5的总比分获胜，从而引起了世人的极大关注。2001年德国的“更弗里茨”国际象棋软件击败了当