是否所有的有限數列都可以由相應的一個公式生成? | 知乎問答精選

 

A-A+

是否所有的有限數列都可以由相應的一個公式生成?

2018年08月20日 知乎問答精選 暫無評論 閱讀 8 ℃ 次

這裡問這個問題,是因為有這樣一個想法:是否計算機上的任意文件,都可以由一個相對應的公式來生成?如果答案是肯定的,那麼這將給文件壓縮帶來質的變化。試想,隨便多大的文件,只要能夠推導出一個數據生成的公式,那麼只要把公式分享給別人,就完成了所有數據的傳遞。

從大家的答案可以看到,上面的猜測是正確的,那麼下一個問題就是是否能夠從有限數列推倒出公式來。

【Filestorm的回答(8票)】

覺得諸位貌似沒有回答道點子上啊。。。

問題的關鍵是,這個公式的複雜度是否低於這個數列的複雜度?

這個問題的答案才是真正解決樓主所說的「文件壓縮」問題。

至於這個問題的本質,請參考Kolmogorov複雜度:

en.wikipedia.org/wiki

而Kolmogorov complexity恰恰正是編碼、壓縮的基石之一。

在實際生活中比較普遍的應用是稀疏分析。這一領域的目標是讓一個「representation」(對應理解為lz所說的公式)的l1 norm(某種意義上的複雜度)盡量低於原來數列的複雜度。

目前日常生活中的典型應用之一就是jpeg/mpeg編碼。

【小離Sidney的回答(4票)】

這個問題可以有以下幾個考慮方向:

  1. 是否存在一個函數,使得x_1到x_n的n個點的分別依次對應函數值為這個有限數列;
  2. 是否存在一個變換矩陣,使得任意有限數列都可由其所構成的n維空間V的基向量變換得到。

對於第一種考慮:

對問題進一步數學化一些,轉述為:對於任意的有限的數列s_1, s_2, ... , s_n是否存在一個函數f,使得f(x_1)=s_1, f(x_2)=s_2, ... , f(x_n)=s_n。也就是,對於數對序列{ (x_1,s_1),?(x_2,s_2), ...,?(x_n,s_n)?},是否對於一個定義域[a,b],且有a≤x_1≤x_2≤...≤x_n≤b,存在函數f滿足上述序列。

於是,這就變成了一個多項式插值問題了,完全可以使用簡單的拉格朗日插值法,求得這樣的為如下形式的函數(按LaTeX的函數書寫方式):

f(x)=sum_{j=0}^n s_j l_j(x),其中 l_j(x)=PI_{i=0,i≠j}^n frac{x-x_i}{x_j-x_i}

對於第二種考慮:

對問題進一步數學化,轉述為:是否存在一個n維空間上的變換矩陣F,使得有限數列s_1, s_2, ... , s_n所構成的向量S滿足F?S=h,h為基向量。根據矩陣變換的相關知識,很顯然,必然存在這樣的變換F滿足這一條件。

綜上,是存在這樣的「公式」,滿足問題條件。只是這樣的公式是否唯一有待驗證罷了……

參考:

  1. 拉格朗日插值法?en.wikipedia.org/wiki
  2. 多項式插值?en.wikipedia.org/wiki
  3. 矩陣變換?en.wikipedia.org/wiki

【曹夢迪的回答(2票)】

可以,解多元方程組即可。

比如有限數列是l1, l2, l3 ... ln

則令f(x) = l1 * x^(n-1) + l2 * x^(n-2) + ... + l(n-1) x + ln

解方程組 f(1) = l1 , f(2) = l2 .... f(n) = ln

即可得到公式。

如果無解,則再令 f(x) = k * x^n + l1 * x^(n-1) + l2 * x^(n-2) + ... + l(n-1) x + ln

(其中k為任選的非零常數),同上方法繼續解方程組即可。

【Ivony的回答(0票)】

如果這個公式沒有什麼限制的話,應該是的。

【garfieldking的回答(0票)】

必須可以。這也是為什麼所有的「找規律填數字」的「智力題」(在數學上)毫無意義的原因:理論上你可以在留空處填上任意數字。

不過你明白你說的「公式」是什麼東西麼?嚴謹地說,應該是:對於任意有限數列 a_1,a_2,...,a_n ,是否存在從集合{1,2,...,n}到集合{a_1,a_2,...,a_n}的映射f使得f(i)=a_i。答案顯然是肯定的(因為問題本身已經給出了這樣一個映射的定義)。而且,顯然的,不止是有限數列,對可數數列同樣成立。

==================

手機打字好痛苦!。。。。

【催眠的回答(0票)】

因為序列可以看作是一個定義在整數子集上的離散函數,求通項公式就類似於求函數表達式,容易處理的是多項式函數。知道了前n個項,就知道了多項式函數(對應的n次方程)的n個根,那麼簡單的形式就是:(x-x1)(x-x2)...(x-xn),這樣總是可以寫出「公式」來,進一步,可以為這個乘積添加任意其它因子,所以符合前n項的序列不會只有一種。

【doubletony的回答(0票)】

必須有的。高一的時候就和同桌玩過。他推出來的就是拉格朗日的那個,而我就推出了下面這個土不拉幾的。。。

1 - | |x - n - 0.5| - ?|x - n + 0.5| |

隨意補充一下:

上面只是係數,完整版本如下:

f(x)=sum_{i=1}^{n}(1-left|left|x-i-0.5right|-left|x-i+0.5right|right|)a_{i}

a_{i} 為 n 個給定值。x = 1時為a_{1};?x = 2時為a_{2},依此類推

【夏玲的回答(0票)】

我認為可以。把這些點進行插值就可以求出數列通項公式。插值點是有限的、離散的,而插值多項式是連續的,應該沒問題。

【許鋮的回答(0票)】

有 但是一般情況下無論是公式還是數列 信息量是一樣的 甚至更多 所以對壓縮無用 還要白白增加計算成本

update:

其實現代的壓縮算法已經非常接近香農第一定律的極限了 所以LZ想用一個單一公式的方法到達給文件壓縮帶來質的變化」是不可能了

標籤:-數學 -Filestorm


相關資源:





給我留言