計(jì)算機(jī)科學(xué)的本史元春-預(yù)覽頁(yè)
【正文】 第 4步 第 3步 圖靈機(jī)計(jì)算實(shí)例 —— f(x) = 2x 0 1 0 q1 q2 q3 q4 q5 q6 q7 q1 q2 q3 q4 q5 q6 q7 q1 q2 q3 q4 q5 q6 q7 1 1 0 0 1 0 第 8步 第 7步 第 6步 圖靈機(jī)計(jì)算實(shí)例 —— f(x) = 2x 0 1 0 q1 q2 q3 q4 q5 q6 q7 0 1 0 q1 q2 q3 q4 q5 q6 q7 0 1 0 q1 q2 q3 q4 q5 q6 q7 第 11步 第 10步 第 9步 圖靈機(jī)計(jì)算實(shí)例 —— f(x) = 2x 0 1 0 q1 q2 q3 q4 q5 q6 q7 0 1 0 0 q1 q2 q3 q4 q5 q6 q7 0 1 0 0 q1 q2 q3 q4 q5 q6 q7 第 14步 第 13步 第 12步 圖靈機(jī)計(jì)算實(shí)例 —— f(x) = 2x 0 1 0 0 q1 q2 q3 q4 q5 q6 q7 0 0 0 0 q1 q2 q3 q4 q5 q6 q7 0 0 0 0 q1 q2 q3 q4 q5 q6 q7 第 17步 第 16步 第 15步 圖靈機(jī)計(jì)算實(shí)例 —— f(x) = 2x 0 0 0 0 q1 q2 q3 q4 q5 q6 q7 0 0 0 0 q1 q2 q3 q4 q5 q6 q7 0 0 0 0 q1 q2 q3 q4 q5 q6 q7 第 20步 第 19步 第 18步 圖靈機(jī)計(jì)算實(shí)例 —— f(x) = 2x 0 0 1 0 0 q1 q2 q3 q4 q5 q6 q7 0 1 0 0 q1 q2 q3 q4 q5 q6 q7 1 0 0 q1 q2 q3 q4 q5 q6 q7 結(jié)束 f(2) = 22 = 4 第 21步 第 22步 圖靈機(jī)計(jì)算實(shí)例 —— f(x) = 2x 表面上看，圖靈機(jī)的計(jì)算功能似乎很弱，實(shí)際上，只要時(shí)間足夠長(zhǎng)（即允許足夠的工作步數(shù)）和有足夠的空間（即磁帶足夠長(zhǎng)），則圖靈機(jī)可以替代目前的任何計(jì)算機(jī) 圖靈論題：凡是可計(jì)算的函數(shù)都可以用圖靈機(jī)來(lái)計(jì)算： 可計(jì)算性 ＝ 圖靈可計(jì)算性 稱其理論計(jì)算機(jī)模型為通用計(jì)算機(jī) ? 只考慮到理論上的可計(jì)算性而沒有考慮計(jì)算的 復(fù)雜性 （現(xiàn)實(shí)的可計(jì)算性）； ? 不是實(shí)際的計(jì)算機(jī)，在實(shí)際的計(jì)算機(jī)研制中需要有具體的實(shí)現(xiàn)方法和實(shí)現(xiàn)技術(shù) Turing Machine ? 對(duì)于可計(jì)算的問(wèn)題，有兩個(gè)重要性質(zhì)： ? 計(jì)算時(shí)間 ：時(shí)間復(fù)雜度 (Time Complexity) ? 內(nèi)存空間 ：空間復(fù)雜度 (Space Complexity) ? 例 1：求解一元二次方程 ax2+bx+c=0 (a≠0) Computational Complexity – 輸入 a, b, c 三個(gè)常數(shù)，在有限的常數(shù)步時(shí)間內(nèi)，就可以完成計(jì)算 – 其時(shí)間復(fù)雜度和空間復(fù)雜度都是常數(shù)， O(1) .2 422aacbabx ????所以利用公式 Computational Complexity 由該公式知計(jì)算 C=AB總共需要 pqr次的數(shù)乘 – 需要的時(shí)間是 O(n3)， 稱為立方時(shí)間 例 2： 在科學(xué)計(jì)算中經(jīng)常要計(jì)算矩陣的乘積。 hanoi (n1, middle, left, right)。 ? to give a detailed example of an introductory course sequence in puter science that is based on the curriculum model and the disciplinary description. This task was extended to enpass both puter science and puter engineering. Computing as a Discipline 計(jì)算學(xué)科是對(duì)描述和變換信息的算法過(guò)程，包括對(duì)其理論、分析、設(shè)計(jì)、效率、實(shí)現(xiàn)和應(yīng)用等進(jìn)行的系統(tǒng)研究。 Computing as a Discipline 知識(shí)體系 概率與統(tǒng)計(jì) 正則語(yǔ)言 與自動(dòng)機(jī) 數(shù)理邏輯 圖論 微積分 離散數(shù)學(xué) 線性代數(shù) 計(jì)算機(jī)原理 編譯原理 操作系統(tǒng) 算法研究 高級(jí)程序設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu) 人工智能 程序設(shè)計(jì) Software 計(jì)算機(jī)網(wǎng)絡(luò) 體系結(jié)構(gòu) 數(shù)字邏輯與數(shù)字電路 普通物理 電子電路 Math 計(jì)算機(jī)科學(xué) Hardware
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1