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