離散數(shù)學簡介

1、2024年3月18日星期一,裘國永,1,離散數(shù)學簡介,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.計算思維是運用計算機科學的基礎概念進行問題求解、系統(tǒng)設計、以

5、及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動。,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,,為什么在用計算機去解決問題時運用計算思維非常重要？例1 數(shù)學中的“=”與編程語言中的“=”（賦值）,2024年3月18日星期一,裘國永,12,,例2 1996 年6月4日，歐洲宇航局的阿里亞那5號火箭(Ariane 5)在發(fā)射37秒后，偏離軌道，不得不自爆炸毀。雖然萬幸無人傷亡，但直接經(jīng)濟損失達3億7千萬美元。事后發(fā)現(xiàn)，問題

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

11、,,離散數(shù)學是研究離散量的關(guān)系的一門科學.Discrete mathematics is the part of mathematics devoted to the study of discrete objects.離散數(shù)學是研究離散結(jié)構(gòu)的數(shù)學分科. -- 辭海,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ù)學是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學學科。離散數(shù)學和連續(xù)數(shù)學一樣是描述、刻畫現(xiàn)實物質(zhì)世界的重

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

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

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

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

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

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

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

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

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

26、,32,離散數(shù)學的學習方法,強調(diào)：邏輯性、抽象性；注重：概念、方法與應用；練習：做中學(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ù)學的先導課程,高等數(shù)學(不是必需的?。┚€性代數(shù)(主要是矩陣運算),2024年3月18日星期一,裘國永,36,離散數(shù)學的后繼課程,數(shù)據(jù)結(jié)構(gòu)、編譯原理、形式語言 算法分析與設計、人工智能、自動機理論 操作系統(tǒng)、數(shù)據(jù)庫、計算機安全 ……,2024年3月18日星期一,裘國永,37,教材,Discrete Mathematics with Combinatorics(Second Edition)，James

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