《电脑科学的理论基础整理ppt》由会员分享，可在线阅读，更多相关《电脑科学的理论基础整理ppt（86页珍藏版）》请在金锄头文库上搜索。
1、电脑科学的理论基础整理pptStillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望第一章簡單的數學與邏輯理論第一章簡單的數學與邏輯理論電腦硬體作業系統應用程式使用者認識電腦系統認識電腦系統電腦簡要結構圖電腦簡要結構圖主記憶體主記憶體CPU 中央處理器中央處理器週邊設備週邊設備程式程式資料資料系統系統算術運算術運算單元算單元邏輯運邏輯運算單元算單元資料暫存區資料暫存區儲存設備儲存設備列印設備列印設備網路設備網路設備資料匯流區資料匯流區運算理論方法運算理論方法n n建構式証明（proof by
2、 construction）n n矛盾證明法（proof by contradiction）n n歸納式証明（proof by induction） 基礎事實、推演步驟基礎事實、推演步驟基礎事實、推演步驟基礎事實、推演步驟離散數學離散數學 (discrete mathematics) n n代數n n邏輯n n組合數學（計數計數 、圖型理論、圖型理論 ）n n圖論n n有限狀態機n n運算性 (computability) n n演算法分析 認識數認識數 (numbers) PNZQR正整數的集合 （包含0）正整數的集合（不含0） 所有整數集合 有理數集合 實數集合 P=n：n是一個正整數N=
3、n：n是一個自然數Z=n：n是一個整數Q=a/b：a與b為整數，b=0R=x：x是一個實數2補述表示負數的方式補述表示負數的方式 10進位制的數值2補述的表示法-4100-3101-2110-11110000100120103011數學基礎數學基礎 集合 (set) 函數 (function) 關聯 (relation) 序列 (sequence) 集合 (sets) 一群物件的組合成員都是該集合的成員（元素 element）集合中沒有重複的成員集合元素可以用波浪括弧框起來 Power set p (s)一個集合的所有子集合所形成的集合一個集合的所有子集合所形成的集合S S為集合，用為集合，用
4、 p (s)p (s) 表示表示假如假如 s s有有 n n個元素，則個元素，則 p p（s s）有）有2 2n n個元素個元素集合的運算集合的運算聯集聯集（union）A B交集交集（intersection）AB相對互補相對互補（relative complement）AB對稱差對稱差（symmetric difference）AB A B =（A B） （AB）=(AB) (BA)集合相關的定律集合相關的定律定律名稱 定律Commutative laws 交換律A B=B A，AB=B AAssociative laws結合律(A B) C= A (B C )Distributive l
5、aws分配律A (B C)= (A B) (A C )Idempotent laws等募定律A A=A，A A=AIdentity laws相等定律A =A，A U=U ，A =， A U=U Double complementation雙重互補（AC）C= A De Morgan laws笛摩根定律(A B) C = AC BC， (A B) C = AC BC關聯關聯(relation)二元關聯的定義二元關聯的定義： S與T為集合，從 S到T的二元關聯(binary relation) 是SxT的子集合，以R來表示。所以R是由有序數對(ordered pairs)組成的集合，有序數對可以用
6、(S，t)來表示。函數（函數（functions）n n運算式n n含有變數n n變數的值會決定函數的值n n函數代表某種對應，存在於變數與函數的輸出值之間函數的結合函數的結合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 =6y+11函數特性函數特性1 1對多對多1 1對對1 11 1對對1( 1(每各均都對應到每各均都對應
7、到) )多對多對1 1，不是函數不是函數序列序列（sequences）函數可以看成一種序列函數可以看成一種序列序列中變數很適合用下標表示序列中變數很適合用下標表示序列表示法序列表示法： 加總加總： =1+4+9+.+400 階乘階乘 ：n!=1x2x3x4xx n = K20N=1nN-1邏輯理論邏輯理論表達論述表達論述(arguments)(arguments)區分有效的或無效的區分有效的或無效的發展出嚴謹的証明發展出嚴謹的証明探討命題探討命題（propostions）之間邏輯關係之間邏輯關係命題可能是真命題可能是真（true）或是偽或是偽（false）命題邏輯命題邏輯（propositio
8、nal logic）命題演算命題演算發展正式規則發展正式規則，用來分析與處理命題用來分析與處理命題看成一種命題代數看成一種命題代數快速算出命題真值快速算出命題真值命題可能是真命題可能是真（true）或是偽或是偽（false）命題邏輯連接符號表示法命題邏輯連接符號表示法：代表not 或否定 ：代表and ：代表 or ：代表暗示，有條件推論 ：代表若且唯若 ：代表 or（exclusive）真假值真假值pqpP qP qP qP qP q00100110011011011000100111011110第二章問題的表示與解決方法第二章問題的表示與解決方法解決問題方法解決問題方法 數學歸納法數學歸納
9、法 遞迴遞迴 計數計數資料結構資料結構資料結構是資料的表示法資料結構是資料的表示法資料結構簡化解決問題程序資料結構簡化解決問題程序資料結構離不開演算法資料結構離不開演算法演算法是解決問題方法演算法是解決問題方法經由演算法分析後，可以某種經由演算法分析後，可以某種程式語言程式語言撰寫演撰寫演算法所代表程式資算法所代表程式資必須以適當必須以適當資料結構來資料結構來描述問題中抽象或具體描述問題中抽象或具體事實事實資料結構分類資料結構分類基本資料型式基本資料型式（整數、浮點數、字串、布林值（整數、浮點數、字串、布林值 ) )系統內定或使用者自訂的資料型態系統內定或使用者自訂的資料型態抽象資料型式抽象資
10、料型式資料結構表示方法資料結構表示方法代數代數（c=5/9*（f-32）表格式表格式資料流程圖資料流程圖（DFD）控制流程圖控制流程圖資料流程圖資料流程圖（Data Flow Diagram）DFD偏重偏重 於資料被處理方式與順序於資料被處理方式與順序描述演算表功能描述演算表功能說明資料操作之間交換資料說明資料操作之間交換資料 ( x+y+a)*( a+b*c) 請参閱請参閱p42 圖圖2-5輸入輸入輸出輸出功能功能資料流資料流控制流程圖控制流程圖（CFD）控制流程與資料流程是演算法一體兩面控制流程與資料流程是演算法一體兩面說明各功能是如何達成說明各功能是如何達成操作操作條件條件falsetr
11、ue資料結構、演算法資料結構、演算法、程式語言之關係、程式語言之關係解決問題解決問題資料資料結構結構演算法演算法程式程式具體化具體化資料結構內涵資料結構內涵資料結構的用途資料結構的用途功功能能定定義義程程式式語語言言演算法演算法演算法演算法儲存結構儲存結構字典字典儲存成對資料儲存成對資料成對值的序列或樹成對值的序列或樹集合集合（set）關聯關聯 （relations) ：有序對的集合有序對的集合映射映射 (mapping) (mapping) ：集合之間特殊的關聯集合之間特殊的關聯映射與關聯的差異映射與關聯的差異有效關聯但不是有效的映射有效關聯但不是有效的映射有效關聯也是有效的映射有效關聯也是
12、有效的映射解決問題的方法解決問題的方法解決問題要先了解問題解決問題要先了解問題解決問題的方法不只一種解決問題的方法不只一種解決問題時需要分析思考解決問題時需要分析思考理論根基可幫助有系統的分析思考理論根基可幫助有系統的分析思考CRCCRC CRC 內涵內涵 類別類別、責任、合作、責任、合作物件導向分析方法物件導向分析方法是用小型開發群組是用小型開發群組配合漸進式軟體開發程序配合漸進式軟體開發程序第三章布林代數第三章布林代數一個含有一個含有0 0與與1 1的集合的集合B B，兩個二元運算元，兩個二元運算元 or 與 and一個單元運算元一個單元運算元，及，及-或或基本的定理基本的定理定理理名稱
13、定理理Commutative laws 交換律X y=y x ，x y=y xAssociative laws結合律X (y z)=（x y） zDistributive laws分配律X (y z)=（x y） （x z）Idempotent laws等募定律X x =x = x x De Morgans laws笛摩根定律 -（x y）=(-x) (-y)Double negation雙重否定否定- -x = xIdentity laws相等定律0 x =0，0 x=1 x=x ， 1 x=1 complementation laws互補01，1= -0 x （-x）=1， x (-x)=
14、0二值布耳代數定義在一個二元素集合上，即 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布耳代數的基本定義與性質布耳代數的基本定義與性質n n基本定理基本定理公設2(a) x+0=x(b) x.1=x公設5(a) X +x=1(b) x. x=0定理1(a) X +x=x(b) X .x=x定理2(a) x+1=1(b) x.0=0定理3,乘方性(x)=x公設3,交換性(a) X +y=y +x(b) X y=y x定理4,結合性(a) X +( y+z)=(x +y)+z (b) X (y z)
15、=( x y) z公設4,分配性(a) X ( y+ z)= x y+ x z(b) X +y z=(x +y) (x +z)定理5,第摩根(a) ( x +y)= x y(b) (x y)=x +y定理6,吸收性(a) X + x y=x(b) X (x +y)=x布耳函數布耳函數布耳函數即由二進位變數，布耳函數即由二進位變數，OROR、ANDAND兩兩個二進位運算元，及單一運算子個二進位運算元，及單一運算子NOTNOT，括，括弧，以及一各等號所組成表示式。弧，以及一各等號所組成表示式。可以藉由代數運算而加以簡化例： x + xy=(x + x)(x + y)=1*(x + y)=x + y
16、 x(x + y)=xx + xy =0 + xy =xy真值表真值表Boolean expression E=(x v y z) (y z) 邏輯電路設計邏輯電路設計基本電路元件基本電路元件（gates）名 稱圖示符號代數函數ANDxy ORxVy NOTx NAND (XY) NOR (XVY) XORXYXYXYxXYXYXYXYWZ(X y) v z v (x z w)卡諾圖卡諾圖( karnaugh maps)成本考量得到最適合設計成本考量得到最適合設計是布林代數是布林代數venn diagram venn diagram 與真假值混合與真假值混合尋找尋找 optimal desin
17、g 的步驟如下的步驟如下:1.依據所描述的函數+號放入卡諾圖中2.劃分區域: (1)畫出8個方塊有涵蓋有+號的地方,假如8個方塊都有 +號,則Boolean function為1 (2)畫出4個方塊有涵蓋+號但之前沒有被涵蓋的地方 (3)畫出2個方塊來涵蓋有+號但之前沒有被涵蓋的地方 (4)畫出剩下有+號但之前沒有被涵蓋的地方3.選擇一組畫出來的區域: (1)整體上要包括所有含有+號的地方 (2)越少方塊越好4.使越少literals越好xYzXyz v x yxYz YzYz+xYzxxYz YzYz+xYzZxYz YzYz+xYzx y v zxYz YzYz+xYzY v xz v x
18、zxYz YzYz+xX v y v zxYz YzYz+第四章 認識數理邏輯 (predicate calculus) 也稱為數理演算，跟命題演算不太一樣。 邏輯程式設計與人工智慧，主要是以數理演算為基礎的。數理邏輯數理邏輯 (predicate calculus) (predicate calculus)導入量詞導入量詞(quantifiers)(quantifiers)的使用的使用。量詞量詞(quantifiers) (quantifiers) ：所有量詞所有量詞 存在量詞運算子運算子（OPERATOROPERATOR）：）：AEVV多重量詞用法多重量詞用法同時使用 與 的情況，必須注意
19、量詞出現順序例： 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的上司的上司 AEAAEE認識命題演算認識命題演算(propositional calculus) 命題演算使用的命題符號(propositional symbols)是英文的大寫字母 命題符號用來表示命題 有關於現實世界的敘述，可能為真(true)或偽(false)，這些符號用來組成句子(sentences)，合法的句子
20、(legal sentences)也稱為WFFs (well-formed formulas)。 認識數理演算認識數理演算(predicate calculus)(predicate calculus) 數理演算特點來自量詞(quantifier)的導入 能處理述詞以及述詞中的成員，推理出其他的句子 可以從語法(syntax)與語意(semantics)上來認識數理演算 數理演算中的符號包括真值符號(truth symbols)、常數符號(constant symbols)、變數符號(variable symbols)與函數符號(function symbols)， 數理演算很像一種邏輯程式語
21、言(logic programming language)。 邏輯程式設計邏輯程式設計 (logicprogramming)(logicprogramming) 邏輯程式設計 (logic programming) 的基礎就是數理邏輯 邏輯程式語言算是非程序式的程式語言 透過事實 (facts) 與推理規則 (inference rules) 的描述，電腦就可以回答一些問題，或是推理出其他的事實 邏輯程式設計邏輯程式設計 邏輯程式設計的思考跟一般程序式的程式語言很不一樣 因為邏輯程式設計不必描述推理的過程，只要把事實與規則列出來 語言本身有固定的推理機制，而程序式的程式語言 (procedur
22、al programming language) 則需要把詳細的步驟寫出來，越複雜的運算或邏輯，往往需要越複雜的描述 C+ 、 Java 與 Visual Basic 都算是程序式的程式語言 了解了解PROLOG尋找與執行流程尋找與執行流程兩種不同推演過程： 向前推演（現有子句推演出目標） 向後推演(從目標開始，試著反解出現有的子句)Prolog 是後向推演單一化作業是推演主要過程，包括型式比對與變數連結單一化之後可以為目標比對到現有事實或規則的頭部，則代表成功 Pro log的直譯程式的直譯程式必須確定所有可能路徑都有被搜尋過搜尋事實與規則的順序是由上而下規則中好幾個子目標須證明，處理順序式
23、由左而右子目標證明方式與目標證明方式一樣 第五章演算法的分析第五章演算法的分析 函數值的成長率函數函數名稱 1constantLog nlogarithmic nlinearN log nLog linear n2Quadratic n3cubic 2nExponential n!factorial大演算法基本概念演算法基本概念 演算法 (algorithm)是一步一步地 解決問題的程序。 電腦程式算是演算法。 用某種語言寫成，內含解決問 題的步驟。 演算法應該具有通用性 。演算法的特性演算法的特性 完整性：每個程序要清楚定義明確性：含義明確，結果一致可決定性(Deterministic )：
24、執行 後結果可預期有限的(finite)：有限步驟完成， 資料量亦有限健全結構一般通用性(generality)效率(Efficiency)演算法的結構演算法的結構 需需求求面面操操作作面面問題的描述問題的描述達到的結果達到的結果主要功能主要功能次功能次功能1次功能次功能n功能功能1功能功能n功能功能m功能功能x操作操作1操作操作n操作操作m操作操作x由需求到詳細操作的設計由需求到詳細操作的設計由上而下的設計由上而下的設計由詳細操作到一般需求的設計由詳細操作到一般需求的設計由下而上的設計由下而上的設計演算法的分析（演算法的分析（效率效率）空間複雜度(Space complexity) 使用記憶
25、體空間大小時間複雜度(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(
26、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) 固定空間需求變動空間需求效率分析與效率計量效率分析與效率計量效率分析效率分析：與機器無關的時間：與機器無關的時間 與空間分析與空間分析效率計量效率計量：取得與機器的執行：取得與機器的執行 時間，用來找出程式中沒有效時間，用來找出
27、程式中沒有效率率 的程式碼。的程式碼。performance analysisperformance analysisPerformance measurementPerformance measurement 程式所需時間(TP)=編譯時間+執行時間TP(m)=c1ADD(m)+c2SUB(m)+c3LAD(m) +c4STA(m)程式步驟(program step) 執行時間與實體變數 性質無關迴圈與遞迴次數相同，但因遞迴負擔大，速度 比迴圈慢效率分析與效率計量效率分析與效率計量效率分析與效率計量效率分析與效率計量 程式步驟(program step) 計算 s/e * F = total
28、_step敘述步驟頻率全部步驟效率分析與效率計量效率分析與效率計量計算程式步數計算程式步數 表1 簡單的迴路加總程式敘述(statement)s/e執行次數步數T fSum(T a, int n) T msum=0; for (int i=0; in; i+) msum = ai+msum; return msum;0000001111n+1n+11nn111000 總 計2n+3效率分析與效率計量效率分析與效率計量n nBig “O” 為時間複雜度理論上限n n 為時間複雜度理論下限n n為函數同時是上限也是下限n nNP problem表示指數時間的解法但無法證明是否有多項式時間的解決n
29、nUn-decidable problem 表示沒有演算法可解第六章常見的資料結構第六章常見的資料結構 陣列(array)基本觀念 1.相同形式(type)元素組合 2.依索引(index) 加以編號，大小 固定(靜態陣列) 3.可以配合控制迴路語法來描述 反覆運算動態陣列動態陣列 元素可有不同型態(type)大小可以變動索引(index)必須用特定方法存取效率高空間節省陣列與動態陣列差異陣列與動態陣列差異 陣列陣列A動態陣列動態陣列B大小可變動大小可變動大小固定大小固定元素有固定的型態元素有固定的型態A0A4B.element().元素可又不同的型態元素可又不同的型態陣列的表示方法陣列的表示
30、方法 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) 一個數節點不大於自己二個子節點(完整二元樹)55155121522鏈結串列鏈結串列(linked li
31、st) 相當有效率的資料結構關鍵在於指標(pointer)的觀念記憶體空間的運用元素的搬移效率57142null頭頭(head)節點節點(node)尾尾(tail)鏈結鏈結(link)從不同的抽象層次來看資料結構從不同的抽象層次來看資料結構 資料結構的層次資料結構的層次資料結構的層次資料結構的層次程式語言的層次程式語言的層次程式語言的層次程式語言的層次arraylistqueuetreesetStackgraph循序表示鏈結表示資料結構資料結構資料結構資料結構的分類的分類的分類的分類聚集arrayvectorpointerreference樹樹(tree) 非線性的資料結構由一個或多個節點組成
32、有限集合具有一個樹根(root) ,不會是空集合其他節點可看成樹根的子樹(subtree)也是樹第n個層次(level)最多有2n-1個節點，n1。以深度d(depth)二元樹，最多節點樹是2 d-1， d 1。樹的表示法樹的表示法 abcjhgfdeiA(b(e) ，c(f，g) ，d(h(i，j)鏈結串列表示法鏈結串列表示法樹的表示法樹的表示法 二元陣列表示法儲存位置ab1cacefb234567儲存位址1234567ef儲存順序實際的樹實際的樹樹的基本運算樹的基本運算 二元樹追蹤二元樹追蹤1.層序追蹤（level-order traversal） 樹根 上 下 左 右 abdefghij
33、2.前序追蹤（Preorder traversal）節點 左 右 abefdghij3.中序追蹤（Inorder traversal） 左 節點 右 ebfagdihj4.後序追蹤（Postorder traversal） 左 右 節點 efbgijhda abdeghfij圖型圖型 包含一組頂點和一組邊頂點可稱作節點邊是有方向性的,則所形成的圖型為 有向圖型圖型允許迴路的存在圖形常見表示法圖形常見表示法abdca b c da b c d0 1 1 11 0 0 11 0 0 01 1 0 0圖型表示法鄰接矩陣表示法abdcbbabcdbaaacdbdnilnilnilnil鄰接串列表示法圖型的應用圖型的應用 最小費用擴張樹(Minimum Spanning Tree) 普林演算法 克魯斯克爾演算法最短路徑演算法(Shortest-Path Algorithm)拓樸分類(Topological Sort)最小費用擴張樹(Minimum Spanning Tree) 包含圖型內所有的頂點的樹樹是沒有迴路費用是所有邊的權重之總和採用貪心法則(Greedy method)找尋 最小費用擴張樹拓樸分類(Topological Sort)不包含迴路的有向圖型有向圖型中節點的線性排列去除頂點謝 謝 聆 聽
