[算法]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世纪以来甚至是人类

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

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

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/7 11:00:54

排序算法在程序中会用到很多，这里介绍几种常见的排序方法以及比较 冒泡排序：对一个队列里的数据，挨个进行轮询和交换，每次轮询出一个当前最大或者最小的值放在队尾，然后继续下次轮询，轮询长度-1，就跟冒泡一样，所以称为冒泡排序，运算时间复杂度N平方 选择排序：对一个队列里的数据，选出当前最大或者最小的值，然后将他与队首的数据交换，然后从第二个开始，进行相同的操作，运算时间复杂度N平方，但由于他不像冒泡一样需要不停的交换位置，所以会比冒泡快一些<

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

 [算法]20世纪最好的10个算法　

dskongenius 发表于 2007/10/24 21:38:46

　一、算法一词的来源

　　Algos是希腊字，意思是“疼”，A1gor是拉丁字，意思是“冷却”。这两个字都不是A1gorithm(算法)一词的词根，a1gorithm一词却与9世纪的阿拉伯学者al-Khwarizmi有关，他写的书《al-jabr w’al muqabalah》(代数学)演变成为现在中学的代数教科书。Ad-Khwarizmi强调求解问题的有条理的步骤。如果他能活到今天的话，他一定会被以他的名字而得名的方法的进展所感动。

二、20世纪10最好的算法

　　20世纪最好的算法，计算机时代的挑选标准是对科学和工程的研究和实践影响最大。下面就是按年代次序排列的20世纪最好的10个算法。

1.  Monte Carlo方法

1946年，在洛斯阿拉莫斯科学实验室工作的John von Neumann，Stan Ulam和Nick
Metropolis编制了Metropolis算法，也称为Monte Carlo方法。
    Metropolis算法旨在通过模

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

 [算法]数学建模的十大算法[收藏]

dskongenius 发表于 2007/10/24 21:34:56

　数学建模的十大算法
发信站: 自在心语 BBS 站 (Fri Dec 23 10:37:29 2005), 站内

1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法）
2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具）
3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现）
4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备）
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中）
6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题

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

 [算法]动态规划的理论模型

dskongenius 发表于 2007/10/24 21:26:53

动态规划 Dynamic Programming

by Starfish


【摘要】

本文介绍了动态规划的基本思想和基本步骤，通过实例研究了利用动态规划设计算
法的具体途径，讨论了动态规划的一些实现技巧，并将动态规划和其他一些算法作
了比较，最后还简单介绍了动态规划的数学理论基础和当前最新的研究成果。

（说明：这是我中学时候写的一篇小论文，因为公式和图比较多，
为了能在bbs上贴出来做了不少删节）


【目录】
一。引言
二。动态规划的基本思想
三。动态规划算法的基本步骤
四。动态规划的适用条件
五。动态规划的实例分析
六。动态规划的技巧——阶段的划分和状态的表示
七。动态规划实现中的问题
八。动态规划与其他算法的比较
九。动态规划的理论模型


一。引言

动态规划(dynamic programming)是

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

 [算法]贪心法，分治法，动态规划的学习总结

dskongenius 发表于 2007/10/24 21:24:10

一，贪心法 首先说说贪心法，贪心法是自然的方法，也是最直观的方法，贪心法的当前选择依赖于已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择，但是该方法不能保证最后得出的解是最优的，需要反复选择策略，加以比较，有时候一些选择策略可以很巧妙的解决问题。贪心法主要有两种思想，即贪心算法领先和交换论证，用来证明所得的解是最优的，交换论证的思想为首先假设一个最优解和通过贪心法所得到的解，然后逐步修改最优解，但保持每步的最优性，最后使得最优解跟通过贪心法所得的解相同。

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