Saturday, June 23, 2007

You are just like a butterfly

蝴蝶

詞 : 陶吉吉‧娃娃 曲 : 陶吉吉 (詞寫的真好)

當這世界已經準備將我遺棄 像一個傷兵被留在孤獨荒野裡
開始懷疑我存在有沒有意義 在別人眼裡 我似乎變成了隱形
難道失敗就永遠翻不了身 誰來挽救墜落的靈魂

每次一見到妳 心理好平靜 就像一隻蝴蝶飛過廢墟
我又能活下去 我又找回勇氣 妳的愛像氧氣幫忙我呼吸
我又能呼吸 我又能呼吸 妳就是不願意放棄

生命充滿亂七八糟的問題 像走在沒有出口的那個迷宮裡
oh no 一次又一次只會用藉口逃避
怎麼妳從來沒對我徹底的死心 我有何德何能值得妳珍惜
為何妳對我有求必應

每次一想到妳 像雨過天晴
看見一隻蝴蝶飛過廢墟 是那麼的美麗 就像一個奇蹟
讓我從倒下的地方站起 Woo....

只要一靠近妳 就覺得安心 妳看著我的眼沒有懷疑
妳對我的相信 讓我又能重生 不管世界多冷我還有妳 我有妳

愛我這樣的人對你來說不容易 我的痛苦妳也經歷
妳是唯一 陪我到天堂與地獄

每次一想到你 像雨過天晴 看見一隻蝴蝶飛過了廢墟
我能撐得下去 我會忘了過去 是妳讓我找回新的生命 yeah..
每次一見到妳 就心存感激 現在我能坦然面對自己
我會永遠珍惜 我會永遠愛妳
在我心底的你的位置沒有人能代替 yeah

妳就是那唯一

English sentences and vocabulary - 2007/06/23

  • stumbling block 絆腳石
  • touchy 敏感的
  • mesmerize 迷住
    • Mitch mesmerized readers around the world with his NO.1 bestsellers.
  • windbreaker 防風上衣
  • peppermint 薄荷
  • close on 接近
  • It was fate that I found him. (It is fate for me to finding him.)
  • backstop (棒球的)擋球網
  • maneuver 操縱
  • lawn mower 刈草機 (刈的發音為 "yi")
  • tanned 曬成棕褐色
  • check out 試試;試試
  • sniff 抽鼻子;嗤之以鼻
  • damn lucky 走狗運
    • He's damn lucky to be alive!
  • chuckle 咯咯地笑
  • crystal clear 清晰明瞭的
  • stomp 跺腳
  • narrative 故事;敘述
  • anyhow, anywise, anyway
  • You know you can go your whole life collecting days, and none will outweigh the one you wish you had back.

Thursday, June 21, 2007

A man with a ring

感覺無名指套上了戒指後,感覺就不再是一個人。

黃老師說,我結了婚以後,就不再是一個人,晚上不要單獨行動。不過,我跟他跑步應該不算單獨行動吧。黃老師還虧我現在得意了,戴戒指又穿新鞋的...

話說,現在突然有不少人跟我說馬尾很漂亮,他們知道得也太晚了吧。

Friday, June 15, 2007

Visiting to Tainan Hospital, Department of Health

之前去過成大醫院、嘉義基督教醫院、骨科診所(陳文毅醫師),今天就去台南醫院讓其他醫師再看看,主要是想確定左膝是否有嚴重的問題,以及左腳腳底的問題是足底筋膜炎還是已經嚴重到長了骨刺。

沒想到去了那裡,又是遇上陳文毅醫師 (XD)。我再次跟他敘述目前左腿與左腳腳板的狀況,他有一些意見如下:

  • 身體過了 25 歲以後會開始退化,肌力慢慢下降,所以要做一些增強的訓練,譬如重量訓練。
  • 我的左右腿大腿股四頭肌強度都還不錯,沒有退化。
  • 我的左腿就算是休息也不一定會好,所以要試著強化肌力看看。
  • 骨刺一般發生在年紀較大的患者,所以我應該是足底筋膜炎。要穿厚底且有彈性的鞋子;此外,不要光腳走路。
  • 膝蓋的問題可以吃藥看看,吃藥的效果比抹藥快得多。
  • 新聞報導通常只報憂不報喜,所以不用過於擔心塗抹藥膏的問題。安啦!發生問題的可能性很低。

看診完,我去照了一下膝蓋的 X 光片,下週五下午要複診。目前就先吃藥看看情況會不會好轉。希望我不是真的退化了,我還年輕啊!

New antivirus software adopted by our lab

因為學校提供的防毒軟體一直不能有效防毒掃毒,所以實驗室去採購了一套叫做 NOD32 的防毒軟體,台灣的官方網站在此: http://www.nod32tw.com/home/home.php

偵測速度、準確度都相當好,獲得多項認證與評比的第一名。此外,不僅安裝檔案小 (12MB 左右),而且安裝完後常駐於 OS 中,卻不會像其他防毒軟體大幅拖慢電腦效能。

將 NOD32 安裝至實驗室的 Notebook 後,偵測並清除了 3 隻木馬。隨身碟裡面也抓到一隻「不明物體」。這些該死的病毒終於被掃掉了。

Thursday, June 14, 2007

Some websites for training English comprehension

看起來應該是很有趣。好學又好玩是最好的學習工具了。


Delving into the implicit ideas and concepts

老師今天又找我談了一下 paper 的事情,給了我一些新的想法。同時也由衷地建議我,既然要做這個題目,就該把問題的環環扣扣弄清楚。像是這幾次老師一問我問題,我就遲疑許久,這樣子太糟糕了。

對於這個問題,前人在 deterministic fixed-parameter algorithms 上的結果,說不定還是可以再加以改善。前提是,我得針對他們發現的性質完全瞭解清楚才行。而且重點不在了解「更多」,而是在了解的更「細膩」。關於 quartet topology 與 consistency 的部分,要非常了解才行,不能老是只在前人的 lemmas 與 theorems 的表面上做文章。

所以說,除了繼續改那篇 paper 以外,我需要再更深入去研讀 Bandelt and Dress 1986 年的文章,希望能發現新的性質,或是有一些新的想法。

Wednesday, June 13, 2007

Missing my wife

每每離開老婆,回到學校,就特別想念跟老婆相處的日子。學校的壓力一來,特別感到難受和孤獨。

真希望趕快有一個屬於我們倆的住處。等明年從德國回國,在台南或是嘉義租個地方住在一起。

The problems of my writing

現在真覺得寫 paper 是一件困難的事,尤其是「寫作」方面。老婆常說我表達能力不好,因為我老是會錯意,我也常講出與我初衷不太一樣的話。

除了寫作的表達不夠嚴謹精確以外,對於現在的研究主題,我更應該多多去了解背後的意義。譬如人家的定理,不能只是在定理的文字上做表面的了解,還得深究其背後的意義與相關的延伸想法。

老實講,我覺得 Gramm 和 Niedermeier 寫的這一篇文章真的是讓我吃足苦頭。除了我的寫作表達能力不佳之外,他們的論文寫的不夠清楚也是讓我寫這篇 paper 這麼辛苦的主要原因之一。

BFS? Bigger-faster-stronger?

今天政螢學弟問我 BFS (breadth-first search) 的 complexity,我就 Google 了一下找答案。有你的,第一個找到的東西居然是:


Bigger - Faster- Stronger

有你的!


話說回來,BFS 的 time complexity 是 O(V + E),對於 graph traversal (or searching on a graph) on unweighted graphs 也是一個 optimal algorithm。

Monday, June 11, 2007

論楊宗緯事件 (About Aska-affair)

原本每個週末陪老婆看超級星光大道看得很高興,這幾週以來卻陸陸續續發生一些事情,讓原以為再簡單不過的節目,現在卻變得十分複雜。 PTT 的鄉民們一陣撻伐,媒體的大肆渲染與報導,造就了台灣當前最熱門的楊宗緯事件 (我稱為 Aska-affair)。

我覺得楊宗緯錯在不該謊報年齡,更不該為了圓謊而撒更多的謊。但是,我以為這都是可以原諒的錯誤,而且畢竟他終究公開認錯了。 Roger 老師說的對,Aska 錯過了承認錯誤的時機,但是先姑且不論「為什麼錯過」這個認錯的時機,有許多鄉民義憤填膺地嚷嚷著,秀出假身份證影本是偽造文書的的嚴重違法行為 (事實上好像並不到違法的地步,有待專家確認),然後一堆鄉民更是一窩蜂地想當「名偵探科南」,欲探究背後的真相。再加上媒體的大幅報導,把整件事情搞得一發不可收拾。我想問,事情真的有那麼嚴重嗎?

今晚我看到 TVXS 的新聞報導,關於 Aska 到節目現場認錯與宣布退賽之事。主撥居然加上了自己的情感和意見,硬要說是「…為了節目的效果…」。ㄟ!妳搞屁啊!妳撥就撥,幹嘛加油添醋的!新聞報導真的不應該這個樣子。你報就報,不該加上自己的意見來煽風點火,誤導社會大眾。

除此之外,我覺得這個社會真的病了。病得不知不覺,而且病得不輕。

沒錯,每個人都有知的權利,也有權利反映自己的意見。但是大家怎麼看似都從「人性本惡」的觀點出發?不知道這個社會是怎麼了,現在每件事情似乎都要先從它的黑暗面看起,然後又擺出一副自己十分正義的樣子,這又是怎麼回事?節目做不好就批評人家不會做節目、主持人毒舌什麼的;節目收視率高就說人家作假,一切都是為了節目的效果和收視率。反正,所有的事情都是不好的,都是黑暗的,似乎只有開口批評別人的人最崇高。

Aska 謊報年齡,就被搞得好像他犯了什麼滔天大罪,欲置之於死地才肯罷休。台灣的媒體真是令人嘆為觀止。唉…希望 Aska 可別因此放棄唱歌,無論如何,都要度過這一關。

Sunday, June 10, 2007

Ken Griffey Jr. is getting hot

話說小葛瑞菲 (Ken Griffey Jr.) 與藍迪強森 (Randy Johnson) 是我小時候的英雄 (以前我是 Seatle Mariners 的球迷),最近兩人的表現都開始加溫了。據說小葛的揮棒速度曾經是全 MLB 最快的。大約 3 年前我還買了「小葛瑞菲 - 投手永遠的夢魘」這本書來看,不過這本書只記載他 1999 年以前的表現,近 8 年來的成績並無法由書上得知。

近年來他受傷新聞不斷,使得他打破 Hank Aaron 的 755 HR 紀錄的可能銳減。不過,誰說他不能像 Barry Bonds 一樣老來俏呢 (只要他守備不要拼過頭又把自己弄傷、跟小孩玩耍時注意安全就好) ?希望在今年,他能平平安安地打完大部分的比賽。

至今日為止,他已打出 15 支 HR,目前生涯全壘打數累計為 578 支,其他打擊成績請見此連結)。看來今年目前為止的狀況真的不錯,再加上他後面的第四棒 Adam Dunn 也是驚人的強打者,應該可以保護小葛。

Saturday, June 09, 2007

After the wedding

成大的尚聰學弟問我說,結了婚以後有什麼不一樣嗎?

其實,我發現我結了婚以後,人長高了一點,變帥了一些,人也聰明了很多,考試都得一百分呢!

不知道這個回覆他滿不滿意。

Distinguishing two graphs by a probabilistic oracle machine

我最近在研讀 Goldreich 與 Trevisan 所合著的這篇 paper:

Three theorems regarding testing graph properties
[Goldreich and Trevisan; RSA 2003]

裡面提到一個很重要的東西,叫做 ε-biased sample space (*)。這個跟一般的 uniform sample space 不一樣的地方在於,每個 element 被取到的機率不是均等的,會有一點誤差,而誤差範圍在 ε 以內。

M 表示一個只能做 o(N^2) 次 queries 的 probabilistic oracle machine。M 擁有的 oracle 即為 input graph,令其為 G,我們假設 query G 中任兩點有無邊相連可在 constant time 得知。假設 R_NN 個點的一個 random graph,而 G_N 為依據 ε-biased sample space 所造出的 graph,Goldreich 與 Trevisan 證明了底下事實:

| Pr[M^(G_N) (N) = 1] - Pr[M^(R_N) (N) = 1] | is less than 0.1

簡單來講,就是說不夠多的 queries (i.e., o(N^2)),無法區別出 G_NR_N;亦即對於給定的 graphs G_NR_N,此 machine accept 他們的機率值差距非常小。

這式子和它的證明困擾了我許久。後來我發現原來是我漏掉了作者的一些敘述。作者給定一個合理的假設: M 可以丟一組 (或「一個」丟好幾次) 自己的 (公平的) 銅板,然後根據擲銅板的結果來對 oracle 做 query,並且每次 query 還能知道並參考前面的結果 (此即"adaptive")

M 擲銅板後所決定的 queries 會得到一組 "有邊 (1) 或沒邊 (0)" 的答案 (i.e., 一組 {0,1}-sequence)。如果 graph 為 R_N,則這些答案出現的機率是均等的。但是如果 graph 為 G_N,根據 ε-biased sample space 的定義與性質,這些「答案」出現的機率就會有一點偏差,但是偏差得十分有限。同樣一個 machine M,根據每一組 queries 的結果來決定要不要回答 accept。

a_i, where i = 1, 2, ..., 2^t, 表示每一種 t-query 的答案,且令 a_i 在 input graph 為 G 的條件下發生的機率為 p_G(i)。令 b_iM 在得到 a_i 後 output 為 accept 的機率。則 | Pr [ M^(G_N) (N) = 1 ] - Pr [ M^(R_N) (N) = 1 ] | 就可利用下面式子來估算:

|\sum_{i=1}^{2^t} [p_(G_N)(i) - p_(R_N)] * b_i | <= ε * 2^t

因為 paper 中把 ε 設定為 0.1 * 2^{-t},所以上式可以得到至多為 0.1。

我想,至少對於想要或正在讀這篇 paper 的人而言,這樣子應該是清楚了。不過 Trevisan 寫的 paper 一直都蠻困擾我的,到現在我問他的問題,他始終沒有回覆我。


(*) 參閱 Joseph Naor 與 Moni Naor 合著的 paper : "Small-bias sample space: efficient constructions and applications",發表於 1993 年 SIAM Journal on Computing, Vol. 22

Glancing the Prime Number Theorem (PNT)

昨晚因為頭暈又覺得有些煩,就到誠品書局逛逛。我特意翻了翻天下文化出版的的一本科普書:

質數魔力 (上、下)。(Prime Obsession - Bernhard Riemann and the Greatest Unsolved Problem in Mathematics, Author: John Derbyshire (中譯為德比‧夏爾))

為何會想翻這本書?因為日前讀到 Szemerédi's theorem 時,裡面有 upper and lower asymptotic density (或稱為 Natural density) 的概念 (定義可見 Wikipedia)。令 S = {1, ..., N} , N 為一個正整數。顯而易見,當 N 趨近於無限大, S 即為所有正整數的集合。Wikipedia 對於 natural density 給了一個例子:

N 趨近於無限大時,S 中質數的 natural density (or asymptotic density) 為 0。

言下之意,質數在正整數當中分佈得很稀鬆。因為這概念並不直覺,所以到了誠品書局,看到天下文化這本科普書,就順手拿來翻閱一下。沒想到想要證明正整數中質數的 natural density 還真不容易,因為我們必須要會估算 "小於 N 的正整數中質數的數目 "。雖然這比 Riemann zeta-hypothesis (看似)稍微簡單一點,但是同樣困擾了數學家很久 (直到 1896 年才被 Hadamard 與 de la Vallée Poussin 解出)。

那到底小於 N 的正整數中有多少質數呢?令所求為 π(N),則

π(N) is approximately N/log(N)


此即大名鼎鼎的 Prime Number Theorem (PNT) 。無怪乎正整數中質數的 natural density 為 0。這也說明我似乎誤解了 Luca Trevisan 某篇文章中的意思。

Friday, June 08, 2007

Kuo had no luck for winning?

碼的!我真的是很生氣!後援投手 Broxton 居然最後一局搞丟 5 分。球速飆到 100 mph 又怎樣?

我想郭泓志本身應該不會生氣,但是台灣的鄉民們,甚至全世界的鄉民們,現在一定剿聲連連。

唉。郭泓志的球運的確是不太好。

Thursday, June 07, 2007

Study schedule about graph property testing

我想我得列出一個 schedule 來研讀 "我所需要的" property testing papers。

  • Three theorems regarding testing graph properties [Goldreich and Trevisan; RSA 2003]
  • Testing graph properties closed under induced subgraphs
    • 詳見 [GT03], [Alon and Shapira; STOC'05] and [Alon and Shapira; FOCS'05]
  • Understanding Szemerédi's regularity lemma and Szemerédi's theorem
    • Szemerédi's regularity lemma 用在 testing in dense graphs
  • Testing k-colorability [Alon, Krivelevich; SIDA 2002]
  • Testing graphs for colorability properties [Fischer; RSA 2005]
  • Testing bipartiteness [Ron; lecture note]
要先找的 papers:
  • A combinatorial characterization of the testable graph properties: it's all about regularity. A. Shapira, STOC'06, pp. 251-260.
  • A characterization of the (natural) graph properties testable with one-sided error. N. Alon and A. Shapira, FOCS'05, pp. 429-438.
Remark:

如果說 "Monotone graph properties are the properties closed under removal of edges or vertices",而 "Hereditary graph properties are the ones closed under removal of vertices"。若一個 graph G in H,則 G 不一定 in M。反過來說,若 G is in M,則 G 必 in H. 所以

Note: Asaf Shapira's talk

Speaker: Asaf Shapira

Noga Alon's Ph.D student
homepage: http://www.math.tau.ac.il/~asafico/


Title: A Charaterization of the Testable Graph Properties
Link: (CLICK HERE)


我所領悟的大意是,許多 Testable graph properties 可以看(轉)成 partition problems,因此跟 Szemerédi's Regularity Lemma 脫不了關係。

另外,很多我所知道的 testers 都是 nonadaptive and oblivious,因為這些 testers 在 query 時不用知道前面 query 的結果(一口氣把所有該 query 的 query 完)而且不用知道 input graph 的 size。

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

今天看了 (upper/lower) asymptotic density of a set of natural numbers,接下來可以試著把 Szemerédi's theorem 弄得更加清楚。

Wednesday, June 06, 2007

Training quadriceps femoris by leaning on the wall

昨晚睡覺前又嘗試一下大腿靜力的練習 (想像圖可參見此連結),沒想到一口氣做了 5 分鐘整,比起上回多做了 1 分半,相當嚇人。聽說職業的滑雪選手可以超過 5 分鐘,看來我的大腿肌耐力有顯著提升了。

不過,有學弟跟我說這對於跑步一點用也沒有,我想不見得吧。或許沒有直接相關,但是總是有益的。(都已經是大腿股四頭肌了,不可能完全沒有用吧。)

不過,我的問題還是在大腿二頭肌啊!想辦法解決左腿的問題還是最重要的。

Solving problems and studying papers

最近好不容易看了一篇 Goldreich and Trevisan 寫的 paper:
Three theorems regarding testing graph properties. Oded Goldreich and Luca Trevisan, Random Structures and Algorithms, Vol. 23 (2003), pp. 23-57.
通常看到這兩個人都要敬禮的,沒想到我還是硬著頭皮去看了他們的著作。我想,要做 property testing 相關的研究,至少得精讀幾篇這樣 papers 吧。

Parity of a 0,1-sequence

The parity of a 0,1-sequence s is the sum of the sequence.

假設 s = 101001,則 s 的 parity 為 1 ,因為 1 + 0 + 1 + 0 + 0 + 1 = 1 (over {0,1})

因此,有人用 exclusive-or 的運算來表示,或者直接用 sum 來表示,意義都是一樣的。也就是說,若一個 0,1-sequence s 中奇數個 1 ,那麼我們就說 s 的 parity 為 1,反之為 0。

Saturday, June 02, 2007

DAAD ? Deutsches Institut Taipei ? NSC ?

DAAD : Deutscher Akademischer Austausch Dienst,即「德國學術交流總署」。我們的 Sandwich scholarship 就是他們與台灣的國科會一起出資協助的。

Deutsches Institut Taipei: 德國在台協會。辦理簽證與英文版戶籍謄本正本(依親簽證需要)的公證事務,都要尋求他們的幫助。

NSC : National Science Council,即台灣的「國家科學委員會」,簡稱「國科會」。發放獎學金以及三明治計畫學員在住宿與生活上的協助,都需要他們駐德國的科技組幫忙。

Submitting the applications for the visa

May 31 凌晨,我和老婆搭早上 5:40 的車,前往台北德國在台協會一起申辦我們的「獎學金簽證」以及「依親簽證」。前一天晚上,台銀的 ATM 不讓我刷簿子,真是嚇了我們一大跳,還好我們去台北的台銀補登成功,才不至於白白跑一趟。

我們在 May 31 早上先到公證組去公證老婆的英文戶籍謄本(好貴好貴,戶政事務所蓋幾個章要 NT. 750,而德國在台協會公證組蓋一個章也要 NT. 890 !!)。下午我們到簽證組準備送簽證申請表,那兒負責承辦的賴小姐說,老婆前往德國的理由可以寫「依親」就好,因為我們不會寫(用英文?德文?反正不確定該怎麼寫),所以賴小姐好心幫我們填好。不過老婆的照片看起來不像是三個月的近照(但是現在看起來像小朋友耶 ......),所以我們趕去最近的相館跑了一趟,還好可以立即取件(我還順便買了兩組大樂透號碼),趕的及在下午三點前回來補齊所有的文件。