《电脑科学的理论基础ppt课件》由会员分享，可在线阅读，更多相关《电脑科学的理论基础ppt课件（86页珍藏版）》请在金锄头文库上搜索。
1、電腦科學的理論基礎,空大面授教師 何 秀 蘭,第一章簡單的數學與邏輯理論,認識電腦系統,電腦簡要結構圖,主記憶體,CPU 中央處理器,週邊設備,程式,資料,系統,算術運算單元,邏輯運算單元,資料暫存區,儲存設備,列印設備,網路設備,資料匯流區,運算理論方法,建構式証明（proof by construction） 矛盾證明法（proof by contradiction） 歸納式証明（proof by induction） 基礎事實、推演步驟,離散數學 (discrete mathematics),代數 邏輯 組合數學（計數 、圖型理論 ） 圖論 有限狀態機 運算性 (computabilit
2、y) 演算法分析,認識數 (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),一個集合的所有子集合
3、所形成的集合 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)來表示。,函數（funct
4、ions）,運算式 含有變數 變數的值會決定函數的值 函數代表某種對應，存在於變數與函數的輸出值之間,函數的結合,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）,函數可以看成一種序列 序列中變數
5、很適合用下標表示 序列表示法： 加總： =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 ：代表暗示，有條件推論 ：代表若且唯若
6、：代表 or（exclusive）,真假值,第二章問題的表示與解決方法,解決問題方法 數學歸納法 遞迴 計數,資料結構,資料結構是資料的表示法 資料結構簡化解決問題程序 資料結構離不開演算法 演算法是解決問題方法 經由演算法分析後，可以某種程式語言撰寫演算法所代表程式資 必須以適當資料結構來描述問題中抽象或具體事實,資料結構分類,基本資料型式（整數、浮點數、字串、布林值 ) 系統內定或使用者自訂的資料型態 抽象資料型式,資料結構表示方法,代數（c=5/9*（f-32） 表格式 資料流程圖（DFD） 控制流程圖,資料流程圖（Data Flow Diagram）,DFD偏重 於資料被處理方式與順序
7、 描述演算表功能 說明資料操作之間交換資料 ( x+y+a)*( a+b*c) 請参閱p42 圖2-5,輸入,輸出,功能,資料流,控制流程圖（CFD）,控制流程與資料流程是演算法一體兩面 說明各功能是如何達成,操作,條件,false,true,資料結構、演算法、程式語言之關係,解決問題,資料 結構,演算法,程式,具體化,資料結構內涵,資料結構的用途,功能定義,程式語言,演算法,演算法,儲存結構,字典,儲存成對資料 成對值的序列或樹 集合（set） 關聯 （relations) ：有序對的集合 映射 (mapping) ：集合之間特殊的關聯,映射與關聯的差異,有效關聯但不是有效的映射,有效關聯也
8、是有效的映射,解決問題的方法,解決問題要先了解問題 解決問題的方法不只一種 解決問題時需要分析思考 理論根基可幫助有系統的分析思考,CRC,CRC 內涵 類別、責任、合作 物件導向分析方法 是用小型開發群組 配合漸進式軟體開發程序,第三章布林代數,一個含有0與1的集合B，兩個二元運算元 or 與 and 一個單元運算元，及-或,基本的定理,二值布耳代數,定義在一個二元素集合上，即 B=0，1,布耳代數的基本定義與性質,基本定理,布耳函數,布耳函數即由二進位變數，OR、AND兩個二進位運算元，及單一運算子NOT，括弧，以及一各等號所組成表示式。 可以藉由代數運算而加以簡化 例： x + xy=(
9、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
10、 (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,Y
11、z,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
12、，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)的導入 能處理述詞
13、以及述詞中的成員，推理出其他的句子 可以從語法(syntax)與語意(semantics)上來認識數理演算 數理演算中的符號包括真值符號(truth symbols)、常數符號(constant symbols)、變數符號(variable symbols)與函數符號(function symbols)， 數理演算很像一種邏輯程式語言(logic programming language)。,邏輯程式設計 (logicprogramming),邏輯程式設計 (logic programming) 的基礎就是數理邏輯 邏輯程式語言算是非程序式的程式語言 透過事實 (facts) 與推理規則 (i
14、nference rules) 的描述，電腦就可以回答一些問題，或是推理出其他的事實,邏輯程式設計,邏輯程式設計的思考跟一般程序式的程式語言很不一樣 因為邏輯程式設計不必描述推理的過程，只要把事實與規則列出來 語言本身有固定的推理機制，而程序式的程式語言 (procedural programming language) 則需要把詳細的步驟寫出來，越複雜的運算或邏輯，往往需要越複雜的描述 C+ 、 Java 與 Visual Basic 都算是程序式的程式語言,了解PROLOG尋找與執行流程,兩種不同推演過程： 向前推演（現有子句推演出目標） 向後推演(從目標開始，試著反解出現有的子句) Pr
15、olog 是後向推演 單一化作業是推演主要過程，包括型式比對與變數連結 單一化之後可以為目標比對到現有事實或規則的頭部，則代表成功,Pro log的直譯程式,必須確定所有可能路徑都有被搜尋過 搜尋事實與規則的順序是由上而下 規則中好幾個子目標須證明，處理順序式由左而右 子目標證明方式與目標證明方式一樣,第五章演算法的分析,函數值的成長率,大,演算法基本概念,演算法 (algorithm)是一步一步地 解決問題的程序。 電腦程式算是演算法。 用某種語言寫成，內含解決問 題的步驟。 演算法應該具有通用性 。,演算法的特性,完整性：每個程序要清楚定義 明確性：含義明確，結果一致 可決定性(Deterministic )：執行 後結果可預期 有限的(finite)：有限步驟完成， 資料量亦有限 健全結構 一般通用性(generality) 效率(Efficiency),演算法的結構,需求面,操作面,問題的描述,達到的結果,主
