美 丽 的 旅 程 理 论 计 算 机 科 学 之 美 南 京 大 学 计 算 机 科 学 与 技 术 系 尹 一 通 2012.3.14
计 算 机 科 学? 是 研 究 计 算 机 的 吗? Computer science is no more about computers than astronomy is about telescopes. --- Edsger Dijkstra
Alan Turing (1912-1954) 什 么 是 计 算? What is computation? 图 灵
Turing Machine 图 灵 机 图 灵
完 备 性 图 灵 机
Conway s Game of Life John Horton Conway
Turing Machine 230 A. M. TUKING [Nov. 12, ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM By A. M. TURING. [Received 28 May, 1936. Read 12 November, 1936.] The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means. Although the subject of this paper is ostensibly the computable numbers. it is almost equally easy to define and investigate computable functions of an integral variable or a real or computable variable, computable predicates, and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique. I hope shortly to give an account of the relations of the computable numbers, functions, and so forth to one another. This will include a development
ENIAC 第 一 台 通 用 电 子 计 算 机 ENIAC(1947 年 )
David Hilbert (1862-1943) n 希 尔 伯 特 问 题 (1900) n 23 个 数 学 难 题 : n 第 2 问 题 : 为 算 数 建 立 完 备 的 公 理 体 系 n 第 10 问 题 : 给 出 解 整 数 方 程 的 算 法 希 尔 伯 特
Euclid (300 BC) 欧 几 里 德
Bertrand Russell (1872-1970) 罗 素 悖 论 (Russell Paradox) 1901: 本 命 题 是 假 的 是 真 是 假? 定 义 集 合 A 为 : 所 有 自 己 不 属 于 自 己 的 集 合 的 集 合 A = {S S S} A 是 否 属 于 它 自 己? 罗 素
Bertrand Russell (1872-1970) 数 学 原 理 罗 素
Kurt Gödel (1906-1978) 本 命 题 不 能 被 证 明 可 以 被 证 明 吗? 哥 德 尔 不 完 备 定 理 (1931) Incompleteness Theorem: ( 不 自 相 矛 盾 的 ) 数 学 是 不 完 备 的 哥 德 尔
埃 舍 尔 的 画
无 穷 的 阶 梯
停 机 问 题 (1936) 程 序 : 输 入 输 出 或 永 远 不 结 束 判 断 程 序 在 某 个 输 入 上 能 否 结 束 如 果 有 这 样 的 程 序 : 就 能 编 个 捣 乱 程 序! 捣 乱 程 序 输 入 ( 程 序 A): 如 果 程 序 A 输 入 ( 程 序 A) 不 结 束 则 结 束 ; 如 果 程 序 A 输 入 ( 程 序 A) 结 束 则 死 循 环 捣 乱 程 序 输 入 ( 捣 乱 程 序 ) 是 否 结 束? 存 在 不 能 被 计 算 的 问 题! 图 灵
数 学 证 明 是 不 完 备 的 计 算 是 不 完 备 的 哥 德 尔 图 灵
David Hilbert (1862-1943) n 希 尔 伯 特 问 题 (1900) n 23 个 数 学 难 题 : n 第 2 问 题 : 为 算 数 建 立 完 备 的 公 理 体 系 n 第 10 问 题 : 给 出 解 整 数 方 程 的 算 法 则 停 机 问 题 可 计 算!(1970) 希 尔 伯 特
Alan Turing (1912-1954) 计 算 正 式 成 为 了 一 个 研 究 的 对 象 什 么 是 计 算? 图 灵 论 题 计 算 的 界 限 在 哪 里? 是 什 么 使 一 个 问 题 难 或 者 容 易? 如 何 更 高 效 的 计 算? 计 算 机 科 学 : 一 门 把 问 题 和 解 决 作 为 研 究 对 象 的 学 科 图 灵
Alan Turing (1912-1954) Enigma machine 迷 图 灵
计 算 的 界 限 有 些 问 题 是 不 可 被 计 算 的 在 那 些 可 以 被 计 算 的 问 题 当 中, 有 的 问 题 难 有 的 容 易 容 易 : 有 高 效 的 算 法 难 : 没 有 高 效 的 算 法 为 什 么 难? 为 什 么 容 易?
计 算 与 验 证 在 人 群 中 找 出 一 个 人 有 人 帮 你 指 出 了 那 个 人, 你 来 确 认 是 不 是 她 为 问 题 寻 找 一 个 解 给 了 一 个 解, 验 证 它 是 不 是 有 效 的 解 证 明 数 学 题 检 查 一 个 数 学 证 明 的 正 确 性 可 以 高 效 计 算 的 问 题 P 可 以 高 效 验 证 的 问 题 NP
千 禧 年 难 题 : Millennium Problems 2000 年, 克 雷 数 学 研 究 所 列 出 了 七 大 数 学 难 题, 每 道 题 目 悬 赏 百 万 美 金 P vs NP 霍 奇 猜 想 庞 加 莱 猜 想 黎 曼 猜 想 杨 - 米 尔 斯 存 在 性 和 质 量 缺 口 内 维 尔 - 斯 托 克 斯 方 程 的 存 在 性 与 光 滑 性 贝 赫 和 斯 维 讷 通 - 戴 尔 猜 想
NP 猜 想 可 以 高 效 计 算 的 问 题 可 以 高 效 验 证 的 问 题 P NP 有 一 些 问 题 容 易 验 证, 计 算 却 很 难 创 造 性 是 存 在 的 : 不 可 被 机 械 的 过 程 取 代 解 决 一 个 数 学 难 题 读 懂 这 个 解 创 作 出 美 妙 的 音 乐 欣 赏 音 乐 设 计 建 筑 规 划 城 市 赞 赏 这 些 设 计 NP P
NP 猜 想 可 以 高 效 计 算 的 问 题 P 可 以 高 效 验 证 的 问 题 NP 有 一 些 NP 问 题, 它 的 解 决 可 以 导 致 所 有 NP 问 题 的 解 决 判 定 数 学 命 题 是 否 成 立 ; 搬 家 时 把 杂 物 装 入 大 小 一 样 的 纸 箱, 用 最 少 的 纸 箱 ; 把 大 小 不 同 的 货 物 放 到 后 车 厢, 放 得 越 多 越 好 ; 把 一 些 大 小 不 同 的 砝 码 放 在 天 平 两 端, 让 天 平 尽 量 平 衡 ; 计 划 一 次 旅 行, 飞 遍 所 有 省 会 城 市, 机 票 钱 尽 量 少 ; 把 人 们 分 配 到 超 市 的 不 同 结 账 口, 总 的 结 账 时 间 最 短 ; 玩 超 级 玛 丽 大 金 刚 塞 尔 达 传 说 会 打 超 级 玛 丽, 就 能 做 数 学 家! NP P
Oracle ( 神 谕 )
更 难 的 题 6 个 人 的 聚 会, 必 有 3 个 人 相 互 认 识 或 相 互 不 认 识 拉 姆 塞 Frank Ramsey (1903-1930)
更 难 的 题 拉 姆 塞 数 R(k): 至 少 R(k) 个 人 的 聚 会, 必 有 k 个 人 相 互 认 识 或 相 互 不 认 识 R(2)=2 R(3)=6 R(4)=18 R(5)=43~49 R(6)=102~165 拉 姆 塞 Frank Ramsey (1903-1930) 人 类 永 远 不 会 知 道 R(6) 真 实 的 值
复 杂 类 复 杂 类 : 将 问 题 依 据 其 难 度 而 归 类
更 强 的 计 算 模 型 31
计 算 难 度 可 以 高 效 计 算 的 问 题 可 以 高 效 验 证 的 问 题 P NP 有 一 些 问 题 容 易 验 证, 计 算 却 很 难 密 码 学 计 算 机 安 全 : 让 好 人 做 得 到 ; 让 坏 人 做 不 到 ; 安 全 : 对 坏 人 很 难
零 知 识 证 明 如 何 向 一 个 你 不 信 任 的 人 证 明 一 个 事 实, 除 了 证 明 的 这 个 事 实 之 外, 不 透 露 任 何 额 外 信 息 证 明 交 互 式 证 明 获 第 一 届 哥 德 尔 奖 理 论 计 算 机 科 学 最 高 成 果 奖
煎 饼 排 序 Bill Gates Christos Papadimitriou
PageRank Larry Page and Sergey Brin
PageRank The Anatomy of a Large-Scale Hypertextual Web Search Engine Sergey Brin and Lawrence Page Computer Science Department, Stanford University, Stanford, CA 94305, USA sergey@cs.stanford.edu and page@cs.stanford.edu Abstract In this paper, we present Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext. Google is designed to crawl and index the Web efficiently and produce much more satisfying search results than existing systems. The prototype with a full text and hyperlink database of at least 24 million pages is available at http://google.stanford.edu/ To engineer a search engine is a challenging task. Search engines index tens to hundreds of millions of web pages involving a comparable number of distinct terms. They answer tens of millions of queries every day. Despite the importance of large-scale search engines on the web, very little academic research has been done on them. Furthermore, due to rapid advance in technology and web proliferation, creating a web search engine today is very different from three years ago. This paper provides an in-depth description of our large-scale web search engine -- the first such detailed public description we know of to date. Apart from the problems of scaling traditional search techniques to data of this magnitude, there are new technical challenges involved with using the additional information present in hypertext to produce better search results. This paper addresses this question of how to build a practical large-scale system which can exploit the additional information present in hypertext. Also we look at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want. Keywords World Wide Web, Search Engines, Information Retrieval, PageRank, Google
110 周 年 的 寄 语 n 你 的 专 业 兴 趣 ; n 你 的 理 想 追 求 ; n 你 的 使 命 39
结 语 谢 谢! 40