计算机科学技术百科全书（第三版）

权威、准确，客观、公正，计算机科学技术领域集大成之重磅作品 

《全书》根据计算机学科的内在联系、相关程度与性质特点，划分为“计算机科学理论”、“计算机组织与体系结构”、“计算机软件”、“计算机硬件”、“计算机应用技术”和“人工智能”6大分支，按4级框架，共设置1293个条目200多万字。由于中文信息处理是我国及全球汉字通用地区计算机应用中的重要技术，特在“计算机应用技术”分支中，设置有关中文信息处理条目80余条，以供读者查阅。《全书》按照不同层次与内容涉及范围，将条目释文分为大、中、小3类。在释文中有一定释义的常用名词术语还择要列作“主题词”者共约1031个，与条目一起编入内容索引中，以利查阅。《全书》“总论”全面总览了计算机科学技术的内涵与对人类社会发展的巨大作用与深远意义，以引导读者全面、科学地认识计算机科学技术。

计算机科学技术总论13

条目分类目录31

正文1

条目汉语音序索引1303

INDEX OF ARTICLES (条目外文索引)1321

内容索引1339

附录Ⅰ缩略语1366

附录Ⅱ计算机及相关学科科技期刊1409

附录Ⅲ计算机及相关学科学术团体1424

计算机科学技术总论

 

《计算机科学技术百科全书》（以下简称《全书》）第二版出版至今已10年有余，在这十多年的时间里，计算机科学技术迅速发展，又涌现出许多新的内容。为适应广大读者获得计算机科学技术领域更新的知识的需求，我们从2010年开始筹划、组织《全书》第三版的编撰工作。进入21世纪后，由于计算机科学技术的快速迭代和市场的迅猛成长，计算机产业已经步入成熟期。计算机、计算机网络、计算机的应用成为绝大多数人生活的基本工具和重要组成部分。因而，计算机科学技术的内容也成为人们必须学习的基础知识，作为“百科全书”理应承担“无围墙大学”的教学责任，为此，在本次修订中着重对有关计算机最基本、最重要的概念再次进行了审改，力求完善、准确。在“总论”中的“基本概念”和“基本内容”部分，分别对“计算机”“计算机科学”“计算机技术”“计算机科学技术”“计算机体系工程”“计算机产业”“计算机科学理论”“计算机体系结构”“计算机软件”“计算机硬件”“计算机网络”“计算机应用技术”“人工智能”的定义均做了完整、严谨的论述。“总论”中还增加了近十年“计算机科学技术”和“计算机产业”发展的新内容。在本次修订中，对二级框架未做大的改动，仍为“计算机科学理论”“计算机体系结构”“计算机软件”“计算机硬件”“计算机网络”“计算机应用技术”“人工智能”七个分支。与二版比较，只将“计算机组织与体系结构”更改为“计算机体系结构”，并撰写了释文。为使各分支更准确涵盖本学科领域知识，在分支之间有个别部分的调整。例如，将“管理信息系统”“电子商务系统”等计算机应用软件的条目调入“计算机软件”二级框架内，新建立了“计算机应用软件”四级框架。在各分支中，又删除了已现陈旧的条目；进一步归并了一些较细的条目；增加了反映新技术应用的如“计算机学科交叉新技术”“网络存储”“数据库应用技术”等系统条目。对反映新技术、新理论且已成熟形成固定概念的新知识主题则列为新的条目，如“云计算”“服务计算”等。网络安全问题日益突出，也增加了相关的条目。修订后，全书共有1509条，其中，“计算机科学理论”179条，“计算机体系结构”158条，“计算机软件”394条，“计算机硬件”181条，“计算机网络”204条，“计算机应用技术”267条，“人工智能”126条。计算机科学技术发展迅猛，虽然我们不断在做《全书》的修订工作，力求跟上其发展步伐，使《全书》的内容能展现和记录计算机科学技术的状况，但总有遗憾。不足之处望广大读者不吝赐教。衷心感谢上百位作者在第三版修订中付出的心血以及清华大学出版社对出版本书的大力支持。 《计算机科学技术百科全书》编撰委员会2015.12

A〖=1〗Aｋeｍɑｎ ｈɑｎｓｈu〖=2〗阿克曼函数 (Ackermann’s function)〖=0〗一种递归而非原始递归的函数(参见〖=H1〗递归函数和〖=H1〗原始递归函数)。阿克曼函数定义如下：ψ(0,y)=y 1ψ(x 1,0)=ψ(x,1)ψ(x 1,y 1)=ψ(x,ψ(x 1,y))该函数定义中包含双重递归。当x>0时，ψ(x,y)的值均可通过“较早”值ψ(x1,y1)来定义。这里，或者x1阿 安〖=1〗ɑｎｑｕɑｎ ｃɑｏｚｕo ｘiｔoｎg〖=2〗安全操作系统（secure operating system）〖=0〗具有强制访问控制机制并可验证的操作系统。强制访问控制机制是一种用于保障信息机密性、完整性和资源隔离性等特性的信息安全机制，与自主访问控制不同，强制访问控制是完全由操作系统而不是由信息的所有者（属主）决定的访问控制；可验证指可以通过某种分析或验证手段得出所实现的安全机制与所描述的安全策略是相符的。从广义上讲，凡是拥有较强抗安全攻击能力的操作系统都可以认定为安全操作系统。〖=5〗沿革〖=0〗安全操作系统的研究始于20世纪60年代。1967年，计算机资源共享系统的安全控制问题引起了美国国防部的高度重视，隶属于国防科学部的计算机安全特别部队开始操作系统安全技术研究。1973年，出现了第一个可证明的信息安全系统的数学模型BLP以及支持BLP模型的安全操作系统Multics。1983年，美国国防部颁布了历史上第一个计算机安全评价标准，简称橙皮书。橙皮书对安全操作系统的研究与发展具有深远影响。90年代以来，随着网络技术的发展，操作系统的环境越来越复杂，1993年出现了更适合互联网环境的计算机安全评价标准Common Criteria，简称CC标准，1999年成为国际标准，并在美国和西欧相继推出了符合CC标准的一系列用于保护重要数据和应对安全攻击风险的安全操作系统。进入21世纪，基于开源的安全操作系统的研究活跃，出现了一批开源的安全操作系统，著名的有美国国家安全局为主开发的基于Linux的SELinux, Novel公司推出的AppArmor等。〖=5〗操作系统安全等级分类〖=0〗根据安全机制及安全保障强度的不同，操作系统通常可以分为不同的安全等级。按橙皮书的经典规范，操作系统一般可以分为D、C1、C2、B1、B2、B3 和A1 七个安全等级。每个等级对应确定的安全特性需求和保障需求，后一个安全等级涵盖前一个安全等级的安全机制，并提供更强的安全功能和安全保障。D级是最小保护级。C1级是自主安全保护级，主要包含用户标识与鉴别，自主访问控制。C2级是受限的访问保护级，提供细粒度的自主访问控制和审计以及不允许遗留在内存或磁盘的信息（客体）被后面的进程或用户使用的“禁止客体重用”等。目前，人们广泛使用的商用操作系统多属C1级或C2级。B1级是安全标记保护级，引入了访问的主客体标记和强制访问控制，并作为其主要特征。符合橙皮书B1安全级及以上评价标准的操作系统通常才称为安全操作系统，也称可信操作系统。B2级是结构化保护级，具有严格的安全策略及其形式化的模型，并提供可信路径以及对隐通道的分析。B3级是安全域级，设有专门负责安全总控的引用监控机，还拥有可信恢复机制。A1级是验证设计级，安全功能与B3相同，但形式化要求更高。〖=5〗主要内容〖=0〗安全操作系统包含的主要技术和安全机制通常有用户标识与鉴别、安全标记、强制访问控制、事件审计、禁止客体重用等，同时至少具有安全策略的非形式化描述，并对系统进行安全设计和验证。用户标识与鉴别一般基于操作系统的可插拔的认证模块（PAM）实现。除了用户名与口令的认证机制外，进一步引入强化的身份认证，如基于智能卡的身份认证、基于指纹的身份认证等。安全标记是操作系统赋予访问主体（用户、进程等）和访问客体（如文件）安全属性的相应标签。用户标记由系统管理员通过操作系统设置，用户经认证后，获得用户标记，并派生进程标记；文件标记是赋予文件的安全属性，文件标记由创建文件的进程或者父目录决定。安全标记是强制访问控制的基础，为进行强制访问控制，还需要以规则形式规定主客体标记间访问关系的安全策略，强制访问控制一般采用策略实施与策略决策分离的原则实现，策略实施仅仅是嵌入到任务管理、文件系统、网络等代码中的一个控制程序，一旦进程需要访问客体，实施程序便通过调用策略决策模块进行权限的判断。基于安全策略逻辑的分析判断的实质性工作由策略决策模块完成，策略决策模块实际上是安全策略相关规则的一个通用解释程序。事件审计是对安全相关的事件进行审计，并可以在事后进行查看和分析。审计事件包括用户登录、文件访问、安全标记创建等。〖=5〗发展趋势〖=0〗随着信息安全与网络安全技术的发展，物理级、运行级、数据级和内容级等许多更有效的安全技术不断融入操作系统中。因此，只要能够为所管理的数据和资源提供相应安全级别的保护，并能有效控制硬件和软件功能的操作系统都可以认定为安全操作系统。典型的例子是OpenBSD操作系统，它不仅拥有很多专用的抗攻击功能，且每一行代码都经过严格细致的手工漏洞检查，被认为最安全的操作系统。可见，专门从安全的角度设计安全操作系统或者融入比强制访问控制更强和更丰富安全机制的操作系统将成为安全操作系统的发展趋势。近年来，为了适应网络应用的更高安全保障需求，广泛引入可信计算技术，从计算机体系结构入手，可信操作系统正成为构建基于信任根的计算系统信任链的重要研究方向。参考文献1. Wikipedia. http://en.wikipedia.org/wiki/Secure_operating_system2. DoD 5200. 28STD, Department of Defense Trusted Computer System Evaluation Criteria.  National Computer Security Center, Ft. Meade, MD, USA, Dec 19853. 刘克龙,冯登国,石文昌. 安全操作系统原理与技术. 北京: 科学出版社, 2004(何连跃)
安〖=1〗ɑｎｑｕɑｎ ｓｈuｊuｋu〖=2〗安全数据库（security database）〖=0〗在通用数据库管理系统基础上，提高安全性标准的〖=H〗数据库管理系统〖=0〗。安全数据库涉及技术、管理和物理等多个层面，主要应对数据库系统的风险和威胁，保证数据机密性、一致性、可用性等特性。和通用数据库相比，安全数据库在数据备份、访问控制、数据加密、审计、推理控制等机制方面得到加强。数据库系统的物理损坏来源于地震、火灾、洪灾、过热、闪电等因素。数据库系统主要通过数据备份策略提高其物理安全性。数据库访问控制机制根据系统存储的访问控制规则，确保用户只能按照其授予的权限来访问和操作数据库中的信息。按照实现方式和保护强度的不同，数据库访问控制可以分为自主访问控制、强制访问控制和基于角色的访问控制等。自主访问控制机制基于用户对象权限矩阵，比较用户的请求与矩阵中保存的权限，判定用户的请求是否合法。强制访问控制机制为访问数据的主体和数据库中的客体设置安全性标签，通过比较安全性标签的级别判定主体是否有权对客体进行进一步的访问操作，确保信息的单向流动只能由低安全级主体向高安全级主体流动。基于角色的访问控制通过引入角色来关联权限和用户，支持灵活的权限管理。数据库安全审计系统提供了一种事后检查的安全机制。安全审计机制将特定用户或者特定对象相关的操作记录到系统审计表中，作为后续对操作的查询分析和追踪的依据。通过审计机制，可以约束用户可能的恶意操作。数据库加密使用已有的密码技术和算法对数据库中存储的信息进行保护。加密后数据的安全性能够进一步提高。即使攻击者获取数据源文件，攻击者也很难获取原始数据。但是，数据库加密增加了查询处理的复杂性，由于可能采用不同的加密方法，同时加密后的数据很难保证原始数据的特性，数据库管理系统一般无法直接查询加密数据，查询效率受到较大影响。加密数据的密钥的管理和数据加密对应用程序的影响也是数据库加密过程中需要考虑的问题。数据库推理控制机制用来避免用户利用其能够访问的数据推知更高密级的数据，即用户利用其被允许的多次查询的结果，结合相关的领域背景知识以及数据之间的约束，推导出其不能访问的数据。推理控制目前尚处于理论研究阶段。实现安全数据库管理系统不仅和数据库系统本身的安全机制相关，还和数据库系统所在环境和安全管理密切相关。数据库系统作为基于操作系统的一种系统软件，依赖操作系统提供的安全功能和机制。同时数据库系统和客户端的信息交换都通过网络实现。因此安全的操作系统、安全的网络、完善的安全管理机制是实现安全数据库管理系统的基础和前提。参考文献1． Silberschatz A, Korth Henry F, Sudarshan S. 数据库系统概念. 6版. 杨冬青，李红燕，唐世渭,等译. 北京：机械工业出版社，20122．  Liu L,  Ozsu M T. Encyclopedia of database systems. Springer, 2009（杨冬青高军）
安B〖=1〗Bɑｋeｓi ｆɑｎｓｈi〖=2〗巴克斯范式 (Backus normal form,BNF)〖=0〗用以精确描述程序设计语言语法的一种形式体系。又称〖=W〗巴克斯诺尔形式〖=0〗或〖=H1〗巴克斯诺尔形式体系。美国IBM公司研究员J.Backus和丹麦哥本哈根大学教授P.Naur最早用以描述ALGOL60语言的局部语法(其全程语法并不能用BNF描述)，因而得名。相对BNF所描述语法之语言说来，BNF为〖=H1〗元语言，它所描述语法之语言为对象语言。BNF之基本成分为如下部分。元符号，一个是元等价符“∷=”，表示“定义为”；一个是元或符“|”，表示对所指出的各款项之选择；还有一对尖括号“〈 〉”，用以连同所括之名表示非终极符。元变量，用以表示相应对象语言之语法单位。元变量本身不属对象语言，其值为对象语言中之符号串。以上述元符号及元变量为基础所构成的一组元公式(或称产生规则)，用以刻画相应对象语言之局部语法。其形为非终极符∷=非终极符与终极符组成之符号串其中非终极符(即上述之元变量)刻画对象语言之语法单位，终极符为对象语言之符号串。元公式中“∷=”之左方称为公式之左部，“∷=”之右方称为公式之右部，具有相同左部之不同公式可以公用同一个左部。例如，在ALGOL60中，有〈二进制数字〉∷=0|1〈十进制数字〉∷=0|1|2|3|4|5|6|7|8|9〈数字〉∷=〈二进制数字〉|〈十进制数字〉元公式之右部亦可出现正在定义的左方非终极符，此时为递归定义。如〈标识符〉∷=〈字母〉|〈标识符〉〈字母〉|〈标识符〉〈数字〉即，标识符定义为以字母起头的字母数字串。BNF能严格表示一类上下文无关语言之局部语法，自从在ALGOL60语言文本中首先采用以来，已在不少计算机学科中得到广泛应用和推广。BNF一词有其演变过程，起初代表Backus normal form或Backus|Naur form，后来人们认为，既然BNF为一形式体系，为一元语言，称之为form，似觉欠妥，F以代表formalism为佳，从而便出现Backus|Naur formalism，这里formalism一词与formal system同义。参考文献1. Naur P, et al. Report on the algorithmic language ALGOL 60. CACM, 1960, 3(5):  2993142. 陈火旺,等.程序设计语言编译原理.北京： 国防工业出版社，1984(陈火旺程虎贲可荣)
〖=1〗BɑｋeｓiNｕoeｒ ｘiｎgｓｈi ｔiｘi〖=2〗巴克斯诺尔形式体系(BackusNaur formalism,BNF)〖=0〗参见〖=H1〗巴克斯范式。
巴 办〖=1〗ｂɑｎgoｎg ｘiｎｘi ｘiｔoｎg〖=2〗办公信息系统（office information system）〖=0〗为政府和企事业等部门各级办公人员提供办公信息服务的〖=H〗应用软件系统〖=0〗。办公信息系统的作用是: 以提高办公效率和办公质量为宗旨，利用部门所涉及的内外部信息，优化办公流程，改善办公信息的流转与管理，实现办公过程的信息化。在2000年11月办公自动化国际学术研讨会上，专家建议将办公自动化（OA）更名为办公信息系统。由此，一般认为办公信息系统与原名办公自动化系统是同义的。办公自动化一词早在1936年就出现了，意在运用打字机和电话设备帮助办公人员处理办公业务。随着现代计算机的诞生和发展，特别是网络通信技术的发展，其外延和内涵都发生了很大变化。现代意义上的办公信息系统经历了3个阶段: ①以简单数据处理为中心的阶段，表现为利用个人计算机和办公套件，实现数据统计和办公文档写作电子化，使办公信息载体从纸介质方式向电子方式转移。②以网络为基础、以工作流为核心的阶段，出现了文档管理、电子邮件、目录服务、公文流转和群组协同工作等办公信息系统。③以决策管理为核心的阶段，不仅出现了网上实时交流信息的集成平台，实现公文和文档的一体化处理，而且在办公处理的每一环节上提供相关的决策知识，使办公人员从被动向主动转变，在提升办公人员决策能力的过程中，提高部门的整体办公质量、效率和应变能力。办公信息系统由〖=H〗计算机硬件〖=0〗、〖=H〗计算机网络〖=0〗和办公专用设备，〖=H〗操作系统〖=0〗、〖=H〗数据库系统〖=0〗、〖=H〗分布计算中间件〖=0〗和办公套件等基础软件以及具体实现办公信息服务的应用软件组成。应用软件的开发参见〖=H〗软件工程〖=0〗。图1典型半导体存储器的基本组成框图办公信息系统的基本功能包括: ①公文处理: 实现公文的签收、登记、分发、归档等处理； ②电子邮件: 依据工作流程将文档传递给下一部门或人员； ③签报管理: 对公文进行拟稿、审核、签收、会签、拟办、签批、电子签名、交办、退稿、备查、销毁等管理； ④会议与会务管理: 提供会议计划、日程安排、会议资料准备、会议记录、会议查询和其他会务管理； ⑤资料管理: 对原始电子资料进行编辑、文摘与提要编写、刊号管理以及查询、统计和汇编； ⑥案卷管理: 将相关文件编辑成卷，并进行查阅和借阅管理； ⑦公共信息服务: 提供机构设置、职能与人员编制信息，各类业务信息以及通讯录、公告板等信息服务。此外，还有向公众提供信息发布、检索、查询、引导和专题电子论坛等功能。在基本功能的基础上，可以按应用层次将办公信息系统分类为: ①事务型,指日常办公事务处理和公文流转等行政事务处理两种； ②信息管理型,指基于〖=H〗管理信息系统〖=0〗功能的办公信息系统； ③决策支持型,指基于〖=H〗决策支持系统〖=0〗功能的办公信息系统。此外，还可以按应用行业特定的业务需求或特点分类为事务型、专业型、生产型、经营型、案例型和政府型等。办公信息系统涉及软件技术、网络通信技术、行为科学和系统科学的综合应用。当前，办公信息系统已成为〖=H〗电子政务系统〖=0〗和〖=H〗电子商务系统〖=0〗的基础，在政府、企业和其他公共机构将得到更广泛更深入的应用。（孙志挥吴泉源）
办 半〖=1〗ｂɑｎｄɑｏｔi ｃuｎｃｈuｑi〖=2〗半导体存储器（semiconductor memory）〖=0〗用半导体大规模集成存储器芯片作为存储介质并能对数字信息进行存取的存储设备。典型半导体存储器的基本组成如图1所示，各部分的功能简述如下。(1) 半导体存储器芯片阵列它是信息存储单元的集合，由〖=H〗半导体存储器芯片〖=0〗按一定结构组成，是供〖=H〗中央处理器〖=0〗(CPU)或输入输出设备(I/O)存取信息的存储空间。(2) 地址输入缓冲及驱动由地址输入寄存器、片选译码器、地址分时电路和地址驱动器等几部分组成。地址输入寄存器的功能是接收CPU给出的地址，再将低位地址直接送给存储器芯片阵列，高位地址经过译码电路产生片选或块选信号。刷新计数器和地址分时电路为动态随机存取存储器(DRAM)所必需，它们的功能是将器件输入的行地址和列地址归并为一路，并将所产生的刷新地址送至存储器芯片的地址端口。(3) 数据锁存及双向驱动包含输入缓冲门、输入数据寄存器、输出锁存器和输出缓冲门等。它的功能是根据CPU的读写命令，将数据总线的内容写入被访问的存储单元，或者将被访问存储单元的内容读出到数据总线上，供CPU或I/O使用。(4) 控制电路包括访问信号控制和刷新电路。它的功能是接收CPU的启动、读、写、清除等命令，并对接收后的命令进行处理，产生各种时序控制脉冲和内部定时脉冲信号来控制存储器的读写操作或刷新操作。在半导体存储器的组成中，存储器芯片阵列是核心，其余三部分是存储器的外围电路。半导体存储器按在计算机中的工作性质可分为〖=H〗主存储器〖=0〗（内存）、〖=H〗辅助存储器〖=0〗（外存）、〖=H〗高速缓冲存储器〖=0〗和控制存储器等。主存储器具有速度高、存储容量较小的特点，用来存放CPU当前执行的程序和数据。通常主存储器是由随机存取方式和只读方式两种半导体存储器组成，它们分享主存储器的同一地址空间。辅助存储器的特点是速度慢，存储容量大，用来存放CPU暂时不用的程序和数据。磁盘是辅助存储器的主流，但半导体盘（〖=H〗固态盘〖=0〗）已能实现磁盘的功能，并已在一些应用领域取代了磁盘。从功能上看半导体盘也可由电荷耦合器件(CCD)存储器实现，但从容量、速度和成本等因素综合考虑，则宜采用由MOS动态存储器(DRAM)或快可擦编程只读存储器构成。缓冲存储器用于在两个不同工作速度的部件之间交换信息过程中起缓冲作用。高速缓冲存储器是一种容量较小、速度很高的存储器，是为了克服主存储器与CPU在数据传输速度上的不匹配而设置的，通常采用双极型半导体存储器芯片来制作。磁盘缓冲存储器是为克服主存储器与磁盘存储器之间数据传输速度的不匹配而设置，利用磁盘缓存的方法可缩短磁盘平均取数时间，进而提高磁盘系统使用效率。磁盘缓冲存储器通常用MOS DRAM构成。半导体存储器种类很多，就其制造工艺而言可分为〖=W〗双极型半导体存储器〖=0〗和〖=W〗金属氧化物半导体存储器〖=0〗（简称MOS存储器）。双极型半导体存储器以双极型触发器作为存储单元，其中采用晶体管晶体管逻辑存储单元的称为TT’L型存储器，采用射极耦合逻辑存储单元的称为ECL型存储器。MOS存储器以金属氧化物半导体场效应晶体管作为存储单元。MOS存储器的特点是集成度高，工作速度较快，适用于作容量较大的主存储器。电荷耦合器件(CCD)也是金属氧化物半导体存储器件，基于此器件构成的存储器称为电荷耦合器件存储器。它是一种易失性串行存储器，通常为非破坏读出，仅当写入新信息时，才清除原来存储的信息。半导体存储器按存取方式可分为随机存取存储器(RAM)和〖=H〗只读存储器〖=0〗(ROM)两大类。1. 随机存取存储器RAM可以随机地按指定地址从存储单元存取数据，在半导体存储器出现以前，主要是以记忆磁心为存储单元的磁心存储器。1971年美国Intel公司推出1103型1kb MOS DRAM芯片后，半导体存储器开始在一些主要厂家用作计算机的主存储器，到1976年MOS RAM主存储器的每信息位的价格已降到磁心存储器的一半，从此MOS RAM取代了磁心存储器，并一直占据主导地位。RAM还可进一步分为〖=H〗静态随机存取存储器〖=0〗SRAM和〖=H〗动态随机存取存储器〖=0〗DRAM两类。〖=3〗静态随机存取存储器〖=0〗一种使用双稳态锁存电路存储每个信息位的半导体随机存储器。它无须像动态存储器一样周期性刷新信息位，但当没有供电情况下，其保持电荷仍然会丢失，因此在一般意义上它也还是易失性的(参见〖=H〗静态随机存取存储器芯片〖=0〗)。SRAM主要用于二级高速缓存(level2 cache)，或者处理器和主板存储器之间的缓存。SRAM也有许多种，如异步SRAM、同步SRAM、流水式突发SRAM(pipelined burst SRAM)等。〖=3〗动态随机存取存储器〖=0〗利用存储单元的电容内存储电荷的多寡来代表一个二进制比特（bit）是1还是0的半导体存储芯片构成的存储器。由于在现实中电容会有漏电的现象，导致电位差不足而使记忆消失，因此除非电容经常周期性地充电，否则无法确保记忆长存。由于这种需要定时刷新的特性，因此被称为“动态”存储器。DRAM主要用于作计算机的主存储器。基本DRAM存储单元结构(参见〖=H〗动态随机存取存储器芯片〖=0〗)多年来都没有太多的改变，但是DRAM间通信接口一直在变化。包括asynchronous DRAM (异步DRAM)，视频DRAM（VRAM），窗口DRAM（WRAM），快页模式DRAM（FPM DRAM），扩展数据输出DRAM（EDO DRAM），突发DEO DRAM（BEDO DRAM），直接rambus DRAM (DRDRAM)，同步DRAM（SDRAM），双倍速率同步DRAM，四倍速率同步DRAM(DDR2)，八倍速率同步DRAM(DDR3)等。半2. 只读存储器在正常运行中只能随机读取预先存入的信息而不能写入新的内容，也即信息一旦写入就不能更改。即使在断电情况下，ROM仍能长期保存信息内容不变，所以它是一种永久存储器。随着大规模集成电路集成技术的发展，出现了多种大规模集成电路ROM芯片，其中掩膜只读存储器(mask ROM)结构简单，存储信息稳定，可靠性高，能够永久性保存信息。可编程只读存储器(PROM)是由半导体厂家制作“空白”存储阵列（即所有存储单元全部为1，或全部为0状态）出售，用户根据需要可以实现现场编程写入，但只能实现一次编程。可擦编程只读存储器(EPROM)、电可擦编程只读存储器(EEPROM)和快闪可擦编程只读存储器(flash EPROM)等ROM不仅可以现场编程，还可以擦除原存储的信息内容，写入新的信息。目前使用的ROM都是大规模集成电路存储器芯片，当它们装入程序或微程序后就称为固件。半导体存储器自1971年以来发展迅猛。以MOS RAM为例，集成度平均以每三年增加4倍的速度增长，存取周期缩短，逻辑功能加强。在MOS RAM中，DRAM的集成度一直约为SRAM的4倍，因此DRAM多用于大容量存储器中。由于DRAM存储单元利用电容存储电荷的机理保存信息，故使用DRAM时必须定时周期性刷新所存储的信息，以免丢失。SRAM不需要刷新操作，使用简便，在一些容量稍小的存储器中使用较广泛。由于MOS SRAM的速度不断提高，已几乎替代了双极型RAM，促使双极型TTL RAM向更高速度方向发展。半导体存储器由于存储单元阵列及其外围电路可集成在同一芯片上，因而生产过程简单，调试方便，容易实现自动化。它具有可靠性高，结构紧凑，组装密度高，体积小，工作速度快等特点；其缺点是信息易失性，所存信息因断电而消失。在不允许信息消失的应用场合，必须采取断电保护措施。但半导体存储器的综合优势是其他类型存储器不能相比的，在相当长时期内其性能与应用范围还将有较大发展。参考文献郑筠.  MOS存储系统与技术. 北京： 科学出版社，1990（郭志先曹强）
〖=1〗ｂɑｎｄɑｏｔi ｃuｎｃｈuｑi ｘiｎｐｉɑｎ〖=2〗半导体存储器芯片（semiconductor memory chip）〖=0〗用半导体集成电路制造工艺把很多存储单元电路排列成阵列，并和外围电路集成在同一硅晶片上，形成能储存大量数据的集成电路。它广泛用于计算机、通信和家用数字电器等数字系统。在数字系统中，指令和数据（包括声音、图像等信息）都以二进制数的形式出现。每个存储单元通常存放一位二进制数。在半导体存储器（SM）芯片中，通常把存储单元排成由行/列寻址的存储单元矩阵（阵列），存放数字系统工作过程中需暂时或长期保存的二进制数。为了存入和取出需要的数，存储阵列的外围电路包括选取存储单元的行/列地址缓冲和译码驱动电路、读出数据放大电路、写入数据驱动电路、片选和内部时序控制电路等。存储器芯片上集成了存储单元阵列及这些外围电路。这种行列结构的单元阵列给SM芯片带来一个共同的特点，当输入的行地址译码后，只激励一条选中的行线，其他行均为未选状态。与选中行相连的所有存储单元同时将所存的数据输出到相应的列数据缓冲寄存器，再由已输入列地址缓冲的列地址译码后将选中列的数据输出到相应的数据输出引脚；若再读出同一行地址而列地址不同的存储单元数据时，只需输入列地址，或由芯片按设定规则改变列地址，就可快速输出相应的数据。而写入时，在行地址输入后，可将仅列地址不同的数据串，根据列地址的变化写入对应的列数据缓冲中，其他数据缓冲保留行选中时读出的数据；再将数据缓冲中的数写入到选中行对应的单元中。这就是SM芯片发展过程中，为提高数据传送速率而采用的页面方式、同步方式的成组传送和双倍数据速率传输等技术的基础。由于半导体存储器（SM）芯片由大量相同的存储单元组成，电路逻辑结构简单，特别易于大规模集成，成为半导体大规模集成电路产品市场非常重要且不可缺少的部分。在计算机，手持通信和娱乐设备，家用电器等数字系统中得到越来越广泛的应用。不仅有单独的SM芯片，而且在包括CPU在内的系统集成的芯片上也集成了不同类型的存储器电路。从20世纪60年代末以来，随着半导体工艺的发展，SM芯片也经历了由双极型、P/NMOS(P/N金属氧化物半导体)型到互补金属氧化物半导体（CMOS）型SM的发展历程。CMOS工艺由于极低的静态功耗和大规模集成的方便，成为现今SM芯片的主流。基本SM芯片分类如图1所示。根据断电后对数据的保存能力，SM芯片可分为〖=W〗易失性存储器芯片〖=0〗和〖=W〗非易失性存储器芯片〖=0〗两大类。易失性存储器又分为随机存取存储器与非随机存取存储器。非随机存取存储器多以模块方式集成在芯片中，较少以单独芯片方式出现。而且其中的先进先出（FIFO）存储器、后进先出（LIFO）存储器的内核是静态随机存取存储器(RAM)，用作高速缓存的关联存储器，也称按内容寻址存储器（CAM），其存储单元也是SRAM单元。所以易失性存储器芯片一般指随机存取存储器（RAM）芯片（参见〖=H〗随机存取存储器芯片〖=0〗）。它可从任何给定地址的存储单元快速读出或写入数据，但断电后数据消失，再加电后数据不确定。非易失性存储器芯片在断电后所存储的数据仍能保存，再加电后所存数据仍可继续使用，通常指只读存储器（ROM）芯片（参见〖=H〗只读存储器芯片〖=0〗）。ROM在初期通常存储引导程序、基本操作系统和常图1基本半导体存储器芯片分类用的不变的数据。因而将ROM数据的输入称为编程。RAM芯片分为静态RAM（SRAM）芯片（参见〖=H〗静态随机存取存储器芯片〖=0〗）和动态RAM（DRAM）芯片（参见〖=H〗动态随机存取存储器芯片〖=0〗）。SRAM具有简单的接口、快速的地址读出时间和读出写入周期，这些优点使其作为高速缓冲存储器的应用一直延续至今。但SRAM偏大的存储单元面积和功耗的缺点，使SRAM芯片的存储容量比不上后来出现的DRAM芯片。DRAM采用单管存储单元，数据存储在与单管相连的电容中，在读出后数据会被破坏，需重新写入。长时间不读时数据也会因漏电而消失，必须周期性地对所存数据进行刷新（读出/重写），以防止数据消失。这就是称为动态RAM的原因。而SRAM芯片则不需要刷新。随着CPU工作频率的不断提高，对高速缓存和内存速度和容量的要求也不断提升。除工艺技术的进步外，SRAM和DRAM都先后增加时钟输入，以同步地址、命令和数据接口。出现了同步SRAM（SSRAM）和同步DRAM（SDRAM）芯片，而内核仍是非同步的SRAM和DRAM电路。再进一步提高数据传输速率的技术是双倍数据速率（DDR），即相对于输入时钟，其上升和下降边沿都是接收数据的时钟。这样，在突发传送时，数据的传送速率是芯片输入时钟频率的二倍。此外，四倍数据速率（QDR）SSRAM将数据输入端口和数据输出端口分开，利用流水线操作交替输入读出命令及地址和写入命令及地址。读出数据和写入数据可分别以双倍数据速率从各自的端口输入和输出。这样，芯片的最大数据输出速率可达时钟频率的四倍。非易失性存储器中的只读存储器（ROM）芯片分为不可擦除ROM芯片和可擦除ROM芯片两种。掩膜型ROM芯片和熔丝型可编程ROM（PROM）芯片（参见〖=H〗可编程只读存储器芯片〖=0〗）是最初使用的不可擦除ROM芯片。最先应用的可擦除可编程ROM（EPROM）芯片是紫外光可擦编程ROM（UVEPROM）芯片，简称EPROM芯片。EPROM芯片用紫外线擦除整个芯片所存数据，然后重新写入所需的数据。之后出现的电可擦除可编程ROM（EEPROM）芯片(参见〖=H〗电可擦编程只读存储器芯片〖=0〗)用高电压实现擦除和写入，可实现在线擦除和编程。后来开发的技术可实现存储块或全芯片擦除，这就是快闪（快擦除）EPROM（Flash EPROM）芯片（参见〖=H〗快可擦编程只读存储器芯片〖=0〗），简称快闪存储器或闪存芯片。根据接口和内部组织的不同，闪存芯片又分为NOR和NAND两种类型。NOR闪存芯片读出速度快，但存储单元面积大，不适合大容量集成。而NAND闪存芯片读出速度慢，但存储单元面积小，适合大容量集成。与RAM不同，EEPROM（包括NOR和NAND闪存）的擦除/写入次数是有限制的，一般为105或106次。写入数据的保存时间可达10年。而且写入前要先擦除，写入时间和擦除时间都偏长，特别是擦除时间更长。因而不能作普通RAM使用。为了满足客户/市场的需要，将满足客户特殊需要的外围电路与所需的核心SM电路集成在同一芯片上，形成了一些专门的存储器芯片。例如伪静态RAM芯片（或称为单管RAM或Ut RAM芯片）就是单管单元DRAM的内核和SRAM的接口，再加上SRAM与DRAM的接口转换和DRAM的时序控制，集成在同一芯片而成。目的在利用SRAM接口的方便性和DRAM易于大规模集成与成本低的优点。但随着技术的发展Ut RAM芯片现已很少单独应用。又如OneNAND芯片具有NOR闪存的接口和速度和NAND闪存的容量，就是在NAND闪存芯片上又嵌入集成了接口转换时序控制、小容量SRAM数据缓存和出错校验电路。可将原来存程序的NOR闪存芯片和存数据的NAND闪存芯片合为一特殊的NAND闪存芯片，用于要求体积小的手持/移动设备上。用多芯片封装（MCP，参见〖=H〗封装内系统〖=0〗）也可形成一些专门的存储器芯片，以减小封装尺寸（例如Ut RAM NOR闪存，NAND DDR2等），适应手持设备限制体积的要求或扩大存储容量，例如由2/4/8片16Gb/片封装成32/64/128Gb的芯片，即多芯片的DDP/QDP/ODP方式，以满足大容量多媒体存储卡和固态硬盘的需求。总的来说半导体存储器芯片向更大容量、更快速度、更多功能和更低功耗方向发展。为此随着工艺设计尺寸的不断缩小，MOS管和存储单元的面积也不断减少。这为加大容量，提高速度，集成更多的功能创造了条件。同时允许的工作电压也不断降低（由初期的5V降到现在的3.3/2.5/1.8/1.5/1.35V），功耗也可降低。为对这些基本的SM芯片的容量和时间参数与应用的关系有一个概念，用表1举例说明。参考文献1. Sharma A K. 先进半导体存储器——结构、设计与应用. 曾莹,等译.   北京： 电子工业出版社,20052. 桑野雅彦.  存储器IC的应用技巧. 王庆,译.  北京: 科学出版社, 20063. http://www.samsung.com/Products/Semiconductor（孙祖希）表1基本半导体存储器芯片的参数和应用实例SM芯片名称〖〗QDRII SSRAM〖〗DDR3 SDRAM〖〗NOR闪存〖〗NAND闪存典型容量〖〗1M×36b〖〗2Gb〖〗4M×16b〖〗(256M×16b) 16MB ECC时钟周期〖〗4.0ns〖〗1.5ns〖〗读周期70ns min〖〗读周期42ns min行地址读出时间/随机读出周期〖〗4.45ns/8ns〖〗27ns/48ns〖〗70ns/70ns〖〗随机读60μs max突发方式数据读出时间/读出周期〖〗0.45ns/2.0ns〖〗数据输出速率1333Mb/s〖〗70ns/70ns〖〗顺序访问42ns突发方式写入时间〖〗突发方式写命令周期8ns/4字〖〗数据输入速率1333Mb/s〖〗字编程14μs块擦除0.7s〖〗页面编程930μs块擦除16ms max工作电源〖〗1.8/1.5V〖〗1.5/1.35V〖〗5~1.8V〖〗3.3/1.8V主要应用〖〗高速缓存〖〗主内存〖〗系统启动和基本操作系统〖〗断电后需保存的大量数据和程序〖=1〗bɑn jiɑndu xuexi〖=2〗半监督学习(semisupervised learning)〖=0〗研究如何综合利用有标记样本和未标记样本的〖=H〗机器学习〖=0〗理论、模型与方法。机器学习算法都有输入和输出(例如分类问题输入就是数据特征，输出就是数据标签)，其目的就是学习一个从输入到输出的映射函数。半监督学习研究如何在已知数据的输入和其中一部分数据的输出的情况下有效准确地学习映射函数。根据映射函数的类型，半监督学习又可分为直推(transduction)和归纳(induction)，其中直推设置下的半监督学习往往只能预测已知输入样本的输出，而不能学习具体的映射函数的形式，因而这类算法往往不具有拓展性。而归纳设置下的半监督学习能够得到映射函数的具体形式，因而具有更好的拓展性，但是具体算法也更加复杂。传统的机器学习算法包含监督学习和非监督学习两大类。其中监督学习假设学习映射函数时已知所有输入数据的对应输出，而其目的就是学习一个具体的映射函数。非监督学习（参见〖=H〗非监督学习〖=0〗）假设仅仅已知输入数据，而没有任何输出的信息，其目的是从这些输入数据中学习有意义的输出。监督学习和非监督学习都有着各自的优势和局限性。监督学习由于有相应的输出监督信息，使得学习到的结果更加准确可靠，但是得到这些监督信息往往需要请相关领域专家标注，这就需要花费人力财力。相反，非监督学习不需要任何的监督信息，这也使得学习到的结果往往不可靠。而半监督学习则综合了以上两种学习算法，它往往只需要一小部分输入数据的输出，却能够得到与监督学习相当甚至更好的学习结果。迄今为止，学者们已经提出了很多种半监督学习的算法，例如基于产生式模型的算法，低密度分离，以及基于图的算法等。半监督学习中也还有很多有争论的问题，例如没有监督信息的样本究竟什么时候会有帮助，以及算法的推广性能如何等。参考文献1. Chapelle O, Schlkopf  B, Zien A. Semisupervised learning. MIT Press. 20062. Zhu X, Goldberg A B. Introduction to semisupervised learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 2009, 3(1):  1130（王飞张长水）
〖=1〗ｂɑｎ ｊｉegoｕｈｕɑ ｓｈuｊu〖=2〗半结构化数据(semistructured data)〖=0〗介于完全结构化数据（如〖=H〗关系数据库〖=0〗与〖=H〗面向对象数据库〖=0〗中的数据）和完全无结构数据（如音像数据与文本数据）之间的数据。和关系数据不同，半结构化数据一般是自描述的数据，它的模式不是统一的、预先给定的，而往往是不规则且经常变动的，并且它的数据和模式是混合存放的。这种特点使得半结构化数据有很大的灵活性，能够满足不同应用、不同企业之间交换信息的需要，但同时也给半结构化数据存储、查询处理带来了很大困难。目前得到广泛应用的XML数据就是半结构化数据。对象交换模型（object exchange model，OEM）可以用来描述半结构化数据。它最初在斯坦福大学的异构数据集成系统TSIMMIS中引入。OEM是一个简单的、自描述的、嵌套的对象模型。每个对象具有唯一的对象标识。对象分为原子对象和复合对象两种。原子对象包含一个原子类型的值，如整数、实数、字符串等。复合对象的值是有序对〈标记，子对象标识〉的集合，每一个标记是对象与子对象之间关系的描述。从结构上看，OEM是一个带标记的有向图，节点表示对象，边表示对象间的关系。每个OEM图都有一个根节点，从根节点至任意节点都是可达的。图1是对象交换模型的一个简单示例。它描述了某个餐饮业的结构。图中每个对象都有一个整型的对象标识，根对象包括三个子对象，两个餐馆和一个酒吧。每个餐馆都是复合对象，而酒吧是一个原子对象，字符串“酒吧1”是该对象的值。图1对象交换模型示例半结构化数据管理中查询处理需要支持从现有的半结构化数据中定位特定部分，或者将一种类型的半结构化数据转换为另一种类型的半结构数据。为了提高半结构化数据查询的效率，通常需要建立面向数值或者面向结构关系的索引。数据模式抽取和增强是半结构化数据管理中一个重要操作。为了有效地管理大量存在的无结构数据和半结构化数据，我们可以抽取或增强其模式信息，从而支持更加丰富的查询类型和精确的查询处理，实现数据优化存储，支持数据有效性验证等。在半结构化数据存储过程中，一方面需要保持半结构化数据的结构信息，支持结构查询处理；另一