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

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

1、離散數(shù)學(xué)(1)DiscreteMath計(jì)算機(jī)軟件研究所趙志濱緒論離散數(shù)學(xué)課性質(zhì)及其內(nèi)容學(xué)習(xí)此課的目的學(xué)習(xí)此課的方法離散數(shù)學(xué)DiscreteMath研究離散對(duì)象及其相互間關(guān)系的一門數(shù)學(xué)學(xué)科。研究離散結(jié)構(gòu)的數(shù)學(xué)分支。（辭海）計(jì)算機(jī)不論硬件還是軟件都屬于離散結(jié)構(gòu)，所以它所應(yīng)用的數(shù)學(xué)必是離散數(shù)學(xué)。性質(zhì)：此課是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的重要的理論基礎(chǔ)課，也是該專業(yè)的主干課。計(jì)算機(jī)科學(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.形式語(yǔ)言與自動(dòng)機(jī)(由于時(shí)間的關(guān)系，只討論前五部分內(nèi)容。)內(nèi)容1.計(jì)算機(jī)的誕生與發(fā)展和離散數(shù)學(xué)密切相關(guān)計(jì)算機(jī)正是在離散數(shù)學(xué)中的圖靈機(jī)的理論指導(dǎo)下誕生的(1936提出圖靈機(jī)---1946誕生計(jì)算機(jī))。學(xué)習(xí)此課的目的1936年，阿蘭·麥席森·圖靈提出了一種抽象的計(jì)算模型──圖靈機(jī)(TuringMachine)。圖靈的基本思想是用機(jī)器來(lái)模擬人們用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過(guò)程，他把這樣的過(guò)程看作下列兩種簡(jiǎn)單的動(dòng)作：(a)在

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

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

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

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

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

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