上海高校示范性全英语教学课程建设

上 海 高 校 示 范 性 全 英 语 教 学 课 程 建 设 项 目 申 报 表 学 校 名 称 ( 盖 章 ) 课 程 名 称 ( 中 文 ) 上 海 交 通 大 学 可 计 算 理 论 ( 英 文 ) Computability Theory 课 程 类 别 专 业 基 础 课 专 业 课 基 础 课 课 程 对 象 ( 院 系 专 业 ) 计 算 机 科 学 与 技 术 专 业, 软 件 工 程 专 业 等 选 用 教 材 ( 名 称 出 版 单 位 ) Computability: An Introduction to Recursive Function Theory, Cambridge University Press 开 设 学 期 课 程 负 责 人 申 报 日 期 第 六 学 期 高 晓 沨 2013 年 4 月 28 日 上 海 市 教 育 委 员 会 制

填 写 要 求 一 以 word 文 档 格 式 如 实 填 写 各 项, 空 缺 项 要 填 无 二 表 格 文 本 中 外 文 名 词 第 一 次 出 现 时, 要 写 清 全 称 和 缩 写, 再 次 出 现 时 可 以 使 用 缩 写 三 涉 密 内 容 不 填 写, 有 可 能 涉 密 和 不 宜 大 范 围 公 开 的 内 容, 请 在 说 明 栏 中 注 明 四 开 设 学 期 是 指 在 教 学 计 划 中 的 开 课 学 期 五 表 格 空 间 不 足 的, 可 以 扩 展 或 另 附 纸 张 ; 均 用 A4 纸 打 印, 于 左 侧 装 订 成 册 2

1. 课 程 负 责 人 情 况 姓 名 高 晓 沨 性 别 女 出 生 年 月 1982 年 9 月 最 终 学 历 博 士 研 究 生 专 业 技 术 职 务 副 教 授 电 话 021-34207407 1-1 基 本 信 息 学 位 博 士 行 政 职 务 传 真 021-34207407 所 在 院 系 通 信 地 址 研 究 方 向 计 算 机 科 学 与 工 程 系 学 科 专 业 计 算 机 科 学 与 技 术 上 海 市 闵 行 区 东 川 路 800 号 邮 编 200240 E-mail gao-xf@cs.sjtu.edu.cn 近 两 年 来 授 课 教 学 研 究 情 况 近 似 算 法 数 据 通 信 与 数 据 工 程 1-2 教 学 情 况 授 课 情 况 : [1] 2013 年 春 季 算 法 分 析 与 理 论 ( 英 语 ) 3 学 时 / 周 学 生 27 人 [2] 2013 年 春 季 可 计 算 理 论 ( 英 语 ) 3 学 时 / 周 学 生 41 人 [3] 2012 年 秋 季 计 算 机 科 学 导 论 ( 致 远 学 院 ) 3 学 时 / 周 学 生 54 人 [4] 2012 年 秋 季 离 散 数 学 ( 基 础 平 台 课 程 ) 2 学 时 / 周 学 生 177 人 [5] 2012 年 春 季 可 计 算 理 论 ( 英 语 ) 3 学 时 / 周 学 生 50 人 教 学 研 究 课 题 : [1] 985 工 程 三 期 可 计 算 理 论 本 科 生 全 英 语 教 学 课 程 建 设,2011-2013 负 责 人 [2] 985 工 程 三 期 算 法 分 析 与 理 论 研 究 生 全 英 语 教 学 课 程 建 设, 2011-2013, 负 责 人 [3] 离 散 数 学 上 海 市 精 品 课 程, 主 要 参 与 人 [4] 上 海 交 通 大 学 基 础 学 科 拔 尖 学 生 培 养 计 划 特 别 课 程 计 算 机 科 学 导 论 ( 致 远 学 院 ), 数 理 学 科 负 责 人 近 两 年 来 科 研 情 况 1-3 学 术 研 究 课 程 负 责 人 高 晓 沨 于 2011 年 9 月 加 入 上 海 交 通 大 学 计 算 机 系 近 五 年 内 在 近 似 算 法 网 络 优 化 数 据 工 程 等 领 域 取 得 了 一 系 列 科 研 成 果, 已 发 表 高 质 量 论 文 46 篇 ( 包 括 期 刊 22 篇, 会 议 20 篇, 专 著 章 节 4 篇 ), 其 中 SCI 收 录 16 篇,EI 23 篇,ISTP 6 篇 这 些 期 刊 会 议 论 文 包 括 Theoretical Computer Science (TCS), Journal of Combinatorial Optimization (JOCO), ACM SIGKDD Conference on Knowledge Discovery and Data Mining (SIGKDD),International Conference on Distributed Computing Systems (ICDCS), and International Conference on Database and Expert Systems Applications (DEXA) 等, 大 多 为 国 际 一 流 会 议 和 顶 级 学 术 刊 物 google scholar 显 示 5 年 内 被 引 次 数 275 次, 3

H-Index 为 10,i10-Index 为 10 近 两 年 来 科 研 情 况 如 下 : 学 术 研 究 课 题 : [1] 国 家 自 然 科 学 基 金 青 年 项 目 ( 项 目 主 持 人, 编 号 :NSFC-61202024, 时 间 2013 年 1 月 至 2015 年 12 月 ) [2] 国 家 自 然 科 学 基 金 面 上 项 目 ( 第 一 参 与 者, 编 号 :NSFC-61272443, 时 间 2013 年 1 月 至 2016 年 12 月 ) [3] 上 海 市 自 然 科 学 基 金 青 年 项 目 ( 项 目 主 持 人, 编 号 :12ZR1445000, 时 间 2012 年 9 月 至 2015 年 8 月 ) [4] 上 海 市 教 育 委 员 会 2012 年 度 晨 光 计 划 ( 项 目 主 持 人, 编 号 :12CG09 时 间 2012 年 9 月 至 2014 年 8 月 ) [5] 上 海 交 通 大 学 SMC- 晨 星 青 年 学 者 奖 励 计 划 (B 类 项 目 支 持 人, 时 间 2013 年 1 月 至 2014 年 12 月 ) [6] 上 海 交 通 大 学 新 进 青 年 教 师 启 动 计 划 ( 项 目 主 持 人, 时 间 2011 年 12 月 至 2013 年 12 月 ) 近 两 年 发 表 学 术 研 究 论 文 : [1] Xiaofeng Gao, Zaixin Lu, Weili Wu, and Bing Fu, Algebraic Data Retrieval Algorithms for Multi-Channel Wireless Data Broadcast, Theoretical Computer Science, online published, http://dx.doi.org/10.1016/j.tcs.2011.12.070, 2012. (SCI Indexed, 计 算 机 系 A 类 奖 励 期 刊 ) [2] Jiaofei Zhong, Weili Wu, Xiaofeng Gao, and Yan Shi, Xiaodong Yue, Efficient Redesign and Comparison of Various Indexing Schemes for Wireless Data Broadcasting, to appear on Knowledge and Information Systems (KAIS), 2013. (SCI Indexed, Corresponding Author) [3] Xiaofeng Gao, Weili Wu, Xuefei Zhang, and Xianyue Li, A Constant-Factor Approximation for d-hop Connected Dominating Sets in Unit Disk Graph, International Journal of Sensor Networks, Vol. 12, No. 3, pp. 125-136, 2012. [4] Jun Li, and Xiaofeng Gao, Performance Analysis for Approximating MCDS in Wireless Ad-Hoc Network, Information: An International Interdisciplinary Journal, Vol.15, No.12, pp.252-258, 2012. (SCI Indexed, Corresponding Author) [5] Shan Shan, Weili Wu, Wei Wang, Hongjie Du, Xiaofeng Gao, Ailian Jiang: Constructing minimum interference connected dominating set for multi-channel multi-radio multi-hop wireless network, International Journal of Sensor Networks, 11(2): 100-108, 2012. (SCI Indexed) [6] Yi Zhu, Xiaofeng Gao, Weili Wu, Jason Jue, Efficient impairment-constrained 3R regenerator placement for light-trees in optical networks, IEEE/OSA Journal of Optical Communications and Networking, 3(4): 359-371, 2011. (SCI Indexed) 4

[7] Shuo Zhang, Xiaofeng Gao, Weili Wu, Jianzhong Li, and Hong Gao, Efficient Algorithms for Supergraph Query Processing on Graph Database, Journal of Combinatorial Optimization, 21(2): 159-191, 2011. (SCI Indexed) [8] Ling Ding, Xiaofeng Gao, Weili Wu, Wonjun Lee, Xu Zhu and Ding-Zhu Du, An Exact Algorithm for Minimum CDS with Shortest Path Constraint in Wireless Networks, Optimization Letters, 5(2): 297-306, 2011. [9] Suogang Gao, Zengti Li, Jiangchen Yu, Xiaofeng Gao, and Weili Wu, DNA Library Screening, Pooling Design and Unitary Spaces, Theoretical Computer Science, 412(3): 217-224, 2011. [10] Yongtian Yang, Xiaofeng Gao, Xinlu, Jiaofei Zhong and Guihai Chen, Distributed AH-Tree Based Index Technology for Multi-Channel Wireless Data Broadcast, The 18th International Conference on Database Systems for Advanced Applications (DASFAA), 2013. (Corresponding Author) [11] Wei Wei, Xuanzhong Wei, Tao Chen, Xiaofeng Gao, and Guihai Chen, Dynamic Correlative VM Placement for Quality-Assured Cloud Service, IEEE International Conference On Communications (IEEE ICC), 2013. (Corresponding Author) [12] Xiaofeng Gao, Yi Zhu, Donghyun Kim, Jianzhong Li, and Weili Wu, A Novel Multi-Channel Data Broadcast Scheme for Multimedia Database System, Proceedings of the 18th International Conference on Parallel and Distributed Systems (IEEE ICPADS), December 17-19, 2012. [13] Xin Lu, Xiaofeng Gao, and Yongtian Yang, SETMES: A Scalable and Efficient Tree-based Mechanical Scheme for Multi-Channel Wireless Data Broadcast, The 7th International Conference on Ubiquitous Information Management and Communication (ACM ICUIMC 2013), Sep. 2012. (Corresponding Author). [14] Guobao Sun, Fan Wu, Xiaofeng Gao, and Guihai Chen, PHED: Pre-Handshaking Neighbor Discovery Protocols in Full Duplex Wireless Ad Hoc Networks, to appear on the IEEE Global Communications Conference (IEEE GLOBECOM), December 3-7, 2012. [15] Kai Yang, Yan Shi, Weili Wu, Xiaofeng Gao, and Jiaofei Zhong, A Novel Hash-Based Streaming Scheme for Energy Efficient Full-Text Search in Wireless Data Broadcast, The 16th International Conference on Database Systems for Advanced Applications (DASFAA), Part I, LNCS 6587, pp. 372 388, 2011. [16] Jiaofei Zhong, Weili Wu, Yan Shi, and Xiaofeng Gao, Energy-Efficient Tree-Based Indexing Schemes for Information Retrieval in Wireless Data Broadcast, The 16th International Conference on Database Systems for Advanced Applications (DASFAA), Part II, LNCS 6588, pp. 335 351, 2011. 5

国 外 学 习 经 历 ; 英 语 教 学 经 历 ( 含 课 程 名 称 学 时 数 学 生 数 开 设 时 间 ) 海 外 学 习 工 作 经 历 : [1] 2006-2010, 美 国 德 克 萨 斯 大 学 达 拉 斯 分 校, 计 算 机 科 学 与 工 程 系, 获 博 士 学 位 [2] 2010-2011, 美 国 佐 吉 亚 温 纳 特 学 院, 信 息 技 术 方 向, 助 理 教 授 1-4 英 语 水 平 及 英 语 教 学 海 外 教 学 经 历 : 美 国 佐 吉 亚 温 纳 特 学 院, 任 2 门 课 程 主 讲 人 ( 共 6 次 ) [1] 2011 春,ITEC1001 Introduction to Computing (3 Sections,4 学 时 / 周, 共 63 人 ) [2] 2010 秋,ITEC1001 Introduction to Computing (2 Sections,4 学 时 / 周, 共 42 人 ) [3] 2010 秋,ITEC2110 Digital Media (1 Section,4 学 时 / 周, 共 23 人 ) 美 国 德 克 萨 斯 大 学 达 拉 斯 分 校, 任 11 门 课 程 助 教 ( 共 15 次 ) [4] 2009 秋,CS6363 Design & Analysis-Computer Algorithm (Graduate) [5] 2009 秋,CS6369 Complexity for Combinatorial Algorithm (Graduate) [6] 2009 春,CS6360 Database Design (Graduate) [7] 2009 春,CS4347 Database System (Undergraduate) [8] 2008 秋,CS5349 Automata Theory (Graduate) [9] 2008 秋,CS4384 Automata (Undergraduate) [10] 2008 夏,CS6385 Telecommunication Network Management [11] 2008 春,CS6360 Database Design (Graduate) [12] 2008 春,CS4347 Database System (Undergraduate) [13] 2007 秋,CS5349 Automata Theory (Graduate) [14] 2007 秋,CS4384 Automata (Undergraduate) [15] 2007 春,CS5333 Discrete Structure (Undergraduate) [16] 2007 春,CS1337 Computer Science I (Java, Undergraduate) [17] 2006 秋,CS3354 Software Engineering (Undergraduate) [18] 2006 秋,CS1337 Computer Science I (Java, Undergraduate) 近 两 年 教 学 科 研 获 奖 情 况 1-5 获 奖 情 况 [1] 2012 年 度 上 海 市 教 育 委 员 会 晨 光 计 划 奖 励 [2] 2012 年 度 上 海 交 通 大 学 SMC- 晨 星 青 年 学 者 奖 励 计 划 (B 类 ) [3] 2012 年 度 国 际 运 筹 育 管 理 科 学 大 会 (IMS) 最 佳 论 文 奖 (Best Paper Award) [4] 2011 年 度 新 疆 维 吾 尔 自 治 区 第 十 一 届 自 然 科 学 优 秀 学 术 论 文 二 等 奖 ( 第 二 完 成 人 ) [5] 2011 年 度 中 国 运 筹 协 会 第 十 届 运 筹 新 人 奖 [6] 2011-2012 第 二 学 期 电 子 信 息 与 电 气 工 程 学 院 英 语 授 课 奖 励 6

奖 状 与 证 书 7

2. 教 学 队 伍 情 况 2-1 人 员 构 成 ( 含 外 聘 教 师 ) 姓 名 性 别 出 生 年 月 专 业 技 术 职 务 学 科 专 业 在 教 学 中 承 担 的 工 作 傅 育 熙 男 1962.2 教 授 计 算 机 科 学 与 技 术 高 晓 沨 女 1982.9 副 教 授 计 算 机 科 学 与 技 术 龙 环 女 1978.10 讲 师 计 算 机 科 学 与 技 术 课 程 建 设 与 授 课 课 程 建 设 与 授 课 课 程 建 设 与 授 课 除 课 程 负 责 人 外 的 其 他 主 讲 教 师 情 况 简 介 ( 国 外 学 习 经 历 ; 近 两 年 来 授 课 教 学 研 究 情 况 ) 主 讲 教 师 傅 育 熙 情 况 简 介 2-2 主 讲 教 师 情 况 个 人 简 介 傅 育 熙, 博 士 教 授 博 士 生 导 师, 国 家 杰 出 青 年 获 得 者 1994 年 1 月 起 在 上 海 交 通 大 学 计 算 机 科 学 与 工 程 系 工 作,1999 年 2 月 任 上 海 交 通 大 学 计 算 机 科 学 与 工 程 系 常 务 副 主 任,2000 年 2 月 -2009 年 5 月 任 上 海 交 通 大 学 计 算 机 科 学 与 工 程 系 主 任,2004 年 任 全 国 示 范 性 软 件 学 院 院 长 联 席 会 主 席 现 为 上 海 交 通 大 学 软 件 学 院 院 长 上 海 高 校 软 件 理 论 研 究 中 心 主 任 教 育 部 高 等 学 校 计 算 机 科 学 与 技 术 教 学 指 导 委 员 会 专 业 教 学 指 导 分 委 员 会 委 员 教 育 部 高 等 学 校 计 算 机 科 学 与 技 术 教 学 指 导 委 员 会 计 算 机 科 学 与 技 术 专 业 教 学 指 导 分 委 员 会 副 主 任 委 员 国 务 院 学 位 委 员 会 第 六 届 学 科 评 议 组 成 员 上 海 市 计 算 机 学 会 副 理 事 长 Asian Association for Foundation of Software 的 执 行 委 员 上 海 市 计 算 机 行 业 协 会 副 会 长 是 Mathematical Structures in Computer Science 等 十 多 个 学 术 刊 物 的 编 委 目 前 主 要 从 事 理 论 计 算 机 科 学 基 础 理 论 研 究, 曾 先 后 在 法 国 巴 黎 七 大 日 本 东 京 大 学 法 国 国 家 信 息 研 究 所 进 行 访 问 研 究 在 国 际 学 术 刊 物 上 发 表 论 文 五 十 余 篇, 先 后 担 任 多 个 国 际 会 议 的 cochair, 多 个 国 际 会 议 ( 如 ICSE 2006) 的 程 序 委 员 会 成 员 曾 负 责 近 二 十 个 国 家 级 科 研 项 目 的 研 究 海 外 学 习 工 作 经 历 : [1] 1988 年 由 国 家 教 委 公 派 至 英 国 曼 彻 斯 特 大 学 计 算 机 系 攻 读 博 士 学 位, 1992 年 获 博 士 学 位 [2] 1993 年 至 1994 年 在 曼 彻 斯 特 大 学 计 算 机 系 作 研 究 助 理 近 两 年 授 课 情 况 : [1] 2013 春 季 计 算 理 论 ( 研 究 生 英 语 ) 3 学 时 / 周 学 生 14 人 [2] 2013 春 季 程 序 语 言 理 论 ( 研 究 生 英 语 ) 3 学 时 / 周 学 生 10 人 [3] 2012 秋 季 可 计 算 理 论 3 学 时 / 周 学 生 107 人 [4] 2012 春 季 可 计 算 理 论 3 学 时 / 周 学 生 30 人 [5] 2011 秋 季 算 法 原 理 3 学 时 / 周 学 生 数 121 人 8

学 术 研 究 课 题 : [1] 新 型 逻 辑 框 架 和 新 型 计 算 模 型,863 高 科 技 项 目,1994 年 1 月 至 1995 年 12 月, 课 题 负 责 人 ; [2] 逻 辑 类 型 理 论, 国 家 教 委 留 学 回 国 人 员 基 金,1995 年 1 月 至 1997 年 12 月, 课 题 负 责 人 ; [3] 逻 辑 类 型 理 论 的 语 义 及 其 应 用, 国 家 自 然 科 学 基 金 项 目,1996 年 1 月 至 1997 年 12 月, 课 题 负 责 人 ; [4] 并 发 计 算 的 元 模 型,863 高 科 技 项 目,1998 年 1 月 至 2000 年 12 月, 课 题 负 责 人 ; [5] 并 发 计 算 模 型 c - 演 算 的 理 论 研 究, 国 家 自 然 科 学 基 金 项 目 1999 年 1 月 至 2001 年 12 月, 课 题 负 责 人 ; [6] 内 类 型 理 论, 国 家 自 然 科 学 基 金,2000 年 1 月 至 2002 年 12 月, 课 题 负 责 人 ; [7] 基 本 并 发 计 算 模 型 的 理 论 研 究, 教 育 部 资 助 优 秀 青 年 教 师,2000 年 1 月 至 2001 年 12 月, 课 题 负 责 人 ; [8] 元 并 发 模 型 的 理 论 研 究, 高 等 学 校 骨 干 教 师 资 助 计 划,2000 年 1 月 至 2001 年 12 月, 课 题 负 责 人 ; [9] M- 可 解 性 M- 计 算 复 杂 性 与 计 算 机 科 学 的 模 型 理 论, 国 家 自 然 科 学 基 金 重 点 项 目, 课 题 负 责 人 ; [10] 计 算 机 科 学 的 结 构 与 核 心 基 础 理 论, 上 海 市 科 委 学 科 带 头 人 项 目, 项 目 负 责 人 ; [11] 多 线 程 程 序 语 言 的 程 序 分 析 研 究, 国 家 自 然 科 学 基 金 国 际 ( 地 区 ) 合 作 与 交 流 项 目, 项 目 负 责 人 代 表 性 学 术 研 究 成 果 : [1] Chaodong He, Yuxi Fu, Hongfei Fu. Decidability of Behavioral Equivalences in Process Calculi with Name Scoping. In Proceedings of FSEN 2011, volume 7141 of Lecture Notes in Computer Science, page 284-298. Springer, 2012. [2] Xiaojuan Cai, Yuxi Fu. The λ-calculus in the π-calculus. Mathematical Structures in Computer Science, 21(5): 943-996 (2011). [3] Yuxi Fu. Theory by Process. In Proceedings of CONCUR 2010, volume 6296 of Lecture Notes in Computer Science, pages 403-416, Springer, 2010. [4] Yuxi Fu, Hao Lu. On the Expressiveness of Interaction. Theoretical Computer Science, 411:1387-1451, 2010. [5] Yuxi Fu. Fair ambients, Acta Informatica, 43(8):535-594, 2007 [6] Yuxi Fu. On quasi open bisimulation. Theoretical Computer Science, 338:96-126, 2005. [7] Yuxi Fu, Zhengrong Yang. Understanding the mismatch combinator in chi calculus. Theoretical Computer Science, 290:779-830, 2003. [8] Yuxi Fu. Testing congruence for mobile process. Journal of Computer Science and Technology, 17(1):73-82, 2002. 9

[9] Yuxi Fu. Semantics of constructions (I): The traditional approach. Journal of Computer Science and Technology, 16(1):13-25, 2001. [10] Yuxi Fu. Semantics of constructions (II): The initial algebraic approach. Journal of Computer Science and Technology, 16(2):137-145, 2001. 获 奖 情 况 : [1] 2011 年 度 上 海 市 优 秀 学 科 带 头 人 [2] 2003 年 度 国 家 杰 出 青 年 基 金 获 得 者 [3] 2000 年 度 国 务 院 政 府 特 殊 津 贴 [4] 2000 年 度 上 海 市 政 府 特 殊 津 贴 [5] 1999 年 度 中 创 软 件 奖 [6] 1997 年 度 上 海 市 优 秀 青 年 教 师 主 讲 教 师 龙 环 情 况 简 介 个 人 简 介 龙 环, 博 士 讲 师 硕 士 生 导 师 2009 年 获 上 海 交 通 大 学 计 算 机 科 学 与 工 程 专 业 博 士, 同 年 起 在 上 海 交 通 大 学 计 算 机 科 学 与 工 程 系 工 作, 现 为 上 海 高 校 软 件 理 论 研 究 中 心 助 理 研 究 员 中 国 计 算 机 学 会 成 员, 目 前 主 要 从 事 理 论 计 算 机 科 学 基 础 理 论 的 研 究, 曾 在 日 本 Nagoya University 进 行 访 问 研 究, 即 将 由 国 家 留 学 基 金 委 员 会 公 派 赴 英 国 爱 丁 堡 大 学 学 习 在 国 际 学 术 刊 物 上 发 表 论 文 十 余 篇 近 两 年 授 课 情 况 : [1] 2013 春 季 离 散 数 学 ( 英 语 ) 3 学 时 / 周 学 生 58 人 [2] 2013 春 季 可 计 算 理 论 3 学 时 / 周 学 生 81 人 [3] 2012 秋 季 计 算 机 科 学 导 论 3 学 时 / 周 学 生 54 人 [4] 2012 春 季 可 计 算 理 论 3 学 时 / 周 学 生 79 人 [5] 2012 春 季 离 散 数 学 ( 英 语 ) 3 学 时 / 周 学 生 78 人 [6] 2011 春 季 离 散 数 学 ( 英 语 ) 3 学 时 / 周 学 生 54 人 海 外 学 习 经 历 : [1] 2012 年 日 本 Nagoya University Visiting Scholar [2] 2013 年 英 国 爱 丁 堡 大 学 Visiting Scholar 学 术 研 究 课 题 : [1] 国 家 自 然 科 学 基 金 青 年 项 目,2013 年 1 月 至 2015 年 12 月, 课 题 负 责 人 ; [2] 国 家 教 育 部 博 士 点 基 金 新 教 师 类,2013 年 1 月 至 2014 年 12 月, 课 题 负 责 人 10

3. 课 程 描 述 3-1 本 课 程 教 学 理 念 与 目 标 可 计 算 理 论 (Computability Theory), 又 称 算 法 理 论, 是 计 算 机 理 论 基 础 的 重 要 基 石, 也 是 算 法 设 计 与 分 析 的 基 础 它 是 研 究 计 算 一 般 性 质 的 数 学 理 论, 通 过 建 立 计 算 的 数 学 模 型 ( 例 如 图 灵 机 ), 精 确 区 分 哪 些 问 题 是 可 计 算 的, 哪 些 问 题 是 不 可 计 算 的 它 从 广 义 上 描 绘 了 什 么 样 的 问 题 可 以 使 用 计 算 机 来 解 决, 使 得 人 们 不 必 浪 费 时 间 在 不 可 能 解 决 的 问 题 上 ( 因 而 可 以 尽 早 转 而 使 用 除 计 算 机 以 外 更 加 有 效 的 手 段 ), 集 中 资 源 在 可 以 解 决 的 问 题 可 计 算 理 论 是 算 法 设 计 软 件 开 发 等 应 用 的 理 论 基 础, 也 是 计 算 复 杂 性 的 前 驱 工 作, 在 计 算 机 理 论 科 学 中 有 着 重 要 意 义, 也 使 得 可 计 算 理 论 课 程 在 计 算 机 科 学 体 系 中 占 有 至 关 重 要 的 地 位, 并 成 为 计 算 机 科 学 与 软 件 工 程 学 科 培 养 计 划 中 的 基 础 课 程 对 可 计 算 理 论 的 学 习 是 计 算 机 科 学 软 件 工 程 专 业 学 生 需 要 掌 握 的 重 要 基 础 课 程, 它 就 如 微 积 分 高 等 代 数 课 程 一 般 是 计 算 机 学 科 其 他 课 程 的 基 础 构 架 本 课 程 所 依 托 的 上 海 交 通 大 学 计 算 机 科 学 与 技 术 学 科 是 教 育 部 认 定 的 国 家 一 级 重 点 学 科 希 望 通 过 全 英 语 教 学 的 实 施, 能 够 使 本 课 程 的 教 学 内 容 更 加 符 合 国 际 化 一 流 化 和 前 沿 化 的 目 标, 让 学 生 实 时 掌 握 最 新 的 理 论 和 实 践 知 识, 提 高 他 们 应 对 高 速 发 展 的 计 算 机 领 域 的 问 题 解 决 能 力 可 计 算 理 论 Computability Theory 课 程 主 要 介 绍 计 算 可 解 性 的 概 念 与 理 论 本 课 程 的 教 学 目 标 是, 让 学 生 掌 握 计 算 数 学 模 型 的 基 本 概 念, 了 解 计 算 可 解 性 的 概 念, 掌 握 计 算 机 可 解 性 的 一 般 规 律 通 过 本 课 程 的 学 习, 学 生 将 理 解 计 算 机 理 论 基 础 与 计 算 能 力 范 畴, 为 将 来 学 习 计 算 机 应 用 与 软 件 工 程 打 下 坚 实 基 础 3-2 教 学 内 容 选 择 与 安 排 可 计 算 理 论 Computability Theory 是 计 算 机 科 学 的 基 础 课 程, 课 程 理 论 教 学 包 含 48 学 时, 其 最 核 心 最 基 本 的 内 容 可 分 为 计 算 模 型 广 义 模 型 可 计 算 集 三 大 部 分 三 部 分 之 间 呈 递 进 关 系, 逐 步 向 学 生 展 示 可 计 算 理 论 的 核 心 思 想 和 计 算 模 型 的 可 计 算 性 具 体 内 容 组 织 安 排 如 下 : ( 一 ) 可 计 算 理 论 概 论 (2 学 时 ) 1. 教 学 目 标 : 通 过 介 绍 可 计 算 理 论 的 历 史 发 展 重 要 概 念 分 支 学 科, 使 学 生 对 整 门 课 程 有 整 体 了 解, 达 到 自 顶 向 下 提 纲 挈 领 的 作 用 同 时 涵 盖 基 础 课 程 复 习 与 概 念 介 绍, 帮 助 学 生 复 习 预 备 知 识, 并 统 一 符 号 与 概 念 体 系 2. 基 本 概 念 :Computational Complexity, Computability Theory, Formal Language, Complexity Class, Chomsky Hierarchy, Set, Degree, Function, Relation, Computable Functions, Turing machine, Symbols, Notations, URM, Decidable 3. 综 合 性 问 题 :History of Computation, Branches for Theory of Computation, Church s 11

Thesis, Computational Complexity Theory, Formal Languages, Complexity Classes, Recursive, Linear-Bounded Automata, Preliminary for Computation, Fundamental Concepts for Computation ( 二 ) 计 算 模 型 (16 学 时, 课 程 重 点 ) 1. 教 学 目 标 : 通 过 对 无 限 注 册 机 图 灵 机 递 归 函 数 等 计 算 模 型 的 介 绍, 让 学 生 理 解 什 么 是 抽 象 的 计 算 模 型, 计 算 模 型 的 定 义 与 演 算 方 式, 计 算 模 型 的 能 力 统 一 性, 并 最 终 理 解 可 计 算 问 题 与 可 计 算 函 数 的 概 念 2. 基 本 概 念 :Algorithm, Effective Procedures, Computable, Decidable, Coding, Recursive Function, Mineralization, Basic Functions, Standard Form, Turing Computable Function, Post System, Denumerable 3. 综 合 性 问 题 :Unlimited Register Machine, Turing machine, Join Programs, Ackermann Function, Primitive/Partial Recursive Functions, Diagonal Method ( 三 ) 广 义 模 型 (15 学 时, 课 程 重 点 ) 1. 教 学 目 标 : 通 过 介 绍 丘 奇 - 图 灵 定 理 歌 德 尔 编 码 通 用 程 序 等 理 论, 让 学 生 从 更 高 地 角 度 理 解 可 计 算 性 的 概 念, 并 进 一 步 认 识 到 计 算 机 计 算 能 力 的 局 限 性 与 统 一 性, 理 解 计 算 机 理 论 模 型 的 通 用 性 2. 基 本 概 念 :Church s Thesis, Universal Programs, Universal Functions, Godel Encoding, Effective Denumerable, Godel's Incompleteness Theory 3. 综 合 性 问 题 :Effective Operation, Kleene s Normal Form Theorem, Diagonal Method, Numbering Computable Functions, The s-m-n Theorem, Proof Using Church s Thesis ( 四 ) 可 计 算 集 (15 学 时, 高 阶 扩 展 ) 1. 教 学 目 标 : 通 过 对 可 计 算 问 题 的 进 一 步 分 类, 让 学 生 理 解 可 计 算 问 题 的 难 度 特 性, 并 学 会 区 分 问 题 的 可 解 性 这 部 分 内 容 对 学 生 以 后 的 学 习 十 分 重 要, 是 学 生 进 一 步 理 解 可 计 算 理 论 的 扩 展 与 细 化 2. 基 本 概 念 :Decidability, Undecidability, Partial Decidability, Recursive Set, Recursively Enumerable Set, Productive Set, Creative Set, Simple Set, Reducibility, Turing Degrees, Diophantine Equation, Post System 3. 综 合 性 问 题 :The Halting Problem, Rice Theorem, Turing Reducibility, Many-one Reducibility, Many-one Equivalent, URMO, Relative Computability, m-complete, m-degrees 四 个 部 分 之 间 呈 链 式 递 进 关 系, 由 浅 入 深 逐 步 细 化, 从 不 同 角 度 不 同 方 式 展 现 计 算 机 科 学 的 理 论 基 础, 使 得 学 生 了 解 什 么 样 的 问 题 是 计 算 机 可 以 求 解 的, 计 算 机 求 解 问 题 的 效 率 如 何, 为 学 生 今 后 的 实 践 操 作 与 算 法 学 习 打 下 坚 实 的 基 础 以 下 图 1 是 2012 年 度 可 计 算 理 论 的 课 程 安 排, 图 2 是 该 年 度 课 程 表 12

图 1:2012 年 度 可 计 算 理 论 日 程 安 排 图 2:2012 年 度 可 计 算 理 论 排 课 情 况 13

3-3 教 学 方 法 手 段 ( 举 例 说 明 采 用 的 各 种 教 学 方 法 及 手 段 的 使 用 目 的 实 施 过 程 实 施 效 果 ) 可 计 算 理 论 Computability Theory 是 一 门 理 论 性 的 基 础 核 心 课 程, 根 据 本 课 程 的 特 点, 教 学 组 采 用 启 发 式 教 学 模 式, 利 用 深 入 式 互 动 促 进 师 生 交 流, 通 过 计 算 模 型 深 入 理 解 知 识, 建 立 自 顶 而 下 刚 要 引 领 的 课 程 设 计 体 系, 并 将 教 学 与 科 研 有 机 结 合, 取 得 了 较 好 的 教 学 效 果 1. 启 发 式 教 学 模 式 在 明 确 的 教 学 目 标 引 领 下, 通 过 在 授 课 过 程 中 逐 步 引 导 学 生 掌 握 解 决 问 题 的 方 式 方 法, 让 学 生 直 接 参 与 探 索 教 学, 充 分 发 挥 学 生 的 主 观 能 动 性, 开 发 学 生 的 创 新 能 力, 使 学 生 在 学 习 中 有 成 就 感 例 如, 通 过 举 例 企 业 在 开 发 软 件 过 程 中, 应 用 可 计 算 理 论 可 以 避 免 许 多 徒 劳 无 果 的 尝 试, 进 而 让 学 生 们 领 会 到 可 计 算 理 论 在 计 算 机 领 域 的 重 要 性 通 过 播 放 可 计 算 理 论 历 史 的 教 学 视 频 让 学 生 对 该 学 科 的 发 展 有 更 直 观 的 认 识 通 过 往 届 的 上 课 同 学 在 研 究 生 入 学 考 试 及 找 工 作 的 面 试 经 历 让 学 生 体 会 到 工 业 界 和 学 术 界 对 可 计 算 理 论 的 重 视 实 践 证 明, 这 种 启 发 式 的 教 学 模 式 对 于 理 论 性 较 强 的 课 程 适 用 良 好, 课 堂 教 学 效 率 较 高 图 3: 可 计 算 理 论 历 史 发 展 教 学 视 频 示 例 14

2. 深 入 式 互 动 交 流 由 于 理 论 课 程 特 有 的 难 以 理 解 抽 象 复 杂 的 特 征, 许 多 同 学 在 学 习 过 程 中 缺 乏 兴 趣, 积 极 性 低, 对 课 程 了 解 也 并 不 清 晰 因 此 理 论 性 课 程 往 往 缺 勤 率 高 作 业 完 成 质 量 低 学 生 学 习 效 果 和 教 评 分 数 都 不 十 分 理 想 为 克 服 这 一 问 题, 本 课 程 特 别 注 重 注 重 师 生 之 间 同 学 之 间 的 互 动 交 流, 以 增 加 同 学 积 极 性 和 参 与 感, 培 养 课 堂 默 契, 培 养 师 生 感 情 具 体 思 想 为, 注 重 学 生 反 馈, 及 时 调 整 教 学 方 式 ; 结 合 教 学 内 容, 利 用 案 例 教 学 法 讨 论 法 角 色 扮 演 法 等 教 学 方 法, 通 过 积 极 参 与 共 同 促 进 的 双 向 沟 通 方 式 来 进 行 授 课, 寓 教 于 乐 例 如, 通 过 给 学 生 制 作 桌 牌, 让 课 堂 更 为 正 式, 增 添 学 生 的 责 任 感 ; 通 过 给 课 程 建 设 学 生 名 册, 让 同 学 彼 此 更 了 解 课 堂, 增 添 学 生 的 从 属 感 ; 通 过 照 相 记 录 课 堂 情 况, 增 加 师 生 的 互 动 了 解, 并 督 促 学 生 考 勤 ; 通 过 和 学 生 单 独 见 面 沟 通, 清 楚 掌 握 学 生 在 课 程 教 学 上 的 需 求 ; 借 助 于 google group 邮 件 群, 加 强 和 同 学 之 间 的 学 术 讨 论 ; 通 过 设 置 答 疑 时 间, 方 便 同 学 随 时 求 学 解 惑 ; 通 过 对 助 教 的 专 业 培 养, 增 加 助 教 辅 助 作 用, 使 得 学 生 有 更 多 机 会 获 得 专 业 指 导 实 践 证 明, 深 入 交 流 互 动 能 够 增 强 学 生 对 课 程 的 兴 趣, 并 能 激 发 学 生 的 自 主 能 动 性, 他 们 不 但 认 真 完 成 课 程 任 务, 还 会 主 动 帮 忙 共 同 建 设 课 程 图 4:2012 年 度 可 计 算 理 论 班 级 合 影 图 5:2012 年 度 可 计 算 理 论 课 堂 记 录 (2012 年 3 月 28 日 ) 15

图 6: 课 程 邮 件 群 (Google Group) 使 用 图 7: 课 程 信 件 示 例 16

图 8: 可 计 算 理 论 课 程 网 页 展 示 17

3. 计 算 模 型 深 化 理 解 通 过 提 供 课 外 阅 读 和 网 络 参 考 资 源, 能 够 开 阔 学 生 的 视 野, 使 学 生 更 加 深 入 地 理 解 可 计 算 理 论 中 的 基 本 概 念 例 如, 在 讲 授 无 限 注 册 机 (URM) 的 过 程 中, 通 过 提 供 URM 测 试 网 站, 使 同 学 们 可 以 自 己 测 试 URM 的 运 行 方 式, 对 URM 知 识 点 更 加 清 楚 在 讲 授 哥 德 尔 不 完 备 定 理 时, 提 供 原 始 手 稿 等 材 料, 让 学 生 对 可 计 算 理 论 的 发 展 有 更 直 观 的 认 识 图 9: 无 限 注 册 机 模 拟 网 页 展 示 图 10: 无 限 注 册 机 课 件 展 示 18

4. 自 顶 而 下 纲 要 引 领 课 程 教 授 过 程 中, 有 必 要 不 时 地 将 所 学 知 识 进 行 归 纳 总 结, 将 看 似 独 立 的 知 识 串 连 起 来, 从 整 体 把 握 全 局, 使 得 学 生 可 以 更 加 清 楚 明 白 可 计 算 理 论 的 内 涵 例 如, 考 前 通 过 提 供 Question List 和 Checklist, 可 以 帮 助 学 生 更 好 地 梳 理 所 学 知 识, 把 握 自 顶 向 下 的 结 构, 更 加 深 入 理 解 计 算 机 的 运 算 限 制 和 有 效 可 解 问 题 的 概 念 图 11:2012 年 度 可 计 算 理 论 复 习 纲 要 19

5. 教 学 与 科 研 相 结 合 教 学 过 程 中, 穿 插 相 关 科 研 前 沿 动 态, 如 介 绍 最 新 的 PCP 复 杂 性 定 理 等 最 新 结 论, 鼓 励 学 生 参 与 科 研 项 目, 培 养 学 生 的 创 新 能 力 目 前, 已 有 多 名 本 科 生 在 相 关 领 域 取 得 了 突 破 性 的 进 展, 且 相 关 工 作 发 表 在 近 似 算 法 计 算 机 网 络 数 据 工 程 等 领 域 的 多 个 国 际 著 名 期 刊 和 会 议 如 参 与 过 本 课 程 的 2009 级 本 科 生, 目 前 已 发 表 算 法 相 关 论 文 多 篇, 正 在 参 与 2013 年 度 可 计 算 理 论 的 同 学 还 有 若 干 投 出 论 文 在 审 稿 过 程 和 准 备 过 程 中 已 发 表 论 文 列 表 : [1]. Wei Wei, Xuanzhong Wei, Tao Chen, Xiaofeng Gao, and Guihai Chen. Dynamic Correlative VM Placement for Quality-Assured Cloud Service, IEEE International Conference On Communications (IEEE ICC 2013). [2]. Wei Wei, Xuanzhong Wei, Xiaofeng Gao, and Guihai Chen. Wireless Technology for Data- center Networks, ZTE Communications, vol. 18, pp. 1 6, 2012. [3]. Guobao Sun, Fan Wu, Xiaofeng Gao, and Guihai Chen, PHED: Pre-Handshaking Neighbor Discovery Protocols in Full Duplex Wireless Ad Hoc Networks, IEEE Global Communications Conference (IEEE GLOBECOM 2012), Anaheim, CA, USA, Dec. 3-7, 2012. [4]. Guobao Sun, Fan Wu, Xiaofeng Gao, Guihai Chen, and Wei Wang, Time-Efficient Protocols for Neighbor Discovery in Wireless Ad Hoc Networks, to appear in IEEE Transactions on Vehicular Technology (TVT), 2013. 已 投 出 与 在 准 备 论 文 列 表 : [1]. Xiaofeng Gao, Wei Wei, Xuanzhong Wei, Tao Chen, Guihai Chen, NEMO: A Novel Efficient Multicast Routing Scheme for Hybrid Data Center Networks, Submission to IEEE Global Communications Conference (IEEE GLOBECOM 2013), Atlanta, USA, Dec. 9-13, 2013. [2]. Wanchao Liang, Wei Wei. Xiaofeng Gao, Guihai Chen, RobinHood: Traffic Load Balancing of Devolved Controllers in Data Center Network, to submit to the 33rd IEEE International Conference on Computer Communications (IEEE INFOCOM 2014). [3]. Xiaofeng Gao, Wei Wei, Xuanzhong Wei, Haibin Guan, Guihai Chen, Wireless Communications in Data Center Networks, to submit to Journal of Network and Computer Applications (JNCA), 2013. 20

3-4 考 核 ( 考 试 ) 方 法 考 核 准 则 : 1) 强 调 概 念 与 理 解 : 考 试 分 为 选 择 判 断 问 答 证 明 阅 读 几 种 题 型, 覆 盖 主 要 知 识 点 2) 多 阶 段 综 合 测 试 : 通 过 期 中 考 试 平 时 测 验 期 末 考 试 分 阶 段 测 试, 督 促 学 生 深 入 理 解, 融 会 贯 通 3) 结 合 平 时 表 现 : 采 用 激 励 机 制, 鼓 励 学 生 参 与 互 动, 多 问 问 题, 认 真 完 成 作 业 4) 英 语 实 用 能 力 : 要 求 学 生 在 教 学 的 各 个 环 节 均 使 用 英 语, 提 高 英 语 实 用 能 力 最 终 成 绩 由 课 堂 表 现 平 时 作 业 期 中 考 试 和 期 末 考 试 成 绩 综 合 组 成 每 个 部 分 所 占 比 例 和 考 核 内 容 如 下 : 项 目 所 占 比 例 考 核 内 容 课 堂 表 现 10% 考 核 课 堂 参 与 度 独 立 思 考 能 力 和 判 断 力 平 时 作 业 30% 考 核 概 念 理 解 程 度 文 字 表 达 能 力 Latex 软 件 应 用 能 力 期 中 考 试 30% 考 核 可 计 算 基 本 原 理 和 计 算 模 型 的 理 解 程 度 期 末 考 试 30% 考 核 理 论 重 要 性 质 与 可 计 算 集 合 的 掌 握 程 度 补 充 说 明 : 使 用 编 译 软 件 提 交 电 子 版 作 业 可 获 得 加 分, 上 限 为 总 分 5%; 正 确 回 答 课 堂 提 问 或 提 出 有 建 设 意 义 的 问 题 可 获 得 课 堂 表 现 加 分, 上 限 为 总 分 的 3%; 小 测 验 计 入 作 业 成 绩 3-5 教 材 ( 含 英 语 教 材 使 用 与 建 设 ; 扩 充 性 英 语 资 料 使 用 情 况 ) 教 材 : Computability: An Introduction to Recursive Function Theory, by Nigel L., Cutland, published by Cambridge University Press 这 是 可 计 算 理 论 的 经 典 教 材, 内 容 难 度 最 适 合 本 科 生 教 学 参 考 书 : [1] Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, by Robert I. Soare, published by Springer-Verlag Berlin Heidelberg. [2] Theory of Computational Complexity, by Ding-Zhu Du, and Ker-I Ko, published by John Wiley & Sons, Inc. [3] Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak, Cambridge University Press. 21

3-6 网 络 资 源 ( 含 网 络 硬 件 环 境, 网 上 资 源 名 称 列 表 网 址 链 接 及 在 教 学 中 的 使 用 情 况 ) 课 程 网 站 http://basics.sjtu.edu.cn/~gaoxiaofeng/computability/ 提 供 资 源 包 括 : 1) 授 课 教 师 信 息 2) 教 学 大 纲 与 教 学 安 排 3) 教 学 资 料, 包 括 课 件 作 业 及 答 案 课 程 设 计 及 相 关 辅 助 材 料 课 程 邮 件 列 表 sjtu_cs363@googlegroups.com 功 能 : 发 布 课 程 参 考 资 料 互 动 交 流 答 疑 等 3-7 教 学 效 果 ( 学 生 评 教 指 标 和 校 内 管 理 部 门 提 供 的 近 两 年 的 学 生 评 价 分 数 及 评 语 ; 课 程 负 责 人 教 学 录 像 要 点 ) 本 课 程 从 2011-2012 学 年 第 二 学 期 开 始 在 上 海 交 通 大 学 计 算 机 科 学 与 工 程 系 开 设, 目 前 已 开 设 2 个 学 期 第 一 次 教 评 得 分 94.13, 具 体 教 评 结 果 请 见 下 表 ( 证 明 材 料 见 附 件 ); 第 二 次 教 评 将 于 近 期 公 布 总 体 评 价 : 学 年 学 期 选 课 学 生 数 参 评 学 生 数 评 教 率 教 师 得 分 院 系 排 名 全 校 排 名 2011-2012 2 50 38 76.00% 94.13 15/158 238/1990 具 体 评 价 : 序 号 指 标 内 容 学 生 评 分 1 我 感 觉 老 师 是 用 心 备 课 9.39 2 老 师 上 课 有 吸 引 力, 能 激 发 我 思 考 和 探 究 的 兴 趣 9.36 3 老 师 具 有 人 格 魅 力, 对 我 的 影 响 很 大 9.45 4 老 师 评 估 学 生 的 表 现 时 公 平 一 致, 对 作 业 及 测 验 成 绩 很 重 视 9.42 5 老 师 关 注 学 生 的 课 堂 表 现 并 能 维 持 良 好 的 学 习 环 境 9.36 6 老 师 批 改 作 业 及 时 认 真, 会 根 据 作 业 情 况 指 导 我 的 学 习 9.36 7 老 师 合 理 运 用 板 书 和 课 件, 便 于 我 理 解 教 学 内 容 9.39 8 在 我 需 要 的 时 候 ( 包 括 课 后 ) 能 够 得 到 老 师 的 指 导 和 帮 助 9.39 9 老 师 会 结 合 学 科 前 沿 或 社 会 热 点, 对 教 材 知 识 进 行 拓 展 性 讲 解 9.39 10 老 师 帮 我 进 一 步 掌 握 了 知 识 的 获 取 方 法 和 理 解 途 径 9.42 (10-9 分 代 表 完 全 同 意,8-7 分 代 表 同 意,6-5 分 代 表 基 本 同 意,4-3 分 代 表 不 同 意, 2-0 分 代 表 完 全 不 同 意 ) 22

学 生 评 语 摘 选 : [1] 学 到 了 可 计 算 的 知 识 知 道 了 这 个 世 界 上 有 很 多 东 西 是 不 可 计 算 的 跟 高 老 师 学 到 了 很 多 做 人 的 东 西, 也 很 有 收 获 学 到 了 latex, 很 有 用! 高 老 师 和 助 教 都 非 常 nice, 态 度 很 认 真, 为 人 很 和 蔼, 做 事 很 公 允 [2] 对 理 论 计 算 机 有 了 进 一 步 的 了 解 与 学 习, 学 到 很 多 有 用 的 东 西 高 中 以 来 一 直 从 Matrix67 的 Blog 之 类 的 地 方 看 到 的 哥 德 尔, 还 有 停 机 问 题 等 等, 终 于 系 统 的 学 到 了 虽 然 大 家 以 后 准 备 搞 理 论 的 可 能 比 较 少, 但 是 多 学 学 数 学 课 收 获 是 很 大 的 高 老 师 超 赞 的 ~ 像 这 样 用 心 的 话, 再 过 一 两 年 很 快 会 入 选 最 受 学 生 欢 迎 教 师 的 ~ [3] 在 可 计 算 理 论 方 面 确 实 懂 了 一 些 东 西 ( 其 实 本 来 就 对 这 方 面 挺 感 兴 趣 的 ); 认 识 了 哥 德 尔 这 个 大 神, 现 在 变 成 他 的 崇 拜 者 ; 基 本 能 使 用 TeX 进 行 技 术 交 流 ; 数 学 能 力 似 乎 有 点 恢 复 了 老 师 上 课 很 体 贴 阿, 看 到 我 们 跟 不 上 了 就 会 放 慢 脚 步 ; 谢 谢 老 师 及 其 周 到 的 考 虑 以 及 对 我 各 方 面 的 帮 助 ~ 您 是 我 见 过 的 最 负 责 的 老 师 之 一 ~ [4] 可 计 算 理 论 虽 然 难, 但 是 在 学 习 这 门 课 的 知 识 的 同 时 更 锻 炼 的 自 己 思 辨 和 理 解 的 能 力 ( 其 实 很 多 难 的 课 都 能 锻 炼 到, 但 以 前 一 般 碰 到 这 样 的 课 我 就 放 弃 了 ) 每 次 看 老 师 把 这 么 难 的 课 讲 解 的 很 有 条 理, 想 必 老 师 为 备 课 付 出 了 很 大 的 心 血 老 师 都 这 么 认 真 负 责, 我 们 当 然 也 要 对 自 己 负 责 了 [5] 对 可 计 算 理 论 有 了 一 定 的 了 解, 算 是 最 大 的 收 获 吧, 不 管 自 己 是 否 喜 欢 这 个 分 支, 至 少 丰 富 了 自 己 的 知 识 面 这 门 课 一 定 程 度 上 也 改 变 了 我 对 Computer Science 的 看 法, 原 来 Computer Science 这 样 我 认 为 非 常 偏 Application 的 课 程 也 有 这 么 深 的 理 论 基 础 [6] 学 习 可 计 算 课 程 收 获 超 级 多 ~ 除 了 知 识 层 面 的, 还 有 很 多 为 人 处 事 方 面 的 我 真 心 的 非 常 非 常 喜 欢 你 高 老 师, 大 学 至 今, 我 觉 得 你 是 我 大 学 期 间 印 象 最 深, 对 我 帮 助 最 大 的 老 师 交 大 不 乏 有 好 老 师, 但 是 很 多 这 样 的 好 老 师 对 我 的 帮 助 也 只 是 知 识 层 面 上 的, 其 实 大 学 生 也 很 希 望 和 老 师 在 心 灵 上 有 更 多 的 交 流, 其 实 老 师 的 一 言 一 行 也 可 以 对 我 们 很 有 启 发 我 觉 得 老 师 是 一 个 细 节 做 的 很 好 也 是 个 心 思 很 细 腻 的 人, 举 个 例 子 吧, 老 师 你 可 以 叫 出 我 们 每 个 同 学 的 名 字, 甚 至 还 记 得 我 们 的 籍 贯, 虽 然 这 其 实 是 个 很 小 的 事 情, 但 自 己 真 的 很 感 动, 就 像 我 们 的 大 姐 姐 一 样, 超 级 贴 心 ; 另 外 我 觉 的 老 师 的 备 课 以 及 答 疑 真 的 很 认 真, 看 着 老 师 凌 晨 4 点 还 给 我 们 做 hint 我 就 觉 得 超 感 动, 然 后 也 很 惭 愧, 所 以 虽 然 自 己 成 绩 不 是 很 好, 学 的 也 比 较 吃 力, 但 是 依 然 很 努 力 的 去 理 解 去 学 习 再 次 谢 谢 老 师! [7] 可 计 算 方 面 懂 了 不 少 ; 老 师 做 的 很 好 也 很 尽 职, 大 概 是 我 们 碰 到 最 负 责 任 也 最 关 心 我 们 的 一 个 老 师 了, 很 感 谢 您 [8] 太 负 责 任 了! 难 得 在 大 学 遇 到 这 么 负 责 任, 这 么 专 注 于 教 学, 这 么 为 学 生 着 想 的 老 师 请 下 次 一 定 参 加 最 受 学 生 欢 迎 的 教 师 的 评 选 ~~ 课 程 太 有 人 文 关 怀 了 都 关 照 到 每 一 个 学 生 这 个 太 感 人 了!mua~ [9] 老 师 真 的 非 常 非 常 认 真, 真 的 感 谢 老 师 的 努 力 付 出, 老 师 的 一 些 细 节 也 深 深 影 响 我, 之 前 我 没 有 遇 到 哪 一 位 老 师 在 这 么 多 人 的 课 堂 上 能 够 记 住 每 一 个 学 生, 之 前 也 没 有 遇 到 哪 一 个 老 师 在 学 生 考 试 成 绩 不 理 想 的 时 候 会 找 学 生 谈 心, 这 一 切 都 让 我 很 感 动, 也 学 到 了 很 多 23

课 程 负 责 人 教 学 录 像 要 点 录 制 内 容 : 递 归 集 与 递 归 可 枚 举 集 录 制 时 间 : 2013 年 4 月 23 日 录 制 长 度 : 45 分 钟 教 学 内 容 : 讲 解 递 归 集 与 递 归 可 枚 举 集 的 概 念, 定 义 原 因 界 定 作 用, 以 及 介 绍 相 关 定 理 和 举 例 讲 解 教 学 要 点 : 递 归 集 指 可 以 用 计 算 机 模 型 在 有 限 时 间 内 终 止 并 判 定 一 个 给 定 元 素 是 否 属 于 这 个 集 合 的 问 题 结 合, 是 判 定 可 计 算 性 的 重 要 界 定 标 准, 属 于 本 课 程 的 重 点 与 难 点 部 分 本 课 程 通 过 以 下 几 点 来 完 成 递 归 集 与 递 归 可 枚 举 集 的 介 绍 : 1) 回 顾 前 期 学 过 的 可 判 定 问 题 与 递 归 函 数, 引 入 递 归 集 的 定 义 2) 提 问 递 归 函 数 的 构 造 方 式, 使 学 生 进 一 步 了 解 递 归 集 的 扩 展 性 3) 通 过 多 媒 体 与 板 书 剖 析 递 归 集 的 特 性 并 举 例 示 范 4) 通 过 总 结 进 一 步 加 深 该 集 合 概 念 图 12: 课 堂 讲 解 与 多 媒 体 使 用 情 况 图 13: 提 问 情 况 图 14: 学 生 学 习 情 况 图 15: 课 件 示 例 24

4. 课 程 建 设 规 划 4-1 本 课 程 四 年 内 建 设 规 划 ( 含 课 程 网 站 建 设 规 划 ) 本 课 程 的 建 设 目 标 是 国 内 一 流 课 程 水 平, 计 划 分 四 阶 段 建 设 第 一 阶 段 2012.1-2012.12( 已 经 启 动 ) 本 阶 段 主 要 进 行 教 学 方 法 手 段 的 实 践 利 用 两 学 期 的 时 间 对 拟 定 的 教 学 方 法 和 教 学 手 段 通 过 课 堂 教 学 实 践 教 学 来 验 证, 从 中 摸 索 出 一 套 针 对 本 课 程 来 说 行 之 有 效 的 教 学 方 法 和 手 段 主 要 方 式 有 : 尝 试 多 种 教 学 方 法, 如 实 例 教 学, 启 发 式 教 学, 习 题 训 练 等, 摸 索 对 本 课 程 最 适 用 的 教 学 法 引 入 国 外 先 进 教 学 理 念, 如 规 范 课 程 大 纲, 规 范 课 程 安 排, 引 导 学 生 对 课 程 产 生 全 局 性 观 念, 提 纲 挈 领 地 把 握 课 程 内 容 尝 试 多 元 交 互, 通 过 课 堂 交 流 网 络 互 动 课 后 会 面 等 方 式 把 握 学 生 对 课 程 的 掌 握 情 况 对 课 程 内 容 进 行 调 整, 把 握 市 场 对 计 算 机 专 业 人 才 的 需 求, 与 时 俱 进 第 二 阶 段 2013.1-2013.12 本 阶 段 主 要 进 行 资 源 的 整 理, 包 括 教 学 资 源 实 践 资 源 以 及 信 息 化 资 源, 建 设 一 个 功 能 齐 备 的 网 络 教 学 平 台 主 要 方 式 有 : 制 作 完 善 规 范 课 程 教 案 和 多 媒 体 课 件 制 作 更 新 调 整 课 程 网 站, 并 搭 建 一 体 化 教 学 平 台 设 计 引 入 多 种 新 式 教 学 手 段, 并 使 之 规 范 化 第 三 阶 段 2014.1-2014.12 将 整 理 设 计 的 教 学 及 实 践 资 源 应 用 到 教 学 及 实 践 中, 通 过 实 践 形 成 一 整 套 课 程 建 设 体 系 主 要 工 作 有 : 通 过 多 次 实 践 掌 握 课 程 难 点 与 重 点 逐 步 调 整 教 学 内 容 与 教 学 大 纲 录 制 课 堂 视 频, 完 成 一 套 示 范 性 教 学 参 考 资 料 第 四 阶 段 2015.1-2015.12 推 广 课 程 使 用 材 料, 公 开 示 范 性 教 学 资 料, 使 课 程 达 到 标 准 化 公 开 化 示 范 化 的 效 果, 为 同 类 别 计 算 机 理 论 性 课 程 提 供 指 导 参 考 与 借 鉴 作 用 课 程 资 料 上 网 计 划 : 目 前 所 有 的 教 学 资 源 都 已 上 网, 最 新 内 容 会 随 时 增 添 25

4-2 聘 请 国 外 教 师 ( 专 家 ) 来 华 授 课 计 划 本 课 程 教 学 团 队 成 员 均 具 有 多 年 海 外 留 学 和 工 作 经 历, 与 许 多 国 外 教 师 已 建 立 了 良 好 的 合 作 关 系 为 进 一 步 建 设 好 本 全 英 语 教 学 课 程, 计 划 邀 请 国 外 在 理 论 计 算 机 方 面 具 有 顶 级 水 平 的 专 家 学 者 向 学 生 讲 解 可 计 算 理 论 计 算 复 杂 性 理 论 的 最 新 研 究 成 果, 并 介 绍 国 际 学 术 前 沿 发 展 的 最 新 动 向 拟 邀 请 来 讲 学 的 有 美 国 Cornell 大 学 的 图 灵 奖 获 得 者 John Hopcroft 教 授 和 美 国 Univ of Texas 的 Ding-Zhu Du 教 授 图 16: 与 图 灵 奖 获 得 者 John Hopcroft 合 影 及 讲 课 片 断 4-3 学 校 鼓 励 全 英 语 教 学 课 程 建 设 的 政 策 措 施 及 实 施 情 况 上 海 交 通 大 学 已 开 始 实 施 全 英 语 教 学 专 业 建 设 计 划, 以 推 动 学 校 国 际 化 战 略 目 标 的 实 现, 努 力 提 高 国 际 化 办 学 效 率 水 平 和 层 次, 提 升 学 校 的 核 心 竞 争 力 和 国 际 影 响 力 并 于 2011 年 3 月 30 日 成 立 全 英 语 教 学 建 设 专 家 组, 以 保 障 全 英 语 教 学 专 业 建 设 计 划 顺 利 实 施 上 海 交 通 大 学 计 算 机 科 学 与 工 程 系 采 取 专 门 立 项 的 方 式, 在 985 工 程 三 期 中 立 项 建 设 11 门 本 科 生 全 英 语 课 程,5 门 研 究 生 全 英 语 课 程, 分 别 给 予 专 项 经 费 支 持 ; 同 时, 在 常 规 的 教 学 政 策 和 经 费 投 入 中 向 全 英 语 教 学 课 程 倾 斜, 全 英 语 教 学 课 程 任 课 教 师 的 教 学 工 作 量 作 为 原 课 程 工 作 量 的 1.5 倍 计 算 另 外, 上 海 交 通 大 学 教 学 发 展 中 心 每 学 期 开 设 教 师 英 语 授 课 能 力 培 训 班, 通 过 集 中 式 培 训 模 式 提 高 教 师 英 语 语 言 运 用 能 力, 训 练 教 师 适 应 授 课 语 言 转 换 带 来 的 课 堂 环 境, 教 学 方 法, 教 学 思 维 等 相 应 转 换, 并 注 重 保 持 培 训 课 程 的 相 关 性, 实 效 性 和 趣 味 性 目 前 该 培 训 课 程 已 开 展 六 期 26

5. 学 校 意 见 5-1 课 程 负 责 人 本 人 承 诺 : 表 中 所 填 内 容 均 真 实 有 效 签 字 : 日 期 : 5-2 教 务 处 意 见 本 课 程 符 合 申 报 条 件, 申 报 材 料 已 于 2013 年 4 月 25 日 至 2013 年 4 月 28 日 在 学 校 网 站 上 公 示 负 责 人 签 字 ( 盖 章 ): 江 志 斌 日 期 :2013 年 4 月 27 日 5-3 学 校 意 见 同 意 申 报 2013 年 上 海 高 校 示 范 性 全 英 语 教 学 课 程 建 设 项 目 主 管 校 长 签 字 ( 盖 章 ): 黄 震 日 期 :2013 年 4 月 28 日 27