ACM的用途與迷思
學演算法有甚麼用呢?
1. 增進思考能力,能讓大腦處理複雜的事情。類似益智遊戲。
2. 運用演算法解決一些已經知道如何解決的問題。
3. 獲得資訊科學的一些基本常識。學演算法和資料結構亦有助於了解資訊科學的全貌。
在Online Judge上面找題目寫有甚麼用呢?
1. 實作演算法,印證自己所理解的是正確的。
2. 學會轉化問題,能夠活用現有的演算法解決問題。
然而OJ的問題都經過設計,比較單純,與真實世界的問題有很大出入。
3. 練習程式設計技巧,讓自己往後能夠寫出邏輯正確而且精煉的程式碼。
4. 減少寫程式犯錯、產生bug的機會。
5. 與其他人交流,學習新知。
讀別人的程式碼、改別人的程式碼、讀程式語言的語法書有甚麼用呢?
1. 學習他人的程式設計技巧,往後自己寫程式時也可以如法炮製。
2. 嘗試了解他人的思考模式,以增進自己的思考能力。
3. 分析利弊,截長補短,讓自己往後能夠寫出邏輯正確而且精煉的程式碼。
4. 減少寫程式犯錯、產生bug的機會。
從事上面行為後,卻沒有學到的東西:
1. 寫出架構清晰、平易近人的程式碼。寫出一兩年後你自己還看得懂的程式碼。
2. 寫出有效率的C/C++程式碼。
3. 發明演算法和資料結構解決目前還沒有解決方法的問題。
4. 教別人程式語言,教別人演算法和資料結構。
5. 設計和製作一套軟體(系統),然後維護一套軟體(系統)。
6. 與他人合作開發程式。
7. 了解資訊科學的各種應用及其理論知識。
8. 能夠寫程式來控制電腦設備,利用電腦設備來達成夢想。
改版
本次改版內容如下:
1. 網站標題。
2. 整合首頁內容。(部分未整合完畢)
3. 改變網頁樣式與配色,並減少HTML原始碼。
4. 程式碼上色功能,上色速度增快許多。(數字上色有點問題,但是應無大礙。)
5. 可拖曳的動態選單,與動態捲動功能。兩三年前John網友建議的「回到首頁」連結也放上去了。
6. 練習題超連結。
7. 目前仍然不支援IE。
如果有任何問題歡迎反映!
致example網友:那個動態選單,我不知道怎麼讓它最大化和最小化,所以就讓它跟文章不會疊在一起,解析度1024×768以上都沒問題。現在你用EeePc能正常顯示嗎?
A Polynomial Time Algorithm For Hamilton Path???
http://www.sciencenet.cn/m/user_content.aspx?id=285543
上網亂逛竟找到這等東西,不知道是真的還是假的。如果NP-Complete問題被解開了,網路世界就要大亂了。
不過Hamilton Path要有虛擬多項式時間解法應該也不奇怪,畢竟Knapsack Problem都有虛擬多項式時間的解了。
Optimal Alphabetic Binary Trees?
這棵樹有許多不同的命名法。我在網路上查到這棵樹的作者T.C. Hu應該是一位叫做胡德強教授的人(Hu, Te Chiang),他本人就替這棵可愛的樹取了許多不同名字。
一個名字:Optimal Alphabetic Tree
Optimal alphabetic trees for binary search. Information Processing Letters, Volume 67, Issue 3, 17 August 1998, Pages 137-140.
另一個名字:Optimum Alphabetic Binary Code Tree
Combinatorial algorithms: T.C. Hu and M.T. Shing
再一個名字:Optimum Alphabetic Binary Tree
http://www.springerlink.com/content/y11m222057476017/
不過很不幸的,網路上幾乎都是用:Optimal Alphabetic Binary Tree。作者應該正躲在角落畫圈圈?
個人認為「optimal」和「optimum」這兩個字的差別,在於「optimal」比較適合用在「最佳狀況」,而「optimum」比較適合用在「極值」。因此求結構最佳的二元搜尋樹,會寫成optimal binary search tree,而不是optimum binary search tree。至於霍夫曼樹也是比較常用optimal binary tree,而沒有在用optimum binary tree。
說到這裡,得提一下T.C. Hu另外還有一篇文章:Binary Search Trees and Binary Code Trees,個人覺得這樣的區分很不錯,兩者都是基本binary tree的延伸。霍夫曼樹被叫做optimal binary tree,其實滿含糊的,我想把它叫做optimal binary code tree應該會更明確一點吧。
既然已經有了code tree這個名詞,我們只要定義一下code tree的權重,那麼在它開頭使用optimum也是可以的。但是search tree既然都用optimal了,那麼code tree也跟著用optimal,還是比較好些。畢竟我們想強調的是樹的結構很好,適用於搜尋和編碼,而不是強調樹的權重很小。
接著討論另一件事,既然search tree的search是動詞,那麼我們應該用coding tree才對吧?現在我們來看看code tree和coding tree這兩個辭彙有沒有人在用。(我得先聲明,我並不瞭解編碼學領域的習慣用語,也不知道編碼學於命名時是否有避免與樹狀資料結構、圖論的名詞撞名。)
網路上,霍夫曼樹最常見的說法是huffman coding tree和optimal binary tree,其餘還有huffman code tree、binary code tree、binary coding tree等等,其實都有人在用。
接著,optimal binary code tree還有些人用,不過optimum binary code tree、optimal binary coding tree、optimum binary coding tree就找不到了。可以看出大家不太喜歡把code這個字插在中間,而且大家喜歡optimal勝過optimum。
我自己覺得最好的名字應該是:Optimal Alphabetic Binary Code Tree。不過全世界除了我的網站以外,沒有人這樣用,哈哈。
題外話,會注意到胡教授,是因為看到Gomory-Hu演算法時,忽然聯想到Hu-Tucker演算法的Hu,一查發現原來都是T.C. Hu。
近期迴響