# 電腦的本質 從計算機發展到現今的電腦,從機械到電子,從簡單到複雜,都脫離不了三個基本性質. 功能分離(function abstraction) 許多不同的階層在獨立運作,而不必顧慮其他階層 通用電腦原理(universal computer) 電腦運作的基本原理都是一樣的,只差在組成的元件不一樣,所以只要程式設計的正確,電腦也能如人腦般的思考 超越工程學 此為全新的電腦設計概念,當電腦的設計變的複雜時,便試圖以全新的概念來設計 ...

# 亂數 數位電腦如何產生隨機訊號?項電腦這樣的決定性系統(deterministic system)可以產生一串真正的隨機數列嗎?嚴格說起來,答案是否定的.因為數位電腦所做的每個工作都是由其設計及輸入所決定的,就好像俄羅斯輪盤,球最後所落下的位置是由球的物理性質及輪盤來決定.理論上,若我們了解輪盤的設計及控制其旋轉與擲球力道等詳細[輸入]內容,就應該能預測球的落點.但輪盤停止轉動後的結果看起來卻是隨機的. 電腦也可以用同樣的觀念產生隨機數列,事實上電腦也可以用一種數學模型模擬俄羅斯輪盤的物理性質,每次用稍微不同的角度擲球,已便產生隨機數列.即使丟球的角度只是固定的週期性變化,電腦所模擬的動態轉輪也會將這些些微差異轉化成不可預測的隨機數列.這種隨機數列稱為假隨機(pseudorandom)序列,因為只有不了解其計算方式的觀察者才認為它是隨機的.這種由[假隨機數產生器]所產生的數列可通過所有的標準統計隨機檢測. 數位電腦和真實世界一樣是可預期的,卻也是不可預期的,它們都遵循著決定性的法則,但這些法則會導致相當難以預測的複雜結果.在電腦執行之前猜測它所要做的動作是很不切實際的,而通常不需太大的功夫就可以讓計算變得很複雜. ...

# 位元和邏輯區組 任何可以表示兩種不同訊息的信號就叫二元(binary)信號,或稱為位元. And Or Invert 函數稱為邏輯區組,把他們依序組合還可以得到其他函數. EX. Or 輸出端接 Invert,便得到 Nor(輸入端均不為 1 時,輸出便為 1) 兩個 Invert 接在 Or 輸入端,輸出端接上 Invert,便得到 And(兩輸入端為 1,輸出為 1) 早期計算機裝置是由機械元件組成的.17 世紀,巴斯卡(Blaise Pascal)建造了一個機械式加法機,也因此激發了萊布尼茲(Gottfried Wilhelm Leibniz)和英國博學家虎克(Robert Hooke)的靈感而製造了可以乘除甚至開根號的機器.1833 年,英國數學家兼發明家巴比奇(Charles Babbage)設計並建構出可程式化機械電腦的一部分. ...

# 作業系統 指令集複雜度之所以不重要,是因為有副程式.副程式可以讓一串指令在程式中被無限使用.事實上,程式設計師可以用呼叫副程式的方式將原有的指令定義為新的指令.利用 Jump 指令把副程式的位址載入程式計數器中,將執行順序轉移到副程式中,但轉移之前,電腦會將之前程式計數器的內容儲存在特定記憶體中,當副程式執行完時,會有另一個指令讀取到這個返回位址(return address),而讓順序跳回到原先呼叫副程式時的位置繼續執行. 這種呼叫副程式的過程可以遞迴的執行,某個副程式本身可以跳到另一個副程式裡執行,然後這個副程式在跳到別的副程式,依此類推,在遞迴函數中,副程式本身亦可以呼叫自己.為了紀錄這種成層疊加的副程式呼叫過程,電腦必須用一種有系統的方式儲存返回位址,當每個副程式執行完畢時才知道該回到哪裡去.但不能把所有的返回位址都紀錄在同一地方,因為一但副程式成層疊加起來,電腦就必須記住一個以上的返回位址.通常,電腦會將返回位址循序儲存在一群記憶體位置中,稱為堆疊(stack),最後一個返回位址會放在[堆疊頂端(top of the stack)].堆疊記憶體的運作方式就好像疊在一起的盤子一樣,總是從頂端加入或取出東西.這種後進先出(last-in,first-out)的儲存方式,對於儲存一疊疊副程式的返回位址來說確實完美,因為每個副程式都必須等它自己所呼叫的副程式執行完成後才會結束. 電腦中總是裝有一些很有用的副程式,它們統稱為作業系統(operating system). 作業系統包含了能讀寫鍵入字元或是在螢幕上畫線條的副程式,不然就是其他與使用者互動的副程式.作業系統決定使用者所看到的界面,也掌控了電腦與所執行程式之間的界面,這是由於作業系統提供了一套比機械語言指令更豐富且更複雜的指令. 事實上,程式設計師並不在乎他所謂的功能是以電腦硬體或是由作業系統軟體所執行,只要它們能產生同樣的效果就好了.同樣的程式在兩種不同的電腦上運作時,可能其中一個是透過硬體的算術運算執行,而另一個則是以作業系統的副程式來執行.同樣的,電腦的作業系統也會仿效它型電腦的指令集.有時電腦製造商會利用這種模仿方式,讓新型電腦像舊型一樣操作,如此一來就可以不經過任何修改而讓舊有的軟體在新型電腦上運作. 作業系統通常包含執行基本輸入輸出的副程式,也就是能讓程式和外界互動的副程式.其運作方式是將電腦記憶體中某特定位置與鍵盤或滑鼠等輸入設備連接在一起,或是與顯示器之類的輸出設備連接. EX.鍵盤上的空白鍵可能接到記憶暫存器23號,當按下空白鍵時就可以在位址 23 中讀到資料 1,反之讀到資料 0.另一個記憶暫存器可能控制螢幕上的某個點的顏色,假設螢幕上的每一點所顯示的資料都儲存再不同的記憶體位置中,那只要將適當的位元資料寫入記憶體中,電腦就可以在螢幕上畫出任何圖案. 除了這些輸出入機制外,我們所描述的電腦其實只是一部接了記憶體的有限狀態機,而這兩者都可以用暫存器和布林邏輯區組建構出來,控制電腦的有限狀態機相當複雜,設計這樣的機器其實是就是經過一連串記憶體資料,位址和狀態順序等細節,以執行每一個指令,然後再將它的狀態轉換成布林邏輯的過程.既然有限狀態機和記憶體是由暫存器和邏輯區組所組成的,那這些東西就可以用各種技術加以實作, EX.電子電路 液壓管路 滑桿. ...

# 布林邏輯 思維規律的研究(an investigation of the laws of thought)-布耳(George Boole) 布林代數(Boolean algebra) 布林代數很像高中所學的的代數,不同的是方程式中的變數所代表的是邏輯敘述而不是數字. 布林的變數象徵對或錯, 透過 MIT工學院學生夏濃(Claude Shannon)的碩士論文,布林的研究結果得以跨入計算機科學領域,夏濃因發明了資訊理論而負盛名,這個理論定義了資訊的計算單位,位元. 夏濃希望建造一部可以下棋的機器,可以模仿人類思考的機器.1940年他發表了碩士論文,替續開關電路的符號分析(a symbolic analysis of relay switching circuits). 他在論文中說明,建立與布林代數運算式相同意義的電路是可行的.夏濃的電路中,開關的On和Off對應布林代數中邏輯變數的對和錯. ...

# 有限狀態機 它可以執行隨時間而改變的函數,也就是不但與目前的輸入值有關,也受之前輸入值影響的函數. 有限狀態機的基本構想是將一個對照表與記憶元件加以結合,而這個對照表則是以布林邏輯建構的,記憶元件儲存過去的概要,本身就是有限狀態機的[狀態]. 密碼鎖就是簡單的例子,它的狀態就是記住一連串數字輸入鎖中的結果.鎖並不記得撥過的所有數字,但它可以記住最後輸入的幾組數 字,而這幾組數字就足以在數字序列正確的時候把鎖打開. 自動筆是一個更簡單的例子,它有兩種可能的狀態,伸出筆芯和縮回筆芯,而且還記得它的按鈕被按了奇數次還是偶數次. 所有有限狀態機都有一組固定的可能狀態、一組可以改變狀態的輸入(按原子筆的按鈕or撥動鎖上的數字盤)以及一組可能的輸出(筆 芯的縮回或伸出or開鎖).輸出只由狀態決定,而狀態則取決於輸入的順序. 為了儲存有限狀態機的狀態,需再介紹最後一個建構區域,也就是可以儲存位元的暫存器.n位元的暫存器有n個輸入及輸出端外,另加一個輸入端以告知暫存器何時該改變狀態.將新資訊存入暫存器的動作叫寫入(writing),當定時輸入端告知暫存器要寫入新狀態時,暫存器的狀態便會改變使與輸入訊號相符.至於暫存器的輸出,則總是顯示目前的狀態. 暫存器的裝置有很多種,其中之一是以布林邏輯區組將狀態訊息推入一個圓圈循環中,這種暫存器是電腦中最常用的一種,所以當電源突然中斷時,電腦便不會繼續當時所做的工作. 有限狀態機包含了一個布林邏輯區組及一個暫存器,有限狀態機將布林邏輯區組的輸出寫入暫存器中,然後邏輯區組會依新的輸入及當時的狀態計算出下一個狀態,並再下一個循環寫入暫存器中,如此週而復始的重複,有限狀態機因此不斷更新其狀態. 包括電腦在內的許多數位計算裝置也都已固定的時間間隔變換其狀態,而變換的頻率則稱為這部機器的時脈(clock rate),在電腦的世界裡,時間並不是連續的,而是一組固定的變換序列.電腦的時脈決定這些狀態變換的速度,因此也決定了實際時間與計算機時間的對應關係. 雖然有限狀態機的功能非常強大,但它卻無法辨識所有序列形式.例如,我們不可能建構一個用迴文開鎖的有限狀態機,所謂迴文就是由前往後唸和由後往前唸都一樣.因為迴文的長度不一定,且必須要記住迴文前半部中的每個字,才能辨識後半部,又由於前半部有無限多種可能,因此需要一部具有無限個狀態的機器才能處理. ...

# 杜林機 計算理論的中心觀念在於通用電腦(universal computer)的概念,所謂的通用電腦是一步功能超強,能夠模擬任何計算裝置的電腦.只要軟體正確,加上足夠的記憶體和時間,每一部通用電腦都可以模擬任何其他種類的電腦,或是我們已知的任何處理資訊的設備. 這種通用原理所衍生的理論,就是任兩種電腦在功能上最大的差異,只在於它們的運算速度和記憶體的大小.不同的電腦或許有不同的輸入或輸出設備,但這些週邊設備並非電腦的基本特性,就功能而言,所有電腦(及所有通用計算裝置)基本上都是一樣的. 通用電腦的觀念是由英國數學家杜林(Alan Turing,1912-1954)於1937年所提出的,和其他許多計算領域的先驅一樣,當時的杜林也醉心於製造一部會思考的機器,他發明了一套針對普遍用途計算機的架構.杜林將這部虛構的機器稱為[通用機器],因為當時計算者(computer)所代表的意義仍為[做計算的人]. 關於杜林機的描述,我們先想像一個數學家在紙卷上進行計算,這紙卷的長度無限長,因此不需要擔心紙會用完而無法運算,不論有多少計算步驟,花掉多少時間,數學家總是可以用這種方式算出任何有解答的計算問題.杜林說明一位精明的數學家所做的計算,即使讓一個愚笨但謹慎的書記員來作,也同樣做得出來,只要他依循一些簡單規則在紙上讀寫資訊.事實上,他宣稱這位書記員甚至可以用一部有限狀態機取代,這部有限狀態機一次只能讀取紙卷上的一個符號,因此我們可以把紙卷想像成一條細長的紙帶,而每一行只有一個符號. 今天,我們稱這部結合有限狀態機及無限長紙帶的機器為杜林機(Turing machine).杜林機的紙帶=現今電腦中的記憶體. 就我們所知,世上沒有任何一種設備的計算能力勝過杜林機,只要時間和記憶體足夠,任何計算裝置能執行的運算,都可以用通用電腦完成.這意味著只要有適當的程式運作,通用電腦就應該能模仿人腦的功能. 目前我們所討論的是二態電腦,以0或1表示所有事物.若電腦以三態邏輯(three-state logic)表示事物(是 否 或許),則它的功能不一定更強,因為可以利用其中一種電腦模擬另一種電腦.但並不代表三態電腦沒有優於二態電腦的地方,Ex.它所需的繞線也許較少,因此體積較小,成本較低,但也只是另一種通用電腦而已.但使用類比訊號的電腦又如何?早期的電腦就是這樣運作,以類比訊號表示量值,稱為類比電腦(analog computer),有別於數位電腦(digital computer),數位電腦的每一個訊號都是獨立的.有人認為類比電腦的功能較強,因為它可以表示連續值,而數位電腦只能表示獨立值.但在現實世界中只有單一數值,而不可能出現一個真正的連續數值. 類比電腦的問題在於其訊號只能達到某種程度的精準度,任何類比訊號都一定會有雜訊,也就是說,當鑑別率達到某種程度之後,訊號就變得雜亂無章.任何類比訊號都會受到不相干或不知名的雜訊干擾,Ex.電子訊號會受到導線內分子的隨機運動干擾,或是打開電燈開關所產生的磁場干擾.雖然可能的訊號有無限多種,但其中能區別出不同意義,表示有效資訊的訊號卻是有限的.若訊號中有個百萬分之ㄧ大小的雜訊,那要區別出不同意義的訊號大約只有百萬個,因此,這個訊號所含的訊息可以用二十位元的數位訊號表示(2**20=1048578).在類比電腦中,要將有效資訊量提升兩倍,就得將所有東西如精準度都提高兩倍,但數位電腦只要增加一個位元就好了.最好的類比電腦其精準度不超過32個位元,而數位電腦往往是以32位元或64位元來表示數字,因此它所能產生的有效訊號個數超過類比電腦. ...

# 流體電腦 管路以水壓來表示兩種不同的訊號.在液壓活門中,控制端的水流可以操作輸出端水流,但輸出端的水流並不會影響控制端的水流,這限制了訊息的傳遞方向,就某方面來說,也決定了時間順序.同樣的它也提供了了一個增強(amplification)的附加功能,使每一段訊號強度都能回到最大值.即使當輸入的水流因流過細長的管路或因漏損造成壓力減低,輸出的水壓仍然會因活門的開關動作而達到最大壓力.這就是數位(digital)和類比(analog)最大的不同.數位活門不是開就是關,類比就像是水龍頭一樣,可以任意控制水量大小.在流體電腦中,所有輸入訊號只要強到足以移動活塞就可以了,因此這裡所謂[造成顯著改變的差異]就是推動活塞的水壓大小. 既然由於輸入一個微弱訊號仍可以得到最強的輸出訊號,我們就可以連接上千層的邏輯函數,用其中一層的輸出訊號控制下一層邏輯,而不用擔心會有壓力減弱的情形發生,因為每個閘門的輸出訊號都是最強. 這設計型態稱為復原邏輯(restoring logic),而這個流體裝置的例子也特別有趣,因為它與現今電子計算機所用的邏輯幾乎相同.水管的水壓=電路的電壓,液壓活門=用金屬氧化物作成的電晶體,活門上的控制端 輸入端 輸出端=電晶體中的三個接點 閘極(gate) 源極(source) 汲極(drain) ...

# 演算法 ## 演算法與啟發式解法 不論是不是用來處理數字,演算法(algorithm)是一種萬全的程序,保證能達成特定的目的.[演算法]一詞源自阿拉伯數學家花拉子密(al-Khwarizmi),它在9世紀時發明許多演算法.在英文中代數(algebra)這個字其實源自於調換(al jabr)之意.花拉子密的許多演算法至今仍被廣泛使用. 電腦演算法通常以程式描述,由於演算法一詞主要描述的是操作順序,因此相同的演算法可以用不同的電腦語言描述,甚至連接適當的暫存器及邏輯閘於硬體上,以建立另一種演算法. 通常,很多演算法都可以得到相同的結果,只是不同的演算法完成同一件工作的時間不同.某些演算法可能有其他的優點,也許它所需的記憶體較少,或是使用的的訊息模式特別簡單,因此很容易將線路連接於硬體中.好的演算法和壞的演算法對時間與記憶體的需求往往相差超過數千倍,甚至數百萬倍.有時發現新的演算法可以讓你解決一個困擾多時的問題. 由於演算法能以各種方式執行,而且能應用在不同難易度的問題上,因此無法只用解決某個問題所花的時間來評斷演算法的速度,因為解題時間是依執行方式及問題大小而異.通常我們會以解題時間與問題大小之間的關係來描述演算法的速度.撰寫電腦程式最大的樂趣再於找到一種更新更快更有效率的方式來處理問題. ## 最佳演算法 最佳演算法往往不是那麼顯而易見.現在我們想辦法將一疊依序編號的卡片,按遞增順序排列.有一種排列方式是先找出最小的卡片,將它取出後放到一邊.然後在剩下的卡片中再取出編號最小的卡片,將它放在剛才取出的第一張卡片上面.重複這過程直到所有的卡片抽完,會得到一疊依遞增順序排的卡片.以這種方式抽出每一張卡片時,都要先檢視剩下未排序的卡片,若剩下 n 張卡片,則每一次都要比較 n 張卡片上的數字,因此這個演算法執行時間的級數為n**2(n 張卡片 X 比較 n 次). 若我們知道卡片上的編號為 1~n,則可以用另一種方式排序.這方式是利用遞迴定義.要以遞迴檢視一疊卡片時,首先檢視全部的卡片,將所有小於平均值的卡片湊一堆,而大於平均值的卡片置於另一堆,再以同樣的方式處理這2堆卡片,則會得到4堆卡片,以此類推,每遞迴一次,每疊卡片的數量便會減半,最後當每疊卡都只剩一張時,排序工作就完成了.由於這個演算法會反覆將卡片對分,直到剩下一張卡為止,因此他所需要的時間與n張卡片可以對分的次數成正比,也就是以2為底,取 n 的對數(log n),所以這演算法的時間級數為 nlog n.除此之外還有一個更優雅的遞迴演算法,卡片的排列方式不必依序編號,它是將名片依英文字母順序排列時所用的演算法.這種演算法蠻有用的,稱為合併排序(merge sort).雖然不太容易理解.若有兩疊已排序的卡片,則我們只要不斷選取兩疊卡片中,頂端那張字母順序較前的卡片,便可以輕易得到一疊排序過的卡片,合併排序就是利用這個特性.這個合併過程只是合併排序的副程式,而整個演算法運作方式如下-若每疊只有一張卡片,則卡片已完成排序,否則將卡片分成兩半,再以遞迴的方式對這兩半作排序合併的動作,合併排序演算法式展現遞迴及簡潔的絕佳示範. ## 旅行推銷員問題 有一個典型的難題叫旅行推銷員問題(traveling salesman problem).想象有個到處旅行的旅行員要拜訪n個城市,假使已知任兩個城市的距離,那旅行員應以什麼樣的順序走訪這n個城市,才能使總距離最短?沒人知道這問題應以多少級數的演算法才能解決,是 n2 還是 n 的任何次方?若已知的最佳演算法級數為 2n,這表示解題時間隨時間大小呈指數次方成長, Ex.若我們將推銷員拜訪的城市個數增加10個,則問題的難度就增加了1000倍(210=1024),若增加30個,則難度將變成10億倍(230約為10**9).指數演算法在問題變大時就沒什麼用處,但對旅行推銷旅行員問題而言,這是目前所知最佳的演算法.旅行推銷員問題看起來也許不重要,但它卻和許多問題是相當的,也就是所謂的N-P完全問題(N-P complete problem,N-P表示[nondeteministic polynomial],非決定性多項式),而這樣的演算法對這些問題都很有用.若能迅速解答旅行推銷員問題,也就能立刻得到這些問題的解答,果真如此的話,要破解機密資料的密碼就變得輕而易舉了.電腦科技在解決旅行推銷員問題仍然沒什麼突破,即使是運算速對非常快的電腦,也會因多加了幾個城市而變的遲緩. 像旅行推銷員這樣的難題,對電腦來說並不是最最困難的,有些問題的解題時間甚至超過指數級數.也有些無法用演算法解不可計算問題,即使某些問題有演算法可解,但也未必是最好的解法,但依定義來看,演算法是保證能夠完成所要執行的工作,但這樣的保證往往需要付出相當高的代價,在許多型況下,使用[幾乎]能夠得到正確答案的程序更切何實際.一般來說,[幾乎]就已經夠不錯了,若一個法則傾向於得到正解,卻不能保證得到正解,則我們稱之為啟發式解法(heuristic).使用啟發式解法往往比演算法來得實際. 啟發式解法在使用上,最間單的例子就是西洋棋遊戲程式.一個聰明的程式設計師,即使他只有普通的棋藝,卻可以寫出打敗自己的西洋棋程式.這種程式並非演算法,因為它不保證穩贏.啟發式解法是利用經驗及知識做各種猜測,而好的啟發式解法往往能做出正確的判斷.電腦的某些最令人印象深刻的行為都是啟發式解法,而非演算法.要寫出良好的下棋程式,則可以下列啟發式解法作為依據: 1 計算棋盤上所剩的棋子,以評估每位玩家相對的局勢. 2 將棋子下在往後幾步內所能預料的最佳位置. 3 假設對手採取與你相似的策略. 這些法則只是大概的策略,我們也可以想像它們失誤的情況.玩家的相對局勢除了要看所剩的棋子外,棋子所在的位置也很重要.好的位置往往比多一個子來得有利. 利用這些啟發式法則,可以寫出一個下棋程式,模擬往後幾步內所有看起來可行的棋路.最好能同時考慮所有看起來可行與不可行的棋路,並盡可能延長到遊戲結束. 對井字遊戲而言是很容易,但對西洋棋來說,這麼做是不切實際的,即使是用最快的電腦也是如此.在西洋棋遊戲中,玩家有36種移動方式,而每一種移動方式又導致對方有36種回應的可能,平均來說,玩西洋棋時至少都會持續80步以上,因此電腦必須在36**80種可能的狀態中搜尋,這種搜尋即使是最快的電腦也要花上百年的時間才能完成.假設(2)是正確的,並同意最佳路線即為未來幾步內使玩家處於最有利地位的棋路,再指定下棋程式檢視往後的六個步驟.根據(1),下棋程式會檢視六個步驟後雙方的局勢.有了這些假設,再接下來的六個步驟中,電腦不能只選它最想走的路,因為其中還參雜著對手所下的棋子.因此我們必須假設對手會選擇對他自己有利的棋路,這就是(3).因此電腦會沿著六個步驟的所有可能棋路,輪流扮演黑白雙方的棋子.程式在電腦記憶體中的虛擬棋盤上遊走,就像西洋棋大師在腦海中摹想它的棋路一樣.評估黑白棋形式的程式會遞迴的呼叫副程式. 大部分的下棋程式會加入一些額外的啟發式法則,已停止搜尋工作,並對可能的棋路做更深度的搜尋,包括犧牲自己的棋子兌換對方的棋子.這些啟發式法則只是一些附加的揣測,在某些情況下可以改善搜尋品質,但同時可能會造成其他方面的失誤.精雕細琢之後,這個基本搜尋程式幾乎就是所有下棋程式的核心.由於電腦的速度足以考慮數百萬條可能的路線因此它非常有效率,而在這幾百萬條棋路中,總有一條出乎程式設計師意料之外的,甚至連西洋棋高手也無法預測,這就是為什麼在與電腦下棋時,程式設計師往往被電腦打敗. 在電腦程式中,利用啟發式法則在可能狀態中搜尋是相當普遍的,而且也有比玩遊戲更重要的應用,它通常也是電腦尋找[創造性]答案的一種方式,這類問題的解答通常落在一組非常龐大卻有限的可能狀態所成的集合中,我們稱這個集合為搜尋空間(search space).西洋棋的搜尋空間是由一組所有能的棋路所成的集合,而旅行推銷員問題的搜尋空間是連接每個城市的所有可能路徑.由於這些空間非常龐大,無法條列式一一搜索,因此必須靠啟發式法則縮小搜尋範圍,像井字遊戲這種搜尋空間很小的問題,條列式搜尋則是最佳的方式,因為它能保證得到正確答案. 搜尋空間之所以龐大,乃因那些可能狀態是產生於簡單元素的組合,這些元素導致了可能狀態的[組合爆炸],它隨著組合元素的增加呈指數倍爆炸性成長.由於可能狀態是由元素組合所產生的,因此在這個空間中會有距離的觀念,公有元素組合出來的距離比稀有元素組合出來更為接近. 可以想像這些可能狀態是落在一處二維風景中,有時也稱為適切度風景(fitness landscape).每個可能解答的適切度或分數以風景中某一點的高度來表示.若相似的可能解有相近的分數,則相鄰的點有相似的高度,因此可以明確的定義出山丘及溪谷,找尋最佳解就等於尋找最高峰. 要搜尋這樣的空間,最簡單的方式就是隨機挑選一些點加以比較,並紀錄其中最好的點.這種方式所能搜尋的點數只受限於時間,而且它可以應用在任一空間上,這就好像叫一群傘兵跳到這風景的不同位置上,然後叫他們回報所在位置的高度.這種搜尋方式並不是很有效率. 在旅行推銷員問題這樣的搜尋空間裡,鄰近的點可能有著相近的分數,通常較適合的搜尋方式是在相鄰的點跟點之間遊走,就如在丘陵地上只有往上攀爬才能找到頂峰一樣,所對應的啟發式法則就是在搜尋空間裡選擇相鄰的兩解中最佳者. 這方法稱為登山法則(hill climbing),弱點在於你即使登上了某座山的山頂也不保證是最高的山頂.登山法則是一種啟發式法則,並非演算法.還有其他類似登山法則的啟發式法則,而且比較部會困於某座山的頂端.Ex.可由一些隨機抽出的位置開始反覆以登山法則向上攀豋,或往下走,避免困於山頂.登山法則這類的啟發式方法在處理旅行者問題時非常有效,它可以再短時間內得到一組不錯的解,即使有數千個城市,由合理的猜測為出發點,並逐次改善,找出最佳解.利用啟發式法則,我們幾乎能得到幾乎是最佳途徑.要想出針對旅行推銷員問題的迅速啟發式解法並不難,困難的是如何找到最快的演算法. 在許多問題上,並不需要每次都得到最佳解,只要一個能被接受的次佳解即可,因為即使有最完美的解答,我們也未必做得到.對這類的問題電腦會根據知識經驗猜出一個深思熟慮的答案,由於電腦能考慮的組合及可能性極多,因此它所做的猜測常常讓程式設計師驚訝.當電腦使用啟發式法則時,它可能讓我們驚喜,但不免犯錯,因此使它變得有點像人類而不像機器. ...

# 與硬體對話 就像布林邏輯和有限狀態機是電腦硬體的建構區組一樣,程式語言等於是組成電腦軟體的建構區組.和人類的語言一樣,程式語言也有字彙和文法,但不同的是,程式語言的每個字句都有其確切的意義.大部分程式語言就如同布林邏輯是通用的,它們可以描述任何電腦所做的事情. 告訴電腦你要做的事情並不如想像中的容易,必須精確描述任何要求電腦進行的細節與步驟. 程式語言種類繁多,照成多樣性的主要因素包括歷史、習慣及喜好等等,但這些不同的程式語言之所以能繼續存在,主要是因為他們在描述不同事物上各有所長.每種語言都有自己的語法,你必須學會它才能撰寫程式,但與法並非語意的基礎,也不是表達語言的動力,而是像一般語言中的拼字和標點符號一樣.就表達語言的動力而言,最重要在於字彙,亦稱為語言的原詞(primitive),以及如何用原詞組合新概念的方法. 電腦語言有很多種,如 LISP Ada FORTRAN C ALGOL 之類,有些語言對於定義遞迴運算,或在處理非數值資料上有其限制,有些則可以讓程式設計師直接操作位元資料.最近新一代的電腦語言漸漸出頭,就是所謂的物件導向(object-oriented)語言,如 Small-Talk C++ Java 等.這些語言將所要處理的資料結構(如螢幕上的圖形)視為擁有屬性的[物件],這些屬性好比圖畫的位置、顏色等等,而物件可以接受其他物件的命令. 物件導向程式語言最大的優點在於它可以個別定義不同的物件,如電腦遊戲中的各種物件,然後再將物件組合在一起變成新的程式.寫一個新的物件導向程式有點像是把一群動物關在一個籠子裡,然後靜觀其變.在這些虛擬物件互相作用的過程中,程式的行為便浮現出來. 有限狀態機如何執行 logo 這類語言所下的指令?要回答這個問題,我們必須再回到布林邏輯這個層面詳加討論.有限狀態機和 logo 語言之間有三個主要步驟加以連結.首先,我們要了解有限狀態機在加上記憶體(memory)這樣的儲存裝置後,是如何延伸、擴充的,而記憶體可以讓電腦儲存它被要求執行的動作.其次,我們將看到擴充後的有限狀態機是如何依機械語言(machine language)的指令運作,這種語言是一種很簡單的語言,可以明確地指示機器所要執行的運算.最後,我們則會看到機械語言是如何指揮機器解讀logo這類程式語言. 電腦其實只是一種連接了記憶體的有限狀態機.電腦的記憶體,實際上相當於許多用來儲存資料的小隔間組成的陣列,由暫存器建構成,和儲存有限狀態機的狀態所用的暫存器相同. 每個暫存器都可以容納一組位元,稱之為字組(word),這些字組可以被有限狀態機讀取或寫入.每部電腦的字組所含的位元數可能都不太一樣,但現今的微處理器通常是8位元 16位元或32位元(隨科技的進步,字組的位元數也越來越大,如64位元).一般記憶體可能有上百萬個甚至數十億個這樣的暫存器,而每個暫存器都可容納一個字組.在同一時間內,每次只能存取一個記憶體中的暫存器,也就是說在有限狀態機的每個循環中,只能寫入或讀取一個暫存器中的資料. 每個暫存器都有不同的位址(address),位址是一組位元的組合形態,可藉由它找到特定的暫存器,因此暫存器也稱為記憶體中的位置(locations in menory),記憶體包含了一些可以解碼的布林邏輯區組,用以選擇所要寫入或讀取的位置.如果要在某個記憶體位置寫入資料,這些邏輯區組便將新資料寫入指定的暫存器中.若要讀取資料,這些邏輯區組也會將資料由指定的暫存器中引導到記憶體的輸出端,而這個輸出端是連接在有限狀態機的輸入端. 記憶體所儲存的字組有些是要運算的資料,如數字和字母等,也可能是指令,告知電腦執行運算的程序.指令以機械語言的方式儲存.機械語言比一般程式語言來的簡單.機械語言可直接由有限狀態機解讀,在我們所介紹的電腦中,每個機械語言指令都以一個字組儲存,而指令就儲存再一塊依序編號的記憶體位置中,這一連串的機械語言指令就是電腦中最簡單的軟體. 有限狀態機會重複執行下列的程序 1.讀取(read)記憶體中的指令. 2.執行(execute)這個指令所代表的運算. 3.推算(calculate)下一個指令所在的位址. 完成這些工作所需的狀態順序就建構在有限狀態機的布林邏輯中,而指令本身則以位元表示,這些位元組可使有限狀態機對記憶體中的資料作各種運算.例如, Add 指令為一個特定的位元組合,它表示將記憶體中的兩個暫存器相加,當有限狀態機辨識出這個位元組後,會透過一連串的狀態轉換將記憶體中要加總的資料讀出,然後相加,再將總和寫回記憶體. 大部分電腦中都有兩種最基本的指令-運算指令(processing instruction) 控制指令(control instruction). 運算指令是由記憶體存取資料,然後將資料做算數或邏輯計算,而資料所在的記憶體位址或暫存器也是由運算指令所指定.通常指令只與少數暫存器有直接關聯,而以間接的方式對其他暫存器下指令,因為它的位址是存在別的暫存器. EX. Move 指令可將暫存器1中的資料搬移到暫存器2指定的位址上. 控制指令則決定下一個呼叫的指令所在的位址,這個位址儲存在一個特別的暫存器中,稱為程式計時器(program counter).在正常的狀態下,指令從連續的記憶體位置中依序叫出,所以每當叫出一個指令後,程式計數器就會自動加1.控制指令可以改變程式計數器的內容,藉此改變程式執行的順序.最簡單的就是Jump指令它可以將指定的位址儲存在程式計數器中,因此下一個指令便會從此位置中呼叫出.另外還有一種條件式的Jump指令,它只在符合條件的狀態下才會改變程式計數器的內容. 若要重複執行一串相同的指令,則可以在這串指令結束時,利用條件式 Jump 指令將程式計數器移回開始的地方,重複幾次都行,這動作稱為迴圈(loop). ...