第4章計(jì)算學(xué)科中的核心概念(編輯修改稿)
2024-11-17 08:08 本頁面
【文章內(nèi)容簡介】 限制了與他人的交流 ， 不利于問題的解決； ? 要花費(fèi)大量的時(shí)間去熟悉和掌握某種特定的程序設(shè)計(jì)語言； ? 要求描述計(jì)算步驟的細(xì)節(jié) ， 而忽視算法的本質(zhì) 。 例 （ C語言）的算法描述： main() { int X,Y。 X=1。 Y=2。 while(Y=100) { X=X+Y。 Y=Y+1。 }。 printf(%d,X)。 } 例 （ C語言）的算法描述 main() { int n。 float X,I。 printf(Please input n:)。 scanf(%d,amp。n)。 X=0。 I=1。 do { X=X+1/I。 I=I+1。 }while(I=n)。 printf(\n%f,X)。 } 算法 算法分析 （ 1）算法的時(shí)間復(fù)雜度； ?用 T(n)表示 ， n表示問題規(guī)模的大小 。 ?使用一個(gè)記號(hào) ? ? Order（ 數(shù)量級(jí) ） 的第一個(gè)字母 ， ? 允許使用 “ =” 代替 “ ≈” 。 如 n2+n+1=?(n2) ?設(shè) f(n)是一個(gè)關(guān)于正整數(shù) n的函數(shù) ， 若存在一個(gè)正 整 數(shù) n0 和 一 個(gè) 常 數(shù) C， 當(dāng) n≥n0 時(shí) ，∣ T(n)∣ ≤∣ C f(n)∣ 均成立 ， 則稱 f(n)為 T(n)的同數(shù)量級(jí)的函數(shù) 。 ? 算法時(shí)間復(fù)雜度 T(n)可表示為： T(n)= ?(f(n)) 常見的大 ?表示形式有： ?(1) ： 稱為常數(shù)級(jí)； ?(logn)： 稱為對(duì)數(shù)級(jí)； ?(n) ：稱為線性級(jí)； ?(nc) ：稱為多項(xiàng)式級(jí)； ?() ：稱為指數(shù)級(jí)； ?(n!) ：稱為階乘級(jí) 。 算法的空間復(fù)雜度 ?指算法在執(zhí)行過程中所占存儲(chǔ)空間的大小， ?用 S(n)表示， S為英文單詞 Space的第一個(gè)字母。與算法的時(shí)間復(fù)雜度相同 ?算法的空間復(fù)雜度 S(n)也可表示為： S(n)= ?(g(n))。 算法 算法的研究 算法 ?算法：定義一向工作如何完成的步驟的集合 ? 在一臺(tái)機(jī)器可以完成一個(gè)任務(wù)之前，必須找到完成這個(gè)任務(wù)的算法并且用與機(jī)器兼容的方式來描述 ? 一個(gè)與機(jī)器兼容的算法的描述 —— 程序 ?算法的研究開始是作為數(shù)學(xué)的一個(gè)學(xué)科 ? 目標(biāo)：找到描述特定類型問題是如何被解決的指令的集合，如 Euclidean算法 ? 一旦一個(gè)完成任務(wù)的算法被找到，任務(wù)的實(shí)現(xiàn)就不再需要對(duì)算法原理的理解，任務(wù)的實(shí)現(xiàn)僅僅是遵循算法的只是過程 ? 現(xiàn)有的解決問題需要的智慧被編碼進(jìn)了算法 算法轉(zhuǎn)化為智慧 ?通過使用算法來得到并轉(zhuǎn)化智慧，我們才可以構(gòu)建起可以表現(xiàn) 智慧行為的機(jī)器 。 ? 機(jī)器表現(xiàn)的智能等級(jí)受到通過算法轉(zhuǎn)化的智慧所限制 ? 如果沒有解決問題的算法，意味著問題的解決方案超出了機(jī)器的能力范圍 ?算法的開發(fā)就成了計(jì)算機(jī)領(lǐng)域的一個(gè)主要目標(biāo) ? 如何找到算法 —— 一個(gè)十分接近于尋找通用問題解決方案 ? 描述這個(gè)算法 —— 轉(zhuǎn)變?yōu)橐粋€(gè)清晰的指令的集合（程序設(shè)計(jì)語言描述） 計(jì)算機(jī)技術(shù)別用于復(fù)雜問題（大型軟件系統(tǒng)） ?不僅僅包括實(shí)現(xiàn)任務(wù)的單個(gè)算法的開發(fā) ? 還要求對(duì)組件之間的交互進(jìn)行設(shè)計(jì) ? 軟件工程：借鑒了工程領(lǐng)域、項(xiàng)目管理領(lǐng)域、人力資源管理以及程序語言設(shè)計(jì)領(lǐng)域的經(jīng)驗(yàn) 執(zhí)行算法的機(jī)器的設(shè)計(jì)和實(shí)現(xiàn) ?數(shù)據(jù)的存儲(chǔ) ?數(shù)據(jù)的操作 ?體系結(jié)構(gòu)中涵蓋了對(duì)現(xiàn)今技術(shù)的討論 ? 我們的目標(biāo)不是去熟知類似當(dāng)今體系結(jié)構(gòu)是如何用電路來實(shí)現(xiàn)這樣的細(xì)節(jié)問題，那將會(huì)導(dǎo)致過分陷入電子工程學(xué)科 ? 正如昨天的齒輪驅(qū)動(dòng)的計(jì)算機(jī)讓位于電子設(shè)備一樣，今天的電子技術(shù)也許很快也被其它的技術(shù)所取代 理想情況下 ?希望計(jì)算機(jī)的體系結(jié)構(gòu)是我們的有關(guān)算法過程知識(shí)的延續(xù)，并且不應(yīng)該被技術(shù)能力酸限制 ? 使我們的算法知識(shí)在當(dāng)代機(jī)器體系結(jié)構(gòu)的發(fā)展背后起推動(dòng)作用，而不僅僅是從技術(shù)的要求觸發(fā)來解頂機(jī)器的設(shè)計(jì) ?構(gòu)建允許使用多個(gè)指令序列來代替算法的機(jī)器是可能的 ? 這些指令被同時(shí)執(zhí)行或者作為 機(jī)器于外部世界的接口的設(shè)計(jì)于計(jì)算機(jī)的設(shè)計(jì)緊密相連 ?算法是如何機(jī)器中的？ ?機(jī)器是如何被告知執(zhí)行的是哪一個(gè)算法？ 計(jì)算理論 ?對(duì)解決越來越復(fù)雜問題的算法的研究 ? 導(dǎo)致了算法過程的最終限制問題 ? 如果沒有算法可以解決這個(gè)問題，那么算法是不能被機(jī)器所解決的，機(jī)器僅僅可以解決在算法上可解的問題 ? Godel的不完全定理闡述了 ? 在任何傳統(tǒng)算術(shù)領(lǐng)域的數(shù)學(xué)理論中，有些是既不能證明有不能被推翻的 ? 任何對(duì)算術(shù)系統(tǒng)的徹底研究都超出了算法的能力 ? 對(duì)算法的限制的研究欲望似的數(shù)學(xué)家們設(shè)計(jì)抽象的機(jī)器來執(zhí)行算法，并在理論上研究這些假想機(jī)器的能力。 數(shù)據(jù)結(jié)構(gòu) ： 一類定性數(shù)學(xué)模型 數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)結(jié)構(gòu)的基本概念 ?組成：數(shù)據(jù)結(jié)構(gòu)是一類定性的數(shù)學(xué)模型，它由以下 3部分組成 ? 邏輯結(jié)構(gòu) ? 存儲(chǔ)結(jié)構(gòu)（或稱
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1