《電腦也搞不定》

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

• 書名：電腦也搞不定－－從數學看計算機科學的罩門（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

Tags: [book] [computer science]