Packing问题的计算复杂性 被引量：6

1

作者 陈传波 何大华 《计算机工程与科学》 CSCD 2005年第3期46-48,共3页

本文讨论了离散模型与连续问题的关系以及图灵机的计算能力,在此基础上扩充了问题及 NP完全问题的定义,根据解空间的拓扑结构特点将NP完全的Packing问题分为三类,并对多边形 Packing问题进行了有益的探讨。这对设计Packing问题的求解算... 本文讨论了离散模型与连续问题的关系以及图灵机的计算能力,在此基础上扩充了问题及 NP完全问题的定义,根据解空间的拓扑结构特点将NP完全的Packing问题分为三类,并对多边形 Packing问题进行了有益的探讨。这对设计Packing问题的求解算法具有借鉴意义。 展开更多

关键词 PACKING问题 计算复杂性 离散模型 可计算性理论 计算机

下载PDF 职称材料

上下文无关语言上的递归函数——I.CFPRF及CFRF的定义 被引量：4

2

作者 董韫美 《中国科学（E辑）》 CSCD 北大核心 2002年第1期103-115,共13页

建立上下文无关语言（CFL）上的递归函数理论,在CFL上定义了函数类CFRF和它的真子类CFPRF,它们可用来十分直接地表述非数值加工算法.事实上它们分别就是上下文无关语言上的偏递归函数和原始递归函数.提出了证明CFPRF函数性质的结构归纳... 建立上下文无关语言（CFL）上的递归函数理论,在CFL上定义了函数类CFRF和它的真子类CFPRF,它们可用来十分直接地表述非数值加工算法.事实上它们分别就是上下文无关语言上的偏递归函数和原始递归函数.提出了证明CFPRF函数性质的结构归纳法,给出一种枚举CFL句子的方法,定义了极小算子.基于CFL句子枚举,提出了极小算子的求值方法.最后,讨论了以CFRF为理论基础的可执行规约语言的设计和实现原则. 展开更多

关键词 CFRF CFPRF 上下文无关语言 递归函数 CFL分层枚举 结构归纳法 形式文法 可计算性理论

原文传递

单向函数与对称密码体制 被引量：2

3

作者 童亚拉 《河南理工大学学报（自然科学版）》 CAS 2006年第4期338-340,共3页

可靠的密码学是建立在数学和形式化的计算机科学产生的结论之上的,本文从计算理论的角度阐述了构建对称密码体制所需的数学背景:算法复杂性与问题复杂性的关系;NP问题与密码学的关系;密钥长度与密码安全的关系.从保长和置换的概念入手,... 可靠的密码学是建立在数学和形式化的计算机科学产生的结论之上的,本文从计算理论的角度阐述了构建对称密码体制所需的数学背景:算法复杂性与问题复杂性的关系;NP问题与密码学的关系;密钥长度与密码安全的关系.从保长和置换的概念入手,说明了构造对称密码体制的理论基础———单向置换和单向函数,并以计算机口令系统为实例说明了如何构造对称密码系统. 展开更多

关键词 复杂性 可计算性理论 密钥 单向置换 单向函数 对称密码体制

下载PDF 职称材料

进化计算的可计算性

4

作者 刘健勤 魏敏洁 《计算技术与自动化》 1998年第3期1-2,共2页

本文针对进化计算的进化控制特点，提出了一种进化程度的描述方式，并讨论了进化计算的可计算性。该项工作有助于进化计算形式化理论的建立和应用系统的开发。

关键词 进化计算 可计算性理论 计算机

下载PDF 职称材料

关于实数的可计算性 被引量：2

5

作者 陈传波 何大华 《微电子学与计算机》 CSCD 北大核心 2003年第5期68-70,共3页

给出了图灵机和可计算数之间的关系和可计算数的若干性质,提出了半可计算数的概念,并在此基础上结合集合的算术层次对实数集进行了算术分层,这一思想对于从可计算性角度理解实数具有借鉴意义。

关键词 可计算性理论 实数 图灵机 递归可枚举 编码

下载PDF 职称材料

李昂生：从图灵计算到网络科学 解40余年可计算性理论之悬疑

6

作者 李玉 郑静 《科技中国》 2012年第11期88-89,共2页

20世纪60年代，加拿大学者Lachlan提出计算可枚举图灵度结构理论的主子度问题。40多年来，世界各国的众多科研人员、专家学者试图挑战这一难题，但却没能成功。 如今，这一重大学术难题在中国科学院软件研究所、计算机科学国家重点实... 20世纪60年代，加拿大学者Lachlan提出计算可枚举图灵度结构理论的主子度问题。40多年来，世界各国的众多科研人员、专家学者试图挑战这一难题，但却没能成功。 如今，这一重大学术难题在中国科学院软件研究所、计算机科学国家重点实验室研究员李昂生这里找到了答案。 展开更多

关键词 可计算性理论 图灵度 网络科学 中国科学院软件研究所 国家重点实验室 专家学者 计算机科学 结构理论

下载PDF 职称材料

一个高的钻石定理(英文)

7

作者 李昂生 杨东屏 《软件学报》 EI CSCD 北大核心 2000年第1期23-39,共17页

证明存在一个保持最大元 1的可计算枚举高度的钻石格 .

关键词 可计算性理论 可计算枚举度 钻石定理

下载PDF 职称材料

P与NP问题

8

作者 StephenCook 杨东屏 《数学译林》 2001年第1期5-14,共10页

关键词 P问题 NP问题 图灵机 Turing机 多项式时间类 可计算性理论

原文传递

图灵:计算理论的奠基人

9

《计算机教育》 2004年第4期54-56,共3页

广义的信息理论包计算理论和通信理论两大部分.计算理论指经典的可计算性理论,代表人物是英国科学家图灵;通信理论指经典的信息论,代表人物是美国科学家香农.

关键词 可计算性理论 图灵 图灵机模型 图灵测试 机器智能

下载PDF 职称材料

Conference Report on Modern Developments in Computability Theory and Its Applications

10

《逻辑学研究》 CSSCI 2012年第3期82-86,共5页

关键词 可计算性理论 中国 技术合作 科学研究工作

下载PDF 职称材料

关于Contor配对函数中左右函数的相互表示及其推广

11

作者 谢云 《长江大学学报（社会科学版）》 1985年第2期32-34,共3页

配对函数是讨论递归函数的重要工具。通过配对函数,可以把每个多元数组都对应一个相应的数,亦即可以给每个多元数组一个相应的编号;反之,如果知道了某个多元数组的编号,也可以求出这个数组,亦即可以求出这个数组中的每个数来。因此,有... 配对函数是讨论递归函数的重要工具。通过配对函数,可以把每个多元数组都对应一个相应的数,亦即可以给每个多元数组一个相应的编号;反之,如果知道了某个多元数组的编号,也可以求出这个数组,亦即可以求出这个数组中的每个数来。因此,有了配对函数就可以把多数元组的性质乃至多元函数的性质转化为一般数的性质或者一元函数的性质来讨论,在得出适当的结论后再化归到多元数组或多元函数中去。更进一步,通过配对函数还可将数理逻辑中所谓“符号行”的计算转化为自然数的计算,“这就是所谓的算术化。 展开更多

关键词 配对函数 Contor 多元函数 算术化 一元函数 递归函数 化归 CANTOR 非负整数 可计算性理论

下载PDF 职称材料