10月1日，人民币纳入了“特别提款权”（SDR）一篮子货币（美元、欧元、日元和英镑），是中国融入全球金融体系的重要里程碑。

Presentation on theme: "10月1日，人民币纳入了“特别提款权”（SDR）一篮子货币（美元、欧元、日元和英镑），是中国融入全球金融体系的重要里程碑。"— Presentation transcript:

1 10月1日，人民币纳入了“特别提款权”（SDR）一篮子货币（美元、欧元、日元和英镑），是中国融入全球金融体系的重要里程碑。
10月3日，日本科学家大隅良典获2016年诺贝尔生理学或医学奖，表彰他在细胞自噬机制研究中取得的成就。 2000年至今的17个年度里，第17个获得诺贝尔奖的日本人。日本成为仅次于美国的第二大“诺奖大户”。原因： 第二基本计划（2001－2005年）里日本明确提出“50年拿30个诺贝尔奖”的目标。 日本人的“工匠精神”，就是一辈子只做一件事，而且将这件事做到极致。而中国人崇尚的是善变的“互联网思维”。总是希望走捷径、抄近道，而不屑于“扎硬寨、打硬仗”。 10月4日，谷歌举行2016年秋季产品发布会 发布内容？

2 2016年谷歌秋季产品发布会 10月4日，旧金山，谷歌发布的硬件新品 目标： 打造每个人“自己的谷歌”！ Google Pixel智能手机
Google Home家庭智能语音助手 Google Daydream View 虚拟现实眼镜 Google Wifi路由器 Google Chrome Cast Ultra电视棒 目标： 打造每个人“自己的谷歌”！

3 Google一个小小的发布会，却打了全球科技大佬的脸
10月4日谷歌发布会看点汇总 人工智能为核心

4 认识计算机学科 ——什么是计算机学科 ——计算机学科的根本问题 ——计算机学科的科学问题
认识计算机学科 ——什么是计算机学科 ——计算机学科的根本问题 ——计算机学科的科学问题

5 Part I. 什么是计算机学科 科学与学科；科学与技术；科学、技术与工程

6 科学与学科 科学是关于自然、社会和思维的发展与变化规律的知识体系，是由人类在生产活动和社会活动中产生和发展的，是人类实践经验的结晶。
科学是逐步发展起来的 科学的发展需要某种特殊的方法 科学在不断超越中永无止境地发展 学科本身具有二重含义： 指知识体系或学术分类，含义较广； 指为培养人才而设立的教学科目。

7 科学与学科 科学研究是以问题为基础的，学科是在科学发展中不断分化和整合而形成和发展的，是科学研究发展成熟的产物。
科学研究发展成熟而成为一个独立学科的标志是：必须有独立的研究内容、成熟的研究方法、规范的学科体制。

8 什么是计算机科学？ Wikipedia(维基百科) [1]
Computer science (or computing science) is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. 计算机科学（或计算科学）是研究信息和计算的理论基础，以及它们在计算机系统上实现和应用的实践技术。 维基百科引用了美国几所大学的报告 [1]

9 计算机学科的定义 计算机学科是对描述和变换信息的算法过程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。
它来源于对算法理论、数理逻辑、计算模型、自动计算机器的研究，并与存储式电子计算机的发明一起形成于20世纪40年代初期。

10 计算机学科的特点 计算机学科包括科学和技术两个方面 科学侧重于研究现象、揭示规律；
技术则侧重于研制计算机、研究使用计算机进行信息处理的方法与技术手段； 科学是技术的依据，技术是科学的体现。 二者高度融合是计算机科学与技术学科的突出特点。 计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。

11 计算机学科的特点 科学：关于自然、社会和思维的发展与变化规律的知识体系，其核心是发现。
技术：根据实践经验和科学原理而发展形成的各种工艺操作方法、技能和技巧，其核心是发明。 工程：将科学原理应用到生产实践中，是某种形式的科学应用，其核心是建造

12 计算机学科的知识体系 随着计算技术的发展，IEEE/ACM 在 CC2001中将计算机学科称为计算学科，并将计算学科分为四个领域（也称专业方向），分别是计算机科学、计算机工程、软件工程和信息系统。于2004年6月1日公布的CC2004报告，在上述四个领域的基础上，增加了一个信息技术专业学科领域，并预留了未来的新发展领域。

13 计算机学科的问题空间 组织系统行为 应用技术 软件开发 系统平台结构 计算机硬件体系 理论原理 创新 开发 应用部署 配置 倾向应用
倾向理论 倾向应用

14 计算机科学 组织系统行为 应用技术 软件开发 系统平台结构 计算机硬件体系 理论原理 创新 开发 应用部署 配置 倾向理论 倾向应用

15 计算机工程 组织系统行为 应用技术 软件开发 系统平台结构 计算机硬件体系 理论原理 创新 开发 应用部署 配置 倾向理论 倾向应用

16 软件工程 组织系统行为 应用技术 软件开发 系统平台结构 计算机硬件体系 理论原理 创新 开发 应用部署 配置 倾向理论 倾向应用

17 信息系统 组织系统行为 应用技术 软件开发 系统平台结构 计算机硬件体系 理论原理 创新 开发 应用部署 配置 倾向理论 倾向应用

18 信息技术 组织系统行为 应用技术 软件开发 系统平台结构 计算机硬件体系 理论原理 创新 开发 应用部署 配置 倾向理论 倾向应用

19 计算机科学的知识领域 CS-DS离散结构 CS-AR计算机体系结构与组织 CS-NC以网络为中心的计算 CS-AL算法与复杂性
CS-PL程序设计语言 CS-GV图形学与可视化计算 CS-IS智能系统 CS-IM信息管理 CS-CN数值计算科学 CS-AR计算机体系结构与组织 CS-AL算法与复杂性 CS-HC人机交互 CS-OS操作系统 CS-PF程序设计基础 CS-SP社会与职业问题 CS-SE软件工程

20 计算机工程的知识领域 CE-HCI 人机交互 CE-ALG 算法与复杂度 CE-NWK 计算机网络 CE-CAO 计算机体系结构和组织
CE-CSE 计算机系统工程 CE-CSG 电路和信号 CE-DBS 数据库系统 CE-DIG 数字逻辑 CE-DSP 数字信号处理 CE-ELE 电子学 CE-ESY 嵌入式系统 CE-HCI 人机交互 CE-NWK 计算机网络 CE-OPS 操作系统 CE-PRF 程序设计基础 CE-SPR 社会和职业问题 CE-SWE 软件工程 CE-VLS VLSI设计与构造 CE-DSC 离散结构 CE-PRS 概率和统计

21 软件工程的知识领域 SE-CMP计算基础 SE-FND数学和工程基础 SE-PRF职业实践 SE-MAA软件建模与分析 SE-DES软件设计
SE-VAV软件验证与确认 SE-EVO软件进化 SE-PRO软件过程 SE-QUA软件质量 SE-MGT软件管理

22 信息技术的知识领域 IT-ITF 信息技术基础 IT-WS WEB系统与技术 IT-PF 程序设计基础 IT-HCI 人机交互
IT-PT 平台技术 IT-NET 计算机网络 IT-IM 信息管理 IT-IPG 整合编程技术 IT-WS WEB系统与技术 IT-HCI 人机交互 IT-IAS 信息安全 IT-SA 系统管理与维护 IT-SIA 系统集成与架构 IT-SP 社会和职业学

23 计算机学科的发展 计算机体系结构的发展 软件开发方法的发展 计算机应用的发展
计算机硬件发展迅速，但计算模型没有质的飞跃，局限于图灵机与冯·诺依曼机的模型。 量子计算机、DNA计算机 软件开发方法的发展 软件开发方法逐渐与认知科学相结合，借鉴认知科学的基本概念和原理，并将其应用到软件开发中来 软件体系结构、中间件、软件设计模式、重构 计算机应用的发展 计算机应用层次综合化、智能化、集成化、网络化、广泛化、个性化和家庭化 Internet网的出现与计算机进入到人类生活的各个方面 说明：更详细的论述可参见讲稿的详细版本或维基百科相关内容

24 计算机学科的发展 学科内涵变化很快、变化很大 从10年前开始：似乎还需要知道这些 20年前：计算机毕业生知道这些差不多了

25 计算机学科的发展 计算的概念在过去10年里发生了巨大变化 Internet 的出现是计算机学科发展的重要里程碑
WWW的出现，将“计算”泛化、平民化了 “计算”已经拓展到难以用一个学科来定义 Internet 的出现是计算机学科发展的重要里程碑 有关计算机学科的更多发展历史可参阅维基百科 计算的历史 有关计算历史事件的时间表

26 Part II. 计算机学科的根本问题

27 引自蒋宗礼的报告

28 计算机学科的根本问题 计算机学科的根本问题是：什么能被（有效地）自动计算。
计算机学科所有分支领域的根本任务就是进行计算，其实质就是字符串的变换。

29 什么是计算 从字源上考察： 计：从言从十，有数数或计数的含义； 算：从竹从具，指计算工具。 《现代汉语词典》对计算的定义：
根据已知数通过数学方法求得未知数。

30 什么是计算 直观的计算：数的加减乘除；函数的微分、积分；微分方程的求解；定理的证明推导等等。
计算的实质：从一个符号串 f（输入）得出另一个符号串 g（输出）。 数学概念 →普适概念

31 计算的例子 从符号串“12+3”变换成符号串“15”——加法计算 符号串“x2”变换成符号串“2x”——微分；
f 表示一组公理和推导规则，g 是一个定理，那么从 f 到 g 的一系列变换——定理g的证明； 符号串 f 代表一个英文句子，符号串 g 为含义相同的中文句子，那么从 f 到 g 的变换——英文翻译成中文；

32 图灵 Alan Mathison Turing 1912年6月23日－1954年6月7日 英国数学家、逻辑学家 计算机之父 人工智能之父

33 图灵简介 1912年6月23日生于伦敦近郊，因父母一度在国外，童年时缺乏父爱和母爱，自幼起性格和行为很怪癖。
13岁入中学，学习成绩不是很好，只有数学例外，演算能力特别强。此外，擅长赛跑。 1931年中学毕业后考入剑桥大学攻读数学。 1935年，图灵开始对数理逻辑发生兴趣。 1936年，发表了“论可计算数及其在判定问题中的应用”论文，提出了著名的理论计算机模型——图灵机。利用这种计算机，可以把推理化做一些简单的机械动作。

34 图灵简介 随后，应邀于美国普林斯顿大学与美国著名数学家和逻辑学家邱奇合作，并于1938年取得博士学位。
1938年回到英国剑桥大学，从事Z函数的计算方法研究。 1939年为“二战”服务，主要从事破译德军密码工作。 二战后，英国国家家物理实验室(National Physical Laboratory，NPL)新建立的”数学部”，开始设计与建造电子计算机ACE (Automatic Computing Engine)

35 图灵简介 1948年，图灵到曼切斯特大学新成立的皇家学会计算实验室当副主任。
1950年10月发表了论文“计算机和智能” ，进一步阐明了他认为计算机可以有智能的思想，并提出了测试机器是否有智能的方法，大家现在称之为“图灵测试” 。 1951年被选为英国皇家学会院士。 1952年因同性恋被法院传讯，指控行为“极端不当”，给予一年监外察看，并给予药物治疗。 1954年6月7日，距他42周岁生日不到两个星期，因吃了在氰化物溶液中浸泡过的苹果而在家中死去。

36 图灵简介 后人为纪念这位”计算机科学之父”，在英国曼彻斯特的Sackville公园塑了真人大的青铜坐像；ACM于1966了设立了第一个奖项——图灵奖，以推动计算机科学技术的发展和学术交流。 2013年12月24日，在英国司法部长克里斯・格雷灵（Chris Grayling）的要求下，英国女王终于向图灵颁发了的皇家赦免 。

37 图灵模型 一条无限长的工作带：工作带上的每个单元可以存放一个符号；所有允许出现的符号属于一个预先规定好的字母表。 有限状态 控制器 …

38 图灵模型 有限状态 控制器 工作带 … … 一个读写头：读写头可以左移一个单元、右移一个单元或者保持不动。

39 图灵模型 有限状态 控制器 工作带 … … 一个控制器：控制器在每个时刻处于一定的状态，当读写头从工作带上读出一个符号后，控制器就根据这个符号和当时的机器状态，指挥读写头进行读写或者移动，并决定是否改变机器状态。

40 计算与可计算 所谓计算就是计算者（人或机器）对一条可以无限延长的工作带上的符号串执行指令，一步一步地改变工作带上的符号串，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。 什么样的任务才是可计算的任务？这是计算机科学必须要回答的一个最基本的问题。这是关系到计算机能做什么、不能做什么的根本问题。

41 用图灵模型来计算 构造一个识别符号串ω＝anbn（n≥1）的图灵机
基本思想：使读写头往返移动，每往返移动一次，就成对地对输入符号串ω左端的一个a和右端的一个b匹配并做标记x。如果恰好把输入符号串ω的所有符号都做了标记，说明左端的符号a和右端的符号b的个数相等；否则，说明左端的符号a和右端的符号b的个数不相等，或者符号a和b交替出现。

42 用图灵模型来计算 假定n＝2，输入符号串ω＝aabb B a a b b B (q0, a a R q0) (q0, b x L q1)
读写头 B a a b b B 工作带 程序 指令 机器状态 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 当前读 到的字符 当前写 入的字符 读写头的动作 R:右移L:左移H:不动 下一机器状态 控制器

43 用图灵模型来计算 字母表：{a, b, B} B a a b b B (q0, a a R q0) (q0, b x L q1)
读写头 B a a b b B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 控制器 读写头扫描到符号a，则继续往右走

44 用图灵模型来计算 B a a b b B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B a a b b B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 控制器 读写头扫描到符号a，则继续往右走

45 用图灵模型来计算 B a a b b B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B a a b b B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头扫描到符号b， 将当前单元写入字符x， 并使读写头往左走， 转移到状态q1。 控制器

46 用图灵模型来计算 B a a x b B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B a a x b B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头扫描到符号b， 将当前单元写入字符x， 并使读写头往左走， 转移到状态q1。 控制器

47 用图灵模型来计算 B a a x b B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B a a x b B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头扫描到符号a， 则把a改为标记x， 并使读写头往右走， 转移到状态q2 控制器

48 用图灵模型来计算 B a x x b B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B a x x b B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头扫描到符号a， 则把a改为标记x， 并使读写头往右走， 转移到状态q2 控制器

49 用图灵模型来计算 B a x x b B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B a x x b B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头扫描到标记x， 则继续往右走 控制器

50 用图灵模型来计算 B a x x b B (q2, b x L q1) (q2, B B L q3) (q3, x x L q3)
读写头 B a x x b B 工作带 程序 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 若读写头扫描到符号b， 则把b改为标记x， 并使读写头往左走， 转移到状态q1 控制器

51 用图灵模型来计算 B a x x x B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B a x x x B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 若读写头扫描到符号b， 则把b改为标记x， 并使读写头往左走， 转移到状态q1 控制器

52 用图灵模型来计算 B a x x x B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B a x x x B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头扫描到标记x， 则继续往左走 控制器

53 用图灵模型来计算 B a x x x B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B a x x x B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头扫描到符号a， 则把a改为标记x， 并使读写头往右走， 转移到状态q2； 控制器

54 用图灵模型来计算 B x x x x B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B x x x x B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头扫描到标记x， 则继续往右走 控制器

55 用图灵模型来计算 B x x x x B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B x x x x B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头扫描到标记x， 则继续往右走 控制器

56 用图灵模型来计算 B x x x x B (q0, a a R q0) (q0, b x L q1) (q1, x x L q1)
读写头 B x x x x B 工作带 程序 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头扫描到标记x， 则继续往右走 控制器

57 用图灵模型来计算 B x x x x B (q2, b x L q1) (q2, B B L q3) (q3, x x L q3)
读写头 B x x x x B 工作带 程序 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头扫描到空白符B， 说明符号b已处理完毕， 则把状态改为q3， 并使读写头往左走 控制器

58 用图灵模型来计算 B x x x x B (q2, b x L q1) (q2, B B L q3) (q3, x x L q3)
读写头 B x x x x B 工作带 程序 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头扫描到空白符B， 说明符号b已处理完毕， 则把状态改为q3， 并使读写头往左走 控制器

59 用图灵模型来计算 B x x x x B (q2, b x L q1) (q2, B B L q3) (q3, x x L q3)
读写头 B x x x x B 工作带 程序 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头扫描到标记x， 则继续往左走 控制器

60 用图灵模型来计算 B x x x x B (q2, b x L q1) (q2, B B L q3) (q3, x x L q3)
读写头 B x x x x B 工作带 程序 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头扫描到标记x， 则继续往左走 控制器

61 用图灵模型来计算 B x x x x B (q2, b x L q1) (q2, B B L q3) (q3, x x L q3)
读写头 B x x x x B 工作带 程序 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头扫描到标记x， 则继续往左走 控制器

62 用图灵模型来计算 B x x x x B (q2, b x L q1) (q2, B B L q3) (q3, x x L q3)
读写头 B x x x x B 工作带 程序 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头扫描到空白符B， 说明符号a和b已成对标记， 转移到状态q4， 达到接受状态。 控制器

63 从图灵机我们看到了什么？ 思考：将做一件复杂事情的过程分解成许多简单的、机械的步骤，你是否有过成功的经验？
图灵机在一定程度上反映了人类最基本的、最原始的计算能力，它的基本动作非常简单、机械、确定。因此，有条件用真正的机器来实现图灵机。 程序并非必须顺序执行，指令中关于下一状态的指定，实际上表明指令可以不按程序中所表示的顺序执行。这意味着，虽然程序只能按线性顺序来表示指令序列，但程序的实际执行可以与表示的顺序不同。 计算的对象、中间结果和最终结果都在带上，程序则在控制器中。这意味着什么？ 思考：将做一件复杂事情的过程分解成许多简单的、机械的步骤，你是否有过成功的经验？

64 计算机学科的符号化特征 抽象思维 逻辑思维 描述问题 问 题 求解问题 形式化描述 自动化运行 符 号 符号变换

65 Part III. 计算机学科的科学问题

66 什么是科学问题 科学问题是指一定时代的科学认识主体，在已完成的科 学知识和科学实践的基础上，提出的需要解决且有可能
解决的问题，它包含一定的求解目标和应答域，但尚无 确定的答案。 科学问题的提出和解决是任何一个学科持续发展的动力。

67 计算机学科的科学问题 1.计算的平台与环境问题 核心：计算问题的能行性 2.计算过程的能行操作与效率问题 核心：算法及算法分析
3.计算的正确性问题 核心：各种语言的语义 上述基本问题普遍出现在学科的各个分支学科和研究方向之中，是学科研究与发展中经常面对而又必须解决的科学问题。

68 计算机学科的经典问题 经典问题是指那些反映学科某一方面内在规律和本质内容的典型问题。
经典问题往往以深入浅出的形式表达学科深奥的科学规律和本质内容，在学科研究中常常用来辅助说明思想、原理、方法和技术。

69 哥尼斯堡七桥问题与图论 东区 北区 岛区 南区 C A D B
哥尼斯堡七桥问题：是否能在一次步行中穿越全部的七座桥后回到起点，且每座桥只经过一次。

70 哥尼斯堡七桥问题与图论 C A D B 欧拉回路的判定规则： 1. 如果通奇数桥的地方多于两个，则不存在欧拉回路；
1. 如果通奇数桥的地方多于两个，则不存在欧拉回路； 2. 如果只有两个地方通奇数桥，可以从这两个地方之一出发， 找到欧拉回路； 3. 如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。

71 哈密顿回路问题 哈密顿回路：要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。 1 14 15 13 19 20 3 2 16
8 3 14 1 20 2 13 15 4 5 6 7 9 10 11 12 16 17 18 哈密顿回路：要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。

72 哲学家共餐问题与进程同步 哲学家的生活进程可表示为： （1）思考问题；
（2）俄了停止思考，左手拿起一只筷子（如果左侧哲学家已持有它，则等待）； （3）右手拿起一只筷子（如果右侧哲学家已持有它，则等待）； （4）进餐； （5）放下左手筷子； （6）放下右手筷子； （7）重新回到状态（1）思考问题；

73 哲学家共餐问题与进程同步 程序并发执行时进程同步的两个关键问题——死锁和饥饿：
（1）按哲学家的生活进程，当所有的哲学家都同时拿起左手筷子时，则所有哲学家都将拿不到右手筷子，并处于等待状态，那么，哲学家都将无法进餐，最终饿死。 （2）将哲学家的生活进程修改为当拿不到右手筷子时，就放下左手筷子。但是，可能在一个瞬间，所有的哲学家都同时拿起左手筷子，则自然拿不到右手筷子，于是都同时放下左手筷子，等一会，又同时拿起左手筷子，如此重复下去，则所有的哲学家都将无法进餐。

74 汉诺塔问题与计算复杂性 汉诺塔问题：在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。

75 汉诺塔问题与计算复杂性 B A C CA (a) (b) (c) (d)

76 汉诺塔问题与计算复杂性 n个碟子的汉诺塔问题需要移动的碟子数是n-1个碟子的汉诺塔问题需要移动的碟子数的2倍再加1。因此：

77 汉诺塔问题与计算复杂性 64个碟子的汉诺塔问题，需要移动的碟子数为： 264－1＝18,446,744,073,709,551,615
如果每秒移动一次，一年有31,536,000秒，则僧侣们一刻不停地来回移动，也需要花费5849亿年的时间； 假定计算机以每秒1000万个碟子的速度进行移动，则需要花费58,490年的时间。 理论上可以计算的问题，实际上并不一定能行，这属于计算复杂性领域的研究内容。

78 证比求易问题与NP完全问题 在计算复杂性领域中，一般认为求解一个问题往往比较困难，但验证一个问题相对来说就比较容易——证比求易。
求大整数S=49,770,428,644,836,899的因子是个难解问题，但是验证a=223,092,871是不是大整数S的因子却很容易； 求一个线性方程组的解可能很困难，但是验证一组解是否是方程组的解却很容易。

79 证比求易问题与NP完全问题 在计算复杂性领域中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有可以在多项式时间内验证的问题称为NP类问题。 P=NP是否成立是计算科学和当代数学研究中最大的悬而未决的问题之一。 20世纪70年代初，库克在证明了NP类中某些问题的复杂性与整个NP类的复杂性有关，当这些问题中的任何一个存在多项式时间算法，则所有这些NP类问题都是在多项式时间内可解决的，这些问题称为NP完全问题。

80 TSP问题与组合爆炸 TSP问题（又称货郎担问题、邮递员问题、售货员问题）是数学家克克曼于19世纪初提出的一个数学问题，是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。 由于TSP问题有着貌似简单的表述、重要的应用、以及和其他NP完全问题的重要关系，它在近200年的时间里强烈地吸引着计算机科学工作者。

81 TSP问题与组合爆炸 a→d→c→b→a 6 a→d→b→c→a 5 11 a→c→d→b→a 4 a→c→b→d→a 3 2 1 否 18
23 a→d→b→c→a 5 是 11 a→c→d→b→a 4 a→c→b→d→a 3 a→b→d→c→a 2 a→b→c→d→a 1 是否最短 路径长度 路径 序号 8 a b d c 2 3 5 7 1

82 TSP问题与组合爆炸 对于具有n个顶点的TSP问题，可能的解有： (n-1)!/2个。 10城市的TSP问题有大约180,000个可能解。

83 组合爆炸 组合优化问题：寻找一个组合对象，比如一个排列或一个组合，这个对象能够满足特定的约束条件并使得某个目标函数取得极值。
无论从理论的观点还是实践的观点，组合优化问题都是计算领域中最难的问题，其原因是： （1）随着问题规模的增大，组合对象的数量增长产生组合爆炸； （2）还没有一种已知算法能在可接受的时间内，精确地求解绝大多数这类问题。

84 图灵测试与人工智能 提问者 回答者A 回答者B

85 图灵测试与人工智能 行为主义（弱AI）：不要求接受测试的思维机器在内部构造上与人脑相同，而只是从功能的角度来判定机器是否具有思维，也就是从行为角度对机器思维进行定义。 符号主义（强AI）：认知是一种符号处理过程，人类思维过程也可以用某种符号来描述。 由于人们对心理学和生物学的认识还很不成熟，对人脑的结构还没有真正了解，更无法建立起人脑思维完整的数学模型。因此，到目前为止，思维就是计算的思想没有实质性的突破。

86 视频资源 [BBC]阿兰·图灵.Alan.Turing ： 2016谷歌秋季发布会

87 课后作业 结合对教材中计算机经典问题的理解，谈谈你对计算机学科的根本问题及计算机科学问题的理解。 观看视频（二选一），写观后感。
[BBC]阿兰·图灵.Alan.Turing ： 2016谷歌秋季发布会

88 推荐书目 逆袭大学——传给IT学子的正能量 浪潮之巅(第三版) 数学之美 信息简史 世界是数字的 贺利坚，人民邮电出版社 ，2014.4
贺利坚，人民邮电出版社 ，2014.4  浪潮之巅(第三版) 吴军，人民邮电出版社 ，2016.5 数学之美 吴军，人民邮电出版社 ，2012.5 信息简史 詹姆斯·格雷克 ，人民邮电出版社 ， 世界是数字的 Brian W. Kernighan , 人民邮电出版社,

89 给计算机专业的大一新生准备的阅读链接 暗时间 编程大师访谈录 …..