电脑科学的理论基础课件.ppt

1、電腦硬體作業系統應用程式使用者主記憶體主記憶體CPU 中央處理器中央處理器週邊設備週邊設備程式程式資料資料系統系統算術運算術運算單元算單元邏輯運邏輯運算單元算單元資料暫存區資料暫存區儲存設備儲存設備列印設備列印設備網路設備網路設備資料匯流區資料匯流區PNZQR正整數的集合（包含0）正整數的集合（不含0）所有整數集合 有理數集合 實數集合 P=n：n是一個正整數N=n：n是一個自然數Z=n：n是一個整數Q=a/b：a與b為整數，b=0R=x：x是一個實數 集合(set)函數(function)關聯(relation)序列(sequence)一群物件的組合成員都是該集合的成員（元素 element

2、）集合中沒有重複的成員集合元素可以用波浪括弧框起來 一個集合的所有子集合所形成的集合一個集合的所有子集合所形成的集合S S為集合，用為集合，用 p(s)p(s)表示表示假如假如 s s有有 n n個元素，則個元素，則 p p（s s）有）有2 2n n個元素個元素聯集聯集（union）AB交集交集（intersection）AB相對互補相對互補（relative complement）AB對稱差對稱差（symmetric difference）A B A B=（AB）（AB）=(AB)(BA)二元關聯的定義二元關聯的定義：S S與與T T為集合，從為集合，從 S S到到T T的二的二元關聯元關

3、聯(binary relation)(binary relation)是是SxTSxT的子集合，以的子集合，以R R來表示。所以來表示。所以R R是由有序數對是由有序數對(ordered pairs)(ordered pairs)組成的集合，有序數對可以用組成的集合，有序數對可以用(S(S，t)t)來表示。來表示。XSTuf(X)g(f(X)g o ffg(g o f)(x)=g(f(x)，xsF(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 =

4、6y+111 1對多對多1 1對對1 11 1對對1(1(每各均都對應到每各均都對應到)多對多對1 1，不是函數不是函數函數可以看成一種序列函數可以看成一種序列序列中變數很適合用下標表示序列中變數很適合用下標表示序列表示法序列表示法：加總加總：=1+4+9+.+400 階乘階乘：n!=1x2x3x4xx n =K20N=1nN-1表達論述表達論述(arguments)(arguments)區分有效的或無效的區分有效的或無效的發展出嚴謹的証明發展出嚴謹的証明探討命題探討命題（propostions）之間邏輯關係之間邏輯關係命題可能是真命題可能是真（true）或是偽或是偽（false）命題演算命題

5、演算發展正式規則發展正式規則，用來分析與處理命題用來分析與處理命題看成一種命題代數看成一種命題代數快速算出命題真值快速算出命題真值命題可能是真命題可能是真（true）或是偽或是偽（false）：代表：代表not not 或否定或否定 ：代表：代表andand ：代表：代表 oror ：代表暗示，有條件推論：代表暗示，有條件推論 ：代表若且唯若：代表若且唯若 ：代表：代表 oror（exclusiveexclusive）解決問題方法解決問題方法 數學歸納法數學歸納法 遞迴遞迴 計數計數資料結構是資料的表示法資料結構是資料的表示法資料結構簡化解決問題程序資料結構簡化解決問題程序資料結構離不開演算法

6、資料結構離不開演算法演算法是解決問題方法演算法是解決問題方法經由演算法分析後，可以某種經由演算法分析後，可以某種程式語言程式語言撰寫演撰寫演算法所代表程式資算法所代表程式資必須以適當必須以適當資料結構來資料結構來描述問題中抽象或具體描述問題中抽象或具體事實事實基本資料型式基本資料型式（整數、浮點數、字串、布林值（整數、浮點數、字串、布林值 )系統內定或使用者自訂的資料型態系統內定或使用者自訂的資料型態抽象資料型式抽象資料型式代數代數（c=5/9*（f-32）表格式表格式 資料流程圖資料流程圖（DFD）控制流程圖控制流程圖 DFD偏重偏重 於資料被處理方式與順序於資料被處理方式與順序 描述演算表

7、功能描述演算表功能 說明資料操作之間交換資料說明資料操作之間交換資料 (x+y+a)*(a+b*c)請参閱請参閱p42 圖圖2-5輸入輸入輸出輸出功能功能資料流資料流控制流程與資料流程是演算法一體兩面控制流程與資料流程是演算法一體兩面說明各功能是如何達成說明各功能是如何達成操作操作條件條件falsetrue解決問題解決問題資料資料結構結構演算法演算法程式程式具體化具體化資料結構的用途資料結構的用途功功能能定定義義程程式式語語言言演算法演算法演算法演算法儲存結構儲存結構儲存成對資料儲存成對資料成對值的序列或樹成對值的序列或樹集合集合（set）關聯關聯 （relations)：有序對的集合有序對的

8、集合映射映射 (mapping)(mapping)：集合之間特殊的關聯集合之間特殊的關聯有效關聯但不是有效的映射有效關聯但不是有效的映射有效關聯也是有效的映射有效關聯也是有效的映射解決問題要先了解問題解決問題要先了解問題 解決問題的方法不只一種解決問題的方法不只一種 解決問題時需要分析思考解決問題時需要分析思考 理論根基可幫助有系統的分析思考理論根基可幫助有系統的分析思考CRC CRC 內涵內涵 類別類別、責任、合作、責任、合作 物件導向分析方法物件導向分析方法 是用小型開發群組是用小型開發群組 配合漸進式軟體開發程序配合漸進式軟體開發程序一個含有一個含有0 0與與1 1的集合的集合B B，兩

9、個二元運算元，兩個二元運算元 or or 與與 andand一個單元運算元一個單元運算元，及，及-或或定義在一個二元素集合上，即 B=0，1x yx.y0 0 00 1 01 0 01 1 1x yx+y0 0 00 1 11 0 11 1 1 x x 0 1 1 0布耳函數即由二進位變數，布耳函數即由二進位變數，OROR、ANDAND兩兩個二進位運算元，及單一運算子個二進位運算元，及單一運算子NOTNOT，括，括弧，以及一各等號所組成表示式。弧，以及一各等號所組成表示式。可以藉由代數運算而加以簡化例：x+xy=(x+x)(x+y)=1*(x+y)=x+y x(x+y)=xx+xy=0+xy=

10、xyBoolean expression E=(x v y z)(y z)基本電路元件基本電路元件（gates）XYXYxXYXYXYXYWZ(X y)v z v(x z w)成本考量得到最適合設計成本考量得到最適合設計是布林代數是布林代數venn diagram venn diagram 與真假值混合與真假值混合1.依據所描述的函數+號放入卡諾圖中2.劃分區域:(1)畫出8個方塊有涵蓋有+號的地方,假如8個方塊都有 +號,則Boolean function為1 (2)畫出4個方塊有涵蓋+號但之前沒有被涵蓋的地方 (3)畫出2個方塊來涵蓋有+號但之前沒有被涵蓋的地方 (4)畫出剩下有+號但之前

11、沒有被涵蓋的地方3.選擇一組畫出來的區域:(1)整體上要包括所有含有+號的地方 (2)越少方塊越好4.使越少literals越好xYzXyz v x yxYz YzYz+xYzxxYz YzYz+xYzZxYz YzYz+xYzx y v zxYz YzYz+xYzY v xz v xzxYz YzYz+xX v y v zxYz YzYz+也稱為數理演算，跟命題演算不太一樣。邏輯程式設計與人工智慧，主要是以數理演算為基礎的。存在量詞AEVV同時使用同時使用 與與 的情況，必須注意量詞出的情況，必須注意量詞出現順序現順序例例：P(X，Y)=X是是Y的上司的上司 X X P(XP(X，Y)意思是

12、所有的人都是意思是所有的人都是Y Y的上司的上司 Y P(X，Y)意思是意思是X是所有的人的上司是所有的人的上司 Y P(X，Y)意思是意思是X是某人所有的上司是某人所有的上司 X P(X，Y)意思是某人是意思是某人是Y的上司的上司 AEAAEE命題演算使用的命題符號(propositional symbols)是英文的大寫字母 命題符號用來表示命題 有關於現實世界的敘述，可能為真(true)或偽(false)，這些符號用來組成句子(sentences)，合法的句子(legal sentences)也稱為WFFs(well-formed formulas)。數理演算特點來自量詞(quantif

13、ier)的導入 能處理述詞以及述詞中的成員，推理出其他的句子 可以從語法(syntax)與語意(semantics)上來認識數理演算 數理演算中的符號包括真值符號(truth symbols)、常數符號(constant symbols)、變數符號(variable symbols)與函數符號(function symbols)，數理演算很像一種邏輯程式語言(logic programming language)。邏輯程式設計(logic programming)的基礎就是數理邏輯 邏輯程式語言算是非程序式的程式語言 透過事實(facts)與推理規則(inference rules)的描述，電

14、腦就可以回答一些問題，或是推理出其他的事實 邏輯程式設計的思考跟一般程序式的程式語言很不一樣 因為邏輯程式設計不必描述推理的過程，只要把事實與規則列出來 語言本身有固定的推理機制，而程序式的程式語言(procedural programming language)則需要把詳細的步驟寫出來，越複雜的運算或邏輯，往往需要越複雜的描述 C+、Java 與 Visual Basic 都算是程序式的程式語言 兩種不同推演過程：向前推演（現有子句推演出目標）向後推演(從目標開始，試著反解出現有的子句)Prolog 是後向推演單一化作業是推演主要過程，包括型式比對與變數連結單一化之後可以為目標比對到現有事實

15、或規則的頭部，則代表成功 必須確定所有可能路徑都有被搜尋過搜尋事實與規則的順序是由上而下規則中好幾個子目標須證明，處理順序式由左而右 子目標證明方式與目標證明方式一樣 n函數值的成長率大 n演算法(algorithm)是一步一步地 解決問題的程序。n電腦程式算是演算法。n用某種語言寫成，內含解決問 題的步驟。n演算法應該具有通用性。n完整性：每個程序要清楚定義n明確性：含義明確，結果一致n可決定性(Deterministic)：執行 n 後結果可預期n有限的(finite)：有限步驟完成，n 資料量亦有限n健全結構n一般通用性(generality)n效率(Efficiency)需需求求面面操

16、操作作面面問題的描述問題的描述達到的結果達到的結果主要功能主要功能次功能次功能1次功能次功能n功能功能1功能功能n功能功能m功能功能x操作操作1操作操作n操作操作m操作操作x由需求到詳細操作的設計由需求到詳細操作的設計由上而下的設計由上而下的設計由詳細操作到一般需求的設計由詳細操作到一般需求的設計由下而上的設計由下而上的設計n空間複雜度(Space complexity)n 使用記憶體空間大小n時間複雜度(Time complexity)n 演算法執行完成所用的時間 n漸近式表示法n 定義:f(n)=O(g(n)若且惟若存在2個正整數c和n0,當nn0時，f(n)c g(n),g(n)代表f(

17、n)的漸近式。n g(n)必須是n最小的函數n g(n)可以看成f(n)最悲觀情況下執行時間nO(1)O(logn)O(n)O(n logn)O(n2)O(n3)O(2n)n定義:f(n)=(g(n)若且惟若存在2個正整數c和n0,當nn0時，f(n)c g(n),g(n)為f(n)的的下限。n g(n)必須是n最大的函數 n定義:f(n)=(g(n)若且惟若存在3個正整數c1、c2和n0,當nn0時，c1g(n)f(n)c2g(n)g(n)為f(n)的的下限。n g(n)同時為f(n)的上、下限。n比 O(f(n)、(f(n)更精確 n固定空間需求n變動空間需求 n程式所需時間(TP)=編譯

18、時間+執行時間nTP(m)=c1ADD(m)+c2SUB(m)+c3LAD(m)n +c4STA(m)n程式步驟(program step)執行時間與實體變數 n 性質無關n迴圈與遞迴次數相同，但因遞迴負擔大，速度n 比迴圈慢 n程式步驟(program step)n 計算n s/e *F =total_step敘述步驟敘述步驟頻率頻率全部步驟全部步驟計算程式步數計算程式步數 表1 簡單的迴路加總程式 n陣列(array)基本觀念n 1.相同形式(type)元素組合n 2.依索引(index)加以編號，大小n 固定(靜態陣列)n 3.可以配合控制迴路語法來描述n 反覆運算 n元素可有不同型態(

19、type)n大小可以變動n索引(index)必須用特定方法存取n效率高n空間節省 陣列陣列A動態陣列動態陣列B大小可變動大小可變動大小固定大小固定元素有固定的型態元素有固定的型態A0A4B.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)n一群同質元素的組合n後進先出(LIFO)n中序轉後序表示法(先乘除後加減)n x/y+5-a*3+6*pn xy/5+a3*-6p*後序後序 n先進先出(FIFO)n相同型式(TYPE)

20、n最大堆積(max heap)n 一個數節點不小於自己二個子節點(完整二元樹)n最小堆積(min heap)n 一個數節點不大於自己二個子節點(完整二元樹)55155121522 n相當有效率的資料結構n關鍵在於指標(pointer)的觀念n記憶體空間的運用n元素的搬移效率5 57 714142 2nullnull頭頭(head)(head)節點節點(node)(node)尾尾(tail)(tail)鏈結鏈結(link)(link)arraylistqueuetreesetStackgraph循序表示鏈結表示聚集arrayvectorpointerreference n非線性的資料結構n由一個

21、或多個節點組成有限集合n具有一個樹根(root),不會是空集合n其他節點可看成樹根的子樹(subtree)也是樹n第n個層次(level)最多有2n-1個節點，n1。n以深度d(depth)二元樹，最多節點樹是2 d-1，n d 1。a ab bc cj jh hg gf fd de ei iA(b(e)，c(f，g)，d(h(i，j)鏈結串列表示法鏈結串列表示法 二元陣列表示法儲存位置ab1cacefb234567儲存位址1234567ef儲存順序實際的樹實際的樹1.層序追蹤（level-order traversal）樹根 上 下 左 右 abdefghij2.前序追蹤（Preorder

22、traversal）節點 左 右 abefdghij3.中序追蹤（Inorder traversal）左 節點 右 ebfagdihj4.後序追蹤（Postorder traversal）左 右 節點 efbgijhda abdeghfij n包含一組頂點和一組邊n頂點可稱作節點n邊是有方向性的,則所形成的圖型為n 有向圖型n圖型允許迴路的存在abdca b c da b c d0 1 1 11 0 0 11 0 0 01 1 0 0圖型表示法鄰接矩陣表示法abdcbbabcdbaaacdbdnilnilnilnil鄰接串列表示法 n最小費用擴張樹(Minimum Spanning Tree)n 普林演算法n 克魯斯克爾演算法n最短路徑演算法(Shortest-Path Algorithm)n拓樸分類(Topological Sort)n包含圖型內所有的頂點的樹n樹是沒有迴路n費用是所有邊的權重之總和n採用貪心法則(Greedy method)找尋 n 最小費用擴張樹n不包含迴路的有向圖型n有向圖型中節點的線性排列n去除頂點謝 謝 聆 聽