《離散數(shù)學(xué)緒論》PPT課件.ppt

《《離散數(shù)學(xué)緒論》PPT課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、離散數(shù)學(xué)(1)DiscreteMath計算機軟件研究所趙志濱緒論離散數(shù)學(xué)課性質(zhì)及其內(nèi)容學(xué)習(xí)此課的目的學(xué)習(xí)此課的方法離散數(shù)學(xué)DiscreteMath研究離散對象及其相互間關(guān)系的一門數(shù)學(xué)學(xué)科。研究離散結(jié)構(gòu)的數(shù)學(xué)分支。（辭海）計算機不論硬件還是軟件都屬于離散結(jié)構(gòu)，所以它所應(yīng)用的數(shù)學(xué)必是離散數(shù)學(xué)。性質(zhì)：此課是計算機科學(xué)與技術(shù)專業(yè)的重要的理論基礎(chǔ)課，也是該專業(yè)的主干課。計算機科學(xué)、信息科學(xué)、數(shù)字化科學(xué)的數(shù)學(xué)基礎(chǔ)。1.數(shù)理邏輯（MathematicsLogic):命題邏輯、謂詞邏輯2.集合論(Sets)：集合與關(guān)系、函數(shù)3.代數(shù)系統(tǒng)（Algbr

2、aSystem)：代數(shù)結(jié)構(gòu)、格和布爾代數(shù)4.圖論（GraphTheory)：圖論5.組合數(shù)學(xué)（Combinatorics)*6.形式語言與自動機(由于時間的關(guān)系，只討論前五部分內(nèi)容。)內(nèi)容1.計算機的誕生與發(fā)展和離散數(shù)學(xué)密切相關(guān)計算機正是在離散數(shù)學(xué)中的圖靈機的理論指導(dǎo)下誕生的(1936提出圖靈機---1946誕生計算機)。學(xué)習(xí)此課的目的1936年，阿蘭·麥席森·圖靈提出了一種抽象的計算模型──圖靈機(TuringMachine)。圖靈的基本思想是用機器來模擬人們用紙筆進行數(shù)學(xué)運算的過程，他把這樣的過程看作下列兩種簡單的動作：(a)在

3、紙上寫上或擦除某個符號；(b)把注意力從紙的一個位置移動到另一個位置；而在每個階段，人要決定下一步的動作，依賴于(a)此人當前所關(guān)注的紙帶上的符號和(b)此人當前思維的狀態(tài)。為了模擬人的這種運算過程，圖靈構(gòu)造出一臺假想的機器，該機器由以下幾個部分組成：(a)一條無限長的紙帶。紙帶被劃分為連續(xù)的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號表示空白。(b)一個讀寫頭。該讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，并能改變當前格子上的符號。(c)一個狀態(tài)寄存器。它用來保存圖靈機當前所處的狀態(tài)。圖

4、靈機的所有可能狀態(tài)的數(shù)目是有限的，并且有一個特殊的狀態(tài)，稱為停機狀態(tài)。(d)一套控制規(guī)則。它根據(jù)當前機器所處的狀態(tài)以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，并改變狀態(tài)寄存器的值，令機器進入一個新的狀態(tài)。注意這個機器的每一部分都是有限的，但它有一個潛在的無限長的紙帶，因此這種機器只是一個理想的設(shè)備。圖靈認為這樣的一臺機器就能模擬人類所能進行的任何計算過程。計算機科學(xué)的發(fā)展十分迅速，計算機的硬件從第1代起現(xiàn)在發(fā)展到第4代(電子管?晶體管?集成電路?大規(guī)模集成電路)，第5代(與人工智能相結(jié)合)即將問世。計算機科學(xué)已發(fā)展成為

5、一門一級學(xué)科。計算機產(chǎn)業(yè)已發(fā)展成為一個高科技的新興產(chǎn)業(yè)。計算機應(yīng)用越來越廣，所有領(lǐng)域幾乎無所不及。計算機科學(xué)的發(fā)展離不開計算機的理論。例如，程序設(shè)計語言：機器語言?匯編語言?高級面向過程語言?面向?qū)ο笳Z言?智能語言?…；系統(tǒng)軟件：如操作系統(tǒng)，單用戶?多用戶?網(wǎng)絡(luò)操作系統(tǒng)，…，即DOS?Windows?WindowsNT?…；這些發(fā)展都依賴于離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫原理、軟件工程、網(wǎng)絡(luò)等理論。其中離散數(shù)學(xué)是基礎(chǔ)，其它理論中都用到離散數(shù)學(xué)中的基本概念、基本思想、基本方法。2.此課是主干課，也是后繼課的基礎(chǔ)課離散數(shù)學(xué)

6、的后繼課程：數(shù)據(jù)結(jié)構(gòu)、編譯原理、算法分析與設(shè)計、人工智能、數(shù)據(jù)庫原理、……3.培養(yǎng)學(xué)生抽象的思維和邏輯推理能力4.培養(yǎng)學(xué)生創(chuàng)新能力離散數(shù)學(xué)可以幫助學(xué)生提高數(shù)學(xué)素質(zhì),提高創(chuàng)造力。特點：內(nèi)容較雜，概念多，定理多，比較抽象，給學(xué)習(xí)帶來一定難度。學(xué)習(xí)方法：強調(diào)：邏輯性、抽象性注重：概念、方法與應(yīng)用此課的特點及學(xué)習(xí)方法邏輯學(xué)--是一門研究思維形式和思維規(guī)律的科學(xué)。它包含：辯證邏輯：是研究人的思維中的辯證法。例如：用全面的和發(fā)展的觀點觀察事物；具體問題具體分析；實踐是檢查事物正誤的唯一標準；等等。形式邏輯：是研究人的思維的形式和一般規(guī)律。概念、

7、判斷、推理是形式邏輯的三大基本要素。第一篇數(shù)理邏輯這里我們只關(guān)心形式邏輯。人的思維過程：概念?判斷?推理正確的思維：概念清楚，判斷正確，推理合乎邏輯。人們是通過各種各樣的學(xué)習(xí)(理論學(xué)習(xí)和實踐學(xué)習(xí))來掌握許多概念和判斷。形式邏輯主要是研究推理的。推理：是由若干個已知的判斷(前提)，推出新的判斷(結(jié)論)的思維過程。一、形式邏輯類比推理：由個別事實推出個別結(jié)論。如：地球上有空氣、水，地球上有生物。火星上有空氣、水。?火星上有生物。歸納推理：由若干個別事實推出一般結(jié)論。如：銅能導(dǎo)電。鐵能導(dǎo)電。錫能導(dǎo)電。鉛能導(dǎo)電。……?一切金屬都導(dǎo)電。演繹推

8、理：由一般規(guī)律推出個別事實。形式邏輯主要是研究演繹推理的。推理方法例1：如果天下雨，則路上有水。(一般規(guī)律)天下雨了。(個別事實)推出結(jié)論：路上有水。(個別結(jié)論)例2：(大前提)：所有金屬都導(dǎo)電。(一般規(guī)律)(小前提)：銅是金屬。(個