2013年7月2日星期二

數學女孩-隨機演算法

好老實,單看書名《隨機演算法》就真係興趣不大,只因前面有數學女孩四字,另加作者結城浩三字,雖然自問並非作者的忠實粉絲,但對作者的功力有信心,內容應該有一定趣味;然後在目錄看見內容有提及Big OP ≠ NP3SAT等等,才猶豫買或不買。最後見定價有七折,就決定買吧。

買後絕不失望,作者功力無容置疑,本人對作者欣賞程度可見於舊文《數學女孩-哥德爾不完備定理》和《數學女孩-費馬最後定理》,不再贅述。這本依然保持作者一貫水準,初看甚似博雜,但見ProbabilityCombinatorics,Matrix等等都有所攝獵。但隨著故事發展,前面每樣所學都能在後續應用。

Probability可算是本人在數學範疇中最沒有興趣的一類,偏偏見於這書。閱讀後對Probability改觀,從前不清楚的地方,因為沒有提問,沒有找尋答案便不了了之,在Set Theory重新定義下,終於明白Probability的意義。

突然間,明白為何骰子一點的洞是特別大,並不單純視覺效果,而是它的背面是六點,若一點的洞和六點的每一個洞都一樣大,那麼六點的一面會輕一點,骰子的重心便偏向一點,這麼便不能保持每面都是接近1/6的機率。

Matrix中的Diagonalize可用SymPy求得,
from sympy import Matrix
m = Matrix(3, 3, [1, 2, 0, 0, 3, 0, 2, -4, 2])
P, D = m.diagonalize()
P * D * P.inv()
D中對角線的數便是Eigenvalue,P便是對應Eigenvalue位置的Eigenvector。

至於P與NP問題,洪教授在導讀中言及,NP ⊂ P,但在第三百二十九頁中,米爾迦說:「全部的P問題是NP問題已得到證明⋯⋯」,出現矛盾。為此上網搜尋,在NP (complexity)中圖解,所有P問題都是NP問題。希望這矛盾會在下一印刷版本修正。

SymPy亦可解決3SAT問題,但它不是用Random Walk,而是用DPLL
from sympy.logic.inference import satisfiable
from sympy import Symbol
x = Symbol('x')
y = Symbol('y')
satisfiable((x | y) & (x | ~y) & (~x | y))

斯特靈公式的近似,Stirling's approximation,是計算n!的近似值。除了Stirling之外,還有另一個更接近的計算方法,Ramanujan's factorial approximation
import sys
from math import factorial, e, pi, sqrt

def stirling(x):
    fact = sqrt(2*pi*x) * (x/e)**x
    return fact

def ramanujan(x):
    fact = sqrt(pi)*(x/e)**x
    fact *= (((8*x + 4)*x + 1)*x + 1/30.)**(1./6.)
    return fact

if __name__ == '__main__':
    n = int(sys.argv[1])
    print('Factorial = {}'.format(factorial(n)))
    print('Stirling = {}'.format(stirling(n)))
    print('Ramanujan = {}'.format(ramanujan(n)))

以10!為例,正確是3628800,Stirling是3598695.6,Ramanujan是3628800.3。

在這本書學到的,不單只是數學,還有學習態度,和對知識的追求。下一本是萬分期待的Galois Theory,一年一本真叫人等待漫長呢。

每項評分1-5星
歴史
實用☆☆☆☆
理論☆☆☆☆
証明☆☆☆☆☆
容易☆☆☆☆

沒有留言:

發佈留言