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

《电脑科学的理论基础ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、電腦科學的理論基礎空大面授教師何秀蘭第一章簡單的數學與邏輯理論電腦硬體作業系統應用程式使用者認識電腦系統電腦簡要結構圖主記憶體CPU中央處理器週邊設備程式資料系統算術運算單元邏輯運算單元資料暫存區儲存設備列印設備網路設備資料匯流區運算理論方法建構式証明（proofbyconstruction）矛盾證明法（proofbycontradiction）歸納式証明（proofbyinduction）基礎事實、推演步驟離散數學(discretemathematics)代數邏輯組合數學（計數、圖型理論）圖論有限狀態機運算性(c

2、omputability)演算法分析認識「數」(numbers)∩∩∩∩PNZQR正整數的集合（包含0）正整數的集合（不含0）所有整數集合有理數集合實數集合P={n：n是一個正整數}N={n：n是一個自然數}Z={n：n是一個整數}Q={a/b：a與b為整數，b=0}R={x：x是一個實數}2補述表示負數的方式10進位制的數值2補述的表示法-4100-3101-2110-11110000100120103011數學基礎集合(set)函數(function)關聯(relation)序列(sequence)集合(set

3、s)一群物件的組合成員都是該集合的成員（元素element）集合中沒有重複的成員集合元素可以用波浪括弧框起來Powersetp(s)一個集合的所有子集合所形成的集合S為集合，用p(s)表示假如s有n個元素，則p（s）有2n個元素集合的運算聯集（union）A∪B交集（intersection）A∩B相對互補（relativecomplement）AB對稱差（symmetricdifference）A⊕BA⊕B=（A∪B）（A∩B）=(AB)∪(BA)集合相關的定律定律名稱定律Commutativelaws交

4、換律A∪B=B∪A，A∩B=B∩AAssociativelaws結合律(A∪B)∪C=A∪(B∪C)Distributivelaws分配律A∪(B∩C)=(A∪B)∩(A∪C)Idempotentlaws等募定律A∪A=A，A∩A=AIdentitylaws相等定律A∪ψ=A，A∪U=U，A∩ψ=ψ，A∩U=UDoublecomplementation雙重互補（AC）C=ADeMorganlaws笛摩根定律(A∪B)C=AC∪BC，(A∩B)C=AC∩BC關聯(relation)二元關聯的定義：S與T為集合，從S到

5、T的二元關聯(binaryrelation)是SxT的子集合，以R來表示。所以R是由有序數對(orderedpairs)組成的集合，有序數對可以用(S，t)來表示。函數（functions）運算式含有變數變數的值會決定函數的值函數代表某種對應，存在於變數與函數的輸出值之間函數的結合XSTuf(X)g(f(X))goffg(gof)(x)=g(f(x))，x€s€F(x)=3x-4，g(y)=2y+5，則gof(x)與fog(x)為何?gof(x)=g(f(x))=2(3x-4)+5=6x-3fog(y)=f(g(y

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

7、題看成一種命題代數快速算出命題真值命題可能是真（true）或是偽（false）命題邏輯連接符號表示法﹁：代表not或否定：代表and：代表or：代表暗示，有條件推論：代表若且唯若⊕：代表or（exclusive）真假值pq﹁pPqPqPqPqP⊕q00100110011011011000100111011110第二章問題的表示與解決方法解決問題方法數學歸納法遞迴計數資料結構資料結構是資料的表示法資料結構簡化解決問題程序資料結構離不開演算法演算法是解決問題方法經由演算法分析後，可以某種程式語言撰寫演算法所代表程式資必

8、須以適當資料結構來描述問題中抽象或具體事實資料結構分類基本資料型式（整數、浮點數、字串、布林值)系統內定或使用者自訂的資料型態抽象資料型式資料結構表示方法代數（c=5/9*（f-32）表格式資料流程圖（DFD）控制流程圖資料流程圖（DataFlowDiagram）DFD偏重於資料被處理方式與順序描述演算表功能說明資料操作之間交換資料(x+y+a)*(a+b*