2030年會有百萬核心的電腦麼？

電腦的速度要有顯著的提昇，
CPU的核心部分要呈倍數增長，
那麼20 年後將會誔生百萬核心以上的個人電腦，
可能麼？個人認為不太可能，
至於2030年是否會有量子個人電腦，
個人也不太樂觀，
雖然現在有人認為多核心是長期的驅勢，
但到了2030年，百萬核心以上的個人電腦是否出現？
或是將有新的量子個人電腦？
兩者我都認為不太可能，
但到底當時的個人電腦會如何，
我一時也沒想法，
但硬要我猜的話，我認為比較可能的是異質核心個人電腦。

在格子圖上做Edge Ranking

一個圖G的邊編號是一個正整數的編號r，使得邊不同的e_i和e_j而r(e_i) = r(e_j)，他們的每一個路徑(path)，之中皆存在邊e_w使得r(e_w) > r(e_i) = r(e_j)。一般來說，邊編號的最佳解，就是求最小的邊編號。
直到2007年，對於不是trival類別的圖以及樹和two-connected outerplanar圖形之外，沒有找到線性時間的演算法。
最近，我想到把邊編號應用到格子圖上，即從中央做cut，如下圖


可以這樣切，或是如下圖這樣切：


如下圖，是一個邊編號完成的成果：

此時，這圖的χ_e(G)=9。顯然的，若都是直的切，從一半切下去是最佳的，這很容易證明，但為啥麼不斜著切？
這個問題，直覺上，認為不會是斜著切，但要怎麼證，笨笨的我，一時也想不出來。

2010年4月17日記：
如果無法從中間切下去，可能就需要有點斜著切了@"@。如下圖：

強者的職業：獵人

李公 ( R. C. T. Lee，因為上過李盃盃的課，所以就稱為李公了)，
在課堂上期勉同學，不要怕，要挑難的事情做。
呼~以下純屬我的想法：
啥是難的呢，做難的事，那麼一定要是強者了，既然是強者的話，那做獵人吧！

啥是獵人！？難道是Hunter × Hunter，哈，當然不是啦。
嗯，就來定義一個給強者做的職業，我們叫他獵人。
所謂獵人就是賞金獵人，而強者的獵人就是專門解有賞金的Open Problem的獵人，
而只靠這些賞金過活的人，我們叫他獵人。至於有賞金的Open Problem從哪來？
就我所知，就有Millennium Problems，裡面有七題，
包括：

• Birch and Swinnerton-Dyer Conjecture
• Hodge Conjecture
• Navier-Stokes Equations
• P vs NP
• Poincaré Conjecture
• Riemann Hypothesis
• Yang-Mills Theory

呼，看來誕生了一個新職業：獵人！要做果然要夠強！
你能做到，我就認為你是能做難的事情的強者！

P.S. 不過，強者麻，話說：「強者我同學。」當然不是我啦…

Note: 2010年3月30日後記：
2010年3月18日，克雷數學研究所對外公布，格里高利·佩雷爾曼因為破解龐加萊猜想(Poincaré Conjecture )而榮膺千禧年大獎。<ref:wiki 龐加萊猜想>

小明問問題

以下O(n)表示Big O notation。

話說，小明所在的班級，小英是第一名，
平常時都是小英下課後，問老師問題。
今天，小英生病沒來。
下課後，小勇拿課本去問老師問題：

1+2+3+...+n = O(n) + O(n) + 3 + ... + n
= O(n) + 3 + 4 + 5 + ... + n = ... = O(n)
錯在哪一步？

小陳在旁邊聽到小勇問老師的問題後，
就插嘴說：最後一個等號錯了，因為n個O(n)相加不等於O(n)，
所以是最後一步錯了。

而在老師不遠處睡覺的小明，聽到後，
則起來，拿出一本不知從哪來的筆記走向老師，
對著他們說：「一定是第零步到第一步錯！」
小勇：「？」
小明：「小陳這樣說也只表明至少錯在最後一步，不保證前面沒錯。」
小陳：「你能看出前面的錯誤麼？」
小明一邊把小勇的課本收好，一邊說：
「一定是第零步到第一步錯！至於怎麼證？」
小陳、小勇：「？」
接著，小明一邊把課本還給小勇，一邊說：「就靠你了。」
小明：「重點是：
現在換我問老師問題了。」

證明2SAT is class P

這幾天讀paper發現2-SAT problem可以在多項式時間內被解出來，
由於SAT和3SAT是NP-complete，很好奇為什麼2SAT例外呢？
就去網路上搜尋，很快的找到了英文的解答。

所謂的2SAT，就是可以寫成C1 and C2 and C3 ... and Cn, where C:clause，
且其size必須是2，例如一clause A∨B就是size為2的clause.

現在，我們定義一個directed graph G=(V,E)
V:對於每一個variable x，取x和~x兩個node
而對於每一個clause A∨B，滿足A∨B，其實就是滿足~A->B(若非A則B)或~B->A(若非B則A)，
E:對於每一個clause得到directed edge (~A,B)和(~B,A)

之後，把每一個(strongly)component依照topoligically sort編號，而strongly component內的編號皆編相同號碼。對於variable x，其編號函式為f(x)。

之後，由以下兩個Lemma，我們可以知道satisfying or not.

Lemma 1: formula F，假如有一個variable x，使得f(x)=f(~x)，則F是unsatisfiable.

證明：
由f(x)=f(~x)，知道x跟~x在同一strongly component，故存在一cycle:(x...~x...x)，
當我們嘗試x=true來滿足時，在其path:(x...~x)都必需為true，但~x不為true。(contradiction)
同理x=false時(~x=true)，也一樣是contradiction的情形。

Lemma 2: 假如對於在V上所有的x : f(x)!=f(~x)，則我們得到satisfying assignment經由設定
x=true if f(x)>f(~x)和x=false if f(x)<f(~x)

證明：
假定(assume)我們要得到矛盾的結果，
則在F中必定有一clause (A ∨B)是false，此時A和B皆為false。
By definition，f(A)<f(~A)和f(B)<f(~B)
而clause (A ∨B)貢獻兩條邊(~A,B)和(~B,A) to E，我們得到f(~A)<=f(B)和f(~B)<=f(A)，
結合以上，得到f(A) <f(~A)<=f(B)<f(~B) <=f(A)，矛盾。

至於演算法，
首先single pass F得到G的adjacency list，需O(n)。(n為clause數)
因此，這個graph有邊2n個和至多4n個的點。
對於每一個variable x，建一list L point到graph的x和~x.
而計算strongly component和那圖的topological order需O(n)
(至於是什麼方法，我也不清楚)，
之後，single pass L經由以上兩lemma的判斷，可知是否satisfying.
故The 2SAT problem for a formula F with n clauses can be solved in time O(n).

從無線充電到暴風女超人

幾年前發現無線充電的技術被實作出來， 目前無線充電的範圍只在90公分內有效，
而基本接收裝置成本只需5美元，大小約在一個硬幣的大小，
其實目前最主要的應用是在植入人体的器官換電上，這樣就可以用一輩子不用動手術換電，
幾個月前我想到的應用是結合無線指環鼠，不過若要結合的完美，
接收端我覺得還要在改小一點，最好在一元硬幣的四分之一以下，
其實目前無線充電有一個大缺點，就是範圍只能在90公分以內，
聽說目前是有FCC的認可，電池波不太強，但是這個範圍也太短了一點，
我的希望當然是愈大愈好…不過也要在合理的電池波範圍內，
但是受限於法規，電池波不能太強，所以到底未來有辦法改到多強，到底好不好改，
我並不是太樂觀，但是目前看來，範圍再長個幾倍，我也不意外。
如果未來無線充電能夠改良，變成範圍長且效能好的充電，
說不定可以大大取代電池…
想像一下未來世界，又有了一個有趣的結合：無線充電+戒指+閃電=魔戒(防狼戒指)。
其實我的想像是在各城市設無線充電，使人走在街上，
就可以用無線充電的戒指來累積能量，若能把電擊改良成放電槍，
再跟無線充電的戒指結合，使得戒指能放出閃電，就像一具有魔法的戒指一樣，
而功用就是遇到色狼時使用，想像一下，一個正妹用戒指放出閃電，
彷彿是漫畫才出現的場景一般，真帥！

多媒体分析

今天，一位暨大的學長來演講，
提到一個多媒体分析系統，
例如棒球，可以把經由畫面和聲音的比對，
自動產生，一些精采事件(如全疊打、安打、雙殺…)的所在位置，
這樣就可以只播放這些精采片斷，而不用播放整個賽事。
這個系統還可以自動產生summary，而跟緯來体育台的summary比較，
有8x%的重複性。相關的應用還有網球、藍球…等。
之後，學長又展示了一個把圖片做slide show的播放系統，
這個系統由使用者輸入圖片和音樂，之後讓電腦自動產生播放，
電腦產生的播放，是把時間、顏色…相關的幾個圖片，放在一個畫面的不同frame中，
之後電腦根據所選音樂的節拍，來播放圖片。
播放的效果還不錯，因為是依據節拍來播放的。
終極目標，我想到的應用是把漫畫丟進去，若能自動產生動畫，那就帥呆了！
不過，看來終極目標在有生之年是無望的。

無線充電+無線滑鼠=新一代滑鼠

幾個月前看到一則新聞：美發明"無線能量傳輸”技術 未來充電不用電線"

今天突然想到一個不錯的結合，就是無線滑鼠要裝電池，

而電池會增加滑鼠的重量，影響到手感…

如果能把電池拿掉改用無線能量傳輸，那就更酷了！

我是沒用過指環鼠，但是如果無線充電+無線指環鼠，又更COOL了！

不過前提當然是無線充電的接收端要做的比直接放電池來得小。

杜拜能源塔(Energy Tower)

最近看到一篇報導，杜拜將建造新的摩天大樓，
並且將產生100%自給自足的能源，
塔上將有一個197英尺高的渦輪機，
而塔的能量來源將是採用太陽能板來收集，
叫做Burj al-Taqa('Energy Tower')，
目前看到的圖片，覺得將會是一座漂亮的建築，
讓我們拭目以待吧。

詳細報導：Skyscraper Creates All Its Own Energy(英文) (連結失效？)

多人編寫小說系統

幾個星期前，聽到有個英文的萬人編寫系統上線了。

一開始聽說成效不太好，現在小說作者也大多為一個人，

覺得這雖然是個不錯的開始，

但是wiki系統可能要經過一些修改，再來拿來寫小說會比較適合。

如果是我設計一個小說系統的話，我想我可能會以三個人為單位。

即一個小說只能有三個人同時在寫，

而目前discussion頁可以在分成，

討論劇情架構、討論場景設定及材料及可能用到的名言佳句及對話內容。

並且在另外加個留言板，以討論其它的相關細節，或者可以在留言相約三個人出來見面，

一起喝咖啡討論劇情。

而管理方式，可以採用自願退出，

則可以在有人退出後補足人數到三人。

又可以規定，若是另一個人三天以上沒參加修改，則可以由另兩人投票請他退出。

又為了避免同時有兩個人以上沒在修改，

可以在加一條規則，若是某一個人超過一個月沒在修改，系統強制將其退出該編劇專案外。

Movie有可能完全由程式製作麼？

Media player在撥放音樂的時候，
可以選擇有視覺效果。
不過反過來想，
在撥放圖或影片的時候，是否也可能自行配音呢？
目前市面上，似乎還沒看到相關的產品。

幾年前，玩了一款叫電影夢工廠的pc game，
裡面是應用一些已經設定好的場景、人物和物件，
來組合出自己想要的movie。
更進階一點，是否有可能直接由電腦程式來製作movie呢？
實際上，那款遊戲，有些movie確實可由電腦隨機組合來產生。
而目前電腦在movie的製作上，比較實用的部份是用來合成，
短時間來看，是不可能出現完全由程式製作的電影，
但是n百年後呢？
像是由圖或影像來自動配音的程式出現，
自動編輯場景，自動產生文稿，
自動構圖的程式出現…
當這些元素集合起來後，沒有道理不可能的。

自動編輯，目前應用比較成功的，應該算是google news。
自動產生文稿程式，像雜誌專訪產生器就是一種，
而自動構圖，所面臨到的可能是美感的問題，
然而這或許可經由類神經網路之類的技術學習，
雖然現在類似這種程式離實用還有很大的一段距離，
但n百年後，您敢說不可能麼？

人工智慧雜談

幾年前對人工智慧感到興趣，
就去玩玩看chatter bot，
最近又去看看有什麼發展了，
結果還是跟以前差不多，
似乎沒什麼重大突破。
最近我一直在想，有沒有可能做個bot自動寫blog啊，
就是把別人的blog經過人工智慧整理修改後，寫成新的blog。
目前Google news已經採用程式自動編排了，
所以實際上，現在硬要搞個bot來產生blog是有可能的，
只是目前離實用大概還有很大的一段距離。
呵呵，為什麼我會這樣想呢？
因為想說如果寫出這樣的bot，
再加上Google AdSense，那就真的可以躺著賺了。

ALICE:有興趣跟機器人聊的，可以連進去聊看看。
或是跟EllaZ talk，雖然EllaZ要註冊才能聊，但是她的圖像是東方人哦。

邏輯問題(二)

X先生、Y先生都具有足夠的推理能力。這天，他們正在接受推理面試。
他們知道桌子的抽屜裡有如下16張撲克牌:
紅心 A、Q、4
黑桃 J、8、4、2、7、3
梅花 K、Q、5、4、6
方塊 A、5

約翰教授從這16張牌中挑出一張牌來，
並把這張牌的點數告訴X先生，
把這張牌的花色告訴Y先生。

這時，約翰教授問X先生和Y先生:
你們能從已知的點數或花色中推知這張牌是什麼牌嗎?
X先生:「我不知道這張牌。」
Y先生:「我知道你不知道這張牌。」
X先生:「現在我知道這張牌了。」
Y先生:「我也知道了。」
請問:這張牌是什麼牌?

這題的答案應該是方塊5，
可參考move或解謎人的說明。
想想如題目改成：

X先生、Y先生都具有足夠的推理能力。這天，他們正在接受推理面試。
他們知道桌子的抽屜裡有如下16張撲克牌:
紅心 A、Q、4
黑桃 J、8、4、2、7、3
梅花 K、Q、5、4、6
方塊 A、5

約翰教授從這16張牌中挑出一張牌來，
並把這張牌的點數告訴X先生，
把這張牌的花色告訴Y先生。

這時，約翰教授問X先生和Y先生:
你們能從已知的點數或花色中推知這張牌是什麼牌嗎?
X先生:「我不知道這張牌。」
Y先生:「我知道你不知道這張牌。」
X先生:「現在我知道這張牌了。」
Y先生:「我早知道了。」

那麼這題的答案又會是什麼呢？
這時答案會是黑桃4，
可參考move的說明。
所以這題就某一方面來說，
也許也可視為語意學的問題。

邏輯問題

X先生、Y先生正在接受面試，

他們知道桌子的抽屜裡有如下16張撲克牌:
紅心 A、Q、4
黑桃 J、8、4、2、7、3
梅花 K、Q、5、4、6
方塊 A、5

史帝芬．周教授從這16張牌中挑出一張牌來，
並把這張牌的點數告訴X先生，
把這張牌的花色告訴Y先生。

這時，教授問X先生和Y先生:
你們能從已知的點數或花色中推知這張牌是什麼牌嗎?
X先生:「我知道這張牌。」
Y先生:「我也知道這張牌。」
X先生:「不會吧」
Y先生:「一切都是幻覺。」
請問:這張牌是什麼牌?







答

案

是



~~~

~~

~






準

備

好

看

答

案

了

嗎

？

~~~

~~

~

答

案

就

是





這張牌是撲克牌


呵呵，不要打我…正經來了，
其實是昨天在網路上，看到一題《邏輯問題》，
題目如下：

X先生、Y先生都具有足夠的推理能力。這天，他們正在接受推理面試。
他們知道桌子的抽屜裡有如下16張撲克牌:
紅心 A、Q、4
黑桃 J、8、4、2、7、3
梅花 K、Q、5、4、6
方塊 A、5

約翰教授從這16張牌中挑出一張牌來，
並把這張牌的點數告訴X先生，
把這張牌的花色告訴Y先生。

這時，約翰教授問X先生和Y先生:
你們能從已知的點數或花色中推知這張牌是什麼牌嗎?
X先生:「我不知道這張牌。」
Y先生:「我知道你不知道這張牌。」
X先生:「現在我知道這張牌了。」
Y先生:「我也知道了。」
請問:這張牌是什麼牌?

答案

Towers of Hanoi is not in class NP

根據定義Towers of Hanoi(河內塔)不是P問題,

書上也沒把它歸在NP,

今天我有點懷疑,它是不是NP-hard,

如果不是,他是屬於啥問題?

就上網查了一下,

在http://www.cs.uidaho.edu/~karenv/cs213/cs213.useful.pages/np.html

發現以下內容:

Contrast with Infeasible Problems

Provably infeasible problems, like the Towers of Hanoi, at not known to be in the class NP.

Consider: how would you solve the Towers of Hanoi with an infinite number of processors? There does not appear to be any way to take advantage of such plenitude.

Any "solution" to Towers of Hanoi would be a sequence of instructions on how to move the disks, which would be exponentially long and so could not be verified in a polynomial number of steps.

Even guessing doesn't help. For example, guessing where each disk goes next would still require an exponential number of guesses to solve the problem. Such an algorithm would require exponential time

由於這篇文章,前半段是在講np問題的,

與Infeasible Problems對比指的就是NP問題,

因此得知Hanoi Towers屬於Infeasible Problems.

另外在網上查NP問題,

有中文網頁把它翻成Non-polynomial time problem,

比較正確應是Nondeterministic Polynomial time,

指的是在non-deterministic Turing machine上能夠在polynomial time解決的問題,

而deterministic Turing machine,指的是由一個state到下一個state只存在唯一的下一個state.

相對的non-deterministic Turing machine的下一個state並不是唯一(包含零個),

因此,P問題指的就是在deterministic Turing machine用polynomial time能解決的問題.

134340

冥王星被改名為小行星134340號了，

不曉得算命的有沒有算到今天？^^

NP Problem

這一、兩天花了一些時間在研究啥是NP,NP-Complete,NP hard,

首先介紹P,是找得到polynomial time可解決的problem,

而NP problem 就是Non-determistic polynomial time problem,

也就是找得到nd-choice在polynomial time可解決的problem.

至於NP hard:有一problem X,而所有的NP problem在polynomial time可reduce to X,

稱problem X為NP hard.

在這邊reduce指的是: A is reducible to problem B, 表示解了B就可以解決A問題,所以計算A問題,

不比計算B問題複雜(A cannot be harder than solving B)

NP-Complete:若是一個problem 屬於NP,也屬於NP hard,則此problem 是NP-COmplete.

而且若是一個NP-Complete problem存在一polynomial time的解法，

則所有NP problem都有 polynomial time的解法。

冥王星降級了

今天看到新聞:

國際天文學聯合會（ＩＡＵ）今天表決通過修正行星定義，冥王星正式遭到降級，失去七十年來公認為太陽系第九大行星、也是最外緣行星的地位，太陽系從此成為八大行星。

小時後背過九大行星沒想到降級了,雖然有點難過,

不過降級也好,因為他跟其他8大行星,

有些顯的格格不入.

今天,冥王星不再是行星...

去查了一下wiki看改了沒,沒想到上面寫說:

自2006年8月24日于布拉格舉行的第26屆国际天文联会中通过第5號決議，將冥王星劃為矮行星(dwarf planet)並自行星之列中除名。

...原來昨天就改了...

2006年8月24日,冥王星自行星中除名,

算是直得紀念的一天.