離散數(shù)學(xué)簡介

1、2024年3月18日星期一,裘國永,1,離散數(shù)學(xué)簡介,Introduction to Discrete Mathematics,2024年3月18日星期一,裘國永,2,,2024年3月18日星期一,裘國永,3,,2024年3月18日星期一,裘國永,4,,Learn to fail Fail to learn,2024年3月18日星期一,裘國永,5,,The goals of the course: let students

2、Learn a particular set of mathematical facts and apply them (mathematical maturity: ability to understand and create mathematical arguments)Think logically and mathematically (mathematical reasoning, algorithmic thinkin

3、g)Think like a computer scientist- computing thinking(計算思維),2024年3月18日星期一,裘國永,6,,It is critical for computer science students to think logically. Essentially, a logical bug-free computer program is equivalent to a logic

4、al proof.,2024年3月18日星期一,裘國永,7,,Computational thinking will be a fundamental skill used by everyone in the world by the middle of the 21st Century，just like reading, writing, and arithmetic.計算思維是運用計算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問題求解、系統(tǒng)設(shè)計、以

5、及人類行為理解等涵蓋計算機(jī)科學(xué)之廣度的一系列思維活動。,2024年3月18日星期一,裘國永,8,,Some Examples of CT How difficult is this problem and how best can I solve it? – Theoretical computer science gives precise meaning to these and related questions and the

6、ir answers. CT is thinking recursively. CT is reformulating a seemingly difficult problem into one which we know how to solve. – Reduction, embedding, transformation, simulation,2024年3月18日星期一,裘國永,9,,CT is interpreting

7、code as data and data as code. CT is using abstraction and decomposition in tackling a large complex task. CT is judging a system’s design for its simplicity and elegance.,2024年3月18日星期一,裘國永,10,,CT is type checking. CT

8、 is prevention, detection, and recovery from worst-case scenarios through redundancy, damage containment, and error correction. CT is modularizing something in anticipation of multiple users and prefetching and caching

9、in anticipation of future use.,2024年3月18日星期一,裘國永,11,,為什么在用計算機(jī)去解決問題時運用計算思維非常重要？例1 數(shù)學(xué)中的“=”與編程語言中的“=”（賦值）,2024年3月18日星期一,裘國永,12,,例2 1996 年6月4日，歐洲宇航局的阿里亞那5號火箭(Ariane 5)在發(fā)射37秒后，偏離軌道，不得不自爆炸毀。雖然萬幸無人傷亡，但直接經(jīng)濟(jì)損失達(dá)3億7千萬美元。事后發(fā)現(xiàn)，問題

10、出在負(fù)責(zé)測量發(fā)射裝置高度及其在空中的運動狀態(tài)的慣性制導(dǎo)參考系統(tǒng)(SRI)所使用的計算機(jī)軟件的一行代碼上，這一行代碼的作用是將數(shù)據(jù)從64 位浮點數(shù)到16位有符號整數(shù)值。但要轉(zhuǎn)換的浮點數(shù)的大小大于16位整數(shù)的表達(dá)能力，從而導(dǎo)致了異常（arithmetic overflow）。本來應(yīng)該在數(shù)據(jù)轉(zhuǎn)換過程中為可能產(chǎn)生的運算符錯誤設(shè)置保護(hù)裝置，但沒有這樣做，從而成就了歷史上有名的一個computer bug。,2024年3月18日星期一,裘國永,13

11、,,離散數(shù)學(xué)是研究離散量的關(guān)系的一門科學(xué).Discrete mathematics is the part of mathematics devoted to the study of discrete objects.離散數(shù)學(xué)是研究離散結(jié)構(gòu)的數(shù)學(xué)分科. -- 辭海,2024年3月18日星期一,裘國永,14,,The word “discrete” in discrete mathem

12、atics is used in the sense of “separated from each other”, the opposite of “continuous”;It is also used in the more restrictive sense of “finite”.,2024年3月18日星期一,裘國永,15,,離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科。離散數(shù)學(xué)和連續(xù)數(shù)學(xué)一樣是描述、刻畫現(xiàn)實物質(zhì)世界的重

13、要工具. 數(shù)學(xué)方法在現(xiàn)代科技的發(fā)展中已經(jīng)成為一種必不可少的認(rèn)識手段. 它的主要作用是為科技研究提供：（1）簡潔精確的形式化語言；（2）數(shù)量分析和計算的方法；（3）邏輯推理的工具. 人們公認(rèn)高技術(shù)本質(zhì)上就是數(shù)學(xué)技術(shù)，而計算學(xué)科（即我們所熟悉的計算機(jī)科學(xué)與技術(shù)）更是一門數(shù)學(xué)技術(shù).,2024年3月18日星期一,裘國永,16,,計算學(xué)科對描述和變換信息的算法過程，包括其理論、分析、設(shè)計、效率、實現(xiàn)和應(yīng)用等進(jìn)行系統(tǒng)研究. 它涉及計算過程的分析以

14、及計算機(jī)的設(shè)計和使用，從算法與可計算性的研究到可計算性硬件和軟件的實際實現(xiàn)問題的研究.,2024年3月18日星期一,裘國永,17,能行性 effectiveness,計算學(xué)科的根本問題是：什么能(有效地)自動進(jìn)行，什么不能(有效地)自動進(jìn)行. 即它的核心問題是“能行”問題. 而只有那些采用構(gòu)造性數(shù)學(xué)描述方法的模型才是能行的，凡是與“能行性”有關(guān)的討論，都是處理離散對象的. 因為非離散對象(即連續(xù)對象)，是很難進(jìn)行“能行”處理的. 因此，

15、“能行性”這個計算學(xué)科的根本問題決定了計算機(jī)本身的結(jié)構(gòu)和它處理的對象都是離散型的，甚至許多連續(xù)型問題也必須在轉(zhuǎn)化為離散型問題以后才能被計算機(jī)處理. 所以計算機(jī)科學(xué)與技術(shù)本質(zhì)上是一門離散數(shù)學(xué)技術(shù).,2024年3月18日星期一,裘國永,18,,離散數(shù)學(xué)的最大特點或最基本特征就在于構(gòu)造性. 因此離散數(shù)學(xué)是計算機(jī)科學(xué)和技術(shù)的重要理論基礎(chǔ)之一，為計算學(xué)科各分支領(lǐng)域解決其基本問題提供了強(qiáng)有力的數(shù)學(xué)工具，在計算機(jī)科學(xué)與技術(shù)中有十分廣泛的應(yīng)用.,202

16、4年3月18日星期一,裘國永,19,,IEEE－CS和ACM聯(lián)合組成的任務(wù)組于2001年12月提交的CC2001將計算學(xué)科劃分為14個主領(lǐng)域（離散結(jié)構(gòu)、程序設(shè)計基礎(chǔ)、算法與復(fù)雜性、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、網(wǎng)絡(luò)計算、程序設(shè)計語言、人機(jī)交互、圖形學(xué)與可視化計算、智能系統(tǒng)、信息管理、軟件工程、社會和職業(yè)的問題和科學(xué)計算），離散數(shù)學(xué)從預(yù)備知識部分獨立出來，列為學(xué)科的第一個主領(lǐng)域，以強(qiáng)調(diào)計算學(xué)科對它的依賴性.,2024年3月18日星期一,裘國永,20

17、,,The kinds of problems that can be solved using discrete mathematics are:How ways are there to choose a valid password on a computer system?What is the probability of winning a lottery?Is there a link between two com

18、puters in a network?How I can identify spam e-mail messages?How can I encrypt a message so that no unintended recipient can read it?,2024年3月18日星期一,裘國永,21,,What is the shortest path between two cities using a transporta

19、tion system?What can a list of integers be sorted so that the integers are in increasing order?How many steps are required to do such a sorting?How can it be proved that a sorting algorithm correctly sorts a list?How

20、 can a circuit that adds two integers be designed?How can valid Internet addresses are there?,2024年3月18日星期一,裘國永,22,,用一組基本的指令來編制一個計算機(jī)程序，非常類似于從一組公理來構(gòu)造一個數(shù)學(xué)證明.

21、 -- D.E.Knuth 編程大師、1974年圖靈獎獲得者,2024年3月18日星期一,裘國永,23,,離散數(shù)學(xué)是計算科學(xué)各專業(yè)最重要的基礎(chǔ)課程之一.,2024年3月18日星期一,裘國永,24,,計算學(xué)科各專業(yè)的學(xué)生學(xué)習(xí)離散數(shù)學(xué)，一方面為學(xué)習(xí)各專業(yè)課程作必要的數(shù)學(xué)準(zhǔn)備，另一方面，培

22、養(yǎng)和訓(xùn)練他們掌握使用數(shù)學(xué)語言或符號系統(tǒng)處理問題的基本方法.它還能幫助培養(yǎng)學(xué)生的邏輯推理能力、抽象思維能力和形式化思維能力.,2024年3月18日星期一,裘國永,25,教學(xué)內(nèi)容,數(shù)理邏輯(Mathematics Logic) 集合論(Set Theory) 組合數(shù)學(xué)(Combinatorics) 圖論(Graph Theory) 代數(shù)結(jié)構(gòu)(Abstract Algebra),2024年3月18日星期一,裘國永,26,離散

23、數(shù)學(xué)內(nèi)容之間的關(guān)系,集合論,數(shù)理邏輯,組合數(shù)學(xué),圖論,代數(shù)結(jié)構(gòu),,,,,,,,2024年3月18日星期一,裘國永,27,數(shù)理邏輯,又稱符號邏輯，是計算機(jī)科學(xué)重要的理論基礎(chǔ)之一，和計算機(jī)的發(fā)展有十分密切的關(guān)系. 它是依靠引進(jìn)一個符號體系，來研究形式推理的學(xué)科. 它為自動機(jī)理論、機(jī)器證明、自動程序設(shè)計和計算機(jī)輔助設(shè)計等提供了必要的理論基礎(chǔ). 主要講命題邏輯和謂詞邏輯兩部分.,2024年3月18日星期一,裘國永,28,集合論,現(xiàn)代數(shù)學(xué)的基

24、礎(chǔ)，是數(shù)學(xué)中不可或缺的基本描述工具. 集合論的概念已深入到現(xiàn)代科學(xué)的各個方面，成為表達(dá)各種嚴(yán)謹(jǐn)科學(xué)概念必不可少的數(shù)學(xué)語言. 不僅可以用來表示數(shù)及其運算，更可以用于非數(shù)值信息的表示和處理，因此它和計算機(jī)科學(xué)及其應(yīng)用有極其密切的關(guān)系.主要講集合、關(guān)系和函數(shù).,2024年3月18日星期一,裘國永,29,組合數(shù)學(xué),研究離散對象的計數(shù). 隨著計算機(jī)科學(xué)的日益發(fā)展，組合數(shù)學(xué)的重要性也日漸凸顯，因為計算機(jī)科學(xué)的核心內(nèi)容是使用算法處理離散數(shù)據(jù).主

25、要講基本計數(shù)原理、容斥原理、排列與組合、鴿巢原理.,2024年3月18日星期一,裘國永,30,代數(shù)結(jié)構(gòu),在自動機(jī)理論、形式語言、邏輯電路設(shè)計、編碼理論等的研究中有著十分廣泛的應(yīng)用. 主要講半群、群、格與布爾代數(shù).,2024年3月18日星期一,裘國永,31,圖論,計算機(jī)中數(shù)據(jù)表示、存儲和運算的基礎(chǔ)，因此圖論在計算機(jī)科學(xué)和信息技術(shù)中發(fā)揮著重要作用.主要講圖的基本概念、歐拉圖、哈密爾頓圖、樹、平面圖等.,2024年3月18日星期一,裘國永

26、,32,離散數(shù)學(xué)的學(xué)習(xí)方法,強(qiáng)調(diào)：邏輯性、抽象性；注重：概念、方法與應(yīng)用；練習(xí)：做中學(xué)(Learn to fail, fail to learn),2024年3月18日星期一,裘國永,33,,It is important to realize that there is no mathematics without proofs. Merely stating the facts, without saying something

27、 about why these facts are valid, would be terribly far from the spirit of mathematics and would make it impossible to give any idea about how it works.,2024年3月18日星期一,裘國永,34,,Another ingredient of mathematics is problem

28、solving. You won’t be able to learn any mathematics without dirtying your hands and trying out the ideas you learn about in the solution of the problems. You will learn the most by actively working exercises.,2024年3月18日

29、星期一,裘國永,35,離散數(shù)學(xué)的先導(dǎo)課程,高等數(shù)學(xué)(不是必需的?。┚€性代數(shù)(主要是矩陣運算),2024年3月18日星期一,裘國永,36,離散數(shù)學(xué)的后繼課程,數(shù)據(jù)結(jié)構(gòu)、編譯原理、形式語言 算法分析與設(shè)計、人工智能、自動機(jī)理論 操作系統(tǒng)、數(shù)據(jù)庫、計算機(jī)安全 ……,2024年3月18日星期一,裘國永,37,教材,Discrete Mathematics with Combinatorics(Second Edition)，James

30、A. Anderson原著，俞正光，陸玫改編，高等教育出版社，2005年,2024年3月18日星期一,裘國永,38,參考書目,《離散數(shù)學(xué)》，方世昌著，西安電子科大出版社 《離散數(shù)學(xué)》，倪子偉，蔡經(jīng)球著，科學(xué)出版社《離散數(shù)學(xué)》，陳莉等著，高等教育出版社《離散數(shù)學(xué)》，孫吉貴等著，高等教育出版社《離散數(shù)學(xué)》，傅彥等著，機(jī)械工業(yè)出版社《離散數(shù)學(xué)》，左孝凌著，上?？萍嘉墨I(xiàn)出版社《離散數(shù)學(xué)》，劉玉珍等著，武漢大學(xué)出版社Discret