離散數學

數學學科

離散數學(Discrete mathematics)是研究離散量的結構及其相互關係的數學學科,是現代數學的一個重要分支。離散的含義是指不同的連接在一起的元素,主要是研究基於離散量的結構和相互間的關係,其對象一般是有限個或可數個元素。

離散數學在各學科領域,特別在計算機科學與技術領域有著廣泛的應用,同時離散數學也是計算機專業的許多專業課程,如程序設計語言、數據結構、操作系統、編譯技術、人工智慧、資料庫、演演算法設計與分析、理論計算機科學基礎等必不可少的先行課程。通過離散數學的學習,不但可以掌握處理離散結構的描述工具和方法,為後續課程的學習創造條件,而且可以提高抽象思維和嚴格的邏輯推理能力,為將來參與創新性的研究和開發工作打下堅實的基礎。

發展


隨著信息時代的到來,工業革命時代以微積分為代表的連續數學佔主流的地位已經發生了變化,離散數學的重要性逐漸被人們認識。離散數學課程所傳授的思想和方法,廣泛地體現在計算機科學技術及相關專業的諸領域,從科學計算到信息處理,從理論計算機科學到計算機應用技術,從計算機軟體到計算機硬體,從人工智慧到認知系統,無不與離散數學密切相關。由於數字電子計算機是一個離散結構,它只能處理離散的或離散化了的數量關係,因此,無論計算機科學本身,還是與計算機科學及其應用密切相關的現代科學研究領域,都面臨著如何對離散結構建立相應的數學模型;又如何將已用連續數量關係建立起來的數學模型離散化,從而可由計算機加以處理。
離散數學是傳統的邏輯學,集合論(包括函數),數論基礎,演演算法設計,組合分析,離散概率,關係理論,圖論與樹,抽象代數(包括代數系統,群、環、域等),布爾代數,計算模型(語言與自動機)等彙集起來的一門綜合學科。離散數學的應用遍及現代科學技術的諸多領域。
離散數學也可以說是計算機科學的基礎核心學科,在離散數學中的有一個著名的典型例子-四色定理又稱四色猜想,這是世界近代三大數學難題之一,它是在1852年,由英國的一名繪圖員弗南西斯·格思里提出的,他在進行地圖著色時,發現了一個現象,“每幅地圖都可以僅用四種顏色著色,並且共同邊界的國家都可以被著上不同的顏色”。那麼這能否從數學上進行證明呢?100多年後的1976年,肯尼斯·阿佩爾(Kenneth Appel)和沃爾夫岡·哈肯(Wolfgang Haken)使用計算機輔助計算,用了1200個小時和100億次的判斷,終於證明了四色定理,轟動世界,這就是離散數學與計算機科學相互協作的結果。
離散數學可以看成是構築在數學和計算機科學之間的橋樑,因為離散數學既離不開集合論、圖論等數學知識,又和計算機科學中的資料庫理論、數據結構等相關,它可以引導人們進入計算機科學的思維領域,促進了計算機科學的發展。

學科內容


1.集合論部分:集合及其運算、二元關係與函數、自然數及自然數集、集合的基數。
2.圖論部分:圖的基本概念、歐拉圖與哈密頓圖、樹、圖的矩陣表示、平面圖、圖著色、支配集、覆蓋集、獨立集與匹配、帶權圖及其應用。
3.代數結構部分:代數系統的基本概念、半群與獨異點、群、環與域、格與布爾代數。
4.組合數學部分:組合存在性定理、基本的計數公式、組合計數方法、組合計數定理。
5.數理邏輯部分:命題邏輯、一階謂詞演算、消解原理。
離散數學被分成三門課程進行教學,即集合論與圖論、代數結構與組合數學、數理邏輯。教學方式以課堂講授為主,課後有書面作業、通過學校網路教學平台發布課件並進行師生交流。