Slide 1

Size: px

Start display at page:

Download "Slide 1"

绮谖薛
9 years ago
Views:

1 美丽的旅程理论计算机科学之美南京大学计算机科学与技术系尹一通

2 计算机科学? 是研究计算机的吗? Computer science is no more about computers than astronomy is about telescopes. --- Edsger Dijkstra

3 Alan Turing ( ) 什么是计算? What is computation? 图灵

4 Turing Machine 图灵机图灵

5 完备性图灵机

6 Conway s Game of Life John Horton Conway

7 Turing Machine 230 A. M. TUKING [Nov. 12, ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM By A. M. TURING. [Received 28 May, 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

Although the subject of this paper is ostensibly the computable numbers.

8 ENIAC 第一台通用电子计算机 ENIAC(1947 年 )

9 David Hilbert ( ) n 希尔伯特问题 (1900) n 23 个数学难题 : n 第 2 问题 : 为算数建立完备的公理体系 n 第 10 问题 : 给出解整数方程的算法希尔伯特

10 Euclid (300 BC) 欧几里德

11 Bertrand Russell ( ) 罗素悖论 (Russell Paradox) 1901: 本命题是假的是真是假? 定义集合 A 为 : 所有自己不属于自己的集合的集合 A = {S S S} A 是否属于它自己? 罗素

12 Bertrand Russell ( ) 数学原理罗素

13 Kurt Gödel ( ) 本命题不能被证明可以被证明吗? 哥德尔不完备定理 (1931) Incompleteness Theorem: ( 不自相矛盾的 ) 数学是不完备的哥德尔

14 埃舍尔的画

15 无穷的阶梯

16 停机问题 (1936) 程序 : 输入输出或永远不结束判断程序在某个输入上能否结束如果有这样的程序 : 就能编个捣乱程序! 捣乱程序输入 ( 程序 A): 如果程序 A 输入 ( 程序 A) 不结束则结束 ; 如果程序 A 输入 ( 程序 A) 结束则死循环捣乱程序输入 ( 捣乱程序 ) 是否结束? 存在不能被计算的问题! 图灵

17 数学证明是不完备的计算是不完备的哥德尔图灵

18 David Hilbert ( ) n 希尔伯特问题 (1900) n 23 个数学难题 : n 第 2 问题 : 为算数建立完备的公理体系 n 第 10 问题 : 给出解整数方程的算法则停机问题可计算!(1970) 希尔伯特

19 Alan Turing ( ) 计算正式成为了一个研究的对象什么是计算? 图灵论题计算的界限在哪里? 是什么使一个问题难或者容易? 如何更高效的计算? 计算机科学 : 一门把问题和解决作为研究对象的学科图灵

20 Alan Turing ( ) Enigma machine 迷图灵

22 计算的界限有些问题是不可被计算的在那些可以被计算的问题当中, 有的问题难有的容易容易 : 有高效的算法难 : 没有高效的算法为什么难? 为什么容易?

23 计算与验证在人群中找出一个人有人帮你指出了那个人, 你来确认是不是她为问题寻找一个解给了一个解, 验证它是不是有效的解证明数学题检查一个数学证明的正确性可以高效计算的问题 P 可以高效验证的问题 NP

24 千禧年难题 : Millennium Problems 2000 年, 克雷数学研究所列出了七大数学难题, 每道题目悬赏百万美金 P vs NP 霍奇猜想庞加莱猜想黎曼猜想杨 - 米尔斯存在性和质量缺口内维尔 - 斯托克斯方程的存在性与光滑性贝赫和斯维讷通 - 戴尔猜想

25 NP 猜想可以高效计算的问题可以高效验证的问题 P NP 有一些问题容易验证, 计算却很难创造性是存在的 : 不可被机械的过程取代解决一个数学难题读懂这个解创作出美妙的音乐欣赏音乐设计建筑规划城市赞赏这些设计 NP P

26 NP 猜想可以高效计算的问题 P 可以高效验证的问题 NP 有一些 NP 问题, 它的解决可以导致所有 NP 问题的解决判定数学命题是否成立 ; 搬家时把杂物装入大小一样的纸箱, 用最少的纸箱 ; 把大小不同的货物放到后车厢, 放得越多越好 ; 把一些大小不同的砝码放在天平两端, 让天平尽量平衡 ; 计划一次旅行, 飞遍所有省会城市, 机票钱尽量少 ; 把人们分配到超市的不同结账口, 总的结账时间最短 ; 玩超级玛丽大金刚塞尔达传说会打超级玛丽, 就能做数学家! NP P

27 Oracle ( 神谕 )

28 更难的题 6 个人的聚会, 必有 3 个人相互认识或相互不认识拉姆塞 Frank Ramsey ( )

29 更难的题拉姆塞数 R(k): 至少 R(k) 个人的聚会, 必有 k 个人相互认识或相互不认识 R(2)=2 R(3)=6 R(4)=18 R(5)=43~49 R(6)=102~165 拉姆塞 Frank Ramsey ( ) 人类永远不会知道 R(6) 真实的值

30 复杂类复杂类 : 将问题依据其难度而归类

31 更强的计算模型 31

32 计算难度可以高效计算的问题可以高效验证的问题 P NP 有一些问题容易验证, 计算却很难密码学计算机安全 : 让好人做得到 ; 让坏人做不到 ; 安全 : 对坏人很难

33 零知识证明如何向一个你不信任的人证明一个事实, 除了证明的这个事实之外, 不透露任何额外信息证明交互式证明获第一届哥德尔奖理论计算机科学最高成果奖

34 煎饼排序 Bill Gates Christos Papadimitriou

37 PageRank Larry Page and Sergey Brin

38 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 [email protected] and [email protected] 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 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

39 110 周年的寄语 n 你的专业兴趣 ; n 你的理想追求 ; n 你的使命 39

40 结语谢谢! 40

马克思主义公正观的基本向度及方法论原则!! # #

马克思主义公正观的基本向度及方法论原则!! # # 马克思主义公正观的基本向度及方法论原则马俊峰在社会公正问题的大讨论中罗尔斯诺齐克哈耶克麦金泰尔等当代西方思想家的论述被反复引用和申说而将马克思恩格斯等经典作家的观点置于一种被忽视甚至被忘却的状态形成这种