演算法熵

演算法熵（粵拼：jin2 syun3 faat3 soeng1），又叫柯爾莫哥洛夫複雜性（Kolmogorov complexity），數學符號係 $K$，係理論電腦科學同相關領域上用嚟量度一件物件嘅複雜性嘅一個指標，一件物件嘅演算法熵係指要產生嗰件物件嘅程式嘅最短可能長度。

曼德博集合碎形當中嘅一橛

概論

睇埋：複雜同演算法

演算法熵以攞嚟比較唔同物件嘅複雜度。舉兩個簡單嘅例子說明，想像以下呢兩串符號：

abababababababababababababababab（串 1）

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7（串 2）

呢兩串符號長度一樣，但喺複雜度上唔同：串 1 可以描述為「將『ab』寫 16 次」，即係 write ab 16 times 噉嘅碼－段碼淨係用咗 17 個符號；相比之下，串 2 冇乜明顯嘅規律，唔能夠用一句嘢簡單噉描述嗮，所以要部電腦死記住 write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7 嘅碼－段碼有成 38 個符號。所以如果用演算法熵做準則嘅話，串 1 簡單過串 2。

好似係文頭幅附圖噉。幅圖像係用曼德博集合（Mandelbrot set）所產生嘅一幅碎形（fractal）。如果想要一部電腦記住呢幅圖，可以有兩個方法：一係要部電腦好似傳統嘅點陣圖噉，死記住幅圖每一點係乜嘢色，如果用 24-位元色嚟記嘅話，成幅圖需要用成 1,620,000 個位元組先至記得到；另一方面，部電腦又可以齋靠記住產生幅圖嘅算式，並且喺用家想睇幅圖嗰陣即場用記住嘅算式砌返幅圖出嚟（睇埋向量圖像），而呢個做法花嘅位元組數目會細好多－呢幅圖嘅演算法熵會遠遠細過 1,620,000 個位元組。

睇埋

• 運算複雜度
• 認知複雜度

文獻

• Blum, M. (1967). "On the size of machines". Information and Control. 11 (3): 257. doi:10.1016/S0019-9958(67)90546-3.
• Brudno, A. (1983). "Entropy and the complexity of the trajectories of a dynamical system". Transactions of the Moscow Mathematical Society. 2: 127–151.
• Cover, Thomas M.; Thomas, Joy A. (2006). Elements of information theory (2nd ed.). Wiley-Interscience. ISBN 0-471-24195-4.
• Lajos, Rónyai; Gábor, Ivanyos; Réka, Szabó (1999). Algoritmusok. TypoTeX. ISBN 963-279-014-6.
• Li, Ming; Vitányi, Paul (1997). An Introduction to Kolmogorov Complexity and Its Applications. Springer. ISBN 978-0387339986.
• Yu, Manin (1977). A Course in Mathematical Logic. Springer-Verlag. ISBN 978-0-7204-2844-5.
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS. ISBN 0-534-95097-3.

拎

• The Legacy of Andrei Nikolaevich Kolmogorov.
• Chaitin's online publications.
• Solomonoff's IDSIA page.