1樓:手機使用者
計算理論 【theory of ***putation】 用來研究計算的過程與功效的數學理論。
可計算性理論的學科簡介
2樓:寶寶
可計算性理論是研究計算的一般性質的數學理論,也稱演算法理論或能行性理論。它通過建立計算的數學模型(例如抽象計算機),精確區分哪些是可計算的,哪些是不可計算的。計算的過程就是執行演算法的過程。
可計算性理論的重要課題之一,是將演算法這一直觀概念精確化。演算法概念精確化的途徑很多,其中之一是通過定義抽象計算機,把演算法看作抽象計算機的程式。通常把那些存在演算法計算其值的函式叫作可計算函式。
因此,可計算函式的精確定義為:能夠在抽象計算機上編出程式計算其值的函式。這樣就可以討論哪些函式是可計算的,哪些函式是不可計算的。
可計算性是指一個實際問題是否可以使用計算機來解決.從廣義上講如「為我烹製一個漢堡」這樣的問題是無法用計算機來解決的.而計算機本身的優勢在於數值計算,因此可計算性通常指這一類問題是否可以用計算機解決.事實上,很多非數值問題(比如文字識別,圖象處理等)都可以通過轉化成為數值問題來交給計算機處理,但是一個可以使用計算機解決的問題應該被定義為「可以在有限步驟內被解決的問題」,故哥德**猜想這樣的問題是不屬於「可計算問題」之列的,因為計算機沒有辦法給出數學意義上的證明,因此也沒有任何理由期待計算機能解決世界上所有的問題.分析某個問題的可計算性意義重大,它使得人們不必浪費時間在不可能解決的問題上(因而可以儘早轉而使用除計算機以外更加有效的手段),集中資源在可以解決的問題集中. 若m和n是兩個正整數,並且m≥n時,求m和n的最大公因子的歐幾里得演算法可表示為
e1[求餘數]以n除m得餘數r。
e2[餘數為0嗎?]若r=0,計算結束,n即為答案;否則轉到步驟e3。
e3[互換]把m的值變為n,n的值變為r,重複上述步驟。
依照這三條規則指示的步驟,可計算出任何兩個正整數的最大公因子。可以把計算過程看成執行這些步驟的序列。我們發現,計算過程是有窮的,而且計算的每一步都是能夠機械實現的(機械性)。
為了精確刻劃演算法的特徵,人們建立了各種各樣的數學模型。
計算理論基礎的問題
3樓:百度使用者
elements of the theory of ***putation 2nd ed.)harry r. lewis, christos h.
papadimitriou 編著 張立昂 劉田 譯 計算理論是電腦科學的理論基礎。本書介紹了計算理論最核心、最基本的內容,包括形式語言與自動機、可計算性和計算複雜性三大部分。全書共分七章,分別為:
集合、關係和語言;有窮自動機;上下文無關語言;turing機;不可判定性;計算複雜性;np完全性。本書突出了演算法,從而使計算機專業的學生更易於接受,也更有收益。 譯者在譯者序中寫道:
「我之所以願意翻譯這兩本書,一是因為它們確實是兩本關於計算理論的優秀教材;二是因為國內太缺乏這樣的書了,儘管計算機類書刊極其繁多,可是計算理論的書卻難覓蹤影。」「特別希望立志致力於電腦科學技術事業的青年學生都來認真地學一點計算理論,那將可能是終身受益的。」 本書適合作為計算機專業及數學專業本科生或研究生的教材,也可供從事電腦科學的教學與研究人員參考。
前言: 看看你的周圍,計算無處不在,無時不在,每一個人都計算,計算影響著所有的人。所以能夠如此,是因為在過去的幾十年中電腦科學家發現了很複雜的方法用來管理計算機資源,實現通訊,翻譯程式,設計晶片和資料庫,創造更快、更廉價、更容易使用、更安全的計算機和程式。
和所有的主要學科一樣,電腦科學的成功實踐建立在優美和堅實的基礎之上。自然科學有一些基本問題,如物質的本質是什麼?有機體生命的基礎和起源是什麼?
電腦科學同樣有它自己的基本問題:什麼是演算法?什麼是能計算的?
什麼是不能計算的?什麼時候可以認為一個演算法是實際可行的?60多年來(甚至從電子計算機出現之前就開始了)電腦科學家一直在考慮這些問題並且給出充滿智慧的回答,這一切對電腦科學產生了深刻的影響。
本書的目的是介紹滲透在電腦科學中的這些基本思想、模型和結果,它們都是該領域的基本範例,它們有很多理由是值得學習的。首先,現代電腦科學中的很多東西直接或間接地以它們為基礎——而其餘的應該......。其次,這些思想和模型是漂亮、有力的,是數學建模的傑出例子,是有長久價值的。
此外,它們更是歷史的一部分,是我們這個領域的「共同潛意識」。不首先了解它們,是很難理解電腦科學的。 這些思想和模型在本質上是數學的,這大概不會讓人感到奇怪。
雖然計算機肯定是一個物理實體,但是同樣肯定的是關於它的物理方面,如它的分子和它的形狀,能夠值得說的很少;對計算機最有用的抽象顯然是數學的,論證這些抽象所必需的手段也一定同樣是數學的。此外,實際的計算工作需要只有數學才能提供的鐵的保證(希望我們的編譯程式正確地翻譯,應用程式最終停機,等等)。但是,在計算理論中使用的數學與其他應用學科中使用的數學有很大的區別,它一般是離散的,在這裡不強調實數和連續變數,而強調有窮集合和序列。
它以很少幾個基本的概念為基礎,通過小心、耐心、仔細、一層一層地處理這些概念,勾畫出它的能力和深奧之處——這很像計算機,在第1章將使你回想這些基本的概念和方法(其中有集合、關係和歸納法),介紹在計算理論中使用它們的風格。 第2章和第3章描述某些受限制的計算模型。它們能夠完成一些非常特殊的字串處理工作,例如回答一個給定的字串是否出現在給定的正文中,如字punk是否出現在莎士比亞文集中,或者檢查一個給定的括號字串是否正好平衡——像()和(())(),而不是)()的樣子。
這些受限制的計算模型(分別叫做有窮自動機和下推自動機)竟然作為像電路和編譯程式之類很普通的系統的非常有用和高度完善的部分出現在現實生活中。在這裡它們為我們探索演算法的一般的形式定義提供極好的熱身練習。此外,看到由於增加或刪除各種特性這些裝置的能力如何增強和減弱(或者,更經常地是,保持不變)是有教益的。
其中最值得注意的特性是非確定性,計算的這個迷惑人的特性既是重要的,又是(相當荒謬地)非現實的。 在第4章,我們研究演算法的一般模型,其中最基本的模型是turing機以卓越的英國數學家和哲學家alan m.turing (1912—1954)的名字命名。
他在2023年發表的開創性的**標誌計算理論的誕生。turing也是人工智慧和計算機下棋以及生物學中形態形成領域中的先驅者。在第二次世界大戰中,他幫助破譯德國海軍密碼enigma。
想更多地瞭解他迷人的一生(以及他最後悲慘地死在官方殘忍和偏執的手中)請閱讀《alan turing: the enigma》,andrew hodges 著,new york: simon schuster,2023年。。
turing機是第2章和第3章中字串處理裝置的相當簡單的推廣,結果令人吃驚地成為描述任意演算法的一般框架。為了證明這一點,即通常所說的church turing論題,我們引入越來越複雜的計算模型(turing機更強的變種,還有隨機存取turing機和遞迴定義的數值函式),並且證明它們在能力上全都完全等價於基本的turing機模型。 再下一章處理不可判定性。
某些自然的明確的計算任務具有這種出人意料的性質,可以證明它們超出了演算法能夠解決的範圍。例如,問你是否能用給定的若干種形狀的磚鋪整個平面。如果這些形狀中包括一個正方形,或者甚至一個三角形,則答案顯然是「能夠」。
但是,如果是幾種稀奇古怪的形狀,或者規定幾種形狀必須至少使用一次,那會怎樣?這肯定是很複雜的問題,你想用機器給出回答。在第5章我們使用turing機的形式表示證明這個問題和許多其他問題是根本不可能用計算機解決的。
即使當一項計算任務能夠用某個演算法解決的時候,也可能不存在解決它的適當快的、實際可行的演算法。在本書的最後兩章,我們說明怎麼用它們的複雜性對現實生活中的計算問題進行分類:某些問題能夠在合理的,即多項式的時間界限內解決,而另一些問題似乎需要以天文速度,即指數地增長的時間。
在第7章我們定義一個叫做np完全的問題類,它們是一些普通的、實際的、但難得出名的問題(旅行商問題僅是它們中的一個)。我們證明所有這些問題在下述意義下是等價的:如果它們中的一個有有效的演算法,則它們每一個都有有效的演算法。
普遍地相信所有np完全問題具有固有的指數複雜度;這個猜想是否實際上為真是著名的p≠np問題,它是當代數學家和電腦科學家面臨的最重要和最深刻的問題之一。 本書有很多篇幅是有關演算法及其形式基礎的。然而,大概你也意識到了,在今天的電腦科學教學計劃中,演算法課程,包括演算法的分析和設計,相當地脫離計算理論的課程。
在本書的現行版本中,我們試圖恢復這門課程的某種統一性。結果是,本書對演算法也提供了相當不錯的介紹,只是有些專門和非傳統。在第1章形式地介紹演算法及其分析,並且在第2章和第3章研究受限制的計算模型和由它們產生的自然的計算問題的時候一再重新提起。
這樣一來,在後面探索演算法的一般模型的時候,讀者處在較好的位置,能正確評價這種探索的目標並且斷定是能成功的。在講解複雜性時演算法同樣擔任主角。因為鑑別複雜問題的最好方法是把它與另一個經得起有效演算法考驗的問題進行比較。
最後一章用一節敘述對付np完全性作為結束,給出在遇到np完全問題時已經成功地使用過的演算法技術(近似演算法、窮舉演算法、啟發式區域性搜尋等)。 計算是必不可少的、有力的、優美的、具有挑戰性和不斷髮展的——它的理論也是如此。本書僅講了一個激動人心的故事的開頭,它是對從計算理論寶庫中精選出的少量基本論題的樸素介紹。
我們希望它將激發讀者去作進一步的探索,每一章最後的參考文獻指出了好的出發點。 目錄: 譯者序(iii) 第一版序言(v) 第二版序言(vii) 導言(ix) 第1章集合、關係和語言(1) 1 1集合(1) 1 2關係與函式(4) 1 3特殊型別的二元關係(7) 1 4有窮集合與無窮集合(11) 1 5三個基本的證明技術(13) 1 6閉包與演算法(17) 1 7字母表與語言(25) 1 8語言的有窮表示(29) 參考文獻(33) 第2章有窮自動機(34) 2 1確定型有窮自動機(34) 2 2非確定型有窮自動機(39) 2 3有窮自動機與正規表示式(47) 2 4正則語言與非正則語言(54) 2 5狀態最小化(58) 2 6關於有窮自動機的演算法(65) 參考文獻(70) 第3章上下文無關語言(72) 3 1上下文無關文法(72) 3 2語法分析樹(79) 3 3下推自動機(83) 3 4下推自動機與上下文無關文法(87) 3 5上下文無關語言與非上下文無關語言(92) 3 6關於上下文無關文法的演算法(97) 3 7確定性與語法分析(102) 參考文獻(115) 第4章turing機(117) 41turing機的定義(117) 4 2用turing機計算(125) 43turing機的擴充(130) 4 4隨機存取turing機(136) 4 5非確定型turing機(144) 4 6文法(148) 4 7數值函式(151) 參考文獻(158) 第5章不可判定性(160) 51church turing論題(160) 5 2通用turing機(161) 5 3停機問題(163) 5 4與turing機有關的不可判定問題(166) 5 5與文法有關的不可解問題(168) 5 6不可解的鋪磚問題(172) 5 7遞迴語言的性質(174) 參考文獻(178) 第6章計算複雜性(179) 61p類(179) 6 2若干問題(181) 6 3布林可滿足性(187) 64np類(190) 參考文獻(194) 第7章np完全性(196) 7 1多項式時間歸約(196) 72cook定理(202) 7 3其他的np完全問題(207) 7 4對付np完全性(218)
麻煩採納,謝謝!
計算複雜性的內容簡介，計算複雜性理論的簡介
複雜性理論是計抄 算機科學的理論基礎的核心。本書是著名電腦科學家oded goldreich的力作，書中對計算任務固有複雜性研究進行了概念性介紹，全面分析了複雜性理論的現代主題。本書涉及複雜性理論的很多子領域 如難度放大 偽隨機性及概率證明系統等 涵蓋了np完整性 空間複雜性 隨機性和計數 偽隨機數...
物業裝置設施的可靠性理論是什麼,可靠性理論指的是什麼
物業裝置設施的可靠性是指其無故障連續運轉工作的效能 可靠性理論指的是什麼?可靠性是產品在規定的條件下和規定的時間內完成規定功能的能力。它涉及產品 規定條件 規定時間 規定功能和能力5個因素。其中,規定時間是可靠性定義的核心,規定時間的長短隨著產品物件不同和使用目的不同而異。因此,討論可靠性時必須事先...
運用微觀經濟學的彈性理論如何分析易腐商品的售賣
銷售者首先要準確地瞭解市場上一天內對鮮魚的需求曲線，然後根據消費者的需求曲線及準備 的鮮魚數量，來確定能使其獲得最大收入的最優 此原則不止運用於易腐商品的銷售，對任何產品的銷售都適用。易腐商抄品由於具有易腐的特點，必須在一定時間內售賣，否則銷售者會蒙受經濟損失。以夏天的鮮魚銷售為例，如果鮮魚的銷售者...