期待大神的出现,NP完全问题

2010年8月12日 施可 3 条评论

日前,HP科学家Vinay Deolalikar宣称其已经证明了P!=NP,目前正在接受其他计算机理论科学家的确认。

我彻底无语了,如果他的证明是真实的话,他的意义不仅仅是解决了人类数学史上七大难题中最难的一道。诺贝尔数学奖,图灵奖更不在话下,更主要的是,从理论基础上解决了很多计算机学科无法盖棺定论的问题。

鄙人有幸得到论文全文,无奈洋文不行,修行不深,粗读一遍,不知所云。

首先,我们来了解几个常识性的问题。
1.数学七大难题
美国麻省Clay数学研究所悬赏100万美元用于解决人类历史上的七大数学难题
P问题与NP问题
Hodge猜想
Poincare猜想
Riemann假设
Yang-Mills存在性和质量缺口
Navier-Stokes方程的存在性与光滑性
Birch和Swinnerton-Dyer猜想。
2.什么是P问题,NP问题
P问题,通俗地讲一个问题可以找到一个可以在多项式的时间内可以解决的算法的问题。
NP问题,是指可以在多项式时间内验证一个解的问题。
这些都属于理论计算机科学的问题,理解起来很麻烦,证明起来就更麻烦了。

好了,理解了这几个常识,我们就来分析一下,为什么要解决P问题和NP问题关系的问题(好绕啊)。
我举一个最通俗的例子。
对于一个加密算法,我们有一个输入,一个输出,一个映射关系,这其中一般情况下是一个输入对应一个或多个输出的问题(我说的是一般情况下)。
那么,我们在多项式时间内根据输入和输出找到映射关系就属于P问题。
而我们能够在多项式时间内根据输出得到一个输入,属于一个NP问题。
好了,P问题是否等于NP问题的意义就在于,如果我能够在多项式时间内根据一个密文得到明文,那么是否意味着我可以在多项式时间内找到加密算法。
如果这个问题可以成立,那就可以推出,我们今天大部分的加密算法(因为今天我们的大部分算法可以证明是NP问题),是在多项式时间内可以找到加密算法的,这是一件很恐怖的事情。

不过庆幸的是,我们目前的大部分的猜测都是P不等于NP。
而且我们目前很多理论的推测都是基于P不等于NP的前提的。

为什么,我们会认为P不等于NP呢?
这里我们要引入另一个概念,NPC问题,也称作NP完全问题。
为了说明NPC问题,我们引入一个新的概念“约化”。
一个问题A可以约化成问题B的含义是:可以用问题B的解法来解答问题A。
问题A可以约化成问题B的一个直观的条件就是问题B的时间复杂度高于等于问题A
约化的准确的概念,应该是问题A的输入经过一定的规则处理可以转化成问题B的输入,并得到正确的结果。
至此,我们可以给我NPC问题的概念:1.他是一个NP问题。2.所以的NP问题都可以约化成他。
而找到一个NPC问题的条件是:

那么我们我谈谈P问题和NP问题的关系。
既然我们认为所有的NP问题都可以约化成NPC问题,那么我们就可以把问题简化成寻找NPC问题是否存在一个多项式解答的问题。
如果我们能够找到NPC问题的多项式解答,那么P问题就等于NP问题了。
但是显然,这是不可能的,虽然我们无法证明他是不可能的。
这也就是为什么能证明出这个问题的人会称之曰大神。

呜呼,说得这么多,我自己都快绕糊涂了。。。
如果你发现写得不对的地方,一定要指出来,谢谢。
从即日起,继续膜拜大神的著作。

分类: 胡言乱语 标签:

GTD, What Why and How

2010年7月14日 施可 1 条评论

What

what is GTD, GTD means “Get Things Done.”
我们可以理解为一种管理时间的理念。
下图是一个通用的GTD的流程图。

GTD的核心理念在于只有将你心中所想的所有的事情都写下来并且安排好下一步的计划,你才能够心无挂念,全力以赴地做好目前的工作,提高效率。

Why

Why GTD?
1.因为我们需要在有限的时间内做更多的时间
2.克服人性懒惰的一面
3.自我约束的方式
more…

How

其实GTD只是一个理念,而GTD的事情,我们一直在做。
比如便签纸,用纸和笔记录需要做的事情。

又比如outlook的待办事项等等

在软件开发项目中,我们可能会遇到很多用于task跟踪的工具,比如经典的JIRA,其实从JIRA更多的应该理解成是一种缺陷跟踪工具,用于和客户的交流。

比如TFS.

我在工作之外的时候,用自己开发的一套软件来实现GTD。
显示效果大致如下
根据每个任务的不同状态用不同的颜色来标出
每个任务的状态大致可分为:新创建,正在进行,已完成,已关闭。

创建一个新的任务

同时,还准备一个windows service,每天会自动检测当天需要完成的任务,以邮件的形式发送,方便查看和跟踪

不管怎么说,GTD只是一种理念,而执行力还是要靠自我约束

分类: 胡言乱语 标签:

《为什么你应该(从现在开始就)写博客》读后感

2010年7月11日 施可 5 条评论

原文地址:http://blog.csdn.net/pongba/archive/2009/02/17/3896311.aspx

我记得小学的时候,我们被老师一次次地逼着写所谓的读后感或者观后感

所谓,观电影《邱少云》后感,《地道战》观后感,等等

我记得,这样的观后感给我儿时的记忆留下了不好的一笔

因为,我。。。真的真的没有感可写。。。

长大后,会写一些读书笔记,但也只是很少一些 很有感触的文章

而刘未鹏的这篇《为什么你应该(从现在开始就)写博客》真的触动了我,让我不得不想写点东西记录此刻的感想

我一直认为自己是一个喜欢思考的人

大到国际局势,小到领导的一个眼神,等等

但是这样的思考,一般也都是想想而已,而很难成为一个有逻辑性的有指导意义的结论

所以,每当回首的时候,总觉得过去是一篇空白

又比如说是技术,总是认为自己有很多很好的创意和想法,但是却总是自生自灭

用博客的形式来记录下你有价值的思考,会带来很多好处,却没有任何明显的坏处

Barbara小姐曾经说过我是一个不愿意轻易和别人交流真实想法的人

而这样的坏处就是无法知道和自己志同道合的人在何处

前进的路上一直就是一个人在黑夜里摸索

呵呵,虚心接受&道谢

写博能够交到很多志同道合的朋友

写的过程其实就是和内心深处最真实的自己交流的过程

我们每天都花了很多时间在别人以及和别人交流上

但是很多时候忽略了和自己的交流

书写是为了更好的思考

从技术的角度来说,一个长期的大量原创的博客就是最好的简历

纸质或者电子简历上毋庸多谢,基本信息然后贴上你的博客地址

懂技术的人,从你写的文字中,已基本知道你的水平

说不定,他还一直在订阅你的博客呢

至少你会因此而结识更多的人,你的博客价值越高,你结识的人就越牛,跟牛人交流又会让你的眼界得到极大的开阔,打开一扇又一扇你原本不知道的门,于是你就变得更牛… 这是一个良性循环

几个推荐:

www.csdn.net,号称是国内最大的技术社区

www.cnblogs.com,国内dotnet平台的高手聚集地

www.asp.net,微软dotnet官方论坛,一堆热心肠的高手的聚集地,(English Only)

最后,推荐博客订阅工具:http://xianguo.com/,鲜果,不多说,用了都说好,其实Google reader也不错,只是由于众所周知的原因,访问可能会出现问题

分类: 胡言乱语 标签:

“天安号”事件之我见

2010年7月10日 施可 没有评论

今天下午刚刚得到消息,联合国关于“天安号”事件发表官方声明
声明中未提到对朝鲜的谴责和所谓的制裁
而只是希望有关各方保持克制以及对遇难者的哀悼云云

据此,鄙人认为“天安号”事件就此告一段落。

关于真相

关于“天安号”的真相,我想估计只有当事者知道,其他全是猜测
好吧,那就让我们猜测一下
搬开脚趾数数,可能的情况只有那么几种
1)朝鲜有意为之
目前美朝日等相关国家均持此观点,认为此事为朝鲜所为。
鄙人认为,这种情况的可能性很大,但是,如果事实果真如此,那么金二的脑袋一定被驴踢了
从实力上说,朝鲜现在根本不具备和美韩联盟对抗的实力,所以这样的行为毫无意义
唯一说得过去的解释就是,朝鲜希望借此看看美朝及其他势力的反应
但是这个冒险未免太刺激了些
而且,从目前情况来看,韩国口口声声说事情是朝鲜干的
但是一直没拿出有绝对说服力的直接证据
按照法律无罪推论的原则,我们目前无法认定一定是朝鲜所为
2)韩国阴谋策划
老实说,如果是这样,那李明博的脑袋一定被驴踢了
因为,这样的事情只会是赔了夫人又折兵。
目前看来可能性不大,也没看到这样的事件会给韩国带来任何好处
3)意外事件
朝韩双方军舰意外碰撞
有这种可能,但是,意外碰撞后,朝鲜死不承认,不太合符情理。

综上所述,各种可能都是存在的,又都没有绝对说服力,姑且认定为悬案

中美博弈

“天安号”事件发生后,主要涉及方包括:直接涉及方:朝鲜和韩国,间接涉及方:中国美国和日本
从某种意义上来说,日本在此事中的牵扯利益不大,因为黄海领域对日本的利益影响不大。
那么从宏观上来讲,此事可以认定为中美的一次博弈
事情发生后,美方首先保持沉默,中方要求有关各方保持克制
在韩国公布调查结果,认定是朝鲜所为是,美方开始谴责朝鲜并对中方施加压力,要求中方认可韩国调查结果,共同谴责朝鲜,但是中方仍然要求有关各方保持理智
今日,美朝双方宣布将在黄海的公海领域举行联合军事演习,其实质,一方面是给予朝鲜以震慑,另一方面就是给中国施加压力,要求其承认韩方调查结果
但是,中国却用一次例行实弹演练予以还击。

鄙人认为,在联合国发表官方声明后,美韩军演会取消或者在黄海领域外举行。

各方利益

如果要我评价,整个事件中的失败者,那当韩国莫属
1)人员和武器装备的损失,天安号的船员的性命以及武器装备
2)李明博在事件发生后,第一时间宣布“发誓必将采取行动”,不过此事最终不了了之,因为鄙人认为其后台老板不支持
3)美国进一步巩固了其在韩国驻军的必要性,鄙人认为,对于一个主权国家,这是莫大的耻辱
4)激起朝鲜更为严重的民愤,朝韩关系恶化,韩国生存环境变得更为险恶

分类: 胡言乱语 标签:

Temporary ASP.Net Files探究

2010年7月4日 施可 没有评论

了解.net平台的兄弟都知道,.net也是采用动态编译的
也就是说我们常说的build生成的dll只是中间代码
而在web第一次请求的时候才是真正意义上的编译生成二进制代码
这也就是为什么刚编译完第一次打开web页面的时候会比较慢的原因

好了,闲话少扯
今天一个兄弟问我,为什么他开发环境打开编译后的页面越来越慢
下面是我的解决方案:
1.关掉inetinfo.exe的进程
2.关掉aspnet_wp.exe
3.关掉打开的visual studio
4.清掉%SystemRoot%\Microsoft.NET\Framework\versionNumber\Temporary ASP.NET Files文件夹下的所有文件。
%SystemRoot%指的是你的系统windows文件夹的路径,一般默认的是C:\WINDOWS\
整个清除过程可能会比较慢,具体时间和目录下文件夹大小有关。
清除完之后,第一次打开还会比较慢,但是以后编译后的打开会快一些。

下面是详细的解释
当我们第一次请求的时候,也就是正式编译的时候,dotnet会写一些临时文件在这个文件夹下。
这个本人验证过,在第一次请求的时候,去关注文件夹的变化。
对于部署在server已经上线的Web Application是不会存在这样的问题的。
而在我们的开发环境下,由于经常要build,经常第一次请求,所以时间久了,这个文件夹就会变得很大。
像我现在在做的项目,源文件和目标文件的大小有4G,那么,写到这个文件夹里的文件就有上百兆。
我们可以去关注下,在选择“附近到进程”操作之后加载的程序集,就是在这个路径下。

不知道有的兄弟,会不会想,要经常手动去清这些文件,岂不是很麻烦?
哈哈,想省事的兄弟,可以写个批处理程序来做这个操作。
这里,我想介绍另一种方法来提升速度。
我们都知道,在我们可以控制的存储单元中,内存的访问速度是最快的。
如果,我们可以把这些临时文件放到内存中,就会成倍地提高速度。

1.安装RamDisk
2.安装好后,设置Debug 输出的Temp 目录为内存盘的path, 不再使用原来预置的 Temporary ASP.NET Files,只需要通过修改 Web.Config 文件中的
  <compilcation debug=”true”> 一般情况是这样的
修改为   <compilcation debug=”true” tempDirectory=”R:\”>
保留原来属性,新加一个 tempDirectory 指定内存盘的path
实践检验,可以花费时间的差距可以到一个数量级。
扩展阅读:http://msdn.microsoft.com/en-us/library/ms366723.aspx

分类: .net技术 标签: