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...

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

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

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

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