电脑科学的理论基础.ppt

電腦科學的理論基礎 空大面授教師 何 秀 蘭 第一章簡單的數學與邏輯理論 電腦簡要結構圖 運算理論方法 建構式証明（proof by construction） 矛盾證明法（proof by contradiction） 歸納式証明（proof by induction） 基礎事實、推演步驟 離散數學 (discrete mathematics) 代數 邏輯 組合數學（計數 、圖型理論 ） 圖論 有限狀態機 運算性 (computability) 演算法分析 認識「數」 (numbers)  2補述表示負數的方式 數學基礎 集合 (sets) Power set p (s) 集合的運算 集合相關的定律 關聯(relation) 函數（functions） 運算式 含有變數 變數的值會決定函數的值 函數代表某種對應，存在於變數與函數的輸出值之間 函數的結合 函數特性 序列（sequences） 邏輯理論 命題邏輯（propositional logic） 命題邏輯連接符號表示法 真假值 第二章問題的表示與解決方法 資料結構 資料結構分類 資料結構表示方法 資料流程圖（Data Flow Diagram） 控制流程圖（CFD） 資料結構、演算法、程式語言之關係 資料結構內涵 字典 映射與關聯的差異 解決問題的方法 CRC 第三章布林代數 基本的定理 二值布耳代數 布耳函數 真值表 邏輯電路設計 卡諾圖( karnaugh maps) 尋找 optimal desing 的步驟如下: 第四章 認識數理邏輯 (predicate calculus) 多重量詞用法 認識命題演算(propositional calculus) 認識數理演算(predicate calculus) 邏輯程式設計 (logicprogramming) 邏輯程式設計 了解PROLOG尋找與執行流程 Pro log的直譯程式 第五章演算法的分析 演算法基本概念 演算法的特性 演算法的結構 演算法的分析（效率） 時間複雜度(Time complexity) 時間複雜度(Time complexity) 時間複雜度(Time complexity) 空間複雜度(Space complexity) 效率分析與效率計量 效率分析與效率計量 效率分析與效率計量 效率分析與效率計量 效率分析與效率計量 Big “O” 為時間複雜度理論上限 Ω 為時間複雜度理論下限 θ為函數同時是上限也是下限 NP problem表示指數時間的解法但無法證明是否有多項式時間的解決 Un-decidable problem 表示沒有演算法可解 第六章常見的資料結構 動態陣列 陣列與動態陣列差異 陣列的表示方法 堆疊(stack) 佇列(queue) 鏈結串列(linked list) 從不同的抽象層次來看資料結構 樹(tree) 樹的表示法 樹的表示法 樹的基本運算 二元樹追蹤 圖型 圖形常見表示法 圖型的應用 最小費用擴張樹(Minimum Spanning Tree) 拓樸分類(Topological Sort) 固定空間需求 變動空間需求 效率分析：與機器無關的時間 與空間分析 效率計量：取得與機器的執行 時間，用來找出程式中沒有效率 的程式碼。 performance analysis Performance measurement 程式所需時間(TP)=編譯時間+執行時間 TP(m)=c1ADD(m)+c2SUB(m)+c3LAD(m) +c4STA(m) 程式步驟(program step) 執行時間與實體變數 性質無關 迴圈與遞迴次數相同，但因遞迴負擔大，速度 比迴圈慢 程式步驟(program step) 計算 s/e * F = total_step 敘述步驟 頻率 全部步驟 計算程式步數 表1 簡單的迴路加總程式 2n+3 總 計 0 0 0 1 1 1 n n 1 n+1 n+1 1 1 1 1 0 0 0 0 0 0 T fSum(T a[], int n) { T msum=0; for (int i=0; in; i++) msum = a[i]+msum; return msum; } 步數 執行次數