f*********g
发帖数: 632 | 1 来自主题: Mathematics版 - 来个问题。 怎么“比较迦勒华群与多项式的完备 性”？
怎么简化“5阶以上多项式无通解”的证明？
啥叫“5阶以上多项式无通解”？
怎么推广到多元情况？
怎么不换个ip来讨论问题。
不好意思。嘻嘻。
请大家继续讨论问题。 |
|
O********9
发帖数: 59 | 2 在"Matrix Algebra From a Statistician's Perspective David A. Harville
Springer"第546页有这个定理的证明。他是通过AB和BA的特征多项式证明的。设A是M×
N的矩阵，设B是N×M的矩阵。设AB的特征多项式是p(s)，BA的特征多项式是q(s)
p(s)=|sI-AB|=s^M |I-s^{-1}AB|
q(s)=|sI-BA|=s^N |I-s^{-1}BA|=s^N |I-s^{-1}AB|
不妨设M>N。有p(s)=s^{M-N}q(s)。所以AB和BA的非零特征值一一对应。AB仅比BA多M-N
个零特征值。 |
|
c*******h
发帖数: 1096 | 3 特征值是特征多项式的根，多项式的跟对多项式的系数来说是连续的，所以特征值
是连续的。
求特征向量本质上就是对矩阵 A-aI 做两次高斯消元，剩下对角线和最右边一列。
其过程基本是就是加减乘除，所以能够看出来应该是连续的。当然特征向量有符号和
子空间的问题，尤其是特征值如果是重根的时候，所以得对“特征向量”的概念做点
约束。 |
|
m**k
发帖数: 1008 | 4 P≠NP，一个简洁的论文标题，或许预示着七大世界数学难题之一的P问题（多项式算法
）对NP问题（非多项式算法）终于有了答案。据英国《新科学家》杂志网站8月11日（
北京时间）报道，美国惠普实验室的数学家维奈·迪奥拉里卡已经于6日提交了关于论
证该问题的论文草稿，如果此答案被证实无误，那么他将获得由美国克雷数学研究所提
供的100万美元奖金。
P对NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一，同时也是计算机科学领
域的最大难题，关系到计算机完成一项任务的速度到底有多快。有些问题计算起来很容
易，利用多项式算法很快能解决，比如求若干个数的乘积，这类问题被称作P问题；另
一类问题计算过程比较繁琐，但验证答案却很容易，比如把整数44427进行因数分解，
求解过程可能会很费时，但如果告诉你答案是177×251，简单计算即可验证答案是对的
，这类问题就被归为NP问题。
因此，如果P=NP，那么每个答案很容易得到验证的问题也同样可以轻松求解。这将对计
算机安全构成巨大威胁，目前加密系统的破解就相当于要将一个整数分解为几个因数的
乘积，正是其求解过程的繁琐，才能杜绝黑客的入侵。
而现在，迪奥拉 |
|
g****t
发帖数: 31659 | 5 x^n的fourier变换是已知的．那么Chebyshev多项式的fourier变换也是闭式的．
设Chebyshev多项式为p1,p2,p3...
其Fourier变换为P1,P2,P3.
例如b(x)=a*p1(x)+b*p2(x)+c*p3(x)+...
那么其Fourier变换就是a*P1+b*P2+...
Chebyshev多项式的好处是，很多函数的Chebyshev展开系数是指数下降的．
往往不用算太多项. |
|
c*******h
发帖数: 1096 | 6 现在讲共轭梯度一般追溯到Lanczos和Stiefel。共轭梯度跟Lanczos的三项递归
是完全等价的，而Lanczos的三项递归当初是受正交多项式的递归定理启发的。
共轭梯度大概是50年代的时侯出来的，那个时侯好像正是函数逼近和正交多项式
研究火热的时侯。那条误差公式基本上就是靠x_k-x*对于不同的k之间是共轭的
而得到最优多项式的结果，从而推出来的。
至于谁最早得出了这个结论，那就真是不知道了。我看了最初Lanczos的论文，
没提到这条公式。共轭梯度花了20年时间，也就是大概七十年代才开始流行起
来。即使后来人看不到Lanczos给了这个结论，也有可能是因为他当初没有被别
人足够的重视而已。毕竟Golub已经去世了，能知道那么多历史的估计也就是
Moler啊，Van Loan啊，Varga啊，Meurant啊，Saad啊这些人了。
Disclaimer: 以上纯属我瞎编，如与事实有出入，请参考历史。 |
|
f*******i
发帖数: 1049 | 7 所谓多项式时间,是指输入大小的多项式,即log n 的多项式 |
|
l*****a
发帖数: 119 | 8 不严格的证明方法
假设sum的通项公式存在(严格说需要证明)且是一个多项式, 之后5次的sum应该是一个6
次的多项式, 之后用7个点解出多项式系数. |
|
b*****u
发帖数: 6 | 9 问题有误,应该是有没有理论证明NPC问题不存在
多项式复杂度的解法.因为P属于NP,NP问题当然
有很多是多项式可解达到.
答案是当然没有.NPC究竟有无多项式解法是一个
大puzzle,任何人如果能证明有或无都将是CS的
一个重要里程碑.嘿嘿,想起本科一个老师上课
说到,宇宙的所有问题都可以归结为NPC的问题,
话语太夸张,但是NPC问题的重要性和难度由此
可见一班. |
|
t****n
发帖数: 56 | 10 在组合学中，还有种方法，就是：
假如closed form的公式是order为n的多项式，那么其n+1阶的差分为0,其
n阶差分为常数。sum i的通项公式是2阶的：n*(n+1)/2，假设sum i^2是
3阶的，那么可以设其通项公式为a*n^3 + b*n^2 + c*n^1 + d。这样，
就需要4个取值来定a,b,c,d。分别让n=1,2,3,4就可以得到四个方程，解
开这4个方程就可以了。
另外，因为组合数和排列数的代数都是多项式，所以，通常的组合问题都
可以假设有一个多项式存在，问题是对于次数的估计要正确。如果，你对于
该问题认定为通常的组合问题，并且知道次数，那么，至此，问题就解决了。
否则，上面的讨论可以给出一个启发式的估计，然后，你就可以用induction
来证明了. |
|
k*****u
发帖数: 1688 | 11 看了dreamer同学的面经，发现跟我的不一样啊不一样。
因为給我打电话的人英语有些听不懂，所以问题可能写得不精确。
上来就问什么是logistic回归。解释了一遍。然后问怎么做参数估计.印象当中有3种方
法，可是及不出来。只好说MLE，score method什么的。 然后问我说MLE又怎么做，我
记得好像用拉格让日乘子什么的，拉格朗日还不知道英文怎么说。还有New-Rapson什么
的。记不清了 。
后面一个问题是，如果logistic回归自变量x不是线性的，怎么办？这个问题我也不知
道。只好说那就用多项式回归，然后问我说多项式回归有什么risk？还有多项式回归怎
么选order
下一个问题好像是contingency table的问题：
先问我怎么来design看人们喜欢google 地图还是别的地图。我说那就做个survey。然
后她问我怎么处理这个survey数据。比如n个人做了这个实验。这样看上去是
contingency table啊，可是刚才面试的时候我也慌了。我说的是用开方检验。
接着问的是，除了记录他们喜欢那个地图以外，还有什么要记录的？我说的是还有
respons... 阅读全帖 |
|
b*******t
发帖数: 117 | 12 多谢分享
看了dreamer同学的面经，发现跟我的不一样啊不一样。
因为給我打电话的人英语有些听不懂，所以问题可能写得不精确。
上来就问什么是logistic回归。解释了一遍。然后问怎么做参数估计.印象当中有3种方
法，可是及不出来。只好说MLE，score method什么的。 然后问我说MLE又怎么做，我
记得好像用拉格让日乘子什么的，拉格朗日还不知道英文怎么说。还有New-Rapson什么
的。记不清了 。
后面一个问题是，如果logistic回归自变量x不是线性的，怎么办？这个问题我也不知
道。只好说那就用多项式回归，然后问我说多项式回归有什么risk？还有多项式回归怎
么选order
下一个问题好像是contingency table的问题：
先问我怎么来design看人们喜欢google 地图还是别的地图。我说那就做个survey。然
后她问我怎么处理这个survey数据。比如n个人做了这个实验。这样看上去是
contingency table啊，可是刚才面试的时候我也慌了。我说的是用开方检验。
接着问的是，除了记录他们喜欢那个地图以外，还有什么要记录的？我说的是还有
r... 阅读全帖 |
|
o*******y
发帖数: 810 | 13 收藏先
因为給我打电话的人英语有些听不懂，所以问题可能写得不精确。
上来就问什么是logistic回归。解释了一遍。然后问怎么做参数估计.印象当中有3种方
法，可是及不出来。只好说MLE，score method什么的。 然后问我说MLE又怎么做，我
记得好像用拉格让日乘子什么的，拉格朗日还不知道英文怎么说。还有New-Rapson什么
的。记不清了 。
后面一个问题是，如果logistic回归自变量x不是线性的，怎么办？这个问题我也不知
道。只好说那就用多项式回归，然后问我说多项式回归有什么risk？还有多项式回归怎
么选order
下一个问题好像是contingency table的问题：
先问我怎么来design看人们喜欢google 地图还是别的地图。我说那就做个survey。然
后她问我怎么处理这个survey数据。比如n个人做了这个实验。这样看上去是
contingency table啊，可是刚才面试的时候我也慌了。我说的是用开方检验。
接着问的是，除了记录他们喜欢那个地图以外，还有什么要记录的？我说的是还有
response time，客户体验，想说的挺多的就是不知道怎... 阅读全帖 |
|
b****r
发帖数: 2555 | 14 ☆─────────────────────────────────────☆
afei (afei) 于 (Thu Oct 27 19:20:48 2011, 美东) 提到:
过于年轻没有背景知识的请自觉跳过。
当年那位1+2的激动了全国人民的数学家，你们都记得宣传上有一条，说是用了十几麻
袋的演算草稿纸，都记得吧？
俺老人家最近收拾东西，整理到当年的笔记。说起来那也是一天到晚看书作笔记的，得
搞十几个小时吧。俺看了看，7-8年下来的笔记，最多一麻袋。还不一定能满。
然后俺就琢磨上了。老陈同学得多大的字，才能搞十几麻袋？再说我应该比他写得多啊
。好多时候那就是不停的写，抄。他老人家证数学，总得脑力劳动为主。不能跟我一样
脑子不动就动手吧？怎么也得想半天再写一个字来的。
那这十几麻袋，搞不好又是层层加码的玩笑吧？
☆─────────────────────────────────────☆
xlzero (Megatron) 于 (Thu Oct 27 19:22:39 2011, 美东) 提到:
估计没压，要是压实了就是演算纸张，两麻袋足够了
☆────────... 阅读全帖 |
|
h****h
发帖数: 90 | 15 孤立的问题再难，也不能吸引主流的兴趣
关键要成体系，能引申出新的领域，方向和问题。
在这方面， Riemann Hypothesis
和 Fermat 大定理， 都是非常有代表性的，
其实这两个大问题，实质上是可以联系起来的，
那就是通过Lanlangds 纲领。
哥德巴赫猜想真的很孤立，陈浸润的工作当然很好，
但绝对算不上大师级别的， 而且后续影响力也是很有限。
数学领域，不是说问题解决了就完了， 还要看看后续发展和应用。
--------------------------------------------
看看当前数学界最看中的七个世纪难题:
千僖难题之一：P （多项式算法）问题对NP（非多项式算法）问题
千僖难题之二：霍奇(Hodge)猜想
千僖难题之三：庞加莱（Poincare）猜想 （已由佩雷斯在2004年解决）
千僖难题之四：黎曼（Riemann）假设
千僖难题之五：杨－米尔斯（Yang-Mills）存在性和质量缺口
千僖难题之六：纳维叶－斯托克斯（Navier-Stokes）方程的存在性与光滑性
千僖难题之七：贝赫（Birch）和斯维讷通－戴尔（Swinnerton... 阅读全帖 |
|
n**s
发帖数: 2230 | 16 就是两类问题
一类是多项式时间内能验证的问题，一类是多项式时间内能解决的问题。问这两类问题
是否等价 |
|
t******l
发帖数: 10908 | 17 奥数不考高等代数。
多项式是美帝数学快班的初中内容，数学慢班的高中内容，咋都不算大学数学。
: 高等代数有部分要学，同模还是什么的 还有多项式这部分
|
|
j****i
发帖数: 68152 | 18 当然是平均分布。多个01分布叠加，是多项式分布。多项式分布的极限，是正态分布。
你这种取法，不管初始是什么分布，最后都是平均分布 |
|
发帖数: 1 | 19 傅立叶变换三角展开养活了这么多人，多项式展开也太憋屈了。
世界不见得就是波动的或多项式的。所谓波动、测不准也可能只是研究工具带来的错觉。
这些工具更应该只看作研究无穷的一些特别案例。而不能假设是普遍现象。 |
|
T*******x
发帖数: 8565 | 20 这个不是解析延拓。这个是zeta函数的一个性质。
解析延拓是说，在一个区域内定义的解析函数，其定义域可以开拓，最后开拓到全部复
平面，所以也叫解析开拓。
比如这个zeta函数，从它的级数定义来看，它能自然定义到的区域是实部为1之右的复
平面。实部为1之左的部分没有自然的定义方法。
然而解析延拓告诉你，有，这么一个解析函数，定义在全复平面，而在实部为1之右的
半复平面，其值等于你能自然定义的那个函数值。
解析延拓是怎样可能的呢？真的是开拓。比如你在实部为1之右的半复平面，靠近边缘
的地方选一点
。解析函数的意思就是这个函数可以在这个点附近表示为无穷多项式。而你会发现，这
个无穷多项式不仅可以在实部为1之右的半复平面求值 - 其值等于原函数值 - 也可以
在实部为1之左的半复平面（靠近这个点的一个小区域）求值。这就把原函数的定义域
开拓了一小部分（到左半复平面）。可以继续这样开拓，直至全复平面。
这是解析延拓的神奇之处。
解析函数本身还有神奇之处。 |
|
T*******x
发帖数: 8565 | 21 这个不是解析延拓。这个是zeta函数的一个性质。
解析延拓是说，在一个区域内定义的解析函数，其定义域可以开拓，最后开拓到全部复
平面，所以也叫解析开拓。
比如这个zeta函数，从它的级数定义来看，它能自然定义到的区域是实部为1之右的复
平面。实部为1之左的部分没有自然的定义方法。
然而解析延拓告诉你，有，这么一个解析函数，定义在全复平面，而在实部为1之右的
半复平面，其值等于你能自然定义的那个函数值。
解析延拓是怎样可能的呢？真的是开拓。比如你在实部为1之右的半复平面，靠近边缘
的地方选一点
。解析函数的意思就是这个函数可以在这个点附近表示为无穷多项式。而你会发现，这
个无穷多项式不仅可以在实部为1之右的半复平面求值 - 其值等于原函数值 - 也可以
在实部为1之左的半复平面（靠近这个点的一个小区域）求值。这就把原函数的定义域
开拓了一小部分（到左半复平面）。可以继续这样开拓，直至全复平面。
这是解析延拓的神奇之处。
解析函数本身还有神奇之处。 |
|
n********g
发帖数: 6504 | 22 根据历史记载，在俺出生之前，有位叫库克研究自动证明的千老在伯克利没混到天牛，
结果愤然到了北美国图灵呆过的学校多伦多。多年以后，伯克利教廷还得为此道歉。当
然因为是俺出生以前的事，所以真相是否如此，俺也说不准。
另外，在地球另一边也有一位研究电路不得志的年轻人。他两从不同领域出发几乎同时
发现了NP完全。也就是新近被重新命名的库克-李文定理。当然，可惜李文没有南俄罗
斯，所以定理能重新命名，图灵奖没得补发。
这个NP完全俺觉得是为何P vs. NP没被证明的最重要原因。所以花点笔墨说一说。后来
人千万别踩这雷区。
首先，库克没能证明P ? NP。但库克定义了一个测度，发现一个NP的子集（不一定是真
子集）NP完全。NP完全的意思是，假设一个NP完全问题是一个写好的函数，所有NP问题
都能在多项式次（因此总时间仍然是多项式次的）地调用此函数后得到解决。
大致可以这样理解，如果P的测度值定为0，一般NP问题的测度就是正整数，而NP完全库
克希望是无穷（比所有整数都大）。在物理、数学里，无穷通常被认为异常、无解。所
以库克应该是希望以此证明存在NP（完全）问题不在P里。所以如果谁想沟通0和无... 阅读全帖 |
|
n********g
发帖数: 6504 | 23 和库克定义的测度不同。库克试图定义一个测度，使NP完全问题的测度为无穷。因此（
潜意识地）证明NP完全问题不属于P。
如果要证明P=NP，按照我上面提到的要求：
1、这个测度的可能值不包括无穷。满足这个的很多，如图灵机使用的时间、空间等可
以无限但都有穷；
2、P=NP/0；
3、可以证明NP/i+1属于等于NP/i。所以P=NP/0=...=NP/i=...
几年前一篇预印给出了这样一个测度：图灵机解决问题的所有步骤中需要"猜/不确定"
多少次。
1、很显然，图灵机不会猜无穷次。否则就是永不停机；
2、很显然，P=NP/0。因为猜0次的不确定图灵机就是确定图灵机。双手合十一一对应。
3、不失一般性，假设NP/i里所有图灵机都是单带。通过两个巧妙的转换：(1)将属于NP
/i+1的单带图灵机用一个多带图灵机模拟其第i+1次猜测的每一种可能。这个多带图灵
机时间复杂度一样但只猜了i次；(2)用一单带图灵机模拟此多带图灵机，通过增加时间
复杂性(t^2)换取回到单带。这样，用增加时间复杂性换取"猜/不确定"测度下降。注意
：对多项式时间函数t而言，t^2也是多项式时间。这就证明了NP/i+... 阅读全帖 |
|
n********g
发帖数: 6504 | 24 嗯，对没学过图灵机的我觉得需要补充几点。
1、语言、类这些概念如果我没记错就是一般集合论里的概念。没有特别的如计算机语
言之类的含义。
2、相同的语言可以被无数不同的图灵机接收。类似于无数不同的程序都排序。所以比
较语言集，没人比较图灵机集。
P=NP的意思就是每一个被不确定图灵机多项式时间接收的语言（输入集合）都存在确定
图灵机多项式时间接收。
一个比喻就是，如果有一个算法能（不确定地）猜到排序后的结果然后只需验证一下，
存在一个算法（确定地）老老实实一步一步地排序也能算出来。
P和NP涉及两种机器，两个世界。一个凡尘，另一个是魔法世界。 |
|
发帖数: 1 | 25 文中讲的是对的。现在的所谓量子计算机用的其实都是普通电子计算机对量子计算机进
行的模拟。所以本质上还是图灵机，不可能突破可计算理论定下的极限，在多项式时间
里计算NP完全问题（除非P=NP).
理论上量子计算机是可以利用纠缠态在多项式时间解决NP完全甚至指数困难问题。但有
这种能力的计算机必须用到N-个纠缠态量子。比如要破解1024位RSA的素数分解，计算
机必须维持至少1024个纠缠态量子。
刚刚狗了一下，目前的纠缠态量子记录是20个，在去年4月发布的。这还是在实验室里
。可以想象一下，从20到1000+,再到可以把物理的纠缠态变成真的计算机，有多长的路
需要走？
https://phys.org/news/2018-04-quantum-physicists-entanglement.html |
|
T*******x
发帖数: 8565 | 26 有了Gauss Lemma，这个小问题就好证了。
这里r1(x),r2(x)是Q[x]中的，是一楼中的两个多项式。分别用两个整数n1，n2乘以两
个多项式，clearing denominator，使得n1*r1(x)和n2*r2(x)都属于Z[x]，并且都是
primitive的。这可以做到吧？而且n1还大于1，因为假定r1(x)不在Z[x]中。
如果r1(x)*r2(x)本身就在Z[x]中，那么n1*r1(x)*n2*r2(x)，一方面根据高斯Lemma，
它应该是primitive的，另一方面它又有一个系数公约数n1*n2，所以不是primitive的
。矛盾。 |
|
发帖数: 1 | 27 你又想让黑人男友口爆你，你想让他爆你菊，心情矛盾
盹盹盹
：有了Gauss Lemma，这个小问题就好证了。
：这里r1(x),r2(x)是Q[x]中的，是一楼中的两个多项式。分别用两个整数n1，n2乘以两
：个多项式，clearing denominator，使得n1*r1(x)和n2*r2(x)都属于Z[x]，并且都是
：primitive的。这可以做到吧？而且n1还大于1，因为假定r1(x)不在Z[x]中。
：如果r1(x)*r2(x)本身就在Z[x]中，那么n1*r1(x)*n2*r2(x)，一方面根据高斯Lemma，
：它应该是primitive的，另一方面它又有一个系数公约数n1*n2，所以不是primitive的
：。矛盾。 |
|
T*******x
发帖数: 8565 | 28 现在证Gauss Lemma. 这是一个beautiful的小lemma。
这里r1(x),r2(x)属于Z[x]，我们证明逆否命题，如果r1(x)*r2(x)如果有系数公约数p
，一个素数，那么r1(x),r2(x)至少一个多项式里面，系数有这个公约数。
假设
r1(x)=a_0 + a_1 x + a_2x^2 + ...+a_nx^n
r2(x)=b_0 + b_1 x + b_2x^2 + ...+b_mx^m
把这两个多项式相乘的全部项写出来，写成阵列，就是一个m*n的矩阵，横坐标为a_0,a
_1,...,纵坐标为b_0,b_1,...
x^k项为反45度对角线上所有项相加，系数c_k=sum_{i+j=k} of a_i*b_j
根据假设，反对角线上所有项相加的系数可以整除p。
从矩阵的左下角开始，推几步就发现，矩阵中的每一项系数都必须整除p。这个结果是
有点惊人的，因为不仅是反对角线上所有项加起来整除p，而且是每一项本身就整除p。
但是推几步就相信了。但是怎么能说清楚呢？挺巧妙的。数学归纳法。假设小于等于k
阶的反对角线内的每一项都整除p，证明k+1阶反对角线上的每一项... 阅读全帖 |
|
发帖数: 1 | 29 你吃黑人男友鸡巴的技术挺巧妙的
盹盹盹
：现在证Gauss Lemma. 这是一个beautiful的小lemma。
：这里r1(x),r2(x)属于Z[x]，我们证明逆否命题，如果r1(x)*r2(x)如果有系数公约数
p
：，一个素数，那么r1(x),r2(x)至少一个多项式里面，系数有这个公约数。
：假设
：r1(x)=a_0 + a_1 x + a_2x^2 + ...+a_nx^n
：r2(x)=b_0 + b_1 x + b_2x^2 + ...+b_mx^m
：把这两个多项式相乘的全部项写出来，写成阵列，就是一个m*n的矩阵，横坐标为a_0
,a_1,...,纵坐标为b_0,b_1,...
：x^k项为反45度对角线上所有项相加，系数c_k=sum_{i+j=k} of a_i*b_j
：根据假设，反对角线上所有项相加的系数可以整除p。
：从矩阵的左下角开始，推几步就发现，矩阵中的每一项系数都必须整除p。这个结果是
：.......... |
|
发帖数: 1 | 30 左起：查济民女儿，周光召，刘璧如，王小云，杨振宁，姚期智
来源 | 《数学文化》2019第10卷第2期
访问整理 | 王涛、王坤
昨天 （9月7日），2019年“未来科学大奖”数学与计算机科学奖宣布授予密码学
家王小云，奖励她在密码学领域的开创性贡献。王小云创造了一种毁灭性的密码分析方
法，破解了一个又一个国际通用的算法。那么，她的数学和密码人生是怎样展开的呢？
王小云，1966年出生于山东诸城，1981年进入诸城一中学习，1983年起就读于山东
大学数学系，先后获得学士、硕士、博士学位，师从潘承洞院士；1993年毕业后留校任
教，历任讲师、副教授、教授；2005年6月受聘为清华大学高等研究院“杨振宁讲座教
授”。现为第十三届全国人大代表、中国科协女科技工作者专门委员会委员、中国密码
学会副理事长、中国数学会常务理事。
王小云的主要研究领域为密码学。在密码分析领域，她系统给出了包括 MD5， SHA
-1 在内的系列 Hash 函数算法的碰撞攻击理论，提出了对多个重要 MAC 算法 ALPHA-
MAC、MD5-MAC 和 PELICAN 等的子密钥恢复攻击，以及 HMAC-MD5 的... 阅读全帖 |
|
发帖数: 1 | 31 你直接说用三次多项式生成的数据，再用三次多项式拟合呗 |
|
g*******y
发帖数: 1930 | 32 1. sort stack using only pop(), top(), push(), isEmpty(),isFull(). Do not
use any auxiliary stacks or arrays.
感觉不用辅助空间做不到啊，这题是真的有很巧妙的方法？还是玩玩文字游戏--比如用
linked list然后宣称它不是stack也不是array...
2. Given a set of coin denominators, find the minimum number of coins to
give a certain amount of change
贪心和DP,回溯法应该都能做的，无非就是状态空间搜索，但是我想到的都是伪多项式
的算法，感觉这道题应该能利用某些数论的知识在多项式时间解决? |
|
k***e
发帖数: 556 | 33 老大，你怎么经常提些npc问题啊。
如果这个问题多项式时间可解，那么就可以多项式时间解longest path in the graph |
|
n*****g
发帖数: 82 | 34 因为每条边的权值为非负，所以必定有一个最优解使得每一个节点只被访问过一次。同
时，对于任何一个最优解，我们都可以找到另外一个最优解使得每一个节点只被访问过
一次，因为我们只要把原来最优解的circle去掉就可以。也就是说，如果这个问题可以
在多项式时间解决，那么travelling sales man problem也可以在多项式时间解决。但
因为TSP是NP-hard，所以。。。 |
|
b**********t
发帖数: 37 | 35 拉格郎日？？我高中倒是学过，是凑一个n阶多项式的公式，使得多项式在n个给定点取
到n个给定值。
t |
|
|
j**l
发帖数: 2911 | 37 这是一道G的题目...
我觉得:
1) 和多重背包有一定关系，每种物品有若干件，假设物品的价值和重量成正比，这样
总价值最大就是总重量最大。不过要把不超重的情况下尽可能的重，改为超重的情况下
尽可能的轻。既然多重背包可以用动态规划，这题肯定也可以，参考楼教主的背包九讲。
2) 转为LP的问题让我耳目一新。其实我学最优化理论的时候学过单纯型法，但这题没
有想到也可以转为LP问题。不过从1)来看，应该是NPC的，用LP解是伪多项式时间吧。
不少用动态规划解的NPC题，也是伪多项式的，要弄清楚输入规模。
3) 最不济，也要想到暴力穷举法，比如你的例子，对x, y, z作三重循环。如果这个不
说出来，又想不到1)或者2), 面试官那里肯定几乎不得分了。
4) 如果想用贪心法或者硬币找零的动态规划法，这题就走弯路和死胡同了。
比如面值为2分，5分，8分 的邮票各
有a, b, c 张，邮资是16分
假设取2分 5分 8分 的各x,y,z 张
limitation:
0<=x<=a
0<=y<=b
0<=z<=c
2x+5y+8z >= 16
obj: min( 2x+5y+8z )
这是LP问... 阅读全帖 |
|
e***l
发帖数: 710 | 38 更正，这个不对。Interval远比vertex特殊，Vertex之间的可以有任意的边。
转换成graph相当于把这个问题一般化了。所以原问题不一定是NPC。
===================
这个想法是对的。如果所有weight想等，那么就是minimum vertex cover，是NP-C问题。
所以说原问题比minimum vertex cover更难，必定不存在多项式时间解法。不然你就NB
大了。
如果一个算法是多项式时间，那么一定不能保证找到全局最优解。 |
|
t********e
发帖数: 1169 | 39 不是做理论的，尝试解释一下， 理论大牛别笑
P跟NP是关于决定性问题(Decision problem)的分类， 有些决定性归于p类， 有些归于
np类. 决定性问题就是些回答是yes/no的问题。
关于一个决定性问题， 比如说旅行推销员问题，人们既关心要多久才能”找到“一个
正确解， 也关心给定一种解法， 多久才能”验证“这个解法是否正确。
如果一个决定性问题的正确解可以在多项式时间内“找到”，那就是属于p类问题
如果能够在多项式时间内”验证“一个解法是否是这个决定性问题的正确解， 那就属
于np问题 |
|
J*****a
发帖数: 4262 | 40 这不是背包 不懂装懂 说入门说明你还没入门呢
背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
这是带权重的scheduling problem，康奈尔的算法教材上的例题原题 |
|
J*****a
发帖数: 4262 | 41 这不是背包 不懂装懂 说入门说明你还没入门呢
背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
这是带权重的scheduling problem，康奈尔的算法教材上的例题原题 |
|
|
I*******y
发帖数: 4893 | 43 你这个算法是不对的。比如一个数列是1, 2, ..., n, 另一面是2, 3, ..., n - 1, n
+ 1
你的算法会比最优解多出将近一倍
这个问题实际上是np hard的，从partition归约，n个数放左面，两个结点放右边，每
个的权分别是左面和的一半。partition问题有解的话，这个问题的解是n，否则这个问
题的解是n+1。所以此题没有多项式时间解。应该有伪多项式时间的DP解法 |
|
t*******r
发帖数: 22634 | 44 我刚才又发现欧氏几何难题的一个弱点，因为丫的那个多元函数
总是一个多元常数函数，所以如果我能够把方程和约束条件都搞
成多项式，那我就可以对各个变量偏微分电算求解求证。。。
因为多项式嘛，你懂的，偏微分多搞几次，阶数就低几次。。。
方程数目多点没关系，反正有矩阵代数电算，计算机最不嫌的就
是多。。。哈哈哈哈。。。。
// 我 run 了。。。 |
|
t*******r
发帖数: 22634 | 45 我刚才又发现欧氏几何难题的一个弱点，因为丫的那个多元函数
总是一个多元常数函数，所以如果我能够把方程和约束条件都搞
成多项式，那我就可以对各个变量偏微分电算求解求证。。。
因为多项式嘛，你懂的，偏微分多搞几次，阶数就低几次。。。
方程数目多点没关系，反正有矩阵代数电算，计算机最不嫌的就
是多。。。哈哈哈哈。。。。
// 我 run 了。。。 |
|
t*******r
发帖数: 22634 | 46 这个平方数前 N 项求和，俺琢磨的教普通小学生概念的办法（避免直接
解三元一次方程组，同时也揭示多项式级数前 n 项求和的 mathematical
structure & logic），这么整：
1^2, 2^2, 3^2, ... k^2, ... N^2
提示观察可知其相邻两项之差是等差级数（这个相邻项的差值的概念，
其实可以用到所有多项式型的级数）。
所以如果能找到另一个级数 s(k) （娃需要能看懂代数表达式就可以了，
反正是大人教概念 exposure 一下），满足
s(k) - s(k-1) = k^2
那么问题就可以转化为求 s(N) - s(0)。
因为我们知道对于等差数列，s_arith(k) 是 k*(k+1)/2（导致
s_arith(k) - s_arith(k-1) = k），那就先猜测对于平方数数列：
s_guess_a(k) = k*(k+1)*k(+2)
然后计算
s_guess_a(k) - s_guess_a(k-1)
= k*(k+1)*(k+2) - (k-1)*k*(k+1)
= 3*k*(k+1)
= 3*(k^2 + k)
那为了去掉系数... 阅读全帖 |
|
t*******r
发帖数: 22634 | 47 我觉得对普通娃而言，没有多项式的知识，就不用教这么巧妙的解法了。
因为我觉得你说的这个就跟平面几何难题差不多，对于这种：
1/(1*2)+1/(2*3)+1/(3*4)+...+1/(99*100)，
我觉得 99.9999% 的人，一辈子也不会用到跟其相关的概念。。。
而 差分降幂 / 通常的移位对称，是重要的数学理念。。。
俺不是说一定要教“差分降幂”的概念（俺那个只是玩玩，教娃未遂，
感慨一下而已）。。。而是说，上面那中那么不常见的求和技巧都
教娃了，却不去教娃多项式，我是很难理解的。。。 |
|
t*******r
发帖数: 22634 | 48 雕虫小技不是因为小技，而是因为只能用来雕虫。。。内接正方形来证明勾股定理，其
实也是小技。但因为是反映勾股的内在对称性，所以不是雕虫。
而俺上面那个是理解数学理论，而不是真的让娃去死记硬背这么算。。。多项式级数前
n 项求和的一个重要用途，就是 combinatorics (combination / permutations /
etc)。。。这个的目的不是算级数，而是反建模来理解求多项式级数前 n 项和的一个
用处。。。而这个级数就是我说的那个排列组合问题的 decision tree 直接硬算，而
使用 permutation 算，是利用那个问题的内在对称性。。。wo/ repetition 其实也表
现在这个级数的 pattern 里。。。退到最后一步，俺那个至少是 word problem 而不
是死记硬背。。。 |
|
t*******r
发帖数: 22634 | 49 这方法不笨。排列组合公式不是都能用上的，有时就算有特别巧妙的办法，也不一定能
马上想到。但一般就用 decision tree 加多项式级数，规约一下多项式级数前 n 项和
，就好了。
所以我说是体力活。 |
|
t*******r
发帖数: 22634 | 50 水车我现在边写边验算，节省点时间。要是错了我就随行更正。
首先说这个玩意儿是啥。这玩意儿是：
通过反建模的方法，把多项式级数前 N 项求和，先规约成固
定长度（长度跟 N 无关）的排列组合公式，然后进一步规约
成固定长度的多项式表达式。
这里拿 1^2 + 2^2 + 3^2 + ... + n^2 作为例子。
（未完待续） |
|
