離散數學簡介

1、2024年3月18日星期一,裘國永,1,離散數學簡介,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 數學中的“=”與編程語言中的“=”（賦值）,2024年3月18日星期一,裘國永,12,,例2 1996 年6月4日，歐洲宇航局的阿里亞那5號火箭(Ariane 5)在發(fā)射37秒后，偏離軌道，不得不自爆炸毀。雖然萬幸無人傷亡，但直接經濟損失達3億7千萬美元。事后發(fā)現，問題

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

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

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

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

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

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

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

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

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

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

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

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

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