《电脑科学的理论基础整.ppt》由会员分享，可在线阅读，更多相关《电脑科学的理论基础整.ppt（86页珍藏版）》请在三一办公上搜索。
1、電腦科學的理論基礎,空大面授教師何 秀 蘭,第一章簡單的數學與邏輯理論,認識電腦系統,電腦簡要結構圖,主記憶體,CPU 中央處理器,週邊設備,程式,資料,系統,算術運算單元,邏輯運算單元,資料暫存區,儲存設備,列印設備,網路設備,資料匯流區,運算理論方法,建構式証明（proof by construction）矛盾證明法（proof by contradiction）歸納式証明（proof by induction）基礎事實、推演步驟,離散數學(discrete mathematics),代數邏輯組合數學（計數、圖型理論）圖論有限狀態機運算性(computability)演算法分析,認識數(n
2、umbers),P,N,Z,Q,R,正整數的集合（包含0）,正整數的集合（不含0）,所有整數集合,有理數集合,實數集合,P=n：n是一個正整數N=n：n是一個自然數Z=n：n是一個整數Q=a/b：a與b為整數，b=0R=x：x是一個實數,2補述表示負數的方式,數學基礎,集合(set)函數(function)關聯(relation)序列(sequence),集合(sets),一群物件的組合成員都是該集合的成員（元素 element）集合中沒有重複的成員集合元素可以用波浪括弧框起來,Power set p(s),一個集合的所有子集合所形成的集合S為集合，用 p(s)表示假如 s有 n個元素，則 p
3、（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）,運算式含有變數變數的值會決定函數的值函數代表某種對應，存在於變數與函數的輸出值
4、之間,函數的結合,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-3f o g(y)=f(g(y)=3(2y+5)-4=6y+11,函數特性,1對多1對11對1(每各均都對應到)多對1，不是函數,序列（sequences）,函數可以看成一種序列序列中變數很適合用下標表示序列表示法：加總：=1+4+9+.+400 階乘：n!=1x2x3x4xx n=K,20,N=1,n,N-1,邏輯理論,表達論述(a
5、rguments)區分有效的或無效的發展出嚴謹的証明探討命題（propostions）之間邏輯關係命題可能是真（true）或是偽（false）,命題邏輯（propositional logic）,命題演算發展正式規則，用來分析與處理命題看成一種命題代數快速算出命題真值命題可能是真（true）或是偽（false）,命題邏輯連接符號表示法,：代表not 或否定：代表and：代表 or：代表暗示，有條件推論：代表若且唯若：代表 or（exclusive）,真假值,第二章問題的表示與解決方法,解決問題方法 數學歸納法 遞迴 計數,資料結構,資料結構是資料的表示法資料結構簡化解決問題程序資料結構離不開演
6、算法演算法是解決問題方法經由演算法分析後，可以某種程式語言撰寫演算法所代表程式資必須以適當資料結構來描述問題中抽象或具體事實,資料結構分類,基本資料型式（整數、浮點數、字串、布林值)系統內定或使用者自訂的資料型態抽象資料型式,資料結構表示方法,代數（c=5/9*（f-32）表格式資料流程圖（DFD）控制流程圖,資料流程圖（Data Flow Diagram）,DFD偏重 於資料被處理方式與順序描述演算表功能說明資料操作之間交換資料(x+y+a)*(a+b*c)請参閱p42 圖2-5,輸入,輸出,功能,資料流,控制流程圖（CFD）,控制流程與資料流程是演算法一體兩面說明各功能是如何達成,操作,條
7、件,false,true,資料結構、演算法、程式語言之關係,解決問題,資料結構,演算法,程式,具體化,資料結構內涵,資料結構的用途,功能定義,程式語言,演算法,演算法,儲存結構,字典,儲存成對資料成對值的序列或樹集合（set）關聯（relations)：有序對的集合映射(mapping)：集合之間特殊的關聯,映射與關聯的差異,有效關聯但不是有效的映射,有效關聯也是有效的映射,解決問題的方法,解決問題要先了解問題解決問題的方法不只一種解決問題時需要分析思考理論根基可幫助有系統的分析思考,CRC,CRC 內涵 類別、責任、合作物件導向分析方法是用小型開發群組配合漸進式軟體開發程序,第三章布林代數,
8、一個含有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),卡諾圖(karn
9、augh 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,
10、+,+,+,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)的使用。量詞(quantifie
11、rs)：所有量詞 存在量詞運算子（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)，這些符號用來組成句
12、子(sentences)，合法的句子(legal sentences)也稱為WFFs(well-formed formulas)。,認識數理演算(predicate calculus),數理演算特點來自量詞(quantifier)的導入 能處理述詞以及述詞中的成員，推理出其他的句子 可以從語法(syntax)與語意(semantics)上來認識數理演算 數理演算中的符號包括真值符號(truth symbols)、常數符號(constant symbols)、變數符號(variable symbols)與函數符號(function symbols)，數理演算很像一種邏輯程式語言(logic pr
13、ogramming language)。,邏輯程式設計(logicprogramming),邏輯程式設計(logic programming)的基礎就是數理邏輯 邏輯程式語言算是非程序式的程式語言 透過事實(facts)與推理規則(inference rules)的描述，電腦就可以回答一些問題，或是推理出其他的事實,邏輯程式設計,邏輯程式設計的思考跟一般程序式的程式語言很不一樣 因為邏輯程式設計不必描述推理的過程，只要把事實與規則列出來 語言本身有固定的推理機制，而程序式的程式語言(procedural programming language)則需要把詳細的步驟寫出來，越複雜的運算或邏輯，往
14、往需要越複雜的描述 C+、Java 與 Visual Basic 都算是程序式的程式語言,了解PROLOG尋找與執行流程,兩種不同推演過程：向前推演（現有子句推演出目標）向後推演(從目標開始，試著反解出現有的子句)Prolog 是後向推演單一化作業是推演主要過程，包括型式比對與變數連結單一化之後可以為目標比對到現有事實或規則的頭部，則代表成功,Pro log的直譯程式,必須確定所有可能路徑都有被搜尋過搜尋事實與規則的順序是由上而下規則中好幾個子目標須證明，處理順序式由左而右子目標證明方式與目標證明方式一樣,第五章演算法的分析,函數值的成長率,大,演算法基本概念,演算法(algorithm)是一
15、步一步地 解決問題的程序。電腦程式算是演算法。用某種語言寫成，內含解決問 題的步驟。演算法應該具有通用性。,演算法的特性,完整性：每個程序要清楚定義明確性：含義明確，結果一致可決定性(Deterministic)：執行 後結果可預期有限的(finite)：有限步驟完成，資料量亦有限健全結構一般通用性(generality)效率(Efficiency),演算法的結構,需求面,操作面,問題的描述,達到的結果,主要功能,次功能1,次功能n,功能1,功能n,功能m,功能x,操作1,操作n,操作m,操作x,由需求到詳細操作的設計,由上而下的設計,由詳細操作到一般需求的設計,由下而上的設計,演算法的分析（
16、效率）,空間複雜度(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
17、)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 mea
18、surement,程式所需時間(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表示指數時間的解法但無法
19、證明是否有多項式時間的解決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,1
20、2,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)的觀念記憶體空間的運用元素的搬移
21、效率,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
22、1。,樹的表示法,a,b,c,j,h,g,f,d,e,i,A(b(e)，c(f，g)，d(h(i，j),鏈結串列表示法,樹的表示法,二元陣列表示法,儲存位置,a,b,1,c,a,c,e,f,b,2,3,4,5,6,7,儲存位址,1,2,3,4,5,6,7,e,f,儲存順序,實際的樹,樹的基本運算 二元樹追蹤,1.層序追蹤（level-order traversal）樹根 上 下 左 右 abdefghij2.前序追蹤（Preorder traversal）節點 左 右 abefdghij3.中序追蹤（Inorder traversal）左 節點 右 ebfagdihj4.後序追蹤（Postor
23、der traversal）左 右 節點 efbgijhda,a,b,d,e,g,h,f,i,j,圖型,包含一組頂點和一組邊頂點可稱作節點邊是有方向性的,則所形成的圖型為 有向圖型圖型允許迴路的存在,圖形常見表示法,a,b,d,c,a b c d,a b c d,0 1 1 11 0 0 11 0 0 01 1 0 0,圖型表示法,鄰接矩陣表示法,a,b,d,c,b,b,a,b,c,d,b,a,a,a,c,d,b,d,nil,nil,nil,nil,鄰接串列表示法,圖型的應用,最小費用擴張樹(Minimum Spanning Tree)普林演算法 克魯斯克爾演算法最短路徑演算法(Shortest-Path Algorithm)拓樸分類(Topological Sort),最小費用擴張樹(Minimum Spanning Tree),包含圖型內所有的頂點的樹樹是沒有迴路費用是所有邊的權重之總和採用貪心法則(Greedy method)找尋 最小費用擴張樹,拓樸分類(Topological Sort),不包含迴路的有向圖型有向圖型中節點的線性排列去除頂點,謝 謝 聆 聽,
