Yukuan's Blog: computer science

Showing posts with label computer science. Show all posts

Tuesday, November 08, 2005

A Good Solution is Hard to Find

國中生就能理解的畢氏定理，古希臘學者竟將它當作祭品獻給上天；數百萬人都能哼唱第九交響曲，卻少有人渴望成為貝多芬那樣的音樂天才。這就是基本的非對稱性——辨識遠比發現來得容易。
-- 摘譯自《Out of Their Minds》〈A Good Solution is Hard to Find〉

我想，需要並非發明唯一的母親。一個人必須對問題的背景資訊有正確的瞭解。我並不是對所有遇到的問題都加以研究。而是對那些我所解決的問題，心中覺得真巧，剛好我有獨特的背景知識，可以用來解決此問題！就像命中註定，也是我責無旁貸的。
-- 高德納

人們心裡想要的東西，很少是他們真正需要的。他們想要的和需要的，往往是南轅北轍。而在科學技術的發明中，最重要的事便是能符合人們的慾念與需求。
-- Alan C. Kay

Thursday, October 20, 2005

《電腦也搞不定》

　　電腦被一些人認為是神奇、無所不能的，竟能完成許多形形色色的任務...
　　相反地，另一些人卻持完全相反的看法，認為其純粹是工具，無論如何都不可能擁有如人腦般的優越性...
　　以下這本書，就從數學的角度來探討電腦的限制，及這些限制的應用等。

書名：電腦也搞不定－－從數學看計算機科學的罩門（Computers Ltd. -- What They Relly Can't Do）
作者：David Harel
譯者：李國偉
出版：天下文化　2002/8/14

　　以下就簡述各個章節的內容概要：

前言

　　前言主要是說明研究電腦限制的四大動機。

第一章　到底怎麼回事

　　快速地解釋、帶過演算法、程式設計等

第二章　有時候我們辦不到

　　提出「計算的侷限性也就是知識的侷限性」並將計算問題分作不可計算的、可計算的等區分；其中不可計算的可再分成高度不可計算的及不可計算的等。
　　此外，本章還展示了基本的計算裝置、丘奇－涂林論點、可計算性的強健性。當然也免不了提一下有名的涂林機及停機問題等。

第三章　有時候我們辦不起

　　前一章提的可計算的問題又可分為好算的和難算的等。說明有些問題就算是可計算的，但由於可能需要消耗大量的時間、空間等資源，所以顯得不切實際。
　　此外，還提出演算法計算時間的上界、下界、演算間隙等評估因素。

第四章　有時候我們就是不知道

　　主要是提出有名的 NP-complete 問題及其相關的議題。
　　如 P=NP? 、近似算法等。

第五章　嘗試減輕痛苦

　　嘗試以各種方法來解決難算的問題，如平行計算、隨機化計算、量子計算、分子計算等。
　　還舉了隨機化檢驗質數例子、量子式因數分解、 DNA 式 TSP 解法等例子。
　　註解中還提出了 NC, PTIME, NP, PSPACE, RP, QP 等其間的關係。

第六章　轉壞為好

　　提出密碼學、公開鑰、信息簽名、 RSA 密碼系統、互動證明、零知識證明等議題。並說明它們如何利用計算的困難性來解決問題。

第七章　我們自己能做得更好嗎？

　　快速帶過演算法智能、涂林測驗、 ELIZA、經驗法則、知識的內涵、類神經、專家系統、自然語言的瞭解等議題。
　　還說明了「雖然很容易認為我們也是個有限機器，所以可以被模擬。
但是真實狀況是，人類的知識庫是難以想像的複雜...」

後語

　　...

~~

　　這裡建議對資訊科學感興趣的同好都可以將本書當作入門的導讀。可幫忙釐清一些觀念。

Original: Yukuan on Sat, 07 Sep 2002 02:38:35

Re: 請推薦值得買回家的好書

我對於值得買回家的書有幾個評判標準：

內容的主旨要能吸引我的注意，令人感到興趣。
要能學到新知識、以前所不知道的或未曾想過的東西。
最好能夠激發思考和想像力，帶來新的思維。
值得一讀再讀的書。
內容豐富、論述清晰，可用於相關主題的綜灠，發揮導讀的作用。
急需對某主題來作運用，而能提供詳細的解答及know how，在加上腦容量一時無法記下那麼多skill方面的細節。
對於此書非常喜歡，雖然可能過一段時間才可能再次閱讀，但擔心想再次閱讀時此書已無法找到了。

其中第 1, 2, 3, 4 點為必要條件，第 5, 6, 7 點為選擇性條件。

無論如何，先介紹幾本書和大家一起分享：

《開放的心靈》"The Open Mind" by DAWNA MARKOVA, 雅音出版公司
強烈推薦每一位擔任教職工作者都義務性地將整本書熟讀並充分運用，對於自己和他人學習方式的不同點感興趣的也可藉由本書而有一個全新的視野。
誤會的釐清來自於對彼此的瞭解，作者透過本書來闡述不同人間認知事物過程的差異性，除了使我們對於不同思考模式的人間能有更大的諒解和包容。也提供了明確的解決方案。
《理性之夢》"The Dreams of Reason" by Heinz R. Pagels, 天下文化
作者對於電腦、複雜性科學、科學方法、人類心理、認知及關於心、物間關係的哲學議題作了一番相當深入的探討。並提出其對於這些新知識綜合體的看法及所持的理由。
《第三種文化》"The Third Culture: Beyon the Scientific revolution" by John Brockman, 天下文化
從本書原文的副標「超越科學的革命」即可約略猜出其是一本探討最新科學研究的書。
全書分成五部，分別探討「演化觀念」、「人工智慧」、「宇宙起源」、「複雜科學」、「在電腦內的演化中的智能」。
共二十三章，每章都訪問針對由一個學者來對其研究領域最重要的主題作一翻介紹。章末還訪談了許多學者對於此章學者看法的評論。訪談的學者有威廉斯、古爾德、道金斯、古德溫、瓊斯、艾垂奇、馬古利斯、閔斯基、單克、丹尼特、韓佛瑞、法瑞拉、平克、潘洛斯、芮斯、谷史、施莫林、戴維斯、葛爾曼、考夫曼、蘭頓、法默、奚力思等二十三位。
趕快翻翻你腦袋裡的科學名人錄有沒有者些學者的名字，挑些你喜歡的主題來看吧。
你應該知道了吧，這本書編排的架構明確，綜灠型的書。如果對相關主題有興趣的話，可發揮導讀的功能。