2010年4月12日 星期一

Assorted Links

  • Ref.: Computational Complexity: Deriving sum of squares: How much to cheat?

    因為我比較笨,所以常常對很多別人認為理所當然的東西,感到困惑。像是 1^2+2^2+...+n^2 的公式,我永遠都記不起來。當然我知道用數學歸納法或者某些技巧,可以推得出來,但是我和這篇文章的作者有一樣的困擾。某些數學技巧,實在太 tricky,"the formula comes out of nowhere",就算看懂了,感覺也學不來。這也是我在讀 concrete mathematics 時的感觸。

    Polya 在他的書中有描述 Euler 找出這條公式的合情推理的過程。不過印象中還蠻複雜的。我自己用類似交換 summation 的 index 的方式,花一個鐘頭才推出來。(真弱)

    我記得當年學的國中還是高中學的時候,應該是用數學歸納法教的吧。可見得教導思考方式遠比學習公式困難得多了。
  • Ref.: A Problem With Proving Problems Are Hard « Gödel’s Lost Letter and P=NP

    我看不太懂這篇在說什麼。我計算理論的訓練不足。不過裡面提到了很有趣的證明技巧。
    great John Littlewood used a similar trick to prove a result in number theory:

    1. If the Riemann Hypothesis is true, then primes behave well and his theorem is true.
    2. If the Riemann Hypothesis is false, then primes behave poorly and his theorem is true.
    這個技巧看起來很像廢話,好像很簡單,但是其實很難看得出來。我記得 The Triangle Removal Lemma 也是用類似的技巧證明。看起來好像沒有很深奧,但是其實非常漂亮。
  • Ref.: Jeremy's Adaptive Analysis
    簡單地說, 應該是把計算幾何裡的 output sensitivity algorithm 的概念推廣到各種不同的參數. 或者說 parameterized complexity 的多項式時間版本. 我個人是覺得很重要啦~~尤其是在討論 algorithmic engineering 的時候. 不過似乎缺乏統一的架構。

沒有留言: