離散數(shù)學概述

《離散數(shù)學概述》由會員分享，可在線閱讀，更多相關《離散數(shù)學概述（24頁珍藏版）》請在裝配圖網上搜索。

1、離 散 數(shù) 學 概 述離 散 數(shù) 學 課 程 名 稱q離 散 數(shù) 學 Discrete Mathematicsq離 散 數(shù) 學 結 構 Discrete Mathematical Structures 課 程 簡 介q離 散 數(shù) 學 ， 是 現(xiàn) 代 數(shù) 學 的 一 個 重 要 分 支 ， 計 算 機 科 學 與技 術 一 級 學 科 的 核 心 課 程 ， 是 整 個 計 算 機 學 科 的 專 業(yè) 基礎 課 。q離 散 數(shù) 學 是 以 研 究 離 散 量 的 結 構 和 相 互 間 的 關 系 為 主 要目 標 ， 其 研 究 對 象 一 般 地 是 有 限 個 或 可 數(shù) 個 元 素 ，

2、因 此它 充 分 描 述 了 計 算 機 科 學 離 散 性 的 特 點 。q離 散 數(shù) 學 是 隨 著 計 算 機 科 學 的 發(fā) 展 而 逐 步 建 立 的 ， 它 形成 于 七 十 年 代 初 期 ， 是 一 門 新 興 的 工 具 性 學 科 。 后 續(xù) 課 程數(shù) 據(jù) 結 構 操 作 系 統(tǒng)編 譯 理 論 算 法 分 析系 統(tǒng) 結 構 容 錯 判 斷機 器 定 理 證 明 數(shù) 據(jù) 庫 原 理人 工 智 能 離 散 數(shù) 學 的 發(fā) 展q18世 紀 以 前 , 數(shù) 學 基 本 上 是 研 究 離 散 對 象 的 數(shù) 量 和 空 間 關 系的 科 學 。q之 后 ,因 天 文 學 ,物 理

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

4、總 是 有 限 的 , 它 代 表 離 散 的 數(shù) 或其 它 離 散 對 象 ， 因 此 隨 著 計 算 機 科 學 和 技 術 的 迅 猛 發(fā) 展 ,離 散 數(shù) 學 就 顯 得 重 要 。 離 散 數(shù) 學 的 內 容q數(shù) 理 邏 輯 ： “ 證 明 ” 在 計 算 科 學 的 某 些 領 域 至 關 重 要 ， 構造 一 個 證 明 和 寫 一 個 程 序 的 思 維 過 程 在 本 質 上 是 一 樣 的 。q組 合 分 析 ： 解 決 問 題 的 一 個 重 要 方 面 就 是 計 數(shù) 或 枚 舉 對 象 。q離 散 結 構 ： 用 來 表 示 離 散 對 象 以 及 它 們 之 間 關

5、 系 的 抽 象 數(shù) 學結 構 ， 包 括 ： 集 合 、 排 列 、 關 系 、 樹 、 圖 。q算 法 化 思 維 ： 許 多 問 題 都 可 以 通 過 構 造 一 個 可 以 被 程 序 實 現(xiàn)的 算 法 來 解 決 。 它 的 三 個 步 驟 是 ： 構 造 （ 選 擇 合 適 的 離 散 模型 和 操 作 步 驟 ） 、 驗 證 （ 算 法 的 正 確 性 ） 、 評 估 （ 時 間 和 空間 的 復 雜 性 ） 。q應 用 和 建 模 ： 在 可 以 想 到 的 任 何 研 究 領 域 都 有 離 散 數(shù) 學 的 應用 。 計 算 科 學 、 化 學 、 植 物 學 、 動 物

6、學 、 語 言 學 、 地 理 、 經 濟 學 等 ， 構 造 離 散 模 型 都 是 極 其 有 用 的 解 決 問 題 的 方 法 。 教 學 內 容 集 合 論數(shù) 理 邏 輯 圖 論代 數(shù) 結 構 為 什 么 要 學 離 散 數(shù) 學 q計 算 機 求 解 的 基 本 模 式 是 ：實 際 問 題 數(shù) 學 建 模 算 法 設 計 編 程 實 現(xiàn) q離 散 數(shù) 學 為 數(shù) 學 建 模 打 下 知 識 基 礎 、 為 算 法 設 計 提 供 具 體指 導q離 散 數(shù) 學 結 構 實 際 上 就 是 通 用 的 抽 象 的 模 式 的 集 合 。 告 訴你 各 種 模 式 的 本 質 特 征 和

7、 它 們 之 間 的 關 系 ， 以 及 選 用 它 們的 策 略 ； 告 訴 你 哪 些 問 題 是 可 解 的 ， 哪 些 是 當 前 在 圖 靈 機模 型 上 無 （ 最 優(yōu) ） 解 的 ， 哪 些 是 可 以 得 到 近 似 /較 優(yōu) 解 的 。q簡 而 言 之 ， 離 散 數(shù) 學 的 作 用 就 在 于 訓 練 運 用 離 散 結 構 作 為問 題 的 抽 象 模 型 、 構 造 算 法 、 解 決 問 題 的 能 力 。 離 散 數(shù) 學 的 應 用 舉 例q關 系 型 數(shù) 據(jù) 庫 的 設 計 （ 關 系 代 數(shù) ）q表 達 式 解 析 （ 樹 ）q優(yōu) 化 編 譯 器 的 構 造 （

8、 閉 包 ）q編 譯 技 術 、 程 序 設 計 語 言 （ 代 數(shù) 結 構 ）qLisp和 Prolog、 人 工 智 能 、 自 動 推 理 、 機 器 證 明 （ 數(shù) 理 邏 輯 ）q網 絡 路 由 算 法 （ 圖 論 ）q游 戲 中 的 人 工 智 能 算 法 （ 圖 論 、 樹 、 博 弈 論 ）q專 家 系 統(tǒng) （ 集 合 論 、 數(shù) 理 邏 輯 知 識 和 推 理 規(guī) 則 的 計 算 機 表 達 ）q軟 件 工 程 團 隊 開 發(fā) 時 間 和 分 工 的 優(yōu) 化 （ 圖 論 網 絡 、 劃 分 ） q(各 種 )算 法 的 構 造 、 正 確 性 的 證 明 和 效 率 的 評

9、估 （ 離 散 數(shù) 學 的 各分 支 ） 學 習 要 求q本 課 程 特 點定 義 +定 理 +例 題q多 做 習 題 ， 完 成 作 業(yè)想 的 清 楚 ， 說 的 明 白 ， 寫 的 工 整 教 材 q耿 素 云 ， 屈 婉 玲 編 著 離 散 數(shù) 學 (修 訂 版 ) 北 京 ： 高 等教 育 出 版 社 ,2004q耿 素 云 ， 屈 婉 玲 編 著 離 散 數(shù) 學 學 習 指 導 與 習 題 解 析 北 京 ： 高 等 教 育 出 版 社 ,2005qhttp:/ 參 考 教 材q左 孝 凌 ， 李 為 鑒 ， 劉 永 才 編 著 離 散 數(shù) 學 上 海 ： 上 海科 學 技 術 文

10、獻 出 版 社 ,1982q孫 吉 貴 ， 楊 鳳 杰 ， 歐 陽 丹 彤 ， 李 占 山 編 著 離 散 數(shù) 學 高 等 教 育 出 版 社 ， 2002q美 Kenneth H.Rosen著 袁 崇 義 ， 屈 婉 玲 ， 王 捍 貧 ， 劉田 譯 離 散 數(shù) 學 及 其 應 用 北 京 ： 機 械 工 業(yè) 出 版 社 ，2002 數(shù) 理 邏 輯 簡 介q邏 輯 學 是 一 門 研 究 思 維 形 式 及 思 維 規(guī) 律 的 科 學 ， 也 就 是 研 究推 理 過 程 的 規(guī) 律 的 科 學 。 邏 輯 規(guī) 律 就 是 客 觀 事 物 在 人 的 主 觀意 識 中 的 反 映 。 q邏

11、輯 學 分 為 辯 證 邏 輯 與 形 式 邏 輯 兩 種 ， 辯 證 邏 輯 是 以 辯 證 法認 識 論 的 世 界 觀 為 基 礎 的 邏 輯 學 ， 形 式 邏 輯 主 要 是 對 思 維 的形 式 結 構 和 規(guī) 律 進 行 研 究 的 類 似 于 語 法 的 一 門 工 具 性 學 科 。q思 維 的 形 式 結 構 包 括 了 概 念 、 判 斷 和 推 理 之 間 的 結 構 和 聯(lián) 系， 其 中 概 念 是 思 維 的 基 本 單 位 ， 通 過 概 念 對 事 物 是 否 具 有 某種 屬 性 進 行 肯 定 或 否 定 的 回 答 ， 這 就 是 判 斷 ； 由 一 個

12、或 幾 個判 斷 推 出 另 一 判 斷 的 思 維 形 式 ， 就 是 推 理 。q用 數(shù) 學 方 法 來 研 究 推 理 的 規(guī) 律 稱 為 數(shù) 理 邏 輯 。 這 里 所 指 的 數(shù)學 方 法 ， 就 是 引 進 一 套 符 號 體 系 的 方 法 ， 在 其 中 表 達 和 研 究推 理 的 規(guī) 律 。 數(shù) 理 邏 輯 簡 介q通 常 認 為 數(shù) 理 邏 輯 是 由 萊 布 尼 茲 (Leibniz)創(chuàng) 立 的 。 q數(shù) 理 邏 輯 的 內 容 包 括 ：證 明 論 、 模 型 論 、 遞 歸 論 、 公 理 化 集 合 論 。 q數(shù) 理 邏 輯 的 應 用 在 形 式 語 義 學 、

13、 程 序 設 計 方 法 學 和 軟 件 工 程 領 域 。 在 邏 輯 程 序 設 計 方 面 。 在 數(shù) 據(jù) 庫 理 論 方 面 。 在 程 序 自 動 生 成 、 自 動 轉 換 等 的 理 論 和 技 術 研 究 中 。 在 形 式 語 言 理 論 、 自 動 機 理 論 、 可 計 算 理 論 、 計 算 復 雜 性理 論 等 方 面 。 在 人 工 智 能 方 面 。 數(shù) 理 邏 輯 簡 介一 個 土 耳 其 商 人 想 找 一 個 十 分 聰 明 的 助 手 協(xié) 助 他 經 商 ， 有 兩人 前 來 應 聘 ， 這 個 商 人 為 了 試 試 哪 個 更 聰 明 些 ， 就 把

14、兩個 人 帶 進 一 間 漆 黑 的 屋 子 里 ， 他 打 開 燈 后 說 ： “ 這 張 桌子 上 有 五 頂 帽 子 ， 兩 頂 是 紅 色 的 ， 三 頂 是 黑 色 的 ， 現(xiàn) 在， 我 把 燈 關 掉 ， 而 且 把 帽 子 擺 的 位 置 弄 亂 ， 然 后 我 們 三個 人 每 人 摸 一 頂 帽 子 戴 在 自 己 頭 上 ， 在 我 開 燈 后 ， 請 你們 盡 快 說 出 自 己 頭 上 戴 的 帽 子 是 什 么 顏 色 的 。 ” 說 完 后， 商 人 將 電 燈 關 掉 ， 然 后 三 人 都 摸 了 一 頂 帽 子 戴 在 頭 上， 同 時 商 人 將 余 下 的

15、 兩 頂 帽 子 藏 了 起 來 ， 接 著 把 燈 打 開。 這 時 ， 那 兩 個 應 試 者 看 到 商 人 頭 上 戴 的 是 一 頂 紅 帽 子， 其 中 一 個 人 便 喊 道 ： “ 我 戴 的 是 黑 帽 子 。 ” 請 問 這 個 人 說 得 對 嗎 ？ 他 是 怎 么 推 導 出 來 的 呢 ？ 數(shù) 理 邏 輯 簡 介前 提 結 論推 理 （ 規(guī) 則 ） 數(shù) 理 邏 輯 的 知 識 體 系1.1 命 題 與 聯(lián) 結 詞1.2 命 題 公 式 及 其 賦 值2.1 等 值 式2.2 析 取 范 式 與 合 取 范 式 3.1 推 理 的 形 式 結 構3.2 自 然 推 理

16、系 統(tǒng) 4.1 一 階 邏 輯 命 題 符 號 化4.2 一 階 邏 輯 公 式 及 解 釋5.1 一 階 邏 輯 等 值 式 與 置 換 規(guī) 則5.2 一 階 邏 輯 前 束 范 式5.3 一 階 邏 輯 的 推 理 理 論 集 合 論 (set theroy)概 述q20世 紀 數(shù) 學 中 最 為 深 刻 的 活 動 ， 是 關 于 數(shù) 學 基 礎 的 探 討 。這 不 僅 涉 及 到 數(shù) 學 的 本 性 ， 也 涉 及 到 演 繹 數(shù) 學 的 正 確 性 。數(shù) 學 中 若 干 悖 論 的 發(fā) 現(xiàn) ， 引 發(fā) 了 數(shù) 學 史 上 的 第 三 次 危 機 ，這 種 悖 論 在 集 合 論 中

17、 尤 為 突 出 。 q集 合 論 最 初 是 一 門 研 究 數(shù) 學 基 礎 的 學 科 ， 它 從 一 個 比 “ 數(shù)” 更 簡 單 的 概 念 -集 合 出 發(fā) ， 定 義 數(shù) 及 其 運 算 ， 進 而 發(fā)展 到 整 個 數(shù) 學 領 域 ， 在 這 方 面 它 取 得 了 極 大 的 成 功 。q集 合 論 的 起 源 可 以 追 溯 到 19世 紀 末 期 。 1874年 ， 29歲 的 德國 數(shù) 學 家 康 托 爾 (Georg Cantor)在 “ 數(shù) 學 雜 志 ” 發(fā) 表 了 關于 無 窮 集 合 論 的 第 一 篇 革 命 性 文 章 ， 從 1874年 至 1884年 間

18、， Cantor的 系 列 有 關 集 合 的 文 章 ， 奠 定 了 集 合 論 的 基 礎 。 集 合 論 概 述q康 托 爾 開 創(chuàng) 的 集 合 論 被 稱 為 樸 素 集 合 論 ， 因 為 他 沒 有 對集 合 論 作 完 整 的 形 式 的 刻 畫 ， 從 而 導 致 了 理 論 的 不 一 致 (產 生 了 悖 論 )。q在 集 合 論 的 若 干 悖 論 中 ， 最 通 俗 易 懂 的 是 Russell(羅 素 )的 理 發(fā) 師 悖 論 ： 一 個 鄉(xiāng) 村 理 發(fā) 師 ， 自 夸 本 村 無 人 可 與 相比 ， 宣 稱 他 當 然 不 給 自 己 刮 臉 的 人 刮 臉 ，

19、 但 卻 給 本 村 所有 自 己 不 刮 臉 的 人 刮 臉 。 一 天 他 發(fā) 生 了 疑 問 ， 他 是 否 應當 給 自 己 刮 臉 。 集 合 論 概 述q集 合 不 僅 可 以 用 來 表 示 數(shù) 即 其 運 算 ， 更 可 以 用 于 非 數(shù) 值信 息 的 表 示 和 處 理 ， 如 數(shù) 據(jù) 的 增 加 、 刪 除 、 修 改 、 排 序， 以 及 數(shù) 據(jù) 間 關 系 的 描 述 ， 有 些 很 難 用 傳 統(tǒng) 的 數(shù) 值 計 算來 處 理 ， 但 可 以 用 集 合 運 算 來 處 理 。q因 此 ， 集 合 論 在 程 序 語 言 、 數(shù) 據(jù) 結 構 、 編 譯 原 理 、

20、數(shù) 據(jù)庫 與 知 識 庫 、 形 式 語 言 和 人 工 智 能 等 領 域 中 都 得 到 了 廣泛 的 應 用 ， 并 且 還 得 到 了 發(fā) 展 ， 如 Zadeh(扎 德 )的 模 糊 集理 論 和 Pawlak的 粗 糙 集 理 論 。 代 數(shù) 系 統(tǒng)q近 世 代 數(shù) ， ， 是 關 于 運 算 的 學 說 ， 是 關 于 運 算 規(guī) 則的 學 說 ， 但 它 不 把 自 己 局 限 在 研 究 數(shù) 的 運 算 性 質 上 ， 而是 企 圖 研 究 一 般 性 元 素 的 運 算 性 質 。 .Kleinq數(shù) 學 之 所 以 重 要 ， 其 中 心 原 因 在 于 它 所 提 供 的

21、 數(shù) 學 系 統(tǒng)的 豐 富 多 彩 ； 此 外 的 原 因 是 ， 數(shù) 學 給 出 了 一 個 系 統(tǒng) ， 以便 于 使 用 這 些 模 型 對 物 理 現(xiàn) 實 和 技 術 領 域 提 出 問 題 ， 回答 問 題 ， 并 且 也 就 探 索 了 模 型 的 行 為 。 R.C.Buck&E.F.Buckq代 數(shù) 系 統(tǒng) -具 有 運 算 的 集 合 -是 抽 象 代 數(shù) 研 究 的 主 要 對 象 。 代 數(shù) 結 構 的 知 識 體 系半 群 與 群 環(huán) 與 域 格 與 布 爾 代 數(shù)分 類 代 數(shù) 推 廣 成 分 ： 載 體 及 運 算公 理 ： 運 算 性 質代 數(shù) 系 統(tǒng) 的 構 成

22、代 數(shù) 系 統(tǒng) 的同 態(tài) 與 同 構代 數(shù) 系 統(tǒng) 間 的 關 系映 射 子 代 數(shù)積 代 數(shù)商 代 數(shù)等 價 關 系笛 卡 兒 積子 集 新 代 數(shù) 系 統(tǒng) 同種的同類型的產 生 半 群 與 群廣 群 二 元 運 算 的 封 閉 性結 合 律半 群 單 位 元獨 異 點每 個 元 素 可 逆 群 交 換 律 交 換 半 群交 換 律 交 換 獨 異 點交 換 律 Abel群有 限 個 元 素 有 限 群 生 成 元 循 環(huán) 群實 例 n元 置 換 群實 例 Klein群 圖 論q圖 論 是 離 散 數(shù) 學 的 重 要 組 成 部 分 ， 是 近 代 應 用 數(shù) 學 的 重 要 分 支 。q1

23、736年 是 圖 論 歷 史 元 年 ， 因 為 在 這 一 年 瑞 士 數(shù) 學 家 歐 拉 (Euler)發(fā) 表 了 圖 論 的 首 篇 論 文 哥 尼 斯 堡 七 橋 問 題 無 解 ， 所 以 人們 普 遍 認 為 歐 拉 是 圖 論 的 創(chuàng) 始 人 。q1936年 ， 匈 牙 利 數(shù) 學 家 寇 尼 格 （ Konig） 出 版 了 圖 論 的 第 一 部 專著 有 限 圖 與 無 限 圖 理 論 ， 這 是 圖 論 發(fā) 展 史 上 的 重 要 的 里 程 碑， 它 標 志 著 圖 論 將 進 入 突 飛 猛 進 發(fā) 展 的 新 階 段 。q計 算 機 科 學 的 發(fā) 展 為 圖 論

24、的 發(fā) 展 提 供 了 計 算 工 具 。q現(xiàn) 代 科 學 技 術 的 發(fā) 展 需 要 借 助 圖 論 來 描 述 和 解 決 各 類 課 題 中 的 各種 關 系 ， 從 而 推 動 科 學 技 術 不 斷 地 攀 登 新 的 高 峰 。 q作 為 描 述 事 務 之 間 關 系 的 手 段 或 稱 工 具 ， 圖 論 在 許 多 領 域 ， 諸 如， 計 算 機 科 學 、 物 理 學 、 化 學 、 運 籌 學 、 信 息 論 、 控 制 論 、 網 絡 通 訊 、 社 會 科 學 以 及 經 濟 管 理 、 軍 事 、 國 防 、 工 農 業(yè) 生 產 等 方 面都 得 到 廣 泛 的 應 用 ， 也 正 是 因 為 在 眾 多 方 面 的 應 用 中 ， 圖 論 自 身才 得 到 了 非 常 迅 速 的 發(fā) 展 。