科学网—liuyu2205的博文 - 第29页

设为首页收藏本站

开启辅助访问切换到宽版

科学网 › 我的中心 › 博文 › liuyu2205的博文

liuyu2205

https://wap.sciencenet.cn/?2322490

在中法文化之间流连| 不确定性问题和算法讨论| 智能哲学| NP理论| 非经典逻辑与中国传统逻辑| 英语博文| 图灵论著专研与精译工作群| AI伦理与社会群| 周剑铭论中国思想与中西文化系列文章| 在法国教逻辑课| 教学中的文化视角| 师徒对话| Paul Jorion的书译文| 解读哥德尔不完全性定理| 波普尔的《科学发现的逻辑》| 《易经》学习| 系统思维|

关于NP讨论中的论域问题（1）: 热度 2 柳渝 2015-5-14 18:03; 1. 逻辑运算（真值表关系）与图灵机计算（可计算函数）具有不同的性质，但这两种不同的性质总是被混淆，它们的内涵更是被混乱。 2. 图灵机是普遍意义上的计算机模型，图灵机以抽象的物理结构表现了作为算法的“机械步骤”的结构和过程。图灵以图灵机的形式严格地表达了“不可判定问题”，这是图灵当时工作的主要目的，但 ...; 个人分类: 不确定性问题和算法讨论|3453 次阅读|10 个评论热度 2

NP二个流行定义与“白马非马”: 热度 2 柳渝 2015-5-8 14:06; 世纪难题“P versus NP”，通俗地讲，P代表计算机易解决的一类问题，NP代表计算机难解决的一类问题，“P versus NP”就是问：NP这类困难的问题到底能否被计算机有效解决（NP＝P）？与此问题相关的研究，就形成了计算复杂性理论。库克（Cook）1971年的那篇论文《The Complexity of Theorem Proving Procedures》，奠定了 ...; 个人分类: 不确定性问题和算法讨论|4225 次阅读|3 个评论热度 2

为什么还要讲“没用的NDTM”？（2）: 热度 2 柳渝 2015-5-3 14:58; 我继续和同事对话：同事：我认为，取消NDTM不会影响NP完备理论，只需将NP理论中涉及到用NDTM定义NP的陈述，改成用DTM在多项式时间内可验证的问题类，就可以了。柳渝：那么，试看2000年柯克（Cook）为克雷数学研究所（CMI）介绍“P versus NP”所写的文章（ http://www.claymath.org/sites/default/files/pvsnp.pdf ） ...; 个人分类: 不确定性问题和算法讨论|3239 次阅读|3 个评论热度 2

为什么还要讲“没用的NDTM”？（1）: 热度 1 柳渝 2015-5-2 14:58; 最近我与一个工作在NP问题实际求解前沿的同事对话：同事：我认为，如果取消了“不确定性图灵机（NonDeterministic Turing Machine NDTM）”这个概念，把NP定义成“确定性图灵机（Deterministic Turing Machine DTM）”在多项式时间内可验证的问题类，不会影响NP问题的实际求解，对NP完备理论也不会产生影响。柳渝：此 ...; 个人分类: 不确定性问题和算法讨论|3809 次阅读|1 个评论热度 1

“问题”的系统观（整体观）: 热度 1 柳渝 2015-4-21 10:08; 一，“问题”的中西文字源 1，英语（ http://www.etymonline.com/index.php?term=problem ） “problem”，源自希腊语：proballo = pro (in face of) + ballo (to throw)，指橫在起点与目标之间的“障礙”。另外，“人问问题”又是无法避免的事实，于是，又有另一词“question”来表达，“question”源自中世纪的“审 ...; 个人分类: 不确定性问题和算法讨论|3573 次阅读|2 个评论热度 1

不确定性图灵机（NDTM）与“不确定性”: 热度 7 柳渝 2015-4-14 13:28; 在NP完备理论（NP－completeness theory）中，把“不确定性图灵机”（NonDeterministic Turing Machine，NDTM）因一个问题存在多算法或多解而具有的“多选择”，当作了“不确定性问题（Nondeterministic Problem）”的“不确定性”，遂有用NDTM定义NP一说，这种观点的理论表达就是教科书中的流行概念：NP＝不确定性多项式 ...; 个人分类: 不确定性问题和算法讨论|8107 次阅读|28 个评论热度 7

NP理论中几个术语的约定: 热度 5 柳渝 2015-4-10 10:24; 于博文（ http://blog.sciencenet.cn/blog-2322490-874183.html ），我们分析了NP二个定义涉及到二个内涵完全不同的“非确定型图灵机”，为了方便表达，我们提议约定几个术语的中文、英文及缩写：一，术语的约定 TM (Turing Machine) = 图灵机 DTM (Deterministic Turing Machine) = 确定性图灵机 NTM (Non Turing ...; 个人分类: 不确定性问题和算法讨论|4839 次阅读|12 个评论热度 5

参详P与NP的二个实例: 热度 2 柳渝 2015-3-31 11:00; P和NP指二个问题类。NP存在着二个流行定义（见Sipser的书“Introduction to the Theory of Computation”，Section 7.3［1］）： 1，基于验证的定义：NP是“确定型图灵机”在多项式时间内可验证的语言类； 2，基于判定的定义：NP是“非确定型图灵机”在多项式时间内可接受的语言类。于博文中（ http://blog.sciencenet ...; 个人分类: 不确定性问题和算法讨论|4587 次阅读|16 个评论热度 2

解读NDTM的概念偷换－NP定义中二个不同的NDTM: 热度 6 柳渝 2015-3-13 15:32; 在计算复杂性理论中，NP是用“非确定型图灵机（nondeterministic Turing machine，NDTM）”来定义的，从“语言”的角度，存在着二个流行的定义（见 : Michael Sipser, Introduction to the Theory of Computation, Section 7.3）： 1，基于验证的定义：NP是“确定型图灵机”在多项式时间内可验证的语言类； 2，基于判 ...; 个人分类: 不确定性问题和算法讨论|5425 次阅读|25 个评论热度 6

在贡比涅大学作报告: 热度 3 柳渝 2015-2-5 12:23; 周一（2015/2/2）到贡比涅大学（Université de Technologie de Compiègne）作报告去了。法国高等教育体制有别于欧洲及美国，分：大学校（Grandes Ecoles）和公立综合大学(Université)。“公立综合大学”属于大众化教育机构，在校生占全国大学生的80%-90%，学生没有入学考试，通过高中毕业会考，就有资格就读，但一、 ...; 个人分类: 不确定性问题和算法讨论|4580 次阅读|8 个评论热度 3

1 ... 22 23 24 25 26 27 282930 下一页

会议

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-4-27 14:14

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部