[算法]P/NP问题

dskongenius 发表于 2007/11/14 0:22:04

　P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay Mathematics Institute, 简称CMI）在千禧年大奖难题中收录。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克(Stephen A. Cook) 和 Leonid Levin 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的（P=NP?）。

P和NP
复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的:

P和NP相等吗?
在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。[1] 对于正确的解答，有一个,000,000美元的奖励。

 [算法]世界七大数学难题　

dskongenius 发表于 2007/11/14 0:13:45

20世纪是数学大发展的一个世纪。数学的许多重大难题得到完满解决， 如费马大定理的证明，有限单群分类工作的完成等， 从而使数学的基本理论得到空前发展。

计算机的出现是20世纪数学发展的重大成就，同时极大推动了数学理论的深化和数学在社会和生产力第一线的直接应用。回首20世纪数学的发展， 数学家们深切感谢20世纪最伟大的数学大师大卫·希尔伯特。希尔伯特在1900年8月8日于巴黎召开的第二届世界数学家大会上的著名演讲中提出了23个数学难题。希尔伯特问题在过去百年中激发数学家的智慧，指引数学前进的方向，其对数学发展的影响和推动是巨大的，无法估量的。

效法希尔伯特， 许多当代世界著名的数学家在过去几年中整理和提出新的数学难题，希冀为新世纪数学的发展指明方向。 这些数学家知名度是高的， 但他们的这项行动并没有引起世界数学界的共同关注。

2000年初美国克雷数学研究所的科学顾问委员会选定了七个“千年大奖问题”，克雷数学研究所的董事会决定建立七百万美元的大奖基金，每个“千年大奖问题”的解决都可获得百万美元的奖励。克雷数学研究所“千年大奖问题”的选定，

 [算法]离散数学图灵机(二)

dskongenius 发表于 2007/11/13 23:37:35

　四、模拟 
1、什么是模拟？ 
什么是模拟？又是一个基本的问题，爱因斯坦说过，越是基本的概念就越是难以刻画
清楚。模拟这个概念就是一个很难说清的问题。 
如果你站在一个朋友面前，冲着他做了一些鬼脸。那么他也会学着你的动作冲你做鬼
脸，那么他就对你进行了模拟。 
很明显，在你和你朋友之间存在着一系列的对应关系：你的手对应他的手，你的眼睛
对应它的眼睛，你的嘴巴对应他的嘴巴……。而且你的手、眼睛、嘴巴做出来的动作也会对
应他的手、眼睛、嘴巴做出来的动作。因而，模拟的关键是对应！如果集合A中的元素可
以完全对应B中的元素，那么A就可以模拟B。 
仍然用你冲你的朋友做鬼脸的例子，假如这次你做出的鬼脸以及动作没有被他立即模
仿而是被他用某种符号语言记录到了日记本上了。比如：“X年X月X日，疯子XX冲我做
了一个鬼脸：他伸出了左手食指放到了右眼下面往下拉他脸上的肉，并且吐出了他长长的舌
头！”。过了N多天后，你的这位朋友掏出了日记本，按照

阅读全文(1607) | 回复(0) | 编辑 | 精华 | 删除

 [算法]离散数学图灵机文章(一)　

dskongenius 发表于 2007/11/13 22:51:59

计算理论可以追溯到1900年，当时著名的大数学家希尔伯特在世纪之交的数学家大会上给
国际数学界提出了著名的23个数学问题。其中第十问题是这样的：存在不存在一种有限的、
机械的步骤能够判断“丢番图方程”是否存在解？这里就提出来了有限的、机械的证明步骤
的问题，用今天的话说就是算法。但在当时，人们还不知道“算法”是什么。实际上，当时
数学领域中已经有很多问题都是跟“算法”密切相关的，因而，科学的 “算法” 定义呼之
欲出。之后到了30年代的时候，终于有两个人分别提出了精确定义算法的方法，一个人是
图灵，一个人是丘奇。而其中图灵提出来的图灵机模型直观形象，于是很快得到了大家的普
遍接受。 
不知道你是否听说过图灵这个名字。可能有些人知道牛顿，知道爱因斯坦，甚至知道冯
诺依曼，但不知道图灵。然而图灵的贡献绝对不亚于这些科学大师。图灵最大的贡献就是把
算法这样一个基本的、深刻的概念用他的图灵机模型讲清楚了。正是因为图灵奠定的理论基
础，人们才有可能发明20世纪以来甚至是人类

阅读全文(2503) | 回复(1) | 编辑 | 精华 | 删除

 [方法总结]两周来的技术总结

dskongenius 发表于 2007/11/13 13:15:17

两周过去了，感觉蛮有收获，现把所用到的技术总结总结： 1.PSO算法： PSO算法，ANN和GA法是三大来源于生物学的算法，又称为进化算法，人工神经网络(ANN)是模拟大脑分析过程的简单数学模型，反向转播算法是最流行的神经网络训练算法。pso和GA是关于最优化问题的，都是产生很多可能的解空间，然后在里面搜索全局最优解。GA具有交叉和变异操作，染色体(chromosomes) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动. 在PSO中, 只有gBest (or lBest) 给出信息给其他的粒子， 这是单向的信息流动. 整个搜索更新过程是跟随当前最优解的过程. 与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解。 2.两种类型的数据集 一种是高维低样本类型，另一种是低维高样本类型，两种类型的处理方法具有相似性，对于前者，可以用MIMST，也就是先用过滤法去掉无关属性和冗余属性，从而减少维数。对于后者，可以先对样本进行层次聚类，然后从每一类选一个代表样本代表这一类进行处理。

阅读全文(4478) | 回复(2) | 编辑 | 精华 | 删除

 [方法总结][推荐]来自MIT人工智能实验室：如何做研究？　

dskongenius 发表于 2007/11/13 11:56:49

  麻省理工学院
人工智能实验室
AI Working Paper 316 1988年10月
来自MIT人工智能实验室：如何做研究？


作者：人工智能实验室全体研究生
编辑：David Chapman
版本：1.3
时间：1988年9月
译者：柳泉波 北京师范大学信息学院2000级博士生

摘要 本文的主旨是解释如何做研究。我们提供的这些建议，对做研究本身（阅读、写作和程序设计），理解研究过程以及开始热爱研究（方法论、选题、选导师和情感因素），都是极具价值的。

Copyright 1987, 1988 作者版权所有

备注：人工智能实验室的Working Papers用于内部交流，包含的信息由于过于初步或者过于详细而无法发表。不像正式论文那样，会列出所有的参考文献。

1. 简介
这是什么？
并没有什么神丹妙药可以保证在研究中取得成功，本文只是列举了一些可能会

阅读全文(1677) | 回复(0) | 编辑 | 精华 | 删除

 [算法]据说是一道李开复出的题目　

dskongenius 发表于 2007/11/12 22:40:58

　据说李开复今年招聘出了一道题目，100个苹果，放在10个篮子里面，问如果有个人要若干个苹果，怎么放才能够保证在不打开篮子的情况下满足他？   思考了一下，感觉这个题目好像来源于8421码，答案很简单 可以这样放 1，2，4，8，16，32，剩下的篮子怎么放都行 可以证明答案的正确性； 六位二进制可以表示0—63之间的任意数，所以 0-63直接用六位二进制码表示 64—100可以先取剩下的37个苹果，再在六位二进制码里面取27—63就可以了

阅读全文(1443) | 回复(0) | 编辑 | 精华 | 删除

 [随笔感悟]忙着充实着

dskongenius 发表于 2007/11/12 22:37:42

　 这两周以来是没日没夜的忙啊，不过貌似收获非常大，以前自己都是懂点皮毛，吹牛都吹不全，更别说应用了。但是现在自己已经积累了两个方法，阅读了很多代码，也写了很多，还掌握了三个进化算法，看一些相似的paper也能够触类旁通了，sas软件也居然花了半天就基本上学会了，以后需要用时再强化强化，看来知识就是这么学的，以前自己都是有“完美情结”，总要等到完美了再去使用，但是根本就完美不起来，使用往往也是五分钟热度，明天做完报告就可以休息休息了，再把两周的知识点沉淀沉淀，哈哈 老板的话是对的，"知识要边用边学，平常只要了解一个大概，真正使用再去细化和深化"，“做项目必须在高强度的学习下才能够有灵感的火花，必须强迫自己在短时间内把所有东西读完，再去思考”，“读paper时先了解一个大概，然后自己觉得闪亮的地方再去细化”

阅读全文(2410) | 回复(2) | 编辑 | 精华 | 删除

 [随笔感悟]终于读完了

dskongenius 发表于 2007/11/11 22:18:05

哈哈，终于读完了85页的程序，居然不全，只有层次聚类部分，看来美国那家伙不厚道，不管他了，下面继续看sas，为了下周二的报告，冲啊

阅读全文(1573) | 回复(0) | 编辑 | 精华 | 删除

 [随笔感悟]希望不是“五分钟热度”

dskongenius 发表于 2007/11/10 20:19:07

师兄最近忙于找工作，今天跟他聊了一下，收获颇为丰富： 1.一流公司看你的发展潜力，主要考的的逻辑思维能力和英语口语，所以面试时会考你智力题，英语口语，数据结构，算法等等。 2.二流公司主要注重你的实际工作能力，所以有一个项目经验还是很有优势的，最好是研发的项目，自己能够参与，熟悉他的技术细节。 3.笔试主要考一些基本的算法，数据结构，数据库，操作系统，c++，还有UNIX等等   所以我的研究生计划： 1.研一时学好课程，打好基础，最好能够拿奖学金，奖学金就是我的名片。反复看一些基础课程，例如，c++，数据结构，操作系统等等。同时尽量发两篇论文。 2.研二时上半年主要去公司实习，最好是能够参与一些研发的项目，实习时需要考试，这就需要研一时打好基础。并且要过老板那一关，最好研一时能够发两篇论文。参与项目要能够看看文档，熟悉他的技术细节。不要找测试的工作 3.研二回来把实习的东西沉淀沉淀，再看基础，为找工作做准备。 学习c++的书籍

阅读全文(1770) | 回复(1) | 编辑 | 精华 | 删除