Six Feelings

2007年5月27日星期日

Google Blogger使用技巧

http://www.williamlong.info/archives/575.html
　Blogger是Google提供的免费博客服务，提供中文界面，是一个很成熟的中文博客发布平台。

　　Blogger一个突出的特点就是简洁但功能强大，没有多余而花哨的功能，必要的功能一个都不差。Bloger自由性最大的地方在于其模板可以自定义，也就是说你可以修改模板里的任何内容，包括Google的广告，这给那些懂Html和CSS的Blogger提供了很大的自由度。Blogger默认把用户的网志发布到免费提供的 Blogspot.com主机上。可惜的是Blogspot.com从中国是无法访问。好在Blogger.com提供了一种很独特的服务，可以将博客的静态页面通过FTP发布到用户选择的服务器上。

　　通过FTP发布到其他主机

　　用户在Blogger.com上的默认Blog地址显然无法从国内访问，但是如果你有一个虚拟主机空间，或者其他支持FTP的空间，那么Blogger.com可以将这个地址上的日志文件全部发布到你的虚拟主机空间上去。

　　具体的方法是：登陆你的Blogger帐号，进入控制面板，更改设置，在"发布"选项卡中点击FTP的超级链接，然后录入FTP服务器地址，FTP用户名和密码。点保存设置后，就可以发布了，这时Blogger.com会将你的整个站发布到你指定的主机上。

　　至于这个FTP服务器，我推荐一个国内GFans提供的免费Blogger Spaces空间，支持FTP发布，最重要的是支持域名绑定，其服务器在广州，速度很快，希望大家不要滥用其服务。

　　通过电子邮件发布日志

　　在Blogger中写日志麻烦？告诉你一个技巧，你可以不登录Blogger网站，只要发送一封电子邮件就可以发表文章了。

　　具体的方法是：登陆你的Blogger帐号，进入控制面板，更改设置，在"电子邮件"中，在Mail-to-Blogger地址中可以自定义一个邮件地址，发送到此地址的邮件会自动张贴，BlogSend地址是另外一个电子邮件地址，只要一发布文章，系统会将其邮寄文章到此地址。

　　这里再介绍一个小技巧，就是在更新Blogger的同时也更新MSN Space。因为MSN Space也是支持邮件发布的，因此将Blogger发布后发送邮件的BlogSend地址修改为MSN Space的发布邮件地址，这样在Blogger上发布一篇文章后，系统就会自动将文章内容发送到Msn Spaces里，这样就同时更新了两个博客。

　　有一点值得注意的是，Blogger默认的编码是UTF-8编码，因此发送邮件的时候要将邮件编码设置为UTF-8的格式，建议登陆GMail发送邮件。一来GMail默认就是UTF-8格式的，编码全兼容，二来GMail支持自动保存功能，不怕电脑死机后丢失文章，三来GMail还可以自动备份发出去的文章，以免文章丢失。

　　使用第三方软件发布文章

　　Zoundry是一个第三方的日志发布软件，可以做到不用登陆Blogger即可发布日志，使用它来编辑和发布，速度和效率都非常理想。

　　添加Google Adsense广告

　　Google Blogger用户可以很快捷方便地申请加入Google Adsense广告服务。Google本身也推荐博客们使用Blogger的广告来为自己和Google赚钱。

　　Google工具栏的应用

　　Google工具栏有一个按钮是"发送到Blogger"，可以快速将当前网页发送到自己的Blogger空间上。

　　Google Picasa的应用

　　Picasa是Google的图像管理软件，在Picasa中点图片，再点"Blog This"，可以将选定图片发送到自己的Blogger空间上。

　　Blogger的申请地址是： http://www.blogger.com

介绍两种国内访问Blogger.com的方式

国内无法访问Blogspot.com，这一直困扰着许多Blogger.com 爱好者们。最近，我也加入了Blogger.com爱好者的队伍。因为，我发现了两个可以方便访问 Blogger.com空间的方法：

一、通过第三方网站提供的免费域名

　　以http://blogname.blogspot.com/为例：

　　(1)www.pkblogs.com

　　　　http://www.pkblogs.com/ blogname/
　　　　相关链接：http://www.pkblogs.com/

　　(2)nyud.net:8089

　　　　http://blogname.blogspot.com.nyud.net:8090/　　

　　　　相关文章：让正常访问blogspot变成现实

二、通过免费FTP空间
　　Blogger.com提供FTP 发布。一般的FTP空间都可以，在 Blogger.com的控制面板里很容易设置。我这里要介绍的是一个不一般的FTP 空间。因为它还提供免费的域名绑定。只是，用户要有Gmail的帐号才能申请FTP 空间和域名绑定。它就是BloggerSpaces，相关链接与文章如下：

　　申请FTP空间的链接地址：

　　　　http://www.bloggerspaces.com/2006/06/blogger-spaces_16.php

　　申请FTP空间的相关文章：

　　　　国人也用上Blogger

　　申请域名绑定的链接地址：
　　　　http://www.bloggerspaces.com/2006/06/blog-post.php

　　如还有不清楚的地方，可访问BloggerSpaces 的论坛：
　　　　http://groups.google.com/group/bloggerspaces

2007年5月22日星期二

未來數學家的挑戰【七、結論+註釋】

七、結論

現在你明白二十世紀的大難題了，P=NP？用簡單的語言說，就是是否能找到一個只呈方次增加的方法去解決旅行、包裝、舞會等問題。平凡的問題，期待您不平凡的解答。

: 1. Gorey, M.R. and Johnson, D.S.《Computers and Intractability-A Guide to Theory of NP-Completeness》, 1979, Freeman and Company.
: 2. Pearl, J.《Hearistics-Intelligent Search Strategies for Computer Problem Solving》,1984, Addsion-Wesley.
: 3. Cook, S.A.〈The complexity of theorm-proving procedure〉, Proc. 3rd Ann. ACM Symp. on Theory of Computing, 1971, 151-158.
: 4. Jonhson, D.S. et. al.〈Worst case performance bounds for simple one-dimensional packing algorithms〉, SIAM J. Comp., 1974, 299-325.
: 5. Rosenkrantz, D.J. et. tl.〈An analysis of several heurishics for the traveling salesman problem〉, SIAM J. Comp., 1977, 563-581.
: 6. Sahin,S. and Gonzalez,〈P-complete approximation problems〉, J. ACM, 1976, 555-565.
: 7. Stockmeyer, L.J. and Meyer, P.R.〈Word problems requiring exponential time〉, Proc. 5th. Ann. ACM Symp. on Theory of Computing, 1973, 1-9.
: 8. Robertson,E. and Munro, I. 〈NP-completeness, puzzles, and games〉 Utilifas Math., 1978, 99-116.
註釋

...¹: 排序 (Sorting) 的方法很多，但都不能低於 $O(n\log{n})$ ，讀者可在一般 Database 的書中找到有關 Sorting 的法則。
...²: 又稱呈多項式上升，但因一個 n 的多項式之大小，在 n 很大時都為第一項所支配，故可寫成 O(n^k)。
...³: 並不失去一般性，即若距離不是正整數也可以把它們化成正整數。
...⁴: 在古克的原文中，並沒有 NP-complete, NP-hard 之明確定義。但是由於他的論文，使這種分法顯得很自然。不過 NP-hard 之定義仍因人而異，不一定同於本文。
...⁵: 本文中之解決，均指一個 O(n^k) 計量算的解法。
...⁶: 與情報人員之單線作用相同。一個諜報人員只知道他的頂頭上司及他的第一線下層下屬，其餘的人他都不知道。
...⁷: A,B,C 表任三城，而 d(A,B),d(B,C),d(C,A) 分別表示 A,B; B,C; C,A 城之距離，則 $d(A,B)\leq d(B,C)+d(C,A)$ 稱為三角不等式。
...⁸: 指 19×19 之棋盤，許多計算機學家都是圍棋高手，中國的算盤與圍棋，好像包含了計算機的開始與終極。

未來數學家的挑戰【六、NP-hardness 與圍棋】

六、NP-hardness 與圍棋

不是所有的難題都可歸結為 NP 問題，像下得一手絕對好的圍棋現在目前的推測是比所有 NP 問題還要難的計算問題，即 NP-hard 問題，NP-hard 問題的定義如下：

: 定義：若 x 為一 NP-hard 問題，則若 NP $\neq P$ ，則 $x\not\in P$ 。

也就是說，即使 P=NP，x 還不一定屬於 P，但 $P\neq$ NP, 則 x 絕不比 NP 的問題容易。在第三節中的問題1、3不一定是 NP 問題，但若能以 O(n^k) 的計算量解決它們，則比較容易的問題2與4也可以 O(n^k) 解決，故若問題1、3 $\in P$ 則問題2、4 $\in P$ ，又因2、4是 NP-complete，即推出 NP=P。這與 NP-hard 之定義相合，故問題1、3均為 NP-hard 問題。同理問題5也屬於 NP-hard，不過這些 NP-hard 似乎比 NP 難不了多少，但下棋問題可能比 NP 問題要難得多，圍棋問題可以作如下觀。

問題11.（圍棋問題）: 以平常的圍棋規則在一個 n x n 的棋盤上下，給定一個殘局（下了二個子就可以算殘局），首先，是否可以確定黑子在最好的下法之下，一定會贏？

這個問題不能用一般的方法證明它是不是為 NP。因為目前沒有人能猜一個必勝的下法且在 O(n^p) 時內證明它是對的，因為它與對方如何應付有關，而敵方的應付又與他對你以後的下法的推測有關，如此往下走，首先發生困難的是記憶上亮了紅燈，即所需要的記憶可能呈方次以上的進展。

因每一個記憶至少要用（來計算）一次，否則這個記憶就不如不要，因此一個問題的記憶若呈指數上升，則其計算量亦非呈指數似的上升不可，但若某問題只需要方次上升的記憶，即不能保證它只需要方次上升的計算量。

因此計算機學家定義三個新的集合：

PSPACE={x：x 只需要方次上升的記憶 }
註：x 均指問題。

PSPACE-complete：

: 若 $x\in$ PSPACE,
: 又 $x\in$ PSPACE-complete,
: 且 $x\in P$ ,
: 則 P= PSPACE。

PSPACE-hard：

: 若 $x\in$ PSPACE-hard,
: 且 $x\in P$ ,
: 則 P= PSPACE。

注意在上式中 PSPACE-complete $\subset$ PSPACE，即 PSPACE-complete 是 PSPACE 中的難題，但 PSPACE-hard 不一定屬於 PSPACE。 Stockmeyer and Meyer 在1937年證明了一個與古克相似的定理。

若令 $\exists x$ 表示存在一個 x， $\forall x$ 表對所有的 x，Q 表 $\exists$ ， $\forall$ 中的一個，x 為布氏變數0與1，則我們稱 f(Q₁ x₁,Q₂ x₂,…,Q_n x_n) 為一量化布氏公式。若 f 有可能為1，則 f 稱之為可滿足，例如把第四節中之(1)式改寫成

$\begin{displaymath} f(\forall u_1,\exists u_2,\forall u_3)\\ =((\forall u_1)\cd... ...ts u_2)\cdot \\ (\exists u_2)+\forall u_3)\cdot(\forall u_3)) \end{displaymath}$

則上式不可能滿足，因對 $\forall u_3$ （u₃ 為 0 或 1）而言，f 不全是1。

Stockmeyer 與 Meyer 之定理為：

定理：: 檢定一個量化布氏公式為可滿足是一個 PSPACE-complete 問題。

當我們下棋面對著一盤殘局沉思的時候，我們的要求是

對我是否存在一著必勝棋可以對付
敵人任何一著應付棋
此後我是否存在一著必勝棋可以對付
敵人任何一著應付棋
……
我是否存在一著必勝棋可以對付
敵人任何一著棋
我贏了

因此這完全是 $\exists$ , $\forall$ , $\exists$ , $\forall$ ,… 之交替作用與Stockmeyer 與 Meyer 定理之關係至為密切， Robertson 與 Munro 在1918年證得圍棋是一種 PSPACE-hard 的問題，目前有人計算到圍棋 ⁸ 必勝法之記憶計算量在 10⁶⁰⁰ 以上，不論人腦或電腦的記憶絕少不了一個原子，而現今所知的宇宙原子數約只有 10⁷⁵。棋之道，大矣哉！要做一個下圍棋必勝的機器人是談何容易！

未來數學家的挑戰【五、NP-complete 問題之近似解】

http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/page5.html
五、NP-complete 問題之近似解

NP-complete 問題既找不到可行的解法，而很大部分的 NP-complete 問題都在計算機語言，程式，電路設計，統計學，程式作業上有大用，因此只好退而求其次找一個可行的近似解。很可惜的是，所有的 NP-complete 問題雖在 NP 的層次上相聯，在近似解上往往各需不同的解法，這些解法多從直觀而來，我們在此舉二個例子。

例1: 在第三節問題5，包裝問題中，若採取「能裝就裝」法，即現有的盒子若可以裝得下，就不用新盒子，則此法所需用之盒子數 k₁ 與最可能少的盒子數 k₀ 滿足 $k_1\leq 2k_0+1$ 。
證明: 今令 n 個物品之重為 w₁,w₂,…,w_n 公斤，因每個盒子只可以裝1公斤，故
$\begin{displaymath} k_0\geq \sum_{i=1}^{n}{w_i} \end{displaymath}$

另一方面，「能裝就裝」法不可能有兩個以上的盒子同時少於 $\frac{1}{2}$ 公斤，故
$\begin{displaymath} k_1\leq 2\sum_{i=1}^{n}{w_i}+1 \end{displaymath}$

本例得證。