計(jì)算機(jī)能做什么與不能做什么

《計(jì)算機(jī)能做什么與不能做什么》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、計(jì)算機(jī)能做什么與不能做什么計(jì)算機(jī)是二十世紀(jì)人類最偉大的發(fā)明，它極大地推動(dòng)了科學(xué)技術(shù)的進(jìn)步，強(qiáng)烈地影響著人類社會(huì)生活的各個(gè)方面，并且對(duì)人類精神與智力的至尊地位提出了巨大的挑戰(zhàn)。近年來(lái)，計(jì)算機(jī)“深藍(lán)”戰(zhàn)勝了國(guó)際象棋天才霸主卡斯帕羅夫，三、四十年前人工智能前輩們的預(yù)言終于成為現(xiàn)實(shí)，從任何意義上將這都是極具震撼力的事件。這既是人類的勝利，也是計(jì)算機(jī)的勝利。計(jì)算機(jī)之所以有力量，硬件的高速發(fā)展是一個(gè)重要原因，但還不是最主要的原因。計(jì)算機(jī)的力量主要來(lái)自其軟件，軟件的核心是算法。算法是計(jì)算機(jī)的靈魂，算法的改進(jìn)所產(chǎn)生的作用要比單純提高硬件速度有效得多。算法的歷史比計(jì)算機(jī)長(zhǎng)得多，例如求兩個(gè)整數(shù)的最大公約數(shù)的歐

2、幾里德算法距今已有兩千多年的歷史了。算法的理論也極為深?yuàn)W，它不僅已是數(shù)學(xué)的一部分，而且有些內(nèi)容可以說(shuō)是元數(shù)學(xué)的一部分，例如交互式證明理論。因此，算法的研究一直是計(jì)算機(jī)研究與應(yīng)用中最具挑戰(zhàn)性的工作。計(jì)算機(jī)算法的研究有兩條截然不同的路線：一條路線研究計(jì)算機(jī)不能做什么，另一條路線研究計(jì)算機(jī)能做什么。研究計(jì)算機(jī)不能做什么早在計(jì)算機(jī)誕生之前就已經(jīng)開(kāi)始并有了明確的結(jié)論。1936年，圖林(Turing)提出了圖林機(jī)模型，用這個(gè)抽象的計(jì)算機(jī)模型定義了算法、計(jì)算、可計(jì)算等概念，證明了存在計(jì)算機(jī)不可計(jì)算的問(wèn)題，從而給出了計(jì)算機(jī)能力的界限。70年代初期，Cook、Karp定義了NP完全的復(fù)雜性類，證明了相當(dāng)多的

3、現(xiàn)實(shí)問(wèn)題是NP完全問(wèn)題。NP完全問(wèn)題用現(xiàn)有的算法求解均需要指數(shù)長(zhǎng)的時(shí)間，因此，在現(xiàn)有計(jì)算資源下實(shí)際上不大可能求解。這是人類對(duì)計(jì)算機(jī)能力的局限性又一次深刻的揭示。由此誕生的計(jì)算復(fù)雜性理論成為理論計(jì)算機(jī)科學(xué)的中心內(nèi)容。計(jì)算復(fù)雜性既是對(duì)計(jì)算機(jī)能力的一大限制，又是對(duì)人類認(rèn)識(shí)能力的一大限制。今天，計(jì)算機(jī)已成為人類認(rèn)識(shí)自然、改造自然必不可少的最有力的武器，因此，計(jì)算機(jī)不能做什么就意味著許多事人類同樣也不能辦到。研究連續(xù)問(wèn)題計(jì)算復(fù)雜性的著名學(xué)者Traub認(rèn)為，或許有可能從形式上證明某些科學(xué)問(wèn)題是無(wú)法解答的，因?yàn)橛钪嬷胁淮嬖谀軌蚪獯疬@類問(wèn)題的計(jì)算資源(時(shí)間，存儲(chǔ)器，能量等)。計(jì)算復(fù)雜性理論也使我們對(duì)什么是

4、數(shù)學(xué)中的美有了新的認(rèn)識(shí)。例如，圖論中一個(gè)著名定理是平面圖判定的Kuratowski定理，這個(gè)定理說(shuō)一個(gè)圖可平面化當(dāng)且僅當(dāng)圖中不含兩種類型的子圖。從數(shù)學(xué)上講，這是個(gè)優(yōu)美的定理。但是，直接按這個(gè)定理設(shè)計(jì)計(jì)算機(jī)程序即算法，復(fù)雜度極高！真正有效的計(jì)算機(jī)算法選擇的完全是另外一條路，其中主要是深度優(yōu)先搜索。這從數(shù)學(xué)上看似乎不太優(yōu)美，但是此算法的復(fù)雜度是線性的，因而是極其有效的。因此我們說(shuō)，計(jì)算復(fù)雜性使我們對(duì)美與效率有了新的認(rèn)識(shí)，沒(méi)有效率的美至少是不完美的。但是，以NP完全性理論為代表的計(jì)算復(fù)雜性理論也逐漸暴露出它的局限性。NP完全性理論指出，NP完全問(wèn)題的求解可能存在本質(zhì)困難。但是，NP完全問(wèn)題在科學(xué)

5、研究和生產(chǎn)實(shí)踐中廣泛存在，而且迫切需要解決。無(wú)論多么困難，這些問(wèn)題是不會(huì)消失的。因此，僅僅指出問(wèn)題的難解性是不夠的，更重要的是給出求解方法。而NP完全性理論最大的不足就是它不提供正面的解決方法。NP完全性理論的所有結(jié)論基本上是否定性的，非常容易使人在面對(duì)真實(shí)問(wèn)題時(shí)持一種悲觀、消極的態(tài)度。NP完全性理論的第二個(gè)缺陷是它僅指出用一個(gè)算法求解一個(gè)問(wèn)題的所有實(shí)例時(shí)在最壞情況下可能是指數(shù)復(fù)雜度的，而我們?cè)谡鎸?shí)世界遇到的問(wèn)題并不一定正好是最壞實(shí)例。即使對(duì)每一個(gè)算法均存在最壞實(shí)例，也并不意味著某一個(gè)實(shí)例對(duì)所有算法均是最壞的。換句話說(shuō)，NP完全性理論只是指出以不變的算法對(duì)付萬(wàn)變的問(wèn)題是存在困難的，而以萬(wàn)變

6、的算法對(duì)付萬(wàn)變的問(wèn)題則就不受NP完全性理論的限制了！可見(jiàn)，NP完全性理論給我們帶來(lái)對(duì)計(jì)算機(jī)能力局限性的深刻認(rèn)識(shí)的同時(shí)，它的非正面的、非構(gòu)造性的研究方法和研究結(jié)論也有很大的局限性。在當(dāng)前大量現(xiàn)實(shí)問(wèn)題迫切需要解決的形勢(shì)下，自然應(yīng)當(dāng)更加重視正面的、構(gòu)造性的算法研究方向，這個(gè)方向的主要內(nèi)容就是算法的設(shè)計(jì)與分析。算法設(shè)計(jì)與分析的目的是探討計(jì)算機(jī)能做什么。1995年，一批優(yōu)秀的理論計(jì)算機(jī)科學(xué)家代表理論計(jì)算機(jī)科學(xué)界總結(jié)了理論計(jì)算機(jī)科學(xué)在通訊網(wǎng)絡(luò)、并行計(jì)算機(jī)體系結(jié)構(gòu)、軟件系統(tǒng)、超大規(guī)模集成電路設(shè)計(jì)、學(xué)習(xí)理論、生物學(xué)、數(shù)學(xué)、制造、天文學(xué)等領(lǐng)域做出的貢獻(xiàn)，所有的貢獻(xiàn)都是算法的形式?？梢哉f(shuō)計(jì)算機(jī)對(duì)人類社會(huì)所做的

7、貢獻(xiàn)必須通過(guò)算法才能被接受，而計(jì)算機(jī)不能做什么的研究對(duì)大多數(shù)人來(lái)說(shuō)是不必關(guān)心的問(wèn)題。那么，從學(xué)術(shù)角度，算法復(fù)雜性理論與算法設(shè)計(jì)與分析理論是什么樣的關(guān)系呢？算法復(fù)雜性理論是算法設(shè)計(jì)與分析理論的元理論。元理論分析這個(gè)理論本身，例如對(duì)這個(gè)理論的基本概念給予精確的定義，并研究這個(gè)理論的局限性。一般而言，理論確立有用的正面結(jié)果，而元理論則多半由反面結(jié)果組成，它限定這種理論的研究范圍。因此，算法復(fù)雜性理論常給出消極結(jié)果，算法設(shè)計(jì)與分