Thursday, December 27, 2007

Christmas party at Peter's office


在 12 月 19 日這天,是 Professor Rossmanith 實驗室的同仁舉行 Christmas party 的日子。我們大夥兒留下這張合照。雖然說閃光燈拍出來不夠好看,但是可惜這也是最好的一張了。以下則是我們準備的聖誕禮物。

咦?花生麵筋?


開玩笑,我們準備的花生麵筋絕對是當晚禮物排行榜的前三名(比起疑似過期的茶包、融化後有死蒼蠅的糖果好太多了)。


Two men from TNFSH 南一中同學哥倆好

以下照片拍攝至上週的布魯塞爾 (Brussels) 一日遊。

照片中這兩個人都來自台南一中的,不過幹嘛搞曖昧呢?


丁丁流行到國外去了 (白色部分是小雪粒)


尿尿小童穿聖誕裝。誰看的出來這是尿尿小童啊?



Brussels 的五十週年紀念門 (Arcade du Cinquantenaire),看起來跟 Berlin 的布蘭登堡門 (Brandenburger Tor) 很像。


Wednesday, December 26, 2007

Tuesday, December 25, 2007

我在想問題 - I'm thinking problems

我有時候就算想要思索一個問題,卻常茫茫然不知從何著手。現在自己理出頭緒的能力慢慢開始建立起來,至少像是一隻有頭的蒼蠅,不會撞得滿頭金星。把解決大問題的步驟細分下來之後,就可以把問題「帶著走」,甚至是「帶著跑」。以前有學弟跟我說跑步時不適合也不該想問題,那我只能說他總是跑的太快了。

可是要集中心力在一個問題上,至少對我來說不是一件容易的事情。等我開始可以進入狀況了以後,我才理解為什麼會有在數學家搬了新家之後卻忘了自己回家的路,還要自己的小女兒帶他回家的糗事。所以我覺得在公車上、走路時其實都可以訓練自己集中在一個小問題上。久而久之大腦會習慣這樣的生活方式。

我想,這也是為什麼我常常做出一些糗事的原因之一吧。但這可不是一件值得驕傲的事情。

在車上也可以做研究。正在寫演算法中......

To have substance in Speech

看了 BarrosH 的 blog,真的覺得我書看的太少。我的文章就算再寫也沒有很高的可讀性,因為從根本上就是沒有內涵。沒有內涵的原因為何?就是「書讀的太少」。

老師不只一次跟我們強調,要多看閒書。當然他說的「閒書」絕對不是漫畫和言情小說這類的書籍,而是市面上可以買到的通俗讀物,譬如科普書、介紹世界情勢的書、金融理財的書以及與生活相關的書等等。多看書,才能言之有物。看了 BarrosH 的 blog 之後,真的覺得不只是我文筆的不好,而且是個人素養的差異。

以後我們將會是國家社會的菁英份子,要能有自己反思與提出個人見解的能力。所以要多充實自己,行有餘力還要能有自己的想法見解。如果成為書呆子,那還有機會產生有用的 output,如果連書呆子都當不成,那麼一個沒有內涵的人,是很難講出什麼道理的。

Read something meaningful, and then do something useful.


以此句勉勵自己。

Tuesday, December 18, 2007

Call for papers (IWPEC 2008)

Hyperlink: http://www.csc.uvic.ca/iwpec2008/cfp.html

Call for Papers:

The International Workshop on Parameterized and Exact Computation covers research in all aspects of parameterized and exact computation and complexity, including but not limited to: new techniques for the design and analysis of parameterized and exact exponential-time algorithms, parameterized complexity theory, relationship between parameterized complexity and traditional complexity classifications, applications of parameterized computation, implementation and experiments, high-performance computing and fixed-parameter tractability. The goal is to present recent research results, including significant work-in-progress, and to identify and explore directions for future research. The two previous workshops were held in Bergen, Norway (2004), and Zurich, Switzerland (2006). The proceedings appeared in the Springer LNCS series, volumes 3162 and 4169. IWPEC 2008 will be colocated frontend with ACM STOC 2008 held from May 17 to May 20. The proceedings of IWPEC 2008 are expected to be published in the Springer series Lecture Notes in Computer Science.

Submissions Authors are invited to submit an extended abstract in English no longer than 12 pages using at least 11-point font describing original unpublished research. Simultaneous submission to other conferences with published proceedings is not permitted. Additional details as necessary may be included in a clearly marked appendix that will be read at the discretion of the program committee. Instructions for electronic submissions will be posted at the conference web site. Authors unable to submit electronically should contact either of the Program Co-Chairs. Accepted papers are expected to be presented at the workshop.

Important Dates

Paper submission deadline: January 4, 2008
Notification of acceptance: February 14, 2008
Final version of accepted papers: March 3, 2008

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

Information for LNCS Authors: Click here



Saturday, December 15, 2007

When and how do I become a master? 老師要我趕快出師?

哈,老師今天跟我說希望我趕快能夠有辦法自己找問題、自己解問題。他說,希望我能趕快出師,不用讓他還要帶著我一步一步想。哈,我也很想啊。

我有很多時候陷入思考的泥沼,思考的盲點。自己要好好「想想」,我是怎麼「想」的。我常常費了很多勁,把思考精力花在不是很重要地方,或是看不出問題點在哪裡;經常思考茫然不頭緒,沒有脈絡。這些都值得好好檢討。

不曉得是不是大家都跟我一樣,一直訓練的是「理解」的能力,而思考解決問題的能力卻一直很弱。也就是說,看了一堆大師的 paper,但是自己寫不出一篇像樣的 paper 來。不過,我覺得至少我在寫作上有明顯的進步了,因為沒有像上次那樣寫出一篇到處是問題 (甚至是邏輯上的問題) 的 paper。

怎麼想?往哪裡想?要想什麼?要解什麼?什麼東西是重要的?......

Thursday, November 29, 2007

國科會-DAAD三明治計畫第一次期中報告 (Midterm Report for NSC-DAAD Sandwich Program)

國科會-DAAD三明治計畫第一次期中報告

林莊傑

國立中正大學資訊工程研究所

中華民國九十六年十一月三十日


摘要

本報告主要包括申請人於三明治計畫之申請與申請德國簽證之注意事項,以及自九十六年九月初抵達德國至十一月底為止,申請人在這三個月內之德國生活體驗與初步研究成果。

Guten Appetit!

今天學到了一句實用又有趣的德文:

Hier gibt es Köstliche Speisen. Guten Appetit!

意思是:
美食當前,請慢用!(祝您好胃口)


Monday, November 19, 2007

Writting a paper by a program

因為最近要寫一篇 paper,便嘗試去寫了一個簡單的 C++ program。又因為 paper 可能需要把程式的結果做成表格,於是我又稍微修改了程式,讓它能列印出 LaTEX 表格的模式。譬如輸出就像這樣:

\hline a & b & c \\
\hline d & e & f \\


這樣子我就不用一行一行去貼,省了不少時間。原來也可以寫一個程式去幫忙自己寫 paper,真是有趣極了。不過把一個 243 行的表格貼進一篇 paper 裡真的有點怪,看看 Peter 和老闆有什麼建議吧!

Friday, November 16, 2007

A funny picture (Peter 入鏡了)


上禮拜跟 Professor Rossmanith 以及其他 group members 出遊,老婆意外地拍下這張好玩的照片。笑點應該在右邊的 Peter 上面。

那天真是冷死我了。


Tuesday, November 13, 2007

Working & Running in RWTH-Aachen

我和 Ling-Ju 現在待在 RWTH-Aachen 的一間 Office 做研究,Professor Rossmanith 給了我們兩台 PC 使用,而老婆在上德語課之前也可以來這邊作陪; 她上她的網,我想我的問題、看我的 paper。這間大大的辦公室就只有我們三個人使用,離我們辦公室 30 公尺不到就有一個茶水間,可以泡咖啡喝或是微波食物來吃。

Professor Peter Rossmanith 是 Linux 的愛用者,想當然不會幫我們安裝 Windows,所以我和 Ling-Ju 得慢慢習慣用 Linux OS 做事。一開始一些問題,譬如說我沒辦法使用隨身碟、無法聽音樂,這對於我真的是很不方便,不過 Peter 總是來問我們有沒有什麼問題,也樂於幫我們解決麻煩事,所以至少現在可以一面聽音樂一面做研究,隨身碟也能使用了。

Aachen 這城市遠比 Bonn 繁榮,也有我們難得一見的夜生活。買生活用品的話,我們可以去 附近的 Kaufland (購物王國); 此外,也可以去市中心的土耳其商店買米和超大的高麗菜。等到申根簽證下來我們還可以坐公車到荷蘭的 Vaals 買菜。其實,在 Aachen 生活還算蠻方便的。

RWTH 沒有 PU 跑道倒是令我有些驚訝,因為畢竟這學校算是重點大學,經費應該不會少。Peter 問我說,難道跑道不夠軟?跑道有軟是沒錯,不過 Aachen 超級常下雨,跑道會容易泥濘,這樣就不好跑了。說到跑步,現在天氣愈來愈冷,氣溫現在都只有攝氏 2-8 度,再過一陣子就要零度上下了,如果只穿一件長袖的排汗衫,我真的會凍未掉。此外,跑步血液都往心臟和雙腿集中,要是沒有戴手套的話,我的手掌到頭來簡直就是結凍了!最近,我和老婆逛街時買了一件防水防風的風衣,再加上之前買的手套以及從台灣帶來的熱身長褲,跑步應該是沒問題。現在只希望天氣好一點,讓我可以在住處附近的山坡跑步,要不然至少不要下雨,下雪不是漂亮多了嗎?

明天要跟 Peter 報告新的 fixed-parameter algorithm,他說不用太緊張,只要跟他們稍微介紹一下就好,也不需要特意準備投影片,可以在辦公室的白板上面畫圖說故事就好。我想,他們一定也會怕我用 Powerpoint 來講,因為對他們而言,開啟 Microsoft 的檔案真是個災難。

Saturday, October 20, 2007

Minus degree in Bonn

今天早上起床,打開 NB 看到可以上網,趕快點到 World Weather 網站看一下今天的氣溫。沒想到 Bonn 在早上 7 點 20 分居然是零下 1 度。

馬的,冷到小弟弟都快掉下來了。

今天還得跟同學去 Flohmarkt (跳蚤市場) 找便宜貨帶去進修地,那邊地勢空曠,我想一定很冷。

Thursday, October 11, 2007

Haarschnitt - 讓老婆小試身手 (有圖示)

Haarschnitt 就是英文的 haircut。

頭髮長了,是個問題。Bonn 的理髮店很貴,不然就是要去土耳其理髮店去剪,大概可以 € 8 以內解決。

老婆幫我延長了必須要剪髮的期限,因為她親手幫我把鬢角和前額的部分「修」了一下。不過前額的頭髮就像她所喜歡的瀏海一樣,變得很齊。從側面看起來,有一種很特別的美感。

我覺得還不錯啊,她倒是笑翻了。不管怎樣,她的第一次剪髮算是成功!也算節省了一點開銷。

目前的頭毛

Monday, October 08, 2007

A trip to Heidelberg - 海德堡照片

話說來到德國,不去一些景點實在對不住自己。上面這張是在九月底時,我和老婆去 Heidelberg 海德堡時所拍下的照片。這城堡從這個角度看起來蠻壯觀也挺漂亮的。目前看到的德國城堡或是教堂,上面都刻了一堆人像。

與可愛的老婆和壯麗的城堡合影


Sunday, October 07, 2007

近日雜感

每天睡覺和上網時不會有身在異鄉的感覺,其他的時間我必須得「說服」自己,我現在在德國。

目前我已經蠻適應這裡的生活,不管氣候、U-Bahn (地鐵)、DB (德國國鐵)、Bus 或是各式各樣膚色的人們,我已經處之泰然。不過,本來就應該是這樣子,不是嗎?

但,我還是很想念台灣。

Saturday, October 06, 2007

My address in Aachen (Oct 27, 2007 - Aug 31, 2008)

Steppenbergallee 221, 52074 Laurensberg, Aachen, Germany

Google map:

檢視較大的地圖

現在的住址:
Spiegelhofstraße 4, 53173 Plittersdorf, Bonn, Germany
Google map:

檢視較大的地圖

Thursday, October 04, 2007

My first time to listen the Orchester

撇開以前聆聽的南一中管弦樂演奏,這一次參加的 100 Jahre Beethoven Orchester Bonn ,是我生平第一次參加的正式管弦樂演奏。我們夫妻倆和其他的三明治學員一同參加,而且因為我們已經註冊為 Bonn 的市民,所以可以免費拿到入場卷,否則,據說票價大概要 € 40,約 NTD. 1800,算是大大地賺到了!


入場卷


這是紀念貝多芬 (Ludwig van Beethoven) 的音樂會,目前舉辦至今年為一百週年,所以格外有意義。演出的時間為 10 月 3 日 晚上 7:00 - 9:00,演奏貝多芬的某個作品,反正跟我講我也不懂那是啥。總共有四個樂章,令我和老婆訝異的是,我居然都沒有打瞌睡。因為我不懂管弦樂,所以我說不清楚哪裡好,不過,我是第一次深深地感受到管弦樂的動人和精彩,跟電視上和 CD 上聽到的感覺差別非常大。

Saturday, September 22, 2007

"Ich esse viel Essen gestern Abend und heute" & My feelings now

昨天與 DAAD (德國學術交流總署)聚會,突然間說要從我和俊榮這邊開始作自我介紹,連打草稿都來不及的情況下,俊榮講得很好很順暢,我的自我介紹就變得有點搞笑。後來 DAAD 向我們介紹 DAAD 的組織與其目標,由申請開始講起,一直講到回國之後的聯繫。推廣德語是 DAAD 極重要的使命,從我們三明治學員必須參與 Goethe-Institut 兩個月的德語學習這點就可以清楚看出。此外,他們也希望德國能夠更加「國際化」,所以也會鼓勵德國的學者出國交流。DAAD 合作的國家,目前亞洲國家佔了相當大的比例。

Wednesday, September 12, 2007

Life in Bonn, Deutschland

http://www.wretch.cc/blog/maggiedonut&article_id=19558500

http://www.wretch.cc/blog/maggiedonut&article_id=19478314

因為很難上網,所以把老婆的文章連結轉來這裡。

我病了有好幾天了,喉嚨痛、流鼻水、鼻塞、頭暈都有。 Ling-Ju 今天也說她的喉嚨很痛。現在三明治學員至少有五個人感冒了。好在總算可以用保險看病了。

希望感冒趕快痊癒,不然真的挺難熬的。


Tuesday, September 04, 2007

The first two days in Bonn

德文不簡單,而且Gothe Institut 的進度很快,每天上課時數又長達 4-5 小時,使我感到學德文真的很累。

現在要解決的問題是:

  • 旅支匯入歐元帳戶。
  • 水水水....
  • 手機 SIM 卡

Saturday, September 01, 2007

The last night at Taiwan in 2007

明天 (Sep 2) 的行程:

  • 11:00 搭和欣客運從台南出發。
  • 19:20 搭乘國泰航空先飛往香港。
  • 23:50 自香港赤臘角機場飛往德國法蘭克福機場。
所以今晚是2007年留在台灣的最後一晚了。心裡有點忐忑不安還有忑忐不安。不管怎樣,還有老婆陪著,心裡至少踏實一點。之後的日子要過的十分規律,做研究、跑步、假日出遊,一切都要有規劃。記得不能亂花錢。

Monday, August 20, 2007

Research notes

現在知道在 worse case 之下,一個 quintet 至少需要改 3 個 QT 才能 consistent。這個結果不但可以從例子中觀察出來,我也已經確定可以用以符號邏輯嚴格地證明它的正確性。
總之,就是可以用「證明」的,而不是靠暴力列舉。
那麼現在要努力朝 sextet,甚至 septet 去想。想辦法針對 quintet 的結果加以推廣。

6 個 taxa involves 5 quintet,所以可以先 fix 一個 quintet,再思考第 6 個 taxon 插入的情形嗎?這是一個方向。

可能需要自己推一個類似 substitution property 的性質出來。

此外,6 taxa 有 15 個 QT,所以所有可能的 input Q 有 種。而擁有 6 個 taxa 的 evolutionary tree 只有 105 種。

目前先想到這樣。

Plane on fire at Japanese airport - by BBC news

http://news.bbc.co.uk/2/hi/asia-pacific/6954397.stm

沒想到華航客機在日本那霸機場著火的新聞居然登上了 BBC breaking news

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

A Taiwanese China Airlines plane has caught fire at an airport on the southern Japanese island of Okinawa.

TV pictures showed the Boeing 737 passenger plane on the tarmac with huge flames and smoke billowing from it, as firefighters doused the fuselage.

A Japanese transport ministry official said all the passengers had left the aircraft before the fire started. There were also no crew members on board.

The plane had flown in from Taipei with more than 150 passengers on board.

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

政府要我們三明治學員搭乘華航的班機前往 Frankfurt,覺得有些不是滋味。

Sunday, August 19, 2007

The first Valentine's Day since the marriage

這幾天來了一個強烈颱風,打亂了這禮拜的情人節計畫。應該說,好像也沒什麼計畫,這樣子真糟糕。老師說,兩人在一起的時間雖然短,但要過的品質要高。但是在這麼一個颱風天,有什麼品質可言呢?

不過老婆還是抽出了時間搞了一個小小的驚喜,真是令我汗顏。她對我總是包容,讓我很感動。希望今天等今天風雨變小之後,還有機會帶她去晃晃,抽時間到外頭來過個節。

Happy Chinese Valentine's Day, my dear wife. Thank God for bringing you to me.



Wednesday, August 15, 2007

After meeting with boss today

有幾項事情要做。

大方向:
  • 學著規劃好時間。與妻子 (家庭) 的相處時間短但品質要好。
  • 目前我吸收學問的訓練夠了,但是我的解決問題的能力非常不足。
  • 想解決問題的辦法前,先想想「該想什麼」、「目的為何」,不是茫茫然亂想。
  • 多去 conjecture,然後加以證明之。
  • Survey 文獻的速度要快!
  • 想辦法讓每天都能有所進展。
細節:
  1. 對於 NP-C 的 graph decision problems 而言,survey 其對應的 graph modification problems 與 property testing problems。
  2. 觀察 quintet、 quartet topologies、 consistent trees 的「結構」。
  3. consistent 的 trees 數量佔所有可能的 topology sets 的比例非常之小。
  4. 對於一個 quintet,光看其中 induced 的 3 個 topologies 就可以知道這個 quintet 是否 consistent?
  5. 當存在一個 quartet error 不在任何一個 local conflict (consistent quintet) 裡面時,又是怎樣的情形?
  6. 與志仁討論或想辦法弄清楚 branch factors。



Tuesday, August 14, 2007

Graph minor and some results

如果一個圖 H 可以經由另一個圖 G 做出 vertex deletions,edge deletions 和/或 edge contractions 而得 (不計動作的順序),則我們稱 HG 的 minor。此外,任何圖皆為自己本身的一個 minor (i.e., 不做任何 taking minor 的動作)。

有三個定理如下:

Theorem: (Wagner's conjecture)
For every class of graphs , that is closed under taking of minors, there exists a finite set of graphs, ob(), called the obstruction set of , such that for each graph G, if and only if there is no that is a minor of

Theorem:
For every graph H, there exists an time algorithm, that, given a graph G, tests whether H is a minor of G.

Theorem:
For every planar graph H, there exists a constant c(H), such that for every graph G, if H is not a minor of G, then the treewidth of G is at most c(H).


印象中,minor 這傢伙還蠻常出現在 fixed-parameterized problems 裡頭的(??)值得注意一下。

Studying treewidth of a graph

A tree-decomposition of a graph G = (V, E) is a pair with a family of subsets of V, one for each node of T, and T is a tree such that


  • for all edges , there exists an with and .
  • for all , if j is on the path from i to k in T, then
  • The treewidth of a tree-decomposition is The treewidth of a graph G is the minimum treewidth over all possible tree-decompositions of G.

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

    感覺上,treewidth 好像是一個圖 G 中 最大 clique 之 size 減 1,不知道有沒有反例。另外,clique tree 是 tree-decomposition 的特例,只是多了一條限制:tree 上的每個 node 都是原圖 G 上的 maximal clique。

    如果一個圖的 treewidth 為 bounded,那麼很多原本是 intractable 的 graph problems,就可以在 polynomial time (甚至很多可以在 linear time) 被解掉。譬如: Independent Set Problem, Hamiltonian Circuit Problem, Steiner tree problem 等等。

    在 R. Niedermeier 的 Invitation to Fixed-Parameter Algorithms 一書中提到底下事實:
    For constant k, there is a famous resulting giving a linear-time algorithm to compute whether a graph has treewidth at most k. More precisely, the algorithm has running time
    此外,給定一個 parameter k 與一個圖 G 當作 input,"決定 G 的 treewidth 是否至多為 k " 的問題已被證明為 NP-C [cite: ACP87]。但是,對於任一固定的 k,這問題存在一個 O(nlog n) 的演算法 [cite: R92]。


    [ACP87] S. Arnborg, D. G. Corneil, and A. Proskurowski: Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Math., Vol. 8 (1987), pp. 277-284.
    [R92] B. Reed: Finding approximate separators and computing treewidth quickly. STOC'92, pp. 221-228.

    Sunday, August 12, 2007

    Free classic music radio

    不錯的免費古典音樂廣播,可以在唸書或思考問題時當背景音樂聆聽。

    http://hichannel.hinet.net/radio/radio.jsp?chid=294

    奇美古典音樂網 (無廣告播放古典小品音樂)


    最近真想說:有奇美真好。
    • ViewSonic LCD 由奇美代工;
    • 奇美咖啡館的奇美冰咖啡超好喝;
    • 奇美古典音樂網提供了以往中廣音樂網的古典音樂*。

    * 註: 台北愛樂電台也不錯

    Wednesday, August 08, 2007

    Unlimited for giving comments at this blog now (回應不設會員的限制囉)

    先前我有設定只有 Blogger 會員才能給 comments(回應),現在這項限制已經取消了。

    其實在看 BarrosH 的 blog 時,我早該發現的。過去我怕廣告以及一些類似垃圾信的東西佔據我的 blog comments,但是現在有字詞驗證的工具,所以也就沒必要限制發言者的身份了。

    這兩天下來,我的個人網頁的訪客數比起我的 blog 所吸引的訪客數少很多很多,不過這才像話嘛!之前我寫的計數器簡直是垃圾,現在使用了 counterservis 提供的免費計數器之後,才反映出真正的訪客人數,而且還能加以分析訪客的來源、所使用瀏覽器以及查詢哪些網頁連結至我的網頁或 blog,似乎還蠻有趣的。

    BTW,我老婆質疑我現在所舉辦的投票意義何在。其實,那只是拿來自爽用的。因為我發現 blogger 現在有提供投票的新功能,覺得好玩所以辦一個試看看。如果有什麼有趣的議題,我會再拿出來讓大家一起參與。

    Thursday, August 02, 2007

    Research notes (2 Aug, 2007)



    Then we have,



    Therefore,




    Note: When n is an odd integer, n!! = n * (n-2) * (n-4) * ... * 3 * 1

    Wednesday, August 01, 2007

    Being husband and a wife now...

    感覺上,結了婚覺得沒差別就是有差別。也許就像某一本書上講的,結了婚以後,女孩要變成女人很快,可是男孩要成長為男人卻相對慢很多。我一直認為婚前婚後我會「始終如一」,這樣子的「沒差別」卻是跟我的另一半有著「大大的差別」。

    結了婚以後,大家都是親人了,所以很多事情上的處理態度應該要有所轉變,可是我常停留在婚前那一套,所以常常使馬尾傻眼。因此,我覺得她對我的要求變多了,實際上,是我應該再成熟一點。總之,不能夠以「這是男人的通病」來混過去。我必須在態度和思維上有一些轉變。

    不過還好結婚了,看了很多情侶交往過久最終仍分道揚鑣的悲慘故事,深深覺得自己很走運,早早把馬尾給定下來了。而從結婚前到現在發生了很多好事,我想我更要深深地感謝上帝的帶領,這當中真的有許多說不出的奇妙。

    接下來的工作,就是讓彼此更加幸福而已。

    Monday, July 30, 2007

    [Forward] I Don't Know - by R. C. T. Lee (轉載自July 30, 2007 聯合報)

    我不知道

    http://udn.com/NEWS/READING/X5/3948415.shtml

    【聯合報╱李家同】 2007.07.30 03:29 am


    他永遠是個醜小鴨,因為他知道他其實對很多事情是弄不清楚的。所以他會毫不猶豫地說「我不知道」……

    Saturday, July 28, 2007

    Research notes (k-almost trees)

    其實 k-almost tree 就是一個擁有 n 個點與 n + k - 1 條邊的連通圖。因為 n 個點的 tree 有 n - 1 條邊,所以一個 k-almost tree 比正常的 tree 多了 k 條邊。

    Got it.

    Monday, July 23, 2007

    Route from Steinke Institut to Goethe Institut


    我利用 Google map 規劃了一條路線,也使我更清楚兩地位置的關係。

    http://tinyurl.com/26hnuc





    Sunday, July 22, 2007

    Buying a new NB and a new DC

    為了到德國能方便做研究,我跟老婆在 NTD. 25000 的預算下順利購得 Acer Aspire 5054WXMi 這台 Notebook。在台南的彩虹 3C 商場的科士德電通買到的。負責的銷售員是他們的副店長小李,感覺蠻懂電腦也十分熱心。

    他是 AMD 64bit 雙核心 1.8 GHz 2x512KB L2 cache、1.5 GB 的 RAM、14 吋的寬螢幕、120 GB 的 SATA 硬碟 (轉速 5400 rpm)雖然沒有獨立顯卡,會吃掉一點主記憶體,不過這台 Notebook 主要只是做一些文書處理和上上網罷了,這樣的規格就很爽了。顯示器的上頭嵌了一塊視訊攝影器,雖然可以 225 度轉動,不過還是不要常轉它比較好。

    一開始安裝的 Operating system 是 Windows Vista Home Basic。後來因為店長幫我灌成 WinXP出了一點問題,我回學校拿學校的授權版本再重灌一次試試。沒想到 Notebook 的重灌還真不容易,首先得至 Acer 的官方網站下載需要的 drivers,還要看安裝的 Windows 版本是 for 32 bit 還是 for 64 bit,不然像是 Wireless LAN 灌了也不會正常啟動。著實吃了不少苦頭。

    至於數位相機,我們到青年路上的「新智」去買 Canon S950,也是以 NTD. 14700 的便宜價格購得,包含腳架一大一小(小的是章魚腳)、充電器、1 GB 的 SD 記憶卡等等。老婆直說真是便宜到不行,因為 DC 和 NB 兩個買起來還不到台幣四萬元,比當初預想的花費少了很多。

    Thursday, July 05, 2007

    Farewell! Professor Tzer-Hsiang Huang

    黃教授已經返回多倫多的老家,以後可以在樹林中踏著落葉與師母慢跑了,冬天還要煩惱剷雪的事情,真令人羨慕唷!

    現在中正操場上少了說故事的黃老師陪大家慢跑,感覺味道都不對了。黃老師說,他希望大家一樣都維持慢跑的習慣,也盡量找朋友一起來參與,我們大家盡量努力囉!(九月以後,我在 Aachen 繼續努力 XD)


    大家雨中合照

    Test for LATEX & research notes

    參見:http://wolverinex02.googlepages.com/emoticonsforblogger2

    以後可以在 Blogger 上面編寫漂亮的數學式子了。先來試用這個套件看看吧!

    Try 看看 two to the power of two to the power of two of the power of two:



    今日的 research notes:

    Given n taxa, we have quartets and sets of three quartet topologies.

    與其探討 local conflicts for three set of quartet topologies, 不如把 taxa 5 個 5 個抓來看。我們暫且稱 5 個 quartets 所關連的 = 5 個 quartet topologies 為一個 "local set"。那麼改一個 quartet,會影響多少 local sets 呢?這是我目前要先去想的。

    另外,tree-consistent 的 local set 要改成另一個 tree-consistent 的 local set,至少要改兩個 quartets 的 topologies 才行。


    Wednesday, July 04, 2007

    Windows Media Player 發生內部應用程式錯誤

    最近只要連到需要內嵌 Windows Media Player 的網頁都有 WMP 跑不出來的問題。所幸我 Google 到底下的解決辦法。

    1. 執行 regsvr32 jscript.dll
    2. 執行 regsvr32 vbscript.dll


    然後問題就解決了。看來是VBscript的問題。

    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 !!)。下午我們到簽證組準備送簽證申請表,那兒負責承辦的賴小姐說,老婆前往德國的理由可以寫「依親」就好,因為我們不會寫(用英文?德文?反正不確定該怎麼寫),所以賴小姐好心幫我們填好。不過老婆的照片看起來不像是三個月的近照(但是現在看起來像小朋友耶 ......),所以我們趕去最近的相館跑了一趟,還好可以立即取件(我還順便買了兩組大樂透號碼),趕的及在下午三點前回來補齊所有的文件。

    Monday, May 28, 2007

    The sufficient conditions for winning a lottery with high probability

    最近看電視新聞的分析,滿足底下三項條件者最有希望成為大樂透的中獎者:

    1. 男子
    2. 射手座
    3. 已婚
    哇...現在我已經滿足了這三項條件,尤其是第三項條件,是我最近才順利達成的。依照以往的經驗,不論是猜獎、摸彩、統一發票、大小樂透,我的中獎率都很低,換句話說,就是我的手氣一向很背。現在結了婚,說不定會有所謂的「轉運」喔?

    Sunday, May 27, 2007

    Hide in the library

    今天下午在房間裡猛流汗,實在是凍未住了!只好跑去圖書館躲避悶熱和高溫。這種天氣,身體一直流汗是怎麼唸得下書呢?

    不過NCKU的圖書館冷氣也夠強了!我稍微趴了一下差點就著涼。一來一往的溫差也真大。

    總算,投影片完成了 80% (約 37 頁 ppt slides) ,下週二的 group meeting 可以稍微檔一下了。

    係係雷蒙(C C Lemon)

    老婆似乎對 C. C. Lemon的廣告很有意見。她一直叫我學飛輪海他們的笑容和動作,說是覺得很白痴。

    不過,老婆似乎還蠻喜歡喝這種飲料的。夏天消暑吧!不看廣告就還好。

    死死 雷蒙~ 耶!

    Friday, May 18, 2007

    Remark for P/poly

    有兩個 equivalent definitions: (感謝 BarrosH 的提供)

    • A language L is in P/poly if there is a language A in P and a set of advice strings {a_0, a_1, …} such that |a_i| ≤ i^{O(1)} and x is in L if and only if (x, a_|x|) is in A.

    • There is a family of circuits {C_0, C_1, …} such that |C_i| ≤ i^{O(1)} and for all i and all x = x_1…x_n, x is in L if and only if C_n(x_1, … , x_n) accepts.

    另外,也可參考 wikipedia 那邊的定義與Prof. Fortnow 那邊的定義

    好久沒碰 computational complexity 了,感覺頭腦頓了不少。不過在與 B 大討論完後,感覺上就是說,根據每個 nonnegative integer i,我們去造一個 advice string a_i 或是 Boolean circuit C_i,只是這 string 或 circuit的大小不會太大。稱呼這些 advice strings 或 circuits 為 non-uniform,不是在於統計上的意義,而是我們無法保證在 polynomial time 內利用 a_i (resp., C_i) 去造出 a_{i+1} (resp., C_{i+1})。接下來對於 input x,我們就根據 |x| 去找對應的 advice string a_|x| 或 C_|x| 來幫忙回答問題。

    B大真強,搞得蠻清楚的。而且不厭其煩地回答我的笨問題,令我真是感激不已。以後要稱他為 B 神了。

    Thursday, May 17, 2007

    Our notarial marriage in Tainan

    May 12, 2007,於台灣台南地方法院舉行的公證典禮上,我和 Maggie 總算是有情人終成眷屬,結成了一對夫妻。雖然稱呼彼此為老公老婆仍然不習慣,但是我想久了就OK吧。


    既興奮又緊張


    其實公證結婚典禮並不「隨便」,比我想像中隆重許多,中間的程序還蠻多的。一開始由一對對的準新人從中間的拱門入場。我聽朋友和岳母說, Maggie 是眾新娘中最耀眼的一位(至於我,大概是裡面最憨的吧)。中間過程當中,法官會詢問各新郎新娘願不願意娶或嫁給對方。當她叫到我名字時,法官居然找不到我,害得我得向他招手,搞的大家哈哈大笑。在我大聲回答「我願意」後,接下來她問 Maggie 願不願意嫁給我為妻子,我當時還真害怕她說「我不願意」。還好一切順利,沒有出槌。

    重頭戲當然就是新郎新娘互相行鞠躬禮,然後親吻對方。此時,相機閃光燈閃個不停。最後,由法官宣布各對新人正是結為夫妻。接下來的工作,就只剩去戶政事務所辦理登記了。


    (左起)佳鈴,齡儀,老婆,我與博文


    這一天,我爸爸、媽媽、奶奶還有弟弟威良都出席了,老婆那邊的家人出席的則是她的弟弟妹妹和岳母。雖然過程中有些小小擔心,因為兩家人還不是很熟識,不過婚禮總算是順利完成了,開開心心地結成親家。婚禮後,我們夫妻倆就帶大家到韓承館吃一頓大餐。希望大家都能有美好的回憶,也十分謝謝大家的祝福。


    (左起)怡伶、瑞軒、岳母、老婆、我、淑萍、美伶


    (左起)我奶奶、我爸、老婆、我、我弟威良和我媽


    Wednesday, May 16, 2007

    Midterm 2 of Discrete Mathematics

    May 15, 2007 舉行了 Discrete Mathematics 的第二次期中考。題目如下:



    我拿相機到了教室拍了幾張照片。題目稍微有一點點難度,但希望同學們都能考得不錯的成績。


    教室前面是我們偉大的助教 & 帥氣小鼓手林志仁


    從教室後頭拍攝