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

0 comments: