回 帖 发 新 帖 刷新版面

主题:(非计算机系学生)如何入门篇(10)---灌水-推荐文章

知识科学及其研究前沿
中国科学院院士 陆汝钤

摘 要: 本文根据知识处理的研究历史和现状,提出了开展知识科学研究的主张并探讨了它的几个重要方面,其中结合了作者本人的研究工作。
关键词:知识科学、知识工程、知识经济、知识产业

Knowledge Science and its Research Frontiers

Lu Ruqian

Abstract: Based on the history and state of art of research on knowledge processing, this paper proposes the study of knowledge science and explores some of its important aspects, by relating them to the author’s own research results.
Keywords: Knowledge Science, Knowledge Engineering, Knowledge Economy, Knowledge Industry .
一.前言

    从古希腊人开始,对于知识的研究与探索一直是人类追求的目标。几千年来的情况都是这样的:哲学家研究有关知识的一般特性与规律,而自然科学家孜孜不倦地猎取具体的知识。二十世纪中叶以后,这种研究格局发生了变化。由于知识在人类文明中所起的作用越来越大,不仅是哲学家、逻辑学家和心理学家,而且计算机科学家也在认真地研究知识的一般特性与规律。这是因为人类已经进入了信息化社会,而且正在向知识化社会前进。人类对知识的掌握很大程度上体现为这些汪洋大海般的知识是能够通过计算机和计算机网络操作和使用的。计算机科学家的任务是要研究处理各种复杂知识的理论与方法。1977年,费根鲍姆教授提出了知识工程的概念,成为知识可操作化的一个里程碑[1]。但是,二十多年来,知识工程主要是一门实验性科学。知识处理的大量理论性问题尚待解决。本文作者认为对知识的研究应该是一门具有坚实理论基础的科学,应该把知识工程的概念上升为知识科学。知识科学的进步将从根本上回答在知识工程中遇到过,但是没有能够很好解决的一系列重大问题[2]。世界进入了知识经济的时代,这要求我们在运用知识去推动社会的繁荣和进步的同时,也应着意开展对知识本身的深入研究。
二. 知识模型研究

    形式化和结构化的知识称为知识模型。在专家系统研究中,不同领域的专业知识被按它们的推理方式分类成不同的知识模型[3][4]。要说明这里不是按领域知识分类的,因为不同的领域可能有相同的推理方式,例如人类疾病诊断和设备故障检测就可用类似的模型刻画。定性推理研究提出了物理世界建模的一般法则。L系统和遗传算法分别给出了生物发育和生命演化的模型。基于模型的推理已成为专家系统的基本技术之一。基于模型的知识获取更是构造知识库的有力手段。模型的应用已经超出了它们原来所指的范围。例如遗传和退火算法被用到优化计算方面。建模概念在人工智能以外的领域如数据库、软件工程和系统工程中也起到重要作用。从目前的发展情况来看,我们认为以下几类模型特别值得重视和研究:面向Agent的模型、面向本体的模型、面向并行推理的新一代黑板模型、面向分布式推理的网络模型、面向移动通信的推理模型、能演化的模型、自组织模型、容错模型、共生模型。

    知识模型研究有着明确的实用意义。大规模的知识模型开发必然会提出一个标准化问题,否则就无法交流,无法推广使用。国外八十年代即已开始研究知识表示的工业化标准。九十年代以来进一步研究知识共享技术。其中斯坦福大学研究的知识交换格式(KIF)和本体建模语言(Ontolingua)较为有名 [5]。马里兰大学研究的知识查询和处理语言(KQML)面向的是知识库查询和知识库通信技术,已被许多学者作为一种事实上的标准接受[6]。


三. 常识性知识研究

    在国际人工智能界,一直公认常识性知识的处理是人工智能的核心难题。所谓常识,是相对于专业知识而言的。研究常识有两条道路。以“人工智能之父” 麦卡锡为代表的学派主张从建立常识的逻辑体系入手,并提出了一整套的非单调逻辑、认知逻辑等形式体系[7][8],而“知识工程之父”费根鲍姆则提出通过建设大规模知识库实现人工智能的计划。勒纳等人正在建的CYC海量知识库就是体现费根鲍姆思想的最有名的一项工程[9]。事实表明,常识表示和常识推理研究的每一进步,都是人类思维形式化和可操作化的一项新成果。
    我们的“常识性知识的实用研究”课题涉及常识表示、常识论域、常识特性、常识分类、常识模型、常识推理、常识应用等。还包括建立一个大规模的常识知识库。在研究中,我们提出了一种新的知识库结构:面向本体、Agent和关系的“三结合”知识库[10]。
    我们不仅把常识知识库看成是常识研究的一种工具,还把这项工作看成是继面向对象数据库之后新一代数据库的探索。常识知识库能帮助解决的实际问题包括自然语言理解、机器翻译、人机界面的智能性和自适应性、专家系统的健壮性、信息检索的智能性、图像识别和语音识别、因特网知识获取、计算机动画自动生成中的故事情节生成等。
四. 非规范知识研究

    非规范知识或因其量太大(海量知识),或内涵不够清楚(模糊知识),或结构残缺不全(不完全知识),或含内在矛盾(不协调知识),或含无用杂质(带噪音知识),或内涵不稳定(时变知识)而需用特殊手段处理。

    传统的逻辑视矛盾为“零秒杀手”,一颗老鼠屎即坏了一锅汤(一个矛盾即使整个系统成为平凡的)。基于非单调推理的真值维护技术是为了保持知识库的内在无矛盾性。次协调逻辑则不排除矛盾而容许它的存在,其努力集中在如何限制它的影响[11]。证伪主义率先打出了不承认有终极真理的旗号[12]。李未院士的开放逻辑研究的是如何在不断排除矛盾的过程中发展出一个相对正确的理论[13]。但是我们至今尚未看到有一个正面处理矛盾的理论。

    知识的矛盾性有时不是绝对的。判断模糊知识之间的矛盾性比判断精确知识之间的矛盾性更困难。应明生教授考虑把定理证明的技术运用到不精确和近似的情况中来,研究不精确知识在近似意义下的证明论[14]。

    因特网知识的收集整理涉及多源时变知识和海量知识。时变知识非常复杂,既有精确,又有模糊;既有矛盾,又有冗余;还有时态和背景依赖性。传统的时态数据库不够用,如果能使用多种逻辑和数学手段,使计算机自动收集和整理多源时变知识,将是很有意义的。

    海量知识处理技术的研究被因特网的普及所大大促进。当前浏览器的智能太低。许多软件机器人和网络机器人之类工具,尚停留在实验室阶段,还不能直接为广大因特网用户掌握和使用。浏览器功能弱的原因在于它们所用的信息检索技术主要是基于语法的,应该发展基于语义、语用和知识的智能浏览器。
五. 知识的数学理论

    指“从数学的观点来看,知识是什么”这样一个问题。仙农曾经对信息的数学本质进行过研究,提出了著名的仙农信息论[15]。他用熵的概念来研究信息的含量。佩特里进一步指出,信息应该看成是像能量、动量、角动量一样的物理量,应该有自己的守恒律和其他物理定律。佩特里认为这应是一门新的学科,称为信息动力学[16]。

    另一方面,仙农的理论不能照搬到作为宏观信息结构的知识上来,因为仙农的研究是以比特为单位的。我们举两个可供研究的问题作为例子。

    在计算机科学中,通信同步理论的研究已经有了很大的进展。CSP和CCS可以看成是信息通信在变量一级的理论,比起早期比特一级的数学理论来提高了一步[17]。∏演算的提出有助于解决移动通信中的理论问题。但∏演算仍然是变量级的[18]。近年来,人们致力于研究知识级的通信理论[19] [20]。

    此外,量子计算机的前景提供了大量有意义的研究课题[21]。复杂性分析是知识的数学理论的又一重要分支[22]。

    不同媒体表示的知识形式转换是另一个理论问题。近几年,因特网上的多媒体节目生成和传送发展迅速。如果能解决文字和非文字形式的互换,将大大提高因特网传输多媒体节目的效率,应用前景很大。

    我们做过十年计算机动画自动生成技术的研究,克服了一系列由自然语言自动生成动画的技术难点。对解决上述问题将会有用。  
六. 知识获取的理论和技术

    多年来,专家们一直公认知识获取是知识工程的一个瓶颈问题。有关知识获取的研究可分为三个流派,它们分别以心理学方法、人工智能方法和软件工程方法为其特征[23]。这方面最著名的成果是由欧洲的学者们在几年前提出的KADS。经过欧共体Esprit计划多年连续支持,如今的Common KADS已发展成欧洲范围内的公认标准[24]。

    我们研究的《天蜂》技术用于书面知识自动获取和CAI系统快速成型[25-30]。它的要点是设计一种类自然语言,使人们能基本按原样把书本或其他书面资料输入计算机。以下的工作,包括阅读资料、抽取和整理知识、组织教材、编写习题、集成教学系统等都由计算机自己完成。《天蜂》技术适用于批量化和大规模地生产CAI系统,开发各类应用软件的专用知识库,开发面向个人的(网上)电子博物馆和电子教室,以及大规模电子编辑出版。

    现在,研究者更多关心的已经不是获取专家头脑里的知识,而是从海量信息中获取知识。因特网的浏览器太笨,自动在网上收集信息的软件机器人应运而生。信息过滤和提炼技术倍受重视,特别是在文本知识获取方面。从数据中获取知识的数据挖掘研究在商业领域已得到广泛应用。
七. 基于知识的软件工程

    软件工程的实践告诉我们,软件开发失败的原因往往在于需求分析没有做好。而需求分析没有做好的原因又往往在于用户和软件工程师之间缺乏良好的合作。

    应该尽可能多地把用户吸引到软件开发过程中来,让用户自己来定义、设计、开发、维护和修改软件。做到这一点的关键是以强大的知识支持作为后盾。我们在《青鸟》技术框架内[32]研究的《天鹰》技术以一个大容量的领域知识库来支持软件的开发。同时提供一种面向领域用户的类自然语言。用户只需说明情况而无需说明需求,计算机即可在上述知识库的支持下自动生成所需的信息系统[33-38]。

    《天鹰》项目的启示是:第一要区分应用软件中的两种知识:软件知识和领域知识。第二要有两支专业队伍:软件工程师和知识工程师。第三要从软件产业中分离出一种新的产业:知识产业。我们相信,循这条路发展,必能使软件产业和知识产业同时发展成两个独立而繁荣的产业。
八. 知识用于计算机艺术


    计算机艺术和人工智能几乎是同步出现的。这里只谈最有实用意义的计算机辅助动画制作。它的某些环节已可实用,甚至成为商品。但据我们所知,充分利用人工智能技术的计算机动画全自动生成技术在我们的工作之前还没有。

    动画应用十分广泛,在精神文明和物质文明的创建中都起着重要作用。但生产动画十分艰巨,费用十分高昂。美国动画片"玩具总动员"据说是投资4000万美元拍摄的.中国应研制出自己的新技术, 以弥补经济实力的不足,取得战略优势.

    我们研究出了一条基于知识的动画生产全过程自动化技术,可使计算机把以受限自然语言形式写的故事自动转换成动画。并开发了相应的软件系统<<天鹅>>[39-41]。

    要把这项技术变成产业,还有大量工作要做。但我们深信它是能够变成产业的,并将引起动画片生产技术的行业改造。
九. 中国国家知识基础设施

    许多有识之士一直在谈论信息高速公路有路无车的问题。如果耗巨资建设起来的信息基础设施不能得到充份利用,将是一个极大的浪费。信息基础设施的主要内涵应该是知识。1995年,曹存根博士在青年科技论坛上首先提出了国家知识基础设施(CNKI)的思想[42]。再往前,中国科学院从八十年代开始即组织有关科学知识库的研究,并拨专项经费支持。十多年来,已建成涉及物理、化学、生物等领域的十几个科学数据库,在科研工作中发挥了积极作用。

    从科学基础研究角度看,国家知识基础设施的基础性体现在两大方面。第一,它提出了大规模知识网络的建设和利用问题。第二,国家知识基础设施将为许多基础研究和应用开发研究提供必要的知识基础 。

    从人类知识保护方面看,国家知识基础设施所提供的知识获取工具将充分吸收人类各种专家的宝贵经验,将它们永远地保存在知识库里,供后人使用或发展。

    最后,从国民文化教育观点看, 国家知识基础设施还将是提高全民族文化和科学素质的有力工具。
参考文献

[1] Feigenbaum, E.A., The art of artificial intelligence, Themes and case studies in knowledge engineering, IJCAI 5, 1014—1029.
[2]陆汝钤(主编)世纪之交的知识工程与知识科学,清华大学出版社,2001。
[3] Stefik, M.J. et al., Artificial Intelligence, V.61, N.1, 1993
[4] 吴建敏,专家系统解题模型分类研究,中国科学院数学研究所博士论文,1991年。
[5] Genesereth M.R. , Fikes R.E., Knowledge Interchange Format, Version 3.0, Reference Manual, Computer Science Department, Stanford University, 1992.
[6] Labrou, Y., Finin, T., A Proposal for a New KQML Specification, TR CS-97-03, UMBC,1997.
[7] McCarthy,J., Formalizing Commonsense: papers by John McCarthy, Ablex Publishing Corporation, 1990. 1997
[8] McCarthy,J., Programs with common sense, Proc. Symp. Mechan. Of Thought Proc., In [3].
[9] Lenat, D.B. and Guha, P.V., Building Large Knowledge Based Systems: Representation and Inference in the CYC Project, Addison Wesley, 1990.
[10] 陆汝钤、石纯一、张松懋、毛希平、徐晋辉、杨萍、范路,面向Agent的常识知识库,中国科学(E),V.30, N.5,pp.453-463, (中文版), V.43, N.6, pp.641-652, (英文版) , 2000.
[11]林作诠,李未,超协调逻辑(I)(II)(III)(IV),计算机科学,1994,N.5,N.6,1995,N.1。
[12] 波普儿,猜测与反驳,科学知识的增长,1963。
[13]李未,开放逻辑:一个关于形式系统序列和极限的理论,在[2]中,197-226页。
[14]Mingsheng Ying,Topology in process calculus: Approximate correctness and infinite evolution in concurrent programs, Springer Verlag, to be published.
[15]C.E. Shannon, A mathematical theory of communication, Bell Sys. Tech. Journal, 27: 379-432, 623-656, 1948.
[16]C.A. Petri, Private communication
[17]M. Hennesy & H.Lin, Symbolic Bisimulations, Theoretical Computer Science, 138: (2) pp.353-389.1995.
[18]R. Milner, Communicating and mobile systems: the p-- calculus, Cambridge university press, 1999.
[19] Cardelli I., Gordon A D., Mobile Ambients, in M.Nivat, editor, Foundations of Software Science and Computational Structures, LNCS No.1378, Springer Verlag, 1998:140—145.
[20] Vitek J., Castagna G., A calculus of secure mobile computations, in Proc. of the IEEE Workshop on internet programming languages, 1998.
[21]夏佩肃,量子计算,中科院计算所技术报告,2001。
[22]李明、P.M.B.威塔涅著,描述复杂性,科学出版社,1998。
[23]Lu Ruqian, New approaches to knowledge acquisition, World Scientific Publ., 1994.
[24] Wielinga, B., Schreiber A.T., Breuker J.A. KADS: A modeling approach to knowledge engineering. Knowledge Acquisition, 4(1):5—53, 1992
[25] Lu Ruqian, Automatic Knowledge Acquisition by Understanding Pseudo-Natural Languages, Theory and Praxis of Machine Learning, Dagstuhl Seminar Report 91 (9426), pp.11-12, 1994.6.
[26] Lu Ruqian,Cao Cungen,Chen Yonghong,Han Zhangang, On Automatic Generation of Intelligent Tutoring Systems, Proc. of 7th International Conference of AI in Education, 1995.
[27] Lu Ruqian,Cao Cengen,Chen Yonghong,Mao Wenjie,Chen Weiqin,Han Zhangang, The PLNU approach to automatic generation of ICAI systems, Science in China, series A, Vol.38, supplement, pp.1-11, 1995.
[28] 毛文吉,陆汝钤, 基于SELD描述语言的英文文本知识自动获取,计算机学报,V.21, 增刊,pp.105-111, 1998
[29] Lu Ruqian, Mao Wenjie, Automatic Generation of ITS from English Text, ICCE 98, pp.319-324,1998.10.
[30] Lu Ruqian, Han Ke, Ma Yinghao, Lu Peijun, Using VR Techniques in ICAI Systems, Proc. of GCCCE'97, pp.230-237, 1997.
[31]David W. Mount, Bioinformatics, sequence and genomic analysis, Cold Springer Lab. Press,
[32]杨芙清、邵维忠、梅宏,面向对象的CASE环境青鸟II型系统的设计与实现,中国科学(A辑),1995,25(5):533-542。
[33] Lu Ruqian,Jin Zhi,Wan Ronglin, Requirement Specification in Pseudo-Natural Language in PROMIS, Proc. of 19th COMPSAC, pp.96-101,1995.
[34] Lu Ruqian, Jin Zhi, Wan Ronglin, A knowledge- based approach for automatically prototyping management information systems, AVIGNON 94'.
[35] Lu Ruqian, Jin Zhi, A Multi-Agent and Pseudo-Natural Language Approach for Intelligent Information Services, Proc. of SEKE'97.
[36] Lu Ruqian, Jin Zhi, Liu Lin, Fan Guochuang, Chen Gang, Xun Xiaojin, Wang Sheng, OSNET-A Language for Domain Modeling, Tools Asia'98, 1998. 9.
[37] Lu Ruqian, Jin Zhi, Hierarchical Software Reuse, Advanced Chinese Journal of Software, 1998. 12.
[38]Ruqian Lu & Zhi Jin, Domain modeling based software engineering, a formal approach, Kluwer Publishers, 2000
[39] Lu Ruqian, Zhang Songmao, Wei Zichu, Generating Computer Animation from Natural Language Texts, Proc. of PACE 99', 1999, Los Angles.
[40]Ruqian Lu & Songmao Zhang, Automatic generation of computer animation, LNAI 2160, Springer Verlag, to be published.
[41]陆汝钤,张松懋,从故事到动画片,全过程计算机辅助动画自动生成,自动化学报,待发表。
[42] 曹存根, 关于建立“中国国家知识基础设施”的建议,计算机世界报,1998年12月。
(本稿最后修改日期:2003年4月7日)

回复列表 (共3个回复)

沙发

计算复杂性理论简介
洪加威

   理论计算机科学的分支学科,使用数学方法对计算中所需的各种资源的耗 费作定量的分析,并研究各类问题之间在计算复杂程度上的相互关系和基本性质 ,是算法分析的理论基础。为了计算一类问题,总要耗费一定的时间以及存储空间 等资源。资源耗费的多少决定于被计算问题的大小,是问题大小的函数,称为问题 对该资源需求的复杂度。对复杂度函数增长的阶作分析,探讨它们对于不同的计 算模型在一定意义下的无关性,根据复杂度的阶对被计算的问题分类,研究各种不 同资源耗费之间的关系,对一些基本问题的资源耗费情况的上、下界作估计等,构 成计算复杂性理论的主要研究内容。

  数理逻辑和数学本身的发展,在20世纪30年代建立了 可计算性理 论 。40年代以后,随着计算机科学技术的发展,人们不仅需要研究理 论上的、原则上的可计算性,还要研究现实的可计算性,即研究计算一个问题类需 要多少时间,多少存储空间;研究哪些问题是现实可计算的,哪些问题虽然原则上 可计算,但由于计算的量太大而实际上无法计算等。这就使得计算复杂性理论作 为理论计算机科学的一个分支而发展起来。

   计算模型  计算模型 为了对计算作深入的研究,需要定义一些抽象的机器。30 年代所定义的简单 图灵机 、递归函数等都是计算的模型 。但当时都只考虑到理论上的可计算性而没有考虑计算的复杂性。因此,为了度 量计算的复杂性,70年代前后又提出 多带图灵机模型 、 随机存取机器模型 等串行计算模型和 向量机器模型 等并行计算模型。

   资源  资源 资源的确切定义决定于计算的模型。例如,对于多带的图灵机 ,就有串行时间、空间、巡回等资源(见 公理复杂性理论 )。一般说来,各种模型的主要资源有并行时间、空间和串行时间三种。

   并行时间和巡回  并行时间一般指并行计算模型计算时所需步数,例如向量机的自始至 终执行指令的总条数。但对串行模型也可以定义一种称为巡回的资源。可以证明 它相当于并行时间。对于多带图灵机,它是工作带头部改变方向的次数。 一般地 说,巡回是周相的总数,而周相则是串行模型工作中的一个阶段, 在此阶段中被计 算出来而记录在工作空间上的信息,在此阶段内不再被读到。

   空间  在计算过程中需要记录下来以备后用的最大中间信息量。对于多带 图灵机,是计算过程中用过的工作带上的方格数。

   串行时间   计算过程中原始运算的总量。因此,对于串行模型而言,它代表计算 自始至终的总步数。对于并行模型而言,每一步可以同时作许多个原始的运算,自 始至终各步的原始运算数目的总和就是串行时间。

   最坏情铝复杂度和平均情铝复杂度  最坏情铝复杂度和平均情铝复杂度 在定义任何一种资源时,例如定 义时间耗费时,时间是输入字符串w的函数,记为t(w)。对于所有长度等于n的字w , t(w)中必有最大的一个(可能是无穷大),这个值只与n有关,可以记为T(n),称为 最坏情况复杂度。如果考虑对所有长度等于n的字,取t(w)的平均值,就得到平均 复杂度。它当然不超过最坏情况复杂度。

   相似性原理  相似性原理 对图灵论题的进一步研究,可断言各计算模型在计算能 力上的大致等价性。也就是说,对于同一类计算问题而言,各理想的计算模型使用 本质上同样多的并行时间、本质上同样多的空间和本质上同样多的串行时间,三 者同时成立。所谓本质上同样多是指多项式相关联。

  以多带图灵机和向量机器为例,可以证明下面的相似性定理:设n是输入字符 串的长度,它代表问题的大小。对于任何一个多带图灵机,设它的巡回为R(n),空 间为S(n),串行时间为T(n),则一定有一个向量机器来模拟它,使得存在一个多项 式p, 向量机器的并行时间R 1 (n),空间S 1 (n)和串行时间T 1 (n)满足R 1 (n)≤p(R(n) )S 1 (n)≤p(S(n))T 1 (n)≤p(T(n))在以上 结论中把多带图灵机和向量机器的位置对调一下也成立。这说明在多项式相关联 意义下,这两个模型没有本质的区别。因此,巡回是串行模型的虚拟并行时间。

   计算的类型  计算的类型 这里只考虑判定问题或是非问题。机器状态转移和接受 输入的方式称为计算的类型。在普通计算中,机器状态只依赖于时间和输入,是完 全确定的。每一步都由前一步所达到的状态唯一确定。如果机器最后进入一个接 受状态,就认为机器接受了输入。这种计算称为确定型的,计算的过程可以用一条 链来表示(图1)。确定型是最简单的一种计算类型。

  但有时机器在某一时刻可以有若干种选择,进入若干不同状态,而在新的情况 下又有若干不同选择等。这时计算过程可用一棵树表示(图2)。若规定只要有一 条路从树根通向一个接受的顶点,就认为机器接受了输入字符串,这种接受方式就 叫做非确定型的(见非确定性)。此 图1 确定型计算 图2 非确定型计算 时,树高被看作是非确定计算所需的时间。

  随机型计算的定义有许多种。较弱的一种定义为:从计算树的根往下走,每到 一个岔路口就扔一枚钱币以决定去向。如果用这种方式碰到一个接受状态的概率 大于1/2,就接受输入字w。较强的一种定义为:如果输入应该被拒绝则机器一定拒 绝,如果输入应该被接受则机器接受的概率大于或等于1/2。或者说,若输入该被 拒绝,机器是不会犯错误的;否则机器犯错误的可能性不超过一半。这种算法又称 为概率算法。

   R.索罗威和V.史托拉森找到一个多项式时间的随机型素数判定算法。若被判 定的数m的确是一个素数,则算法一定会回答是素数。若m不是素数,则算法回答是 素数的可能性小于1/2。可以不断对m重复这一算法,而且每次的结果是独立的。 例如重复100次,若每次回答都是素数则可断言它是素数,只要有一次回答不是素 数则可以肯定它不是素数。这样,犯错误的可能性将小于2 -100 。由于尚未找到确定型多项式时间素数判定算法,这类概率算法就具有 很重要的意义。最早的这样一个算法由E.R.伯勒嵌普给出。他找到一个多项式时 间的概率算法,去分解p个元素的域GF(p)上的一个多项式。

  计算理论中有重要意义的计算类型还有交错型等。

  相似性原理和相似性定理不仅对确定型计算成立,而且对非确定型、交错型 、随机型等各种计算类型都是成立的。

   复杂性类  复杂性类 根据识别时资源耗费的复杂程度而对形式语言所作的分类 。在多项式时间内用确定型机器可识别的语言可归入一类,记为P。把那些用非确 定型机器在多项式的串行时间内可识别的语言归入一类,记为NP(见NP 完全性 )。在这种条件下无需说明采用什么计算模型,因为根据相似 性原理,不论采用何种模型,P和NP的意义是不变的。

   N.皮彭格提出P的一个重要子类称为NC,它由所有同时可在多项式的空间和对 数多项式的并行时间内可计算的函数组成。如果说P代表现实可计算的问题,那么 NC即代表其中用多项式处理机在对数多项式时间内计算的问题。整数的加减乘除 运算、整序、图联通性、矩阵的乘法、除法、行列式、多项式的最大公因子、上 下文无关语言识别、找图的最小张开树等问题都属于NC。

  与之对偶的另一个子类由所有同时可在多项式的并行时间和对数多项式的空 间内计算的函数所组成,称为SC。

  在确定型多项式空间中可判定的语言类记为PSPACE。就已有的计算模型而言 ,在确定型多项式并行时间中可判定的语言类恰为PSPACE。

  当然,还可以考虑概率型的机器在对数多项式并行时间和多项式空间中可识 别的语言类等。根据相似性原理,这些类的定义都是独立于计算模型的。

   归约和完全性  归约和完全性 研究复杂性类和其间关系的方法。在数学中,常常把 一类问题的计算归结为另一类问题的计算。例如,利用公式 〖FK(W2〗〖WTBX〗〖JZ〗x〖DK〗·y=〖SX(〗1〖〗2〖SX)〗[(x+y )2-x2-y2]〖FK)〗〖WTBX〗 可把乘法归约为平方、加减法和用2除。如果平方、加减法和用2除 能很快算出来,乘法也就可以很快地算出来。

  设有两个语言L 1 、L 2 和一个简单易行 的变换T,如果一个字X属于L 1 ,当且仅当变换以后的字T(x)属 于L 2 ,那麽就说变换T把L 1 归约成L 2 。因为,若要判定某个字X是否属于L 1 ,只 要用T变换一下,然后去判断T(x)是否属于L 2 就行了。为了使 得归约是有实际意义的,就要求T是一个容易实现的变换。例如,可在对数空间中 实现。这时就说L 1 在对数空间中归约为L 2 。

  设C是一个复杂性类, L是任一语言。 如果C中任何语言都可以在对数空间中 归约为L,就说C可在对数空间中归约为L。 或者说, L属于C难。其直观意义为: 若L可以容易地计算出来,则C中任何问题均可以容易地计算出来。 反之, 若C中 有难于识别的问题, 则L的识别肯定不会更容易 (故称为C难)。 进一步说, 如果 L属于C难, 而且本身也属于C,就说L在C中是完全的。意思是:C中任何语言可以很 快识别, 当且仅当人可以很快识别。

  归约和完全性是复杂性理论中重要的研究方法。第一个NP完全性问题由S.A .库克在1971年提出,R.卡尔普等人解决了一系列基本的NP完全性问题。

   复杂度的上界和下界  复杂度的上界和下界 用以估计问题所需某资源的复杂程度的界限函 数。如果找到解某问题的算法,其资源的复杂度为u(n),则u(n)是问题本身复杂度 的一个上界。如果对任何算法,其复杂度都必需大于l(n),则l(n)是问题复杂度的 一个下界。

  对各类具体问题的复杂度的上、下界的研究,一般说来属于算法分析的范围 。但有时也把某些基本问题的上、下界的研究归入复杂性理论。

   n维的快速傅里叶变换需要O(n log n)次算术运算;n位的乘法在多带图灵机 上需时O(n log n log log n);n阶矩阵乘法只需要4.7n 2.81 次算术运算,判定一个n位数是否为素数需时O(n clogloglog n );在出度限定情形下的图同构的判定,存在多项式时间算法。

  下界的结果多借助于对角线方法得出,最典型的是关于复杂性谱系的一系列 结果。带有平方的正规表达式的等价问题的判定需要指数的空间。例如,不难证 明,为了把n个数排序,比较的次数至少正比于n log n。又如n个点的多项式的插 值问题,若只许用算术运算,则至少需要 nlogn次乘法。关于两个资源乘积的下界 ,为了识别n位的完全平方数,在一个离线的图灵机上,时间和空间的乘积至少正比 于n 2 。为了对n个大小从1到n 2 之间的数排 序,时间和空间的乘积至少正比于n 2 /log n。为了识别任何非 正规的语言,多带图灵机的工作空间和工作带巡回数的乘积的阶不能小于n。

  从发展趋势来看, 计算复杂性理论将深入到各个数学分支中去。计算机科 学的发展,特别是 新一代计算机系统 和 人工智 能 的研究,又会给计算复杂性理论提出许多新的课题。计算复杂性理 论、描述复杂性理论、信息论、数理逻辑等学科将有可能更紧密结合,得到有关 信息加工或信息活动的一些深刻结论。 参考书目 A.V.Aho,J.E.Hopcroft & J .D.Ullman,The Design and Analysis of Computer Algorithms,Addison-Wesl ey,Reading,Mass.,1974. J.E.Hopcroft& J.D.Ullman,Introduction to Autom ata Theory, Languages and Computation,Addison-Wesley,Reading, Mass., 1979. 

板凳

万丈高楼平地起——浅谈网格计算基础
中科院计算所 李伟  
    网格技术的产生、发展必须具备以下三个基本条件:计算资源的广域分布、网络技术(特别是Internet)以及不断增长的对资源共享的需求。在计算机技术发展的早期阶段,只有很少数量的大型计算机,它们通常被安装在相互独立的计算中心内,多个计算机用户通过使用终端来共享一台大型机的资源,但却不能同时共享多台大型机的计算资源。随着网络技术的发展,多台大型计算机可以在局域网(LAN)内互连,用户通过网络便可以同时使用多台计算机的资源。而Internet的飞速发展和普及使得网格计算技术的产生成为可能。图1显示了计算资源共享的发展过程。

   
系统构成
    网格系统可以分为三个基本层次:资源层、中间件层和应用层。
    网格资源层是构成网格系统的硬件基础,它包括各种计算资源,如超级计算机、贵重仪器、可视化设备、现有应用软件等,这些计算资源通过网络设备连接起来。网格资源层仅仅实现了计算资源在物理上的连通,但从逻辑上看,这些资源仍然是孤立的,资源共享问题仍然没有得到解决。因此,必须在网格资源层的基础上通过网格中间件层来完成广域计算资源的有效共享。
    网格中间件层是指一系列工具和协议软件,其功能是屏蔽网格资源层中计算资源的分布、异构特性,向网格应用层提供透明、一致的使用接口。网格中间件层也称为网格操作系统(Grid Operating System),它同时需要提供用户编程接口和相应的环境,以支持网格应用的开发。
    网格应用层是用户需求的具体体现。在网格操作系统的支持下,网格用户可以使用其提供的工具或环境开发各种应用系统。能否在网格系统上开发应用系统以解决各种大型计算问题是衡量网格系统优劣的关键。最近两年,在美国的高性能计算研究领域,网格计算成为非常引人注目的热点。与此同时,企业界也纷纷推出了各自的产品,但到目前为止,仍有相当多的关键技术还有待突破。
【三大挑战】
    网格计算要真正步入实用阶段必须解决以下三大问题:
1. 体系结构设计
    从第一台计算机出现到现在,计算机体系结构已经发生了一系列变化,经历了大规模并行处理系统、共享存储型多处理器系统、群集系统等各个发展阶段,这些系统的共性是构成系统的资源相对集中。与此相反的是,组成网格系统的资源是广域分散的,不再局限于单台计算机和小规模局域网范围内。网格计算的最终目标是用网上的多台计算机构成一台虚拟的超级计算机,因此,网格系统的体系结构是我们必须首先解决的问题。简言之,网格系统有哪些组成部分、组成部分之间的关系以及如何协同工作是网格体系结构研究需要解决的问题。
2. 操作系统设计
    伴随着计算机体系结构的发展,计算机操作系统也经历了一系列发展变化,总的发展趋势是如何更高效、更合理地使用计算机资源。网格操作系统是网格系统资源的管理者,它所管理的将是广域分布、动态、异构的资源,现有操作系统显然无法满足这一需求。
3. 使用模式设计
    网格使用模式解决的是如何使用网格超级计算机的问题。在现有的操作系统上,计算机用户可以使用各种软件工具来完成各种任务。而在网格环境下,用户可能需要通过新的方式来利用网格系统资源。因此,在网格操作系统上设计开发各种工具、应用软件是网格使用模式研究需要解决的关键问题。
研究现状
    在国外,最著名的网格计算研究是美国的Globus项目。该项目的主要研究目标有两个:其一是网格技术的研究;其二是相应软件的开发和标准的制定。同时,Globus项目还涉及到网格应用的开发及试验床的建立。最近,Globus项目提出了网格的体系结构模型(图2)。
网格体系结构主要分为以下几个部分:
● 网格结构层(Grid Fabric) 提供资源相关、站点相关的基本功能,便于高层分布式网格服务的实现;
● 网格服务层(Grid Services)实现资源无关和应用无关的功能,网格服务的实现涉及到地域和机构分布; ● 网格应用工具层(Grid Application Toolkits) 提供更为专业化的服务和组件用于不同类型的应用;
● 应用层(Application) 由用户开发的应用系统组成,网格用户可以使用其他层次的接口和服务完成网格应用的开发。     我国对网格计算的研究起步较晚,相关工作开始于1998年。由于网格计算是一项刚起步的研究,因此我们在网格计算关键技术的研究方面与国外差距不大,基本处于相同的起跑线上。目前,我国的网格计算研究主要集中于中科院计算所、国防科大、江南计算所、清华大学等几家在高性能计算方面有较强实力的研究单位。这些单位在高性能计算研究方面有很好的技术积累和很强的科研能力。其中,中科院计算所在高性能计算领域的主要成果是曙光3000超级服务器,其他单位的主要成果有银河巨型机、同方探索机群系统等。
    从1999年底到2001年初,中科院计算所联合国内十几家科研单位,共同承担了“863”重点项目——“国家高性能计算环境(National High Performance Computing Environment,简称NHPCE)”的研发任务。该项目的目标是建立一个计算资源广域分布、支持异构特性的计算网格示范系统,它把我国的8个高性能计算中心通过Internet连接起来,进行统一的资源管理、信息管理和用户管理,并在此基础上开发了多个需要高性能计算能力的网格应用系统,取得了一系列研究成果。
【网格计算】
---- Internet的产生与发展,对人们的思维方式、工作模式以及生活理念都产生了巨大的影响与冲击。以E-mail为主要应用的第一代Internet把遍布于世界各地的计算机用TCP/IP协议连接在一起; 第二代Internet则通过Web信息浏览及电子商务应用等信息服务,实现了全球网页的连通; 第三代Internet将“试图实现互联网上所有资源的全面连通,包括计算资源、存储资源、通信资源、软件资源、信息资源、知识资源等”,这就是网格计算(Gird Computing)。
---- 网格计算是构筑在Internet上的一组新兴技术,其基础设施一定是基于IP协议的宽带数字通信网络,它将改变传统的Client/Server和Client/Cluster结构,形成新的Pervasive/Grid体系结构,这种体系结构将使得用户把整个网络视为一个巨大的计算机,并从中享受一体化的、动态变化的、可灵活控制的、智能的、协作式信息服务。目前,网格计算不仅在学术界、研究领域进行着深入的研究与实验,同时也得到了来自产业界诸如IBM、HP、Microsoft、NTT、Intel、SGI和Sun等各大公司的巨资支持与商业应用开发。
---- 网格计算系统一般由网格硬件、网格操作系统、网格界面、网格应用4层基本结构构成,其最突出的特点是资源共享、协同工作和开放性标准。也正因为如此,网格计算目前研究发展的主要障碍便是标准协议的建立和体系结构的确定。
---- 网格计算虽然致力于高速互联网、高性能计算机、大型数据库、远程设备等连通和“一体化”,但网格计算的根本特征应该是资源共享而不是规模巨大,完全可以根据需要建造企业内部网格、局域网网格、家庭网格和个人网格,因此网格计算的应用将非常广泛:卫星图像的快速分析、先进芯片的设计、生物信息科学研究、超级视频会议、制造业的设计与生产、电子商务、数字图书馆及一般的商务应用。此外,开发新的应用、集成现有应用、消除信息及资源孤岛也将成为网格计算责无旁贷的任务。
---- 我们看到在2001年网格计算的概念已被众多的国内外媒体所关注,2002年它的发展将会引起世人更多的重视。
【什么是网格计算】
    随着超级计算机的不断发展,它已经成为复杂科学计算领域的主宰。但以超级计算机为中心的计算模式存在明显的不足,而且目前正在经受挑战。超级计算机虽然是一台处理能力强大的“巨无霸”,但它造价极高,通常只有一些国家级的部门,如航天、气象等部门才有能力配置这样的设备。而随着人们日常工作遇到的商业计算越来越复杂,人们越来越需要数据处理能力更强大的计算机,而超级计算机的价格显然阻止了它进入普通人的工作领域。于是,人们开始寻找一种造价低廉而数据处理能力超强的计算模式,最终科学家们找到了答案———Grid Computing(网格计算)。
    网格计算是伴随着互联网而迅速发展起来的,专门针对复杂科学计算的新型计算模式。这种计算模式是利用互联网把分散在不同地理位置的电脑组织成一个“虚拟的超级计算机”,其中每一台参与计算的计算机就是一个“节点”,而整个计算是由成千上万个“节点”组成的“一张网格”,所以这种计算方式叫网格计算。这样组织起来的“虚拟的超级计算机”有两个优势,一个是数据处理能力超强;另一个是能充分利用网上的闲置处理能力。
    实际上,网格计算是分布式计算(Distributed Computing)的一种,如果我们说某项工作是分布式的,那么,参与这项工作的一定不只是一台计算机,而是一个计算机网络,显然这种“蚂蚁搬山”的方式将具有很强的数据处理能力。今年年中,NTTData计划与Intel和SGI联合进行一项为期三个月的网格计算试验,届时将有包括家庭、企业和学术机构的100万台计算机相联,其总处理能力将比现有的最快的超级计算机还要快五倍。
    充分利用网上的闲置处理能力则是网格计算的有一个优势,网格计算模式首先把要计算的数据分割成若干“小片”,而计算这些“小片”的软件通常是一个预先编制好的屏幕保护程序,然后不同节点的计算机可以根据自己的处理能力下载一个或多个数据片断和这个屏幕保护程序。于是“演出开始了”,只要,节点的计算机的用户不使用计算机时,屏保程序就会工作,这样这台计算机的闲置计算能力就被充分地调动起来了。
    这种“蚂蚁搬山”式的计算式的网格计算,看似普通,但却有过及其出色的表现。1999年,SETI@HOME项目是网格计算的一个成功典范。该项目在1999年初开始将分布于世界各地的200万台个人电脑组成计算机阵列,用于搜索射电天文望远镜信号中的外星文明迹象。该项目组称,在不到两年的时间里,这种计算方法已经完成了单台计算机345000年的计算量。可见,这种“蚂蚁搬山”式的分布式计算的处理能力十分强大,正所谓“泰山不辞抔土,故能成其大”。
    网格计算不仅受到需要大型科学计算的国家级部门,如航天、气象部门的关注,目前很多大公司也开始追捧这种计算模式,并开始有了相关“动作”。
    “蓝色巨人”IBM正在构筑一项名为“Grid Computing”的计划,旨在通过因特网,向每一台个人电脑提供超级的处理能力。IBM公司副总裁、也是这项计划的总设计师欧文·伯杰说,“Grid Computing”是一种整合电脑资源的新手段,它通过因特网把分散在各地的个人电脑连接起来,不仅可使每台个人电脑通过充分利用相互间闲置的电脑能源,来提升各自的电脑处理能力,还可使成千上万的用户在大范围的网络上共享电脑处理功能、文件以及应用软件。 正如网络技术总是从科学开发领域转向企业商务领域一样,我们也希望看到‘Grid Computing’能取得这样的进展。
    另一个业界巨人SUN也推出新软件促进网络计算的发展。2001年11月,Sun推出了Sun Grid Engine企业版5.3版软件的β版,继续提升它的网络技术计算水平。该软件自一年前推出以来, Sun Grid Engine 5.2.3版软件的用户已经增长了20倍。今天,全球有118000多颗CPU都是采用Sun Grid Engine软件管理的。
    除此之外,一批围绕网格计算的软件公司也逐渐壮大和为人所知并成为受到关注的新商机,如:Entropia、Avaki、Noemix、Data Synapse等等。有业界专家预测,网格计算将成为2002年网络市场发展的热点。据《ForbesASAP》预测,网格技术将在2005年达到高峰,并带来因特网的新生。如果网格技术能促使市场按预期的17%年增长率持续成长的话,那么在2020年将会形成一个年产值20万亿美元的大产业。

3 楼

扫除一切旁门左道----降龙十八掌用法.
丐帮帮主   萧峰
啪----啪啪----啪啪啪啪!!!!----呜呜哎哎唷!-----

我来回复

您尚未登录,请登录后再回复。点此登录或注册