離散數(shù)學課件1

1、離散數(shù)學,數(shù)學與計算機科學學院王 一 蕾yilei@fzu.edu.cn,2024/3/18,計算機科學與技術系,2,學時安排：總學時72，其中：課堂授課62學時，半期考2學時，習題課8學時。教材：耿素云，屈婉玲，離散數(shù)學，高等教育出版社，2004主要參考書： [1]耿素云，屈婉玲，王捍貧，離散數(shù)學教程，北京大學出版社，2002 [2]袁崇義 屈婉玲 王捍貧 劉田譯，離散數(shù)學及其應用（譯著），機械工業(yè)出版

2、社，2002[3][美]Bernard Kolman等 著，羅平譯，離散數(shù)學結構，高等教育出版社,離散數(shù)學的學習安排,2024/3/18,計算機科學與技術系,3,課程考核方法,課程考核按照平時作業(yè)、半期考和期末考試綜合評定學期成績。 1．平時作業(yè)：每次課后都留作業(yè)，占總成績10%。 2．半期考：占總成績的20%。 3．期末考試：占總成績的70%。,2024/3/18,計算機科學與技術系,4,離散數(shù)學概述,18世紀以前,

3、 數(shù)學基本上是研究離散對象的數(shù)量和空間關系的科學。之后,因天文學,物理學的發(fā)展,如行星軌道,牛頓三大力學定律等研究,極大地推動了連續(xù)數(shù)學(以微積分,數(shù)學物理方程, 實、復變函數(shù)論為代表)的發(fā)展。離散對象的研究則處于停滯狀態(tài)。20世紀30年代, 圖靈提出計算機的理論模型——圖靈機。這種模型早于實際制造計算機十多年,現(xiàn)實的計算機的計算能力, 本質上和圖靈機的計算能力一樣。由于在計算機內,機器字長總是有限的, 它代表離散的數(shù)或其它離

4、散對象，因此隨著計算機科學和技術的迅猛發(fā)展,離散數(shù)學就顯得重要。,2024/3/18,計算機科學與技術系,5,離散數(shù)學是現(xiàn)代數(shù)學的一個重要分支，是計算機科學與技術的理論基礎，所以又稱為計算機數(shù)學，是計算機科學與技術專業(yè)的核心、骨干課程。它以研究離散量的結構和相互間的關系為主要目標，其研究對象一般是有限個或可數(shù)個元素，因此它充分描述了計算機科學離散性的特點。,離散數(shù)學概述,2024/3/18,計算機科學與技術系,6,計算機求解的基本模式

5、是：實際問題 ? 數(shù)學建模 ? 算法設計 ? 編程實現(xiàn) 離散數(shù)學為數(shù)學建模打下知識基礎、為算法設計提供具體指導離散數(shù)學結構實際上就是通用的抽象的模式的集合。告訴你各種模式的本質特征和它們之間的關系，以及選用它們的策略；告訴你哪些問題是可解的，哪些是當前在圖靈機模型上無（最優(yōu)）解的，哪些是可以得到近似/較優(yōu)解的。簡而言之，離散數(shù)學的作用就在于訓練運用離散結構作為問題的抽象模型、構造算法、解決問題的能力。,離散數(shù)學概述,2024/3

6、/18,計算機科學與技術系,7,,離散數(shù)學的知識結構,2024/3/18,計算機科學與技術系,8,離散數(shù)學與后續(xù)課程,2024/3/18,計算機科學與技術系,9,學習離散數(shù)學的目的和意義,1、目的：培養(yǎng)數(shù)學抽象能力；培養(yǎng)用數(shù)學語言描述問題的能力；培養(yǎng)邏輯思維能力；培養(yǎng)數(shù)學論證能力。即培養(yǎng)抽象、表示、推理、論證的能力。2、意義：一是能針對科研和生產中產生的問題來建立數(shù)學模型，設計新的算法并論證算法的有效性，并寫出

7、優(yōu)秀的程序來解決實際問題；二是為學習專業(yè)課打好基礎。,2024/3/18,計算機科學與技術系,10,邏輯學是一門研究思維形式及思維規(guī)律的科學，也就是研究推理過程的規(guī)律的科學。邏輯規(guī)律就是客觀事物在人的主觀意識中的反映。 邏輯學分為辯證邏輯與形式邏輯兩種，辯證邏輯是以辯證法認識論的世界觀為基礎的邏輯學，形式邏輯主要是對思維的形式結構和規(guī)律進行研究的類似于語法的一門工具性學科。思維的形式結構包括了概念、判斷和推理之間的結構和聯(lián)系，其

8、中概念是思維的基本單位，通過概念對事物是否具有某種屬性進行肯定或否定的回答，這就是判斷；由一個或幾個判斷推出另一判斷的思維形式，就是推理。用數(shù)學方法來研究推理的規(guī)律稱為數(shù)理邏輯。這里所指的數(shù)學方法，就是引進一套符號體系的方法，在其中表達和研究推理的規(guī)律。,數(shù)理邏輯簡介,2024/3/18,計算機科學與技術系,11,數(shù)理邏輯簡介,通常認為數(shù)理邏輯是由萊布尼茲(Leibniz)創(chuàng)立的。 數(shù)理邏輯的內容包括：證明論、模型論、遞歸論、公理

9、化集合論和命題演算、謂詞演算。 數(shù)理邏輯的應用在形式語義學、程序設計方法學和軟件工程領域。 在邏輯程序設計方面。 在數(shù)據(jù)庫理論方面。 在程序自動生成、自動轉換等的理論和技術研究中。 在形式語言理論、自動機理論、可計算理論、計算復雜性理論等方面。 在人工智能方面。,2024/3/18,計算機科學與技術系,12,一個土耳其商人想找一個十分聰明的助手協(xié)助他經商，有兩人前來應聘，這個商人為了試試哪個更聰明些，就把兩個人帶進一

10、間漆黑的屋子里，他打開燈后說：“這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的，現(xiàn)在，我把燈關掉，而且把帽子擺的位置弄亂，然后我們三個人每人摸一頂帽子戴在自己頭上，在我開燈后，請你們盡快說出自己頭上戴的帽子是什么顏色的?！闭f完后，商人將電燈關掉，然后三人都摸了一頂帽子戴在頭上，同時商人將余下的兩頂帽子藏了起來，接著把燈打開。這時，那兩個應試者看到商人頭上戴的是一頂紅帽子，其中一個人便喊道：“我戴的是黑帽子?！?請問這個人說得對嗎？

11、他是怎么推導出來的呢？,數(shù)理邏輯簡介,2024/3/18,計算機科學與技術系,13,前提,結論,推理（規(guī)則）,數(shù)理邏輯簡介,2024/3/18,計算機科學與技術系,14,1.1 命題與聯(lián)結詞,1.2 命題公式及其賦值,2.1 等值式,2.2 析取范式與合取范式,3.1 推理的形式結構,3.2 自然推理系統(tǒng),4.1 一階邏輯命題符號化,4.2 一階邏輯公式及解釋,5.1 一階邏輯等值式與置換規(guī)則,5.2 一階邏輯前束范式,5.3 一階邏輯

12、的推理理論,數(shù)理邏輯簡介,2024/3/18,計算機科學與技術系,15,20世紀數(shù)學中最為深刻的活動，是關于數(shù)學基礎的探討。這不僅涉及到數(shù)學的本性，也涉及到演繹數(shù)學的正確性。數(shù)學中若干悖論的發(fā)現(xiàn)，引發(fā)了數(shù)學史上的第三次危機，這種悖論在集合論中尤為突出。 集合論最初是一門研究數(shù)學基礎的學科，它從一個比“數(shù)”更簡單的概念----集合出發(fā)，定義數(shù)及其運算，進而發(fā)展到整個數(shù)學領域，在這方面它取得了極大的成功。集合論的起源可以追溯到19世紀末

13、期。1874年，29歲的德國數(shù)學家康托爾(Georg Cantor)在“數(shù)學雜志”發(fā)表了關于無窮集合論的第一篇革命性文章，從1874年至1884年間，Cantor的系列有關集合的文章，奠定了集合論的基礎。,集合論簡介,2024/3/18,計算機科學與技術系,16,康托爾開創(chuàng)的集合論被稱為樸素集合論，因為他沒有對集合論作完整的形式的刻畫，從而導致了理論的不一致(產生了悖論)。在集合論的若干悖論中，最通俗易懂的是Russell(羅素)的理

14、發(fā)師悖論：一個鄉(xiāng)村理發(fā)師，自夸本村無人可與相比，宣稱他當然不給自己理發(fā)的人理發(fā)，但卻給本村所有自己不理發(fā)的人理發(fā)。一天他發(fā)生了疑問，他是否應當給自己理發(fā)。,集合論簡介,解：設C＝{x|x是不給自己理發(fā)的人} b是這位理發(fā)師如 b?C，則 b?C；如 b?C，則 b?C。,2024/3/18,計算機科學與技術系,17,集合不僅可以用來表示數(shù)及其運算，更可以用于非數(shù)值信息的表示和處理，如數(shù)據(jù)的增加、刪除、修改、排序，以及數(shù)據(jù)間關

15、系的描述，有些很難用傳統(tǒng)的數(shù)值計算來處理，但可以用集合運算來處理。因此，集合論在程序語言、數(shù)據(jù)結構、編譯原理、數(shù)據(jù)庫與知識庫、形式語言和人工智能等領域中都得到了廣泛的應用，并且還得到了發(fā)展，如Zadeh(扎德)的模糊集理論和Pawlak的粗糙集理論。,集合論簡介,2024/3/18,計算機科學與技術系,18,近世代數(shù)，……，是關于運算的學說，是關于運算規(guī)則的學說，但它不把自己局限在研究數(shù)的運算性質上，而是企圖研究一般性元素的運算性質。

16、——Ｍ.Klein數(shù)學之所以重要，其中心原因在于它所提供的數(shù)學系統(tǒng)的豐富多彩；此外的原因是，數(shù)學給出了一個系統(tǒng)，以便于使用這些模型對物理現(xiàn)實和技術領域提出問題，回答問題，并且也就探索了模型的行為?！猂.C.Buck&E.F.Buck代數(shù)系統(tǒng)--具有運算的集合--是抽象代數(shù)研究的主要對象。,代數(shù)結構簡介,2024/3/18,計算機科學與技術系,19,代數(shù)結構簡介,2024/3/18,計算機科學與技術系,20,半群,獨

17、異點,群,交換半群,交換獨異點,Abel 群,有限群,循環(huán)群,n元置換群,Klein 群,代數(shù)結構簡介,2024/3/18,計算機科學與技術系,21,組合數(shù)學是一個古老而又年輕的數(shù)學分支。 據(jù)傳說，大禹在4000多年前就觀察到神龜背上的幻方…...,組合數(shù)學簡介,2024/3/18,計算機科學與技術系,22,幻方可以看作是一個3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對角線的和都是15。,,,,,,5,1,9,3,7

18、,2,4,8,6,組合數(shù)學簡介,2024/3/18,計算機科學與技術系,23,賈憲 北宋數(shù)學家（約11世紀） 著有《黃帝九章細草》、《算法斅古集》斅 音“笑（“古算法導引”）都已失傳。楊輝著《詳解九章算法》（1261年）中曾引賈憲的“開方作法本源”圖（即指數(shù)為正整數(shù)的二項式展開系數(shù)表，現(xiàn)稱“楊輝三角形”）和“增乘開方法”（求高次冪的正根法）。前者比帕斯卡三角形早600年，后者比霍納（William Geoge Horner，

19、1786—1837）的方法（1819年）早770年。,組合數(shù)學簡介,2024/3/18,計算機科學與技術系,24,1666年萊布尼茲所著《組合學論文》一書問世，這是組合數(shù)學的第一部專著。書中首次使用了組合論（Combinatorics）一詞。組合數(shù)學的蓬勃發(fā)展則是在計算機問世和普遍應用之后。由于組合數(shù)學涉及面廣，內容龐雜，并且仍在很快地發(fā)展著，因而還沒有一個統(tǒng)一而有效的理論體系。這與數(shù)學分析形成了對照。組合分析是組合算法的基礎。,組

20、合數(shù)學簡介,2024/3/18,計算機科學與技術系,25,組合數(shù)學經常使用的方法并不高深復雜。最主要的方法是計數(shù)時的合理分類和組合模型的轉換。 但是，要學好組合數(shù)學并非易事，既需要一定的數(shù)學修養(yǎng)，也要進行相當?shù)挠柧殹?組合數(shù)學簡介,2024/3/18,計算機科學與技術系,26,圖論是離散數(shù)學的重要組成部分，是近代應用數(shù)學的重要分支。1736年是圖論歷史元年，因為在這一年瑞士數(shù)學家歐拉(Euler)發(fā)表了圖論的首篇論文——《哥尼

21、斯堡七橋問題無解》，所以人們普遍認為歐拉是圖論的創(chuàng)始人。1936年，匈牙利數(shù)學家寇尼格（Konig）出版了圖論的第一部專著《有限圖與無限圖理論》，這是圖論發(fā)展史上的重要的里程碑，它標志著圖論將進入突飛猛進發(fā)展的新階段。計算機科學的發(fā)展為圖論的發(fā)展提供了計算工具?，F(xiàn)代科學技術的發(fā)展需要借助圖論來描述和解決各類課題中的各種關系，從而推動科學技術不斷地攀登新的高峰。 作為描述事務之間關系的手段或稱工具，圖論在許多領域都得到廣泛的應用，

22、也正是因為在眾多方面的應用中，圖論自身才得到了非常迅速的發(fā)展。,圖論簡介,2024/3/18,計算機科學與技術系,27,離散數(shù)學應用典型實例,離散數(shù)學無處不在。主要應用于在各種復雜的關系中找出最優(yōu)方案。離散數(shù)學完全可以看成是一門量化了的關系學，量化了的運籌學，量化了的管理學。,2024/3/18,計算機科學與技術系,28,1、四色猜想問題,一張世界地圖，若用一種顏色對一個國家著色，那么只需四種顏色，即可以保證每兩個相鄰的國家顏色不同

23、。世界近代三大數(shù)學難題之一。1852年，英國弗南西斯·格思里(Francis Guthrie)提出四色猜想。1976年，在J. Koch的算法的支持下，美國數(shù)學家阿佩爾(Kenneth Appel)與哈肯(Wolfgang Haken)在美國伊利諾斯大學的兩臺不同的電子計算機上，用了1200個小時，作了100億判斷，終于完成了四色定理的計算機證明。 最近人們發(fā)現(xiàn)了更簡單的證明。,2024/3/18,計算機科學與技術系,2

24、9,2、裝箱問題,當你裝一個箱子時，要想盡可能地把箱子裝滿卻非易事，你往往需要試圖多次調整。理論上講，裝箱問題是一個即使用計算機也不易解決的很難的數(shù)學問題。[問題描述]有一個箱子容量為V(正整數(shù)，0≤V≤20000），同時有n個物品（0≤n≤30),每個物品有一個體積（正整數(shù)）。要求從n個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。,2024/3/18,計算機科學與技術系,30,3、船夫過河問題,船夫要把一匹狼、一只羊和

25、一棵白菜運過河。只要船夫不在場,羊就會吃白菜、狼就會吃羊。船夫的船每次只能運送一種東西。怎樣才能把三者都運過河?,2024/3/18,計算機科學與技術系,31,4、工作調度和安排問題,如在生產原子彈的曼哈頓計劃中，涉及到很多工序、很多人員安排、很多元件生產怎樣合理調度各種人員的工作？怎樣科學安排各種工序間的銜接？怎樣計劃使整個工期的時間盡可能短？,2024/3/18,計算機科學與技術系,32,5、航空調度和航班設定問題,怎樣

26、周密設定各個航班，以滿足不同旅客轉機的需求？怎樣同時也使得每個機場的各個航班的起降分布合理？另外，在一些航班有延誤的特殊情況下，怎樣作出科學的調整？,2024/3/18,計算機科學與技術系,33,6、交通規(guī)劃與管理問題,哪些地方可能是阻塞要地？哪些地方應設單行道？立交橋建在哪里最合適？紅綠燈怎樣設置最合理？,2024/3/18,計算機科學與技術系,34,7、中國郵路問題,一個郵遞員送信，要走完他負責投遞的全部街道，完成任務后回

27、到郵局，應按怎樣的路線走，他所走的路程才會最短呢？ 由我國數(shù)學家管梅谷在1962年首先提出的，因此，在國際上稱為中國郵路問題。,2024/3/18,計算機科學與技術系,35,8、工程工序管理問題,世界著名的假日飯店在其科學的管理中嚴格規(guī)定了有關工序：清潔工第一步是換什么，洗什么？第二步又做什么？同時需要確保他進出房間的次數(shù)最少？一個如此簡單的工作都要講究工程工序管理，那么更復雜的的工作就更不用說了。,2024/3/18,計算機科

28、學與技術系,36,9、地面鋪磚問題,用形狀相同的方形磚塊，無疑可將地面鋪滿（不考慮邊緣的特殊情況）而如用不同形狀，又非方形的磚塊來鋪地面時，能否鋪滿？這一常見的實際的簡單問題，也涉及到很深的數(shù)學原理。,2024/3/18,計算機科學與技術系,37,10、網絡布局問題,一個通信網絡怎樣布局最節(jié)??？美國的貝爾實驗室和IBM公司都有世界一流的組合數(shù)學家在研究這個問題。該問題關系到巨大的經濟效益。,2024/3/18,計算機科學與技術系

29、,38,11、金融分析問題,投資方案的確定。怎樣找出好的投資組合以降低投資風險。南開大學組合數(shù)學研究中心開發(fā)出“金沙股市風險分析系統(tǒng)”，已投放市場，為短線投資者提供有效的風險防范工具。,2024/3/18,計算機科學與技術系,39,12、一筆畫問題,所謂一筆畫，就是從圖形上的某點出發(fā)，筆不離開紙，而且每條線都只畫一次不準重復。什么樣的圖形能一筆畫成呢？,,,2024/3/18,計算機科學與技術系,40,13、螞蟻比賽問題,甲乙兩只

30、螞蟻進行比賽：從他們所在的結點出發(fā)，在圖中走過所有的邊，最后到達C處，如果他們的速度相同，問誰先到達目的地？,2024/3/18,計算機科學與技術系,41,14、哥尼斯堡七橋問題,18世紀時，歐洲有一個風景秀麗的小城哥尼斯堡，那里有七座橋。如圖所示。當時哥尼斯堡的居民中流傳著一道難題：一個人怎樣才能一次走遍七座橋，每座橋只走過一次，最后回到出發(fā)點？,2024/3/18,計算機科學與技術系,42,15、環(huán)游世界問題,從正十二面體的一個頂