电脑科学的理论基础整.ppt

電腦科學的理論基礎,空大面授教師 何 秀 蘭,第一章簡單的數學與邏輯理論,認識電腦系統,電腦簡要結構圖,主記憶體,CPU 中央處理器,週邊設備,程式,資料,系統,算術運算單元,邏輯運算單元,資料暫存區,儲存設備,列印設備,網路設備,資料匯流區,運算理論方法,建構式証明（proof by construction） 矛盾證明法（proof by contradiction） 歸納式証明（proof by induction） 基礎事實、推演步驟,離散數學 (discrete mathematics),代數 邏輯 組合數學（計數 、圖型理論 ） 圖論 有限狀態機 運算性 (computability) 演算法分析,認識數 (numbers),P,N,Z,Q,R,正整數的集合 （包含0）,正整數的集合 （不含0）,所有整數集合,有理數集合,實數集合,P=n：n是一個正整數 N=n：n是一個自然數 Z=n：n是一個整數 Q=a/b：a與b為整數，b=0 R=x：x是一個實數,2補述表示負數的方式,數學基礎,集合 (set) 函數 (function) 關聯 (relation) 序列 (sequence),集合 (sets),一群物件的組合 成員都是該集合的成員（元素 element） 集合中沒有重複的成員 集合元素可以用波浪括弧框起來,Power set p (s),一個集合的所有子集合所形成的集合 S為集合，用 p (s) 表示 假如 s有 n個元素，則 p（s）有2n個元素,集合的運算,聯集（union）AB 交集（intersection）AB 相對互補（relative complement）AB 對稱差（symmetric difference）AB A B =（AB） （AB）=(AB) (BA),集合相關的定律,關聯(relation),二元關聯的定義： S與T為集合，從 S到T的二元關聯(binary relation) 是SxT的子集合，以R來表示。所以R是由有序數對(ordered pairs)組成的集合，有序數對可以用(S，t)來表示。,函數（functions）,運算式 含有變數 變數的值會決定函數的值 函數代表某種對應，存在於變數與函數的輸出值之間,函數的結合,X,S,T,u,f(X),g(f(X),g o f,f,g,(g o f )(x)=g (f (x) ，xs,F (x) = 3x-4，g (y)=2y+5，則 g o f (x) 與 f o g (x)為何? g o f (x)=g (f (x) =2(3x-4)+5 =6x-3 f o g(y)=f (g (y) =3(2y+5)-4 =6y+11,函數特性,1對多 1對1 1對1(每各均都對應到) 多對1，不是函數,序列（sequences）,函數可以看成一種序列 序列中變數很適合用下標表示 序列表示法： 加總： =1+4+9+400 階乘 ：n!=1x2x3x4xx n = K,20,N=1,n,N-1,邏輯理論,表達論述(arguments) 區分有效的或無效的 發展出嚴謹的証明 探討命題（propostions）之間邏輯關係 命題可能是真（true）或是偽（false）,命題邏輯（propositional logic）,命題演算 發展正式規則，用來分析與處理命題 看成一種命題代數 快速算出命題真值 命題可能是真（true）或是偽（false）,命題邏輯連接符號表示法,：代表not 或否定 ：代表and ：代表 or ：代表暗示，有條件推論 ：代表若且唯若 ：代表 or（exclusive）,真假值,第二章問題的表示與解決方法,解決問題方法 數學歸納法 遞迴 計數,資料結構,資料結構是資料的表示法 資料結構簡化解決問題程序 資料結構離不開演算法 演算法是解決問題方法 經由演算法分析後，可以某種程式語言撰寫演算法所代表程式資 必須以適當資料結構來描述問題中抽象或具體事實,資料結構分類,基本資料型式（整數、浮點數、字串、布林值 ) 系統內定或使用者自訂的資料型態 抽象資料型式,資料結構表示方法,代數（c=5/9*（f-32） 表格式 資料流程圖（DFD） 控制流程圖,資料流程圖（Data Flow Diagram）,DFD偏重 於資料被處理方式與順序 描述演算表功能 說明資料操作之間交換資料 ( x+y+a)*( a+b*c) 請参閱p42 圖2-5,輸入,輸出,功能,資料流,控制流程圖（CFD）,控制流程與資料流程是演算法一體兩面 說明各功能是如何達成,操作,條件,false,true,資料結構、演算法、程式語言之關係,解決問題,資料 結構,演算法,程式,具體化,資料結構內涵,資料結構的用途,功能定義,程式語言,演算法,演算法,儲存結構,字典,儲存成對資料 成對值的序列或樹 集合（set） 關聯 （relations) ：有序對的集合 映射 (mapping) ：集合之間特殊的關聯,映射與關聯的差異,有效關聯但不是有效的映射,有效關聯也是有效的映射,解決問題的方法,解決問題要先了解問題 解決問題的方法不只一種 解決問題時需要分析思考 理論根基可幫助有系統的分析思考,CRC,CRC 內涵 類別、責任、合作 物件導向分析方法 是用小型開發群組 配合漸進式軟體開發程序,第三章布林代數,一個含有0與1的集合B，兩個二元運算元 or 與 and 一個單元運算元，及-或,基本的定理,二值布耳代數,定義在一個二元素集合上，即 B=0，1,布耳代數的基本定義與性質,基本定理,布耳函數,布耳函數即由二進位變數，OR、AND兩個二進位運算元，及單一運算子NOT，括弧，以及一各等號所組成表示式。 可以藉由代數運算而加以簡化 例： x + xy=(x + x)(x + y)=1*(x + y)=x + y x(x + y)=xx + xy =0 + xy =xy,真值表,Boolean expression E=(x,v y z) (y z),邏輯電路設計,基本電路元件（gates）,(X y) v z v (x z w),卡諾圖( karnaugh maps),成本考量得到最適合設計 是布林代數venn diagram 與真假值混合,尋找 optimal desing 的步驟如下:,1.依據所描述的函數+號放入卡諾圖中 2.劃分區域: (1)畫出8個方塊有涵蓋有+號的地方,假如8個方塊都有 +號,則Boolean function為1 (2)畫出4個方塊有涵蓋+號但之前沒有被涵蓋的地方 (3)畫出2個方塊來涵蓋有+號但之前沒有被涵蓋的地方 (4)畫出剩下有+號但之前沒有被涵蓋的地方 3.選擇一組畫出來的區域: (1)整體上要包括所有含有+號的地方 (2)越少方塊越好 4.使越少literals越好,x,Yz,Xyz v x y,x,Yz,Yz,Yz,+,+,+,x,Yz,x,x,Yz,Yz,Yz,+,+,+,x,Yz,Z,x,Yz,Yz,Yz,+,+,+,x,Yz,x y v z,x,Yz,Yz,Yz,+,+,+,+,+,+,+,x,Yz,Y v xz v xz,x,Yz,Yz,Yz,+,+,x,X v y v z,x,Yz,Yz,Yz,+,+,+,+,+,+,+,+,+,+,+,第四章 認識數理邏輯 (predicate calculus),也稱為數理演算，跟命題演算不太一樣。 邏輯程式設計與人工智慧，主要是以數理演算為基礎的。 數理邏輯 (predicate calculus)導入量詞(quantifiers)的使用。 量詞(quantifiers) ：所有量詞 存在量詞 運算子（OPERATOR）：,A,E,V,V,多重量詞用法,同時使用 與 的情況，必須注意量詞出現順序 例： P(X，Y)=X是Y的上司 X P(X，Y) 意思是所有的人都是Y的上司 Y P(X，Y) 意思是X是所有的人的上司 Y P(X，Y) 意思是X是某人所有的上司 X P(X，Y) 意思是某人是Y的上司,A,E,A,A,E,E,認識命題演算(propositional calculus),命題演算使用的命題符號(propositional symbols)是英文的大寫字母 命題符號用來表示命題 有關於現實世界的敘述，可能為真(true)或偽(false)， 這些符號用來組成句子(sentences)，合法的句子(legal sentences)也稱為WFFs (well-formed formulas)。,認識數理演算(predicate calculus),數理演算特點來自量詞(quantifier)的導入 能處理述詞以及述詞中的成員，推理出其他的句子 可以從語法(syntax)與語意(semantics)上來認識數理演算 數理演算中的符號包括真值符號(truth symbols)、常數符號(constant symbols)、變數符號(variable symbols)與函數符號(function symbols)， 數理演算很像一種邏輯程式語言(logic programming language)。,邏輯程式設計 (logicprogramming),邏輯程式設計 (logic programming) 的基礎就是數理邏輯 邏輯程式語言算是非程序式的程式語言 透過事實 (facts) 與推理規則 (inference rules) 的描述，電腦就可以回答一些問題，或是推理出其他的事實,邏輯程式設計,邏輯程式設計的思考跟一般程序式的程式語言很不一樣 因為邏輯程式設計不必描述推理的過程，只要把事實與規則列出來 語言本身有固定的推理機制，而程序式的程式語言 (procedural programming language) 則需要把詳細的步驟寫出來，越複雜的運算或邏輯，往往需要越複雜的描述 C+ 、 Java 與 Visual Basic 都算是程序式的程式語言,了解PROLOG尋找與執行流程,兩種不同推演過程： 向前推演（現有子句推演出目標） 向後推演(從目標開始，試著反解出現有的子句) Prolog 是後向推演 單一化作業是推演主要過程，包括型式比對與變數連結 單一化之後可以為目標比對到現有事實或規則的頭部，則代表成功,Pro log的直譯程式,必須確定所有可能路徑都有被搜尋過 搜尋事實與規則的順序是由上而下 規則中好幾個子目標須證明，處理順序式由左而右 子目標證明方式與目標證明方式一樣,第五章演算法的分析,函數值的成長率,大,演算法基本概念,演算法 (algorithm)是一步一步地 解決問題的程序。 電腦程式算是演算法。 用某種語言寫成，內含解決問 題的步驟。 演算法應該具有通用性 。,演算法的特性,完整性：每個程序要清楚定義 明確性：含義明確，結果一致 可決定性(Deterministic )：執行 後結果可預期 有限的(finite)：有限步驟完成， 資料量亦有限 健全結構 一般通用性(generality) 效率(Efficiency),演算法的結構,需求面,操作面,問題的描述,達到的結果,主要功能,次功能1,次功能n,功能1,功能n,功能m,功能x,操作1,操作n,操作m,操作x,由需求到詳細操作的設計,由上而下的設計,由詳細操作到一般需求的設計,由下而上的設計,演算法的分析（效率）,空間複雜度(Space complexity) 使用記憶體空間大小 時間複雜度(Time complexity) 演算法執行完成所用的時間,時間複雜度(Time complexity),漸近式表示法 定義: f (n)=O (g (n) 若且惟若存在2個正整數c和n0,當nn0時， f (n) c g(n),g(n)代表f(n)的漸近式。 g(n)必須是n最小的函數 g(n)可以看成f(n)最悲觀情況下執行時間 O(1)O(logn) O(n) O(n logn) O(n2) O(n3) O(2n),時間複雜度(Time complexity),定義: f (n)= (g (n) 若且惟若存在2個正整數c和n0, 當nn0時，f (n) c g(n), g(n)為f(n)的的下限。 g(n)必須是n最大的函數,時間複雜度(Time complexity),定義: f (n)= (g (n) 若且惟若存在3個正整數c1、c2和n0, 當nn0時，c1g(n)f(n) c2g(n) g(n)為f(n)的的下限。 g(n)同時為f(n)的上、下限。 比 O(f(n)、 (f(n)更精確,空間複雜度(Space complexity),固定空間需求 變動空間需求,效率分析與效率計量,效率分析：與機器無關的時間 與空間分析 效率計量：取得與機器的執行 時間，用來找出程式中沒有效率 的程式碼。,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 簡單的迴路加總程式,效率分析與效率計量,Big “O” 為時間複雜度理論上限 為時間複雜度理論下限 為函數同時是上限也是下限 NP problem表示指數時間的解法但無法證明是否有多項式時間的解決 Un-decidable problem 表示沒有演算法可解,第六章常見的資料結構,陣列(array)基本觀念 1.相同形式(type)元素組合 2.依索引(index) 加以編號，大小 固定(靜態陣列) 3.可以配合控制迴路語法來描述 反覆運算,動態陣列,元素可有不同型態(type) 大小可以變動 索引(index)必須用特定方法存取 效率高 空間節省,陣列與動態陣列差異,陣列A,動態陣列B,大小可變動,大小固定,元素有固定的型態,A0A4,B.element(),.,元素可又不同的型態,陣列的表示方法,F(x)=12x5+2x3+4 第一種表示法： array f(7)=(7,12,0,2,0,0,4) 第二種表示法 array f(7)=(3,5,12,3,2,0,4),堆疊(stack),一群同質元素的組合 後進先出(LIFO) 中序轉後序表示法(先乘除後加減) x/y+5-a*3+6*p xy/5+a3*-6p*,後序,佇列(queue),先進先出(FIFO) 相同型式(TYPE) 最大堆積(max heap) 一個數節點不小於自己二個子節點(完整二元樹) 最小堆積(min heap) 一個數節點不大於自己二個子節點(完整二元樹),55,15,5,12,15,22,鏈結串列(linked list),相當有效率的資料結構 關鍵在於指標(pointer)的觀念 記憶體空間的運用 元素的搬移效率,5,7,14,2,null,頭(head),節點(node),尾(tail),鏈結(link),從不同的抽象層次來看資料結構,資料結構的層次,程式語言的層次,array,list,queue,tree,set,Stack,graph,循序表示,鏈結表示,資料結構 的分類,聚集,array,vector,pointer,reference,樹(tree),非線性的資料結構 由一個或多個節點組成有限集合 具有一個樹根(root) ,不會是空集合 其他節點可看成樹根的子樹(subtree)也是樹 第n個層次(level)最多有2n-1個節點，n1。 以深度d(depth)二元樹，最多節點樹是2 d-1， d 1。,樹的表示法,a,b,c,j,h,g,f,d,e,i,A(b(e) ，c(f，g) ，d(h(i，j),鏈結串列表示法,樹的表示法,二元陣列表示法