離散數學(北京交通大學提供的慕課課程)

離散數學課程是北京交通大學於2018年03月05日首次在中國大學MOOC開設的慕課課程、國家精品線上開放課程。該課程授課教師為劉鐸、趙宏、陳旭東、張順利。據2021年3月中國大學MOOC官網顯示，該課程已開課7次。

離散數學課程共13個模組，包括基礎知識、命題邏輯、謂詞邏輯、二元關係、函式、偏序關係、圖論、無向樹、專題、作業及考試主觀題講解等內容。

基本介紹

• 中文名：離散數學
• 外文名：Discrete Mathemtics
• 類別：慕課、國家精品線上開放課程
• 提供院校：北京交通大學
• 授課平台：中國大學MOOC
• 授課教師：劉鐸、趙宏、陳旭東、張順利
• 開課時間：2018年03月05日（首次）

課程性質

課程定位

離散數學課程是面向所有專業的本科生、專科生和社會公眾開放的基礎課程，是研究不同離散量的各自結構、規律及相互關係的一門學科，在程式設計語言、數據結構、作業系統、軟體工程、資料庫原理、計算機網路、人工智慧、軟體設計形式化等方面都有套用。

適應對象

離散數學課程適合計算機科學和軟體科學等專業學生學習。

開課信息

開課次數	開課時間	授課教師	學時安排	參與人數
第1次開課	2018年03月05日~2018年07月09日	劉鐸、趙宏、陳旭東、張順利	4~5小時每周	14233人
第2次開課	2018年09月03日~2019年01月16日			18695人
第3次開課	2019年02月25日~2019年07月28日		4~6小時每周	19093人
第4次開課	2019年08月26日~2019年12月29日			16229人
第5次開課	2020年02月17日~2020年07月19日	劉鐸		17198人
第5次開課	2020年08月31日~2020年12月27日			7789人
第7次開課	2021年02月22日~2021年06月04日			待定

（註：表格內容參考資料）

課程簡介

離散數學課程介紹了集合與序列基本旬祖章概念和命題邏輯的基本知識；謂詞邏輯的套用；關係的基本知識和函式的基本內容；偏序關係的基本內容；圖的基本概念和圖的套用；樹的分類和部分專題；部分拓展抹悼主祝內容以及作業及考試主觀題講解等內容。

課程大綱

第1次開課大綱

第1講 基礎知識 1.1 集合與序列 1.2 數論基礎 1.3 計數基礎 1.4 布爾矩陣及其運算 第2講 命題邏輯 2.1 命題邏輯的基本概念 2.2 命題公式及其分類 2.3 命題邏輯的等值演算 2.4 範式 2.5 命題邏輯的推理 第3講 謂詞邏輯 3.1 謂詞、量詞與自然語句形式化 3.2 謂詞公式及分類 3.3 自然語句形式化 3.4 謂詞邏輯的等值演算 3.5 前束范全盼再式 3.6 謂詞邏輯的推理 第4講 二元關係 4.1 關係及其表示 4.2 關係的運算 4.3 關係的性質 4.4 關係的閉包 4.5 等價關係和集合的劃分

第5講 函式 5.1 函式的定義 5.2 函式的性質 5.3 函式的複合 5.4 逆函式 5.5 計算機科學中的常用函式 第6講 偏序關係 6.1 偏序關係和偏序集 6.2 偏序集中的特殊元素 6.3 格 第7講 圖論 7.1 圖的基本概念 7.2 歐拉圖 7.3 哈密爾頓圖 7.4 平面圖 7.5 頂點支配、獨立與覆蓋 7.6 圖的著色 第8講 樹及其套用 8.1 無向樹 8.2 支撐樹及其套用 8.3 最短道路樹 8.4 根樹 8.5 二叉樹的遍歷 8.6 最優二叉樹與霍夫曼編碼

（註：課程大綱排版從左到右列）

第2次開課大綱

第1講 基礎知識 1.2 數論基礎 1.1 集合與序列 1.4 布爾矩陣及其運算 1.3 計數基協槓礎 第1講單元作業 第1講單元測試 第2講 命題邏輯 擴展內容——新裙子的顏色 2.3 命題邏輯的等值演算 擴展內容——說謊人與妖魔戒指 擴展內容——從一個競賽題目說起 擴展內容——早餐吃的什麼 2.5 命題邏輯的推理 擴展內容——對偶 擴展內容——邏輯聯接詞的完備集 2.4 範式 2.1 命題邏輯的基本概念 2.2 命題公式及其分類 第2講單元作業 第2講單元測試 課程介紹 課程介紹 第3講 謂詞邏輯 3.5 前束範式 3.6 謂詞邏輯的推理 3.2 謂詞公式及分類 3.4 謂詞邏輯的等值演算 擴展內容——Prolog語言 3.1 謂詞與量詞 3.3 自然語句形式化 第3講單元測試 第3講單元作業 第4講 二元關係 4.2 關係戒燥堡夜的運算 4.3 關係的性質 4.1 關係及其表示 4.5 等價關係和集合的劃分 4.4 關係的閉包 第4講單元測試(2) 第4講單元測試(1) 第4講單元作業 第5講 函式 5.4 逆函式 擴展內精定院容——集合的勢 5.3 函式的複合 5.2 函式的性質 擴展內容——置換 5.5 計算機科學中的常用函式 5.1 函式的定義 第5講單元作業 第5講單元測試 作業講解 第2講單元作業講解 第4講單元作業講解 第3講單元作業講解 第7講單元作業講解 第5講單元作業講解 第1講單元作業講解

第6講單元作業講解 第8講單元作業講解 第6講 偏序關係 擴展內容——信息流的安滲棵灶全格模型 擴展內容——Chomp遊戲 6.1 偏序關係和偏序集 6.2 偏序集中的特殊元素 6.3 格 第6講單元測試 第6講單元作業 第7講 圖論 7.1 圖的基本概念 7.3 哈密爾頓圖 7.6 圖的著色 7.2 歐拉圖 擴展內容——中國郵路問題 擴展內容——抱子甘藍遊戲（Brussels sprouts） 7.4 平面圖 擴展內容——頓時錯亂遊戲 7.5 頂點支配、獨立與覆蓋 擴展內容——抽芽遊戲(Sprouts) 第7講單元測試 第7講單元作業 第8講 樹及其套用 8.4 根樹 8.6 最優二叉樹與霍夫曼編碼 第8講單元作業 第8講單元測試 8.3 最短道路樹 8.5 二叉樹的遍歷 8.1 無向樹 8.2 支撐樹及其套用 可自學章節——有限語言與自動機 正則文法和有限狀態自動機 巴科斯-諾爾範式和語法圖 有限狀態自動機 正則表達式 擴展內容——林登麥伊爾系統 形式語言 字母表與串 文法 文法的分類 非確定性有限狀態自動機 可自學章節——代數結構 代數結構 擴展內容——麻花辮 擴展內容——魔方 群 環與域 擴展內容——伯恩賽德引理與波利亞定理 專題 漢諾塔專題 正多面體 格路問題專題 裴蜀等式專題 “德·布魯因”專題 格雷碼專題 鴿巢原理的紙牌魔術 謝爾賓斯基三角形

（註：課程大綱排版從左到右列）

第3~7次開課大綱

01基礎知識 課時 1.1 集合與序列 1.2 數論基礎 1.3 計數基礎 1.4 布爾矩陣及其運算 02命題邏輯 課時 2.1 命題邏輯的基本概念 2.2 命題公式及其分類 2.3 命題邏輯的等值演算 2.4 範式 2.5 命題邏輯的推理 擴展內容——對偶 擴展內容——邏輯聯接詞的完備集 擴展內容——說謊人與妖魔戒指 擴展內容——新裙子的顏色 擴展內容——早餐吃的什麼 擴展內容——從一個競賽題目說起 03謂詞邏輯 課時 3.1 謂詞與量詞 3.2 謂詞公式及分類 3.3 自然語句形式化 3.4 謂詞邏輯的等值演算 3.5 前束範式 3.6 謂詞邏輯的推理 擴展內容——Prolog語言 04二元關係 課時 4.1 關係及其表示 4.2 關係的運算 4.3 關係的性質 4.4 關係的閉包 4.5 等價關係和集合的劃分 擴展內容——過河問題 05函式 課時 5.1 函式的定義 5.2 函式的性質 5.3 函式的複合 5.4 逆函式 5.5 計算機科學中的常用函式 擴展內容——置換 擴展內容——集合的勢 06偏序關係 課時 6.1 偏序關係和偏序集 6.2 偏序集中的特殊元素 6.3 格 擴展內容——信息流的安全格模型 擴展內容——Chomp遊戲 07圖論 課時 7.1 圖的基本概念 7.2 歐拉圖 7.3 哈密爾頓圖

7.4 平面圖 7.5 頂點支配、獨立與覆蓋 7.6 圖的著色 擴展內容——頓時錯亂遊戲 擴展內容——中國郵路問題 擴展內容——抽芽遊戲(Sprouts) 擴展內容——抱子甘藍遊戲（Brussels sprouts） 08無向樹 課時 8.1 無向樹 8.2 支撐樹及其套用 8.3 最短道路樹 8.4 根樹 8.5 二叉樹的遍歷 8.6 最優二叉樹與霍夫曼編碼 09專題 課時 格雷碼專題 漢諾塔專題 裴蜀等式專題 正多面體“德·布魯因”專題 謝爾賓斯基三角形格路問題 專題鴿巢原理的紙牌魔術 10可自學章節——代數結構 課時 代數結構群環與域 擴展內容——伯恩賽德引理與波利亞定理 擴展內容——麻花辮 擴展內容——魔方 11可自學章節——圖論進階 課時 匹配 流網路 12可自學章節——有限語言與自動機 課時 字母表與串 形式語言 文法 文法的分類 巴科斯-諾爾範式和語法圖 有限狀態自動機 非確定性有限狀態自動機 正則文法和有限狀態自動機 正則表達式 擴展內容——林登麥伊爾系統 13作業及考試主觀題講解 課時 第1講單元作業講解 第2講單元作業講解 第3講單元作業講解 第4講單元作業講解 第5講單元作業講解 第6講單元作業講解 第7講單元作業講解 第8講單元作業講解 考試主觀題講解

（註：課程大綱排版從左到右列）

課前預備

預備知識

學習離散數學課程需預備高中階段知識儲備。

學習資料

《離散數學及套用（第2版）》，劉鐸主編，清華大學出版社出版，ISBN：9787302496632。

所獲榮譽

2020年，該課程被中華人民共和國教育部認定為首批首批國家級一流本科課程。

教師簡介

該課程授課教師為北京交通大學教師團隊，其中劉鐸、趙宏、陳旭東三位教師為副教授，張順利為講師。