什么是計算：直觀地看姥卢，計算一般是指運(yùn)用事先規(guī)定的規(guī)則卷要，將一組數(shù)值變換為另一(所需的)數(shù)值的過程．對某一類問題，如果能找到一組確定的規(guī)則独榴，按這組規(guī)則僧叉，當(dāng)給出這類問題中的任一具體問題后，就可以完全機(jī)械地在有限步內(nèi)求出結(jié)果棺榔，則說這類問題是可計算的瓶堕。這種規(guī)則就是算法。

當(dāng)時的科學(xué)家為了證明世界上的所有東西都是可以有一個某種特定的算法去實現(xiàn)的掷豺，結(jié)果后來發(fā)現(xiàn)錯了捞烟，某些東西算法解決不了，那么哪些是算法能解決也就是可計算函數(shù)的哪些又是不能解決的呢当船？為了解決這個問題，科學(xué)家提出了算法可計算函數(shù)等同于一般遞歸函數(shù)或λ可定義函數(shù)默辨，這就是著名的“丘奇論點”德频。

用一般遞歸函數(shù)雖給出了可計算函數(shù)的嚴(yán)格數(shù)學(xué)定義，但在具體的計算過程中缩幸，就某一步運(yùn)算而言壹置，選用什么初始函數(shù)和基本運(yùn)算仍有不確定性。為消除所有的不確定性表谊，圖靈在他的“論可計算數(shù)及其在判定問題中的應(yīng)用”一文中從一個全新的角度定義了可計算函數(shù)钞护。他全面分析了人的計算過程，把計算歸結(jié)為最簡單爆办、最基本难咕、最確定的操作動作，從而用一種簡單的方法來描述那種直觀上具有機(jī)械性的基本計算程序，使任何機(jī)械(能行)的程序都可以歸約為這些動作余佃。這種簡單的方法是以一個抽象自動機(jī)概念為基礎(chǔ)的暮刃，其結(jié)果是：算法可計算函數(shù)就是這種自動機(jī)能計算的函數(shù)。這不僅給計算下了一個完全確定的定義爆土，而且第一次把計算和自動機(jī)聯(lián)系起來椭懊，對后世產(chǎn)生了巨大的影響，這種“自動機(jī)”后來被人們稱為“圖靈機(jī)”步势。

圖靈把可計算函數(shù)定義為圖靈機(jī)可計算函數(shù)．1937年氧猬，圖靈在他的“可計算性與λ可定義性”一文中證明了圖靈機(jī)可計算函數(shù)與λ可定義函數(shù)是等價的，從而拓廣了丘奇論點坏瘩，得出：算法(能行)可計算函數(shù)等同于一般遞歸函數(shù)或λ可定義函數(shù)或圖靈機(jī)可計算函數(shù)．這就是“丘奇-圖靈論點”狂窑，相當(dāng)完善地解決了可計算函數(shù)的精確定義問題，對數(shù)理邏輯的發(fā)展起了巨大的推動作用桑腮。

圖靈機(jī)的概念有十分獨特的意義：如果把圖靈機(jī)的內(nèi)部狀態(tài)解釋為指令泉哈，用字母表的字來表示，與輸出字輸入字同樣存貯在機(jī)器里破讨，那就成為電子計算機(jī)了丛晦。由此開創(chuàng)了“自動機(jī)”這一學(xué)科分支，促進(jìn)了電子計算機(jī)的研制工作．

與此同時提陶，圖靈還提出了通用圖靈機(jī)的概念烫沙，它相當(dāng)于通用計算機(jī)的解釋程序，這一點直接促進(jìn)了后來通用計算機(jī)的設(shè)計和研制工作隙笆，圖靈自己也參加了這一工作锌蓄。

在給出通用圖靈機(jī)的同時，圖靈就指出撑柔，通用圖靈機(jī)在計算時瘸爽，其“機(jī)械性的復(fù)雜性”是有臨界限度的，超過這一限度铅忿，就要靠增加程序的長度和存貯量來解決．這種思想開啟了后來計算機(jī)科學(xué)中計算復(fù)雜性理論的先河剪决。

關(guān)于算法和計算機(jī)

算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令檀训，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制柑潦。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入峻凫，在有限時間內(nèi)獲得所要求的輸出渗鬼。如果一個算法有缺陷，或不適合于某個問題荧琼，執(zhí)行這個算法將不會解決這個問題譬胎。不同的算法可能用不同的時間差牛、空間或效率來完成同樣的任務(wù)。一個算法的優(yōu)劣可以用空間復(fù)雜度與時間復(fù)雜度來衡量银择。

算法中的指令描述的是一個計算多糠，當(dāng)其運(yùn)行時能從一個初始狀態(tài)和（可能為空的）初始輸入開始，經(jīng)過一系列有限而清晰定義的狀態(tài)浩考，最終產(chǎn)生輸出并停止于一個終態(tài)夹孔。一個狀態(tài)到另一個狀態(tài)的轉(zhuǎn)移不一定是確定的。隨機(jī)化算法在內(nèi)的一些算法析孽，包含了一些隨機(jī)輸入搭伤。

一個算法應(yīng)該具有以下五個重要的特征：

有窮性

（Finiteness）

算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止；

確切性

(Definiteness)

算法的每一步驟必須有確切的定義袜瞬；

輸入項

(Input)

一個算法有0個或多個輸入怜俐，以刻畫運(yùn)算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件邓尤；

輸出項

(Output)

一個算法有一個或多個輸出拍鲤，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的汞扎；

可行性

(Effectiveness)

算法中執(zhí)行的任何計算步驟都是可以被分解為基本的可執(zhí)行的操作步驟季稳，即每個計算步驟都可以在有限時間內(nèi)完成（也稱之為有效性）。

要素

一澈魄、數(shù)據(jù)對象的運(yùn)算和操作：計算機(jī)可以執(zhí)行的基本操作是以指令的形式描述的景鼠。一個計算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合，成為該計算機(jī)系統(tǒng)的指令系統(tǒng)痹扇。一個計算機(jī)的基本運(yùn)算和操作有如下四類：

1.算術(shù)運(yùn)算：加減乘除等運(yùn)算

2.邏輯運(yùn)算：或铛漓、且、非等運(yùn)算

3.關(guān)系運(yùn)算：大于鲫构、小于浓恶、等于、不等于等運(yùn)算

4.數(shù)據(jù)傳輸：輸入芬迄、輸出问顷、賦值等運(yùn)算

二、算法的控制結(jié)構(gòu)：一個算法的功能結(jié)構(gòu)不僅取決于所選用的操作禀梳，而且還與各操作之間的執(zhí)行順序有關(guān)。

方法

遞推法

遞推是序列計算機(jī)中的一種常用算法肠骆。它是按照一定的規(guī)律來計算序列中的每個項算途，通常是通過計算機(jī)前面的一些項來得出序列中的指定項的值。其思想是把一個復(fù)雜的龐大的計算過程轉(zhuǎn)化為簡單過程的多次重復(fù)蚀腿，該算法利用了計算機(jī)速度快和不知疲倦的機(jī)器特點嘴瓤。

遞歸法

程序調(diào)用自身的編程技巧稱為遞歸（recursion）扫外。一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解廓脆，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算筛谚，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合停忿。一般來說驾讲，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段席赂。當(dāng)邊界條件不滿足時吮铭，遞歸前進(jìn)；當(dāng)邊界條件滿足時颅停，遞歸返回谓晌。

注意：

(1) 遞歸就是在過程或函數(shù)里調(diào)用自身;

(2) 在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件癞揉，稱為遞歸出口纸肉。

窮舉法

窮舉法，或稱為暴力破解法喊熟，其基本思路是：對于要解決的問題柏肪，列舉出它的所有可能的情況，逐個判斷有哪些是符合問題所要求的條件逊移，從而得到問題的解预吆。它也常用于對于密碼的破譯，即將密碼進(jìn)行逐個推算直到找出真正的密碼為止胳泉。例如一個已知是四位并且全部由數(shù)字組成的密碼拐叉，其可能共有10000種組合，因此最多嘗試10000次就能找到正確的密碼扇商。理論上利用這種方法可以破解任何一種密碼凤瘦，問題只在于如何縮短試誤時間。因此有些人運(yùn)用計算機(jī)來增加效率案铺，有些人輔以字典來縮小密碼組合的范圍蔬芥。

貪心算法

貪心算法是一種對某些求最優(yōu)解問題的更簡單、更迅速的設(shè)計技術(shù)控汉。

用貪心法設(shè)計算法的特點是一步一步地進(jìn)行笔诵，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個優(yōu)化測度作最優(yōu)選擇，而不考慮各種可能的整體情況姑子，它省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時間乎婿，它采用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題, 通過每一步貪心選擇,可得到問題的一個最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解街佑，但由此產(chǎn)生的全局解有時不一定是最優(yōu)的谢翎，所以貪婪法不要回溯捍靠。

貪婪算法是一種改進(jìn)了的分級處理方法，其核心是根據(jù)題意選取一種量度標(biāo)準(zhǔn)森逮，然后將這多個輸入排成這種量度標(biāo)準(zhǔn)所要求的順序榨婆，按這種順序一次輸入一個量，如果這個輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最佳解加在一起不能產(chǎn)生一個可行解褒侧，則不把此輸入加到這部分解中良风。這種能夠得到某種量度意義下最優(yōu)解的分級處理方法稱為貪婪算法。

對于一個給定的問題璃搜，往往可能有好幾種量度標(biāo)準(zhǔn)拖吼。初看起來，這些量度標(biāo)準(zhǔn)似乎都是可取的这吻，但實際上吊档，用其中的大多數(shù)量度標(biāo)準(zhǔn)作貪婪處理所得到該量度意義下的最優(yōu)解并不是問題的最優(yōu)解，而是次優(yōu)解唾糯。因此怠硼，選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪婪算法的核心。

一般情況下移怯，要選出最優(yōu)量度標(biāo)準(zhǔn)并不是一件容易的事香璃，但對某問題能選擇出最優(yōu)量度標(biāo)準(zhǔn)后，用貪婪算法求解則特別有效舟误。

分治法

分治法是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題葡秒，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并嵌溢。

分治法所能解決的問題一般具有以下幾個特征：

(1) 該問題的規(guī)拿心粒縮小到一定的程度就可以容易地解決；

(2) 該問題可以分解為若干個規(guī)模較小的相同問題赖草，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)学少；

(3) 利用該問題分解出的子問題的解可以合并為該問題的解；

(4) 該問題所分解出的各個子問題是相互獨立的秧骑，即子問題之間不包含公共的子子問題版确。

動態(tài)規(guī)劃法

動態(tài)規(guī)劃是一種在數(shù)學(xué)和計算機(jī)科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法乎折。其基本思想是绒疗，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解骂澄。動態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)忌堂，被廣泛應(yīng)用于計算機(jī)科學(xué)和工程領(lǐng)域。

動態(tài)規(guī)劃程序設(shè)計是對解最優(yōu)化問題的一種途徑酗洒、一種方法士修，而不是一種特殊算法。不象前面所述的那些搜索或數(shù)值計算那樣樱衷，具有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法棋嘲。動態(tài)規(guī)劃程序設(shè)計往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同矩桂，確定最優(yōu)解的條件也互不相同沸移，因而動態(tài)規(guī)劃的設(shè)計方法對不同的問題，有各具特色的解題方法侄榴，而不存在一種萬能的動態(tài)規(guī)劃算法雹锣，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時癞蚕，除了要對基本概念和方法正確理解外蕊爵，必須具體問題具體分析處理，以豐富的想象力去建立模型桦山，用創(chuàng)造性的技巧去求解攒射。

迭代法

迭代法也稱輾轉(zhuǎn)法恒水，是一種不斷用變量的舊值遞推新值的過程会放，跟迭代法相對應(yīng)的是直接法（或者稱為一次解法），即一次性解決問題钉凌。迭代法又分為精確迭代和近似迭代咧最。“二分法”和“牛頓迭代法”屬于近似迭代法御雕。迭代算法是用計算機(jī)解決問題的一種基本方法矢沿。它利用計算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點饮笛，讓計算機(jī)對一組指令（或一定步驟）進(jìn)行重復(fù)執(zhí)行咨察，在每次執(zhí)行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值福青。

分支界限法

分枝界限法是一個用途十分廣泛的算法摄狱，運(yùn)用這種算法的技巧性很強(qiáng)，不同類型的問題解法也各不相同无午。

分支定界法的基本思想是對有約束條件的最優(yōu)化問題的所有可行解（數(shù)目有限）空間進(jìn)行搜索媒役。該算法在具體執(zhí)行時，把全部可行的解空間不斷分割為越來越小的子集（稱為分支）宪迟，并為每個子集內(nèi)的解的值計算一個下界或上界（稱為定界）酣衷。在每次分支后，對凡是界限超出已知可行解值那些子集不再做進(jìn)一步分支次泽，這樣穿仪，解的許多子集（即搜索樹上的許多結(jié)點）就可以不予考慮了席爽，從而縮小了搜索范圍。這一過程一直進(jìn)行到找出可行解為止啊片，該可行解的值不大于任何子集的界限只锻。因此這種算法一般可以求得最優(yōu)解。

與貪心算法一樣紫谷，這種方法也是用來為組合優(yōu)化問題設(shè)計求解算法的齐饮，所不同的是它在問題的整個可能解空間搜索，所設(shè)計出來的算法雖其時間復(fù)雜度比貪婪算法高笤昨，但它的優(yōu)點是與窮舉法類似祖驱，都能保證求出問題的最佳解，而且這種方法不是盲目的窮舉搜索瞒窒，而是在搜索過程中通過限界捺僻，可以中途停止對某些不可能得到最優(yōu)解的子空間進(jìn)一步搜索（類似于人工智能中的剪枝），故它比窮舉法效率更高根竿。

回溯法

回溯法（探索與回溯法）是一種選優(yōu)搜索法陵像，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)寇壳。但當(dāng)探索到某一步時醒颖，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇壳炎，這種走不通就退回再走的技術(shù)為回溯法泞歉，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。

其基本思想是匿辩，在包含問題的所有解的解空間樹中腰耙，按照深度優(yōu)先搜索的策略，從根結(jié)點出發(fā)深度探索解空間樹铲球。當(dāng)探索到某一結(jié)點時挺庞，要先判斷該結(jié)點是否包含問題的解，如果包含稼病，就從該結(jié)點出發(fā)繼續(xù)探索下去选侨，如果該結(jié)點不包含問題的解，則逐層向其祖先結(jié)點回溯然走。（其實回溯法就是對隱式圖的深度優(yōu)先搜索算法）援制。 若用回溯法求問題的所有解時，要回溯到根芍瑞，且根結(jié)點的所有可行的子樹都要已被搜索遍才結(jié)束晨仑。 而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結(jié)束。

人工智能其實也是圖靈機(jī)的延續(xù)洪己。妥凳。。

------------------------------------------

但是這些算法歸根到底都會調(diào)用邏輯門電路執(zhí)行最簡單的加減乘除位移等操作? 也就是邏輯門電路才是算法的硬件表現(xiàn)底層基礎(chǔ)形式 那么電子邏輯門和量子邏輯門電路有何區(qū)別呢码泛？

量子計算機(jī)中的信息是用量子邏輯門來進(jìn)行處理的猾封，其算法是記錄量子原理的全新算法。主要區(qū)別如下：

（1）經(jīng)典計算機(jī)中比特有0和1兩種狀態(tài)，而量子比特可以存在即不是0也不是1的狀態(tài)也可以處于0或者1的經(jīng)典態(tài)鹦马，也可以是兩種疊加態(tài)搂抒。

（2）量子邏輯電路的實現(xiàn)在復(fù)矢量空間，而電子邏輯門電路實現(xiàn)在相空間谒拴。

（3）量子邏輯門輸入輸出可逆，可以由輸出得出輸入，但是電子邏輯門不可逆阵难。

（4）量子邏輯門可以并行運(yùn)算速度指數(shù)級增長。