T007520 NPC理论导引

书籍:中国图书大辞典:1949-1992第16册工业技术(下) 更新时间:2018-11-09 13:11:28

出处:按学科分类—综合性图书 湖北人民出版社《中国图书大辞典:1949-1992第16册工业技术(下)》第794页(306字)

张泽增着。

贵州人民出版社1989年3月版。15.8万字。主要介绍计算复杂度理论入门知识——NPC理论的基础概念和基础理论。

分5章,第一章主要介绍问题的难易性和复杂度的有关概念,其中图灵机和基于图灵机的复杂度概念,是全书的基础;第二章介绍证明NPC类的方法,主要有限制法、局部替换法与分量设计法;第三章讨论P类与NPC类的分界,并通过举例来讲述证明问题属于P类的方法;第四章讨论对付NPC问题的办法,简要介绍近似算法、概率算法与并行算法;第五章介绍NPC类的结构及进一步的知识,包括CO-NP,强NPC,PSPACE,NPC的相对化等。

为“计算机科学丛书”之一。

分享到: