离散数学教学课件

离散数学教学课件第一章离散数学简介12离散数学定义与重要性计算机科学中的应用场景离散数学是研究离散结构的数学分支，离散数学在计算机科学中无处不在与连续数学形成鲜明对比离散对象算法分析依赖于组合数学和图论；数可以被单独计数，如整数、图形和命据库系统基于集合论和关系理论；计题等它是计算机科学的理论基础，算机网络利用图论模型；密码学基于为算法设计、编程语言、人工智能等数论和抽象代数；人工智能应用逻辑提供数学工具推理和概率论等3课程结构与学习目标离散数学的历史与发展世纪数学与计算机的交汇关键人物库尔特哥德尔、艾20·伦图灵·离散数学的发展历程与计算机科学的诞生密不可分世纪初，数学家们开始关注可计算性20库尔特哥德尔（）通过其不完·1906-1978问题，数理逻辑研究取得重大突破年1930备性定理对数理逻辑做出了革命性贡献，证明代，随着计算理论的发展，离散数学从传统数了任何包含基本算术的形式系统都存在不可证学中逐渐分化出来，形成独立学科二战期间，明的真命题，这一发现深刻影响了计算机科学密码学的需求进一步促进了离散数学的发展的理论基础艾伦图灵（）提出了图灵机模·1912-195420世纪中期，随着电子计算机的发明，离散数型，奠定了计算理论的基础，并通过不可解问学与计算机科学的联系日益紧密图论、组合题的研究确立了计算机科学的理论界限他的数学、形式语言理论等分支迅速发展，为计算工作直接促成了现代计算机的诞生，也使离散机科学提供了理论基础到20世纪末，随着互数学在计算机科学中的应用变得更加系统化联网和信息技术的普及，离散数学已成为计算离散数学在现代科技中的角色机科学不可或缺的理论支柱第二章逻辑基础逻辑运算符及其真值表基本逻辑运算符包括否定将命题的真值取反•¬p合取∧当且仅当和都为真时结果为真•p q p q析取∨当且仅当和至少一个为真时结•p q p q果为真命题逻辑与谓词逻辑简介蕴含当且仅当为真且为假时结果为假•p→qp q命题逻辑研究简单陈述句的真假关系，是最基本的形双条件当且仅当和真值相同时结果为真p↔qp q式逻辑系统命题是一个陈述句，具有确定的真值（真或假）逻辑等价与推理规则谓词逻辑是命题逻辑的扩展，引入量词和谓词，能够表达更复杂的逻辑关系，如对所有（全称量词∀）逻辑等价指两个逻辑表达式在所有可能的真值赋值下x和存在（存在量词∃）都具有相同的真值x重要的等价关系包括德摩根律∧∨和∨•¬p q≡¬p¬q¬p q≡∧¬p¬q分配律∧∨∧∨∧和•p qr≡p qp r∨∧∨∧∨p qr≡p qp r逻辑推理的典型例题经典谬误分析肯定后件与否定前件证明方法直接证明、反证法、归纳法肯定后件谬误从和推出，这是无效的直接证明从已知条件出发，通过一系列逻辑推理直接得出结论p→q qp例如如果下雨，地面湿地面湿因此下雨（错误推理，地面湿可能有其他原因）反证法假设结论的否定为真，推导出矛盾，从而证明原结论为真否定前件谬误从和推出，这也是无效的归纳法先证明基本情况成立，再证明若第种情况成立则第种情况也成立，从而证明所有情p→q¬p¬q k k+1况都成立例如如果下雨，地面湿没有下雨因此地面不湿（错误推理，可能有其他原因导致地面湿）例题演示证明若且，则p qp直接证明法真值表证明法假设前提且为真构造命题∧的真值表

1.p qp q→p根据合取的定义，为真且为真

2.p q∧∧因此为真p qp qpq→p

3.p所以若且，则成立

4.pqpT TT TTF F TF TFTF FFT逻辑表达式的简化技巧卡诺图（）介逻辑表达式最简化实例Karnaugh Map绍例如，对于函数，fA,B,C=Σm0,1,2,5,7我们可以卡诺图是一种图形化方法，用于简化布尔代数表达式它将真值表以特殊排列呈现，使相邻单元在卡诺图上标记对应的最小项（

1.0,1,2,5,7格只有一个变量的值不同，便于识别逻辑表达式位置标）1中的冗余项圈出最大的相邻组组合得到

2.1{0,1}¬A·¬B卡诺图的主要特点圈出得到

3.{2}¬A·B·¬C二维或多维网格表示，每个单元格对应一个圈出组合得到•

4.{5,7}A·C最小项得到最简表达式

5.fA,B,C=¬A·¬B+相邻单元格的变量值只差一位•¬A·B·¬C+A·C通过在图上圈出（或）的相邻组来识别•10应用数字电路设计基础最简表达式组必须包含的幂次个单元格（等）卡诺图在数字电路设计中的应用•21,2,4,8目标是用最少的组覆盖所有的（或）•10减少逻辑门的数量，降低电路复杂度•优化电路性能，减少延迟•节约电路设计成本和空间•第三章集合论基础集合的定义与表示方法集合是具有某种特定性质的对象的全体，是离散数学中最基本的概念之一每个集合由不同的元素组成，元素的顺序无关紧要，且不存在重复元素集合的表示方法列举法直接列出所有元素，如•A={1,2,3,4}描述法给出元素的特性，如是小于的正整数•B={x|x10}文氏图使用图形直观表示集合关系•子集、幂集与笛卡尔积子集如果集合的每个元素都是集合的元素，则是的子集，记为⊆A B A B A B幂集集合的所有子集构成的集合，记为例如，如果，则∅S PSS={a,b}PS={,{a},{b},{a,b}}笛卡尔积两个集合和的笛卡尔积×是所有有序对的集合，其中∈且∈例如，A B A Ba,b a A bB×{1,2}{a,b}={1,a,1,b,2,a,2,b}集合运算及其性质基本集合运算包括并集∪属于或的所有元素的集合•A B A B交集同时属于和的所有元素的集合•A∩B A B差集属于但不属于的所有元素的集合•A-B A B补集全集中不属于的所有元素的集合•A A集合的应用案例数据库中的集合操作集合论在搜索引擎中的应用关系数据库的核心概念直接源自集合论表可视为记录的集合，而SQL查询语言中的许多操作都对应于集合运算搜索引擎技术大量依赖集合论概念•SELECT语句从集合中选择满足特定条件的元素•倒排索引将文档集合映射到关键词集合•UNION操作对应集合的并集•布尔检索通过AND交集、OR并集、NOT补集等操作组合查询条件•INTERSECT操作对应集合的交集•相关性排序利用集合相似度度量如Jaccard系数计算文档与查询的匹配度•EXCEPT操作对应集合的差集•聚类算法基于文档集合间的相似性进行分组数据库设计中的范式化过程也广泛应用了集合论的概念，如函数依赖集、属性集等搜索结果过滤、个性化推荐等功能也都基于集合操作实现例题计算两个集合的交集与差集已知集合A={1,3,5,7,9,11}，B={3,6,9,12,15}，计算解答

1.A∩B（A与B的交集）

1.A∩B={3,9}（同时属于A和B的元素）

2.A-B（A与B的差集）

2.A-B={1,5,7,11}（属于A但不属于B的元素）

3.B-A（B与A的差集）

3.B-A={6,12,15}（属于B但不属于A的元素）

4.A△B（A与B的对称差）

4.A△B=A-B∪B-A={1,5,7,11,6,12,15}第四章关系与函数关系的定义与表示关系是两个集合之间的对应关系，形式上定义为两个集合笛卡尔积的子集若和是集合，则从到的二元关系是×的子集，记为⊆×A B A B R A BRA B关系的性质关系的重要性质包括自反性∀∈∈•aA,a,a R2对称性如果∈，则∈•a,b Rb,a R传递性如果∈且∈，则∈•a,b Rb,c Ra,c R反对称性如果∈且∈，则•a,b Rb,a Ra=b函数的概念及分类函数是一种特殊的关系，满足对于定义域中的每个元素，都有唯一的值域元素与之对应函数可分为单射函数不同的定义域元素映射到不同的值域元素•满射函数值域中的每个元素都是定义域中某元素的像•关系的实际应用社交网络中的关系模型数据库关系模式简介社交网络可以自然地建模为图结构，其中关系数据库直接基于关系理论用户作为节点，关系作为边表格（关系）是元组（行）的集合••好友关系通常是对称的（如果是的好友，则主键确保每个元组唯一性•A B B•也是的好友）A外键表示表间关系•关注关系通常不对称（关注不意味着关注）•A B BA函数依赖用于数据库范式化•可传递关系如朋友的朋友用于推荐系统•图（实体关系图）用于数据库设计，将现实世界抽E-R-图算法可分析网络结构中心度计算（找出最有影响力象为实体和它们之间的关系，然后转化为关系模式关的用户）、社区发现（用户聚类）、信息传播模拟等系代数为数据操作提供理论基础，包括选择、投影、连接等操作例题判断关系的等价关系性质在整数集上定义关系当且仅当能被整除判断是否为等价关系结论关系满足自反性、对称性和传递性，因此是一个等价关系Z RaRb a-b3R RR解等价关系需同时满足自反性、对称性和传递性分别验证应用意义这个关系实际上把整数分成了三个等价类自反性对任意∈，能被整除，所以成立，具有自反性（被整除的整数）

1.a Za-a=03aRa R•

[0]={...,-3,0,3,6,...}3对称性若，则能被整除，设则也能被整除，（除以余的整数）

2.aRb a-b3a-b=3k b-a=-a-b=-3k3•

[1]={...,-2,1,4,7,...}31所以也成立，具有对称性bRa R（除以余的整数）•

[2]={...,-1,2,5,8,...}32传递性若且，则₁且₂，其中₁₂∈所以

3.aRb bRca-b=3k b-c=3kk,k Za-c=a-₁₂₁₂能被整除，所以成立，具有传递性b+b-c=3k+3k=3k+k3aRc R第五章图论基础图的定义与分类图的表示方法图是由顶点集和边集组成的数学结构，形式化定义为，其中是顶点集，是边集计算机中表示图的主要方法G=V,E V E根据边的特性，图可分为邻接矩阵使用×的矩阵，若顶点和之间有边，则（或权重值），否则为

1.V VA i j A[i][j]=10邻接表对每个顶点维护一个链表，存储与其相邻的所有顶点无向图边没有方向，表示为无序对

2.•u,v边表直接存储所有边的列表有向图边有方向，表示为有序对

3.•关联矩阵×的矩阵，表示顶点与边的关联关系加权图边具有权重值，表示距离、成本等

4.VE•简单图不含自环和重边的图基本术语•多重图允许存在重边的图•路径从一个顶点到另一个顶点经过的边序列•完全图任意两个顶点之间都有边相连•简单路径不含重复顶点的路径•二分图顶点可分为两个独立集，集内顶点不相连•回路环起点和终点相同的路径•/连通图任意两点之间都存在路径的图•连通分量图中的极大连通子图•图论经典问题最短路径问题（算法简介）Dijkstra最短路径问题是寻找图中两点之间权重和最小的路径Dijkstra算法是解决单源最短路径的经典算法

1.初始化将起点距离设为0，其他顶点距离设为无穷大

2.选择每次选择未访问的距离最小的顶点

3.更新更新所选顶点的邻居的最短距离

4.重复直到所有顶点都被访问或找到目标顶点Dijkstra算法适用于所有边权为非负的图，时间复杂度为OV²，使用优先队列可优化到OE+VlogV欧拉路径与哈密顿路径欧拉路径是指遍历图中每条边恰好一次的路径•欧拉回路遍历每条边一次并回到起点•必要条件图是连通的，且所有顶点度数为偶数•历史源于柯尼斯堡七桥问题•应用邮递员问题、电路设计哈密顿路径是指访问图中每个顶点恰好一次的路径•哈密顿回路访问每个顶点一次并回到起点•NP完全问题没有已知的多项式时间算法•应用旅行商问题、电路板钻孔例题判断图的连通性给定一个无向图G，如下所示的邻接表解答•顶点1连接到2,3使用深度优先搜索DFS或广度优先搜索BFS遍历图，记录访问到的顶点•顶点2连接到1,4,5从顶点1开始DFS•顶点3连接到

11.访问顶点1，标记为已访问•顶点4连接到

22.访问相邻顶点2，标记为已访问•顶点5连接到2,

63.访问2的相邻顶点4和5，标记为已访问•顶点6连接到

54.访问5的相邻顶点6，标记为已访问•顶点7连接到

85.返回访问1的另一个相邻顶点3，标记为已访问•顶点8连接到7,9•顶点9连接到8从顶点1出发，只能访问到顶点{1,2,3,4,5,6}，无法到达{7,8,9}请判断该图是否连通，如果不连通，找出其所有连通分量从顶点7开始新的DFS，可以访问到顶点{7,8,9}图论在计算机中的应用网络路由与通信社交网络分析任务调度与资源分配计算机网络本质上是由节点（路由器、交换机、社交媒体平台利用图论进行数据挖掘和用户行操作系统和项目管理中的调度问题常建模为图主机）和连接（网络链路）组成的图结构图为分析论问题论算法在网络中的关键应用影响力分析通过中心度算法（度中心性、任务依赖图使用有向无环图表示••DAG路由算法如使用算法计介数中心性等）识别关键用户任务间的依赖关系•OSPF Dijkstra算最短路径社区发现使用聚类算法发现紧密联系的关键路径方法确定项目中影响总完成时••生成树协议如使用最小生成树算法用户群体间的任务序列•STP避免网络环路信息传播模型预测消息、观点或趋势的资源分配使用二分图匹配算法进行处理••网络流量优化使用最大流算法分配带宽传播路径和速度器分配•网络可靠性分析通过计算图的连通性和推荐系统基于图的协同过滤算法推荐好死锁检测通过寻找资源分配图中的环来•••关键节点友或内容检测系统死锁互联网的路由表更新、网络的拓扑管理都图数据库（如）专为高效存储和查询复P2P Neo4j依赖于高效的图算法杂关系网络而设计第六章组合数学基础计数原理加法与乘法规则组合数学的基本计数原理是解决有多少种可能类问题的基础加法原理若事件有种可能，事件有种可能，且、互斥，则或共有种可能•A mB n A BA Bm+n乘法原理若事件有种可能，对每种可能，事件有种可能，则和按顺序发生共有×种可能•A mB nA Bm n例如一个密码由位数字组成，且每位可以是中的任意数字根据乘法原理，可能的密码总数为40-910×10×10×10=10⁴=10000种排列与组合公式排列考虑顺序的选择方式Permutation从个不同元素中取出个按顺序排列•n kPn,k=n!/n-k!特例个不同元素的全排列•n Pn,n=n!组合不考虑顺序的选择方式Combination从个不同元素中取出个不考虑顺序•n kCn,k=n!/[k!n-k!]组合数性质•Cn,k=Cn,n-k例如从人中选出人委员会，有种可能103C10,3=10!/[3!10-3!]=120二项式定理简介二项式定理是组合数学中的重要公式，用于展开的幂a+bⁿa+bⁿ=∑k=0to nCn,kaⁿ⁻ᵏbᵏ展开式中共有项•n+1•第k+1项为Cn,kaⁿ⁻ᵏbᵏ系数称为二项式系数•Cn,k例如a+b³=a³+3a²b+3ab²+b³组合数学应用实例彩票中奖概率计算密码学中的组合问题以中国双色球为例，其规则为从个红球中选择个，从个蓝球中密码学安全性分析依赖组合数学33616选择个计算中奖概率1密码强度分析位密码，包含大小写字母和数字，可能组合数为•8一等奖（6红+1蓝全中）概率26+26+10⁸≈

2.18×10¹⁴生日攻击问题在人群体中，至少两人同一天生日的概率达到וnP=1/[C33,6C16,1]只需人，这源于组合学中的生日悖论50%23×=1/[1,107,56816]•密钥空间分析64位密钥的可能组合为2⁶⁴≈

1.8×10¹⁹=1/17,721,088现代加密算法如、的安全性评估都需要组合数学的深入分析随AES RSA着量子计算的发展，密码学正面临新的组合挑战约为千万分之，极其微小

0.56二等奖（红全中，蓝球不中）概率6×P=15/161/C33,6=15/17,721,088理解这些概率有助于人们理性看待彩票投注，避免过度投入例题计算从个元素中选取个的组合数n k问题班级有名学生，需要选出名代表参加学校活动计算解答305不考虑角色分配，有多少种不同的选择方式？选个男生的方式选个男生的方式

1.=C30,5-0+1如果名代表需分配为名队长和名队员，有多少种不同的选择方式？

2.514×=C30,5-[C18,5+C12,1C18,4]如果名学生中有名女生和名男生，要求选出的名代表中

3.3018125×包含至少名男生，有多少种选择方式？=142,506-[8,568+123,060]2=142,506-[8,568+36,720]种选择方式=142,506-45,288=97,218不考虑角色，这是典型的组合问题，答案为

1.C30,5=×种选择方式30!/5!25!=142,506先选出名学生，再从中选人作队长，答案为×

2.51C30,55=×种选择方式142,5065=712,530第七章递归与归纳递归思想问题通过自身简化解决1递归定义基础情况（终止条件）

21.递推关系（自引用）

2.递归算法将问题分解为子问题

1.3解决子问题

2.合并子问题的解

3.数学归纳法证明基础情况（）

1.n=14假设成立

2.n=k证明也成立

3.n=k+1应用领域5算法设计、数学证明、程序设计、数据结构、自动定理证明递归与归纳是解决问题的两种相关方法递归是一种算法设计技术，其中函数调用自身解决问题的较小实例归纳法是一种数学证明技术，用于证明对所有自然数成立的命题递归定义通常包含两部分基础情况（递归终止条件）和递推关系（递归调用）例如，阶乘函数递归定义为当时；×当时n!=1n=0n!=n n-1!n0数学归纳法的基本步骤证明命题对基础情况成立；假设命题对成立；证明在此假设下命题对也成立如果这三步都能完成，则命题对所有自然数都成立12k3k+1递归算法示例斐波那契数列递归实现汉诺塔问题分析斐波那契数列是递归的经典示例，定义为汉诺塔是展示递归威力的经典问题将个不同大小的盘子从柱移动到柱，借助柱，每次只能移nA C B动一个盘子，且大盘不能放在小盘上（基础情况）•F0=0递归解法思路（基础情况）•F1=1•Fn=Fn-1+Fn-2（递推关系），当n

11.将上面n-1个盘子从A移到B（递归）将最大的盘子从移到（基本步骤）递归算法伪代码

2.A C将个盘子从移到（递归）

3.n-1B Cfunctionfibonaccin:if n=0:return0if n=1:return最少移动次数为，这可以通过归纳法证明2ⁿ-11return fibonaccin-1+fibonaccin-2归纳法证明斐波那契数列性质证明对于任意，×n≥0Fn+2Fn-Fn+1²=-1ⁿ

1.基础情况n=0时，F2×F0-F1²=1×0-1²=-1=-1⁰，成立

2.归纳假设假设对于k≥0，Fk+2×Fk-Fk+1²=-1ᵏ成立虽然简洁优雅，但这种实现效率低下，时间复杂度为使用动态规划或迭代方法可以优化到O2ⁿOn第八章布尔代数布尔代数定律主要定律包括布尔代数的基本运算交换律，•x+y=y+x x·y=y·x布尔代数是研究取值为或的变量上的代数系统，基本运结合律，01•x+y+z=x+y+z x·y·z=x·y·z算包括分配律，•x·y+z=x·y+x·z x+y·z=x+y·x+z•与ANDx·y或x∧y，当且仅当x=1且y=1时结果为1•同一律x+0=x，x·1=x•或ORx+y或x∨y，当且仅当x=0且y=0时结果为0•零律和一律x+1=1，x·0=0•非NOTx或¬x，将0变为1，1变为0•补律x+x=1，x·x=0吸收律，•x+x·y=x x·x+y=x德摩根律，•x+y=x·y x·y=x+y逻辑电路设计基础布尔函数与表达式布尔代数是数字电路设计的理论基础基本逻辑门布尔函数是将个布尔变量映射到一个布尔值的函数表示n与门实现布尔乘法•AND方法或门实现布尔加法•OR真值表列出所有可能的输入组合及对应输出•非门实现布尔求补•NOT代数表达式使用与、或、非运算符的表达式•与非门万能门，可构造其他所有逻辑门•NAND最小项之和由与项构成的或表达式•SOP或非门万能门，可构造其他所有逻辑门•NOR最大项之积由或项构成的与表达式•POS布尔代数应用数字电路简化逻辑门电路实例布尔代数最重要的应用之一是简化数字电路，减少所需的考虑一个实际电路设计一个位二进制数比较器，输出三2逻辑门数量种状态、、AB A=BA代数方法使用布尔代数定律进行表达式变换输入为₁₀和₁₀（两个位二进制数）

1.A A BB2卡诺图方法通过图形化方式识别相邻最小项

2.分析比较条件算法适用于变量较多的情况

3.Quine–McCluskey₁₁或₁₁且₀₀•AB A BA=BA B简化示例₁₁且₀₀•A=BA=BA=B原表达式fx,y,z=xy+xz+xyz•A简化过程将这些条件转换为布尔表达式₁₁等价于₁₁•f=xy+xz+xyz•A BA B（应用₁₁等价于₁₁₁₁或₁⊕₁•=xy+xz+xyz xyz=xyz·1=xyzz+z•A=BA B+A BAB）=xyzz+xyzz=0+xyz=xyz₀₀等价于₀₀•ABAB（应用分配律）•=xy1+z+xz最终实现需要与门、或门、非门和异或门的组合（应用）•=xy+xz1+z=1例题设计简单的加法器电路简化后的电路只需个与门和个或门，比原电路少个与211门设计一个位二进制全加器，输入、和进位输入，1AB Cin输出和和进位输出S Cout逻辑表达式⊕⊕•S=ABCin第九章代数结构简介半群Semigroup半群是代数结构中最基本的类型之一，由一个集合S和一个满足结合律的二元运算•组成形式定义半群S,•满足1•封闭性∀a,b∈S，a•b∈S•结合律∀a,b,c∈S，a•b•c=a•b•c例如N,+和N,×都是半群，其中N是自然数集群Group群是在半群基础上增加了单位元和逆元的代数结构形式定义群G,•是满足以下条件的半群2•存在单位元e∈G，使得∀a∈G，a•e=e•a=a•对每个元素a∈G，存在逆元a⁻¹∈G，使得a•a⁻¹=a⁻¹•a=e如果还满足交换律a•b=b•a，则称为阿贝尔群交换群例如Z,+是阿贝尔群，单位元是0，每个整数n的逆元是-n环Ring环是具有两种运算的代数结构，一种运算构成阿贝尔群，另一种构成半群，并且两种运算之间满足分配律形式定义环R,+,×满足3•R,+是阿贝尔群•R,×是半群•分配律∀a,b,c∈R，a×b+c=a×b+a×c和a+b×c=a×c+b×c例如整数集Z构成环Z,+,×域Field域是环的一种特殊情况，除了满足环的所有性质外，乘法也构成一个群除去0元素形式定义域F,+,×满足4•F,+是阿贝尔群，单位元为0•F-{0},×是阿贝尔群，单位元为1•乘法对加法满足分配律例如有理数集Q、实数集R和复数集C都构成域代数结构在密码学中的应用现代密码学广泛应用代数结构，特别是有限域理论例题群的性质验证第十章算法复杂度基础O1Olog n On On log n常数时间对数时间线性时间线性对数时间无论输入规模如何，算法执行时间保持不变例如随着输入规模增长，执行时间以对数方式增加例执行时间与输入规模成正比例如线性搜索、遍比线性稍差但比平方好的复杂度例如归并排序、数组索引访问、哈希表查找（平均情况）如二分查找、平衡二叉树操作历数组或链表快速排序（平均情况）、堆排序On²O2ⁿ平方时间指数时间执行时间与输入规模的平方成正比例如冒泡排执行时间随输入规模呈指数增长例如旅行商问序、插入排序、简单的嵌套循环题的暴力解法、递归斐波那契计算时间复杂度与空间复杂度概念离散数学在算法分析中的作用算法复杂度是评估算法效率的重要指标离散数学为算法分析提供了理论基础时间复杂度衡量算法执行所需的计算步骤数量，通常用大符号表示增长率的上界组合数学计算问题的可能解数量•O•空间复杂度衡量算法执行所需的额外存储空间，同样用大符号表示递归方程分析分治算法的复杂度•O•图论分析图算法的时间和空间复杂度复杂度分析基于渐近分析，关注输入规模很大时的表现，忽略常数因子和低阶项•概率论分析随机算法的期望性能•数论分析模运算和加密算法•算法复杂度实例分析100%50%线性搜索二分搜索时间复杂度时间复杂度On Olog n空间复杂度空间复杂度（迭代实现）或（递归实现）O1O1Olog n最坏情况目标元素在末尾或不存在，需检查所有个元素每次比较后，搜索范围减半n平均情况期望检查个元素仅适用于已排序数据n/2排序算法复杂度简介算法最坏时间复杂度平均时间复杂度最好时间复杂度空间复杂度稳定性冒泡排序稳定On²On²On O1选择排序不稳定On²On²On²O1插入排序稳定On²On²On O1归并排序稳定On log n On log n On logn On快速排序不稳定On²On logn OnlognOlog n堆排序不稳定OnlognOnlognOnlognO1例题计算算法的渐进复杂度分析以下算法的时间复杂度解析最外层循环执行次

1.nfunction mysteryn:sum=0for i=1to n:for j=1to i*i:if j%i==0:中间循环对每个执行次

2.i i²for k=1to j:sum=sum+1return sum最内层循环对每个执行次

3.j j但只有当是的倍数时才执行最内层循环

4.j i对于每个，是的倍数的情况有，共个数i ji i,2i,3i,...,i·i i对于这个值，最内层循环分别执行次iji,2i,3i,...,i·i总执行次数为i+2i+3i+...+i·i=i·1+2+...+i=i·ii+1/2=Oi³第十一章概率论基础12概率的定义与性质条件概率与独立事件概率是对随机事件发生可能性的度量在离散数学中，我们主条件概率表示在事件已经发生的条件下，事件发生PA|BBA要关注离散概率模型的概率样本空间所有可能结果的集合，其中•S PA|B=PA∩B/PB PB0•事件E样本空间的子集两个事件A和B是独立的，当且仅当概率函数将事件映射到区间的实数•P[0,1]×PA∩B=PA PB概率的基本性质或等价地，且PA|B=PA PB|A=PB非负性对任意事件，•E PE≥0贝叶斯定理是条件概率的重要推论规范性整个样本空间的概率•PS=1×PA|B=PB|A PA/PB可加性对于互不相容的事件和，∪•ABPA B=PA+PB3离散随机变量简介随机变量是将样本空间中的结果映射到实数的函数离散随机变量只取有限或可数无限多个值描述离散随机变量的主要方式概率质量函数•PMF px=PX=x累积分布函数•CDF Fx=PX≤x随机变量的数字特征期望值•EX=∑x·px方差•VarX=E[X-EX²]=EX²-[EX]²概率论在计算机科学中的应用随机算法机器学习中的概率模型随机算法在执行过程中使用随机数，具有以下特点概率是许多机器学习算法的理论基础•蒙特卡洛算法可能给出错误结果，但概率很小（如随机素性测试）•贝叶斯网络表示变量间概率依赖关系的图模型第十二章离散数学综合应用组合优化简介组合优化是寻找离散结构中的最优解，如最短路径、最小生成树等常见问题旅行商问题•TSP背包问题•图着色问题图分割问题•图着色问题是为图的顶点分配颜色，使相邻顶点颜色不同，且使用最少的最大流最小割问题•/颜色数求解方法包括精确算法（动态规划、分支限界）和近似算法（贪心、局部搜应用领域索、遗传算法）地图着色（四色定理）•调度问题（时间表安排）•离散数学在人工智能中的应用频率分配（移动通信）•离散数学为人工智能提供了理论基础和算法工具寄存器分配（编译器优化）•逻辑推理与知识表示•图搜索算法（、启发式搜索）•A*概率图模型（贝叶斯网络）•组合优化在机器学习中的应用•博弈论与多智能体系统•图着色算法详解人工智能中的离散优化图着色是完全问题，但有实用的近似算法机器学习和人工智能中的许多问题可转化为离散优化问题NP贪心着色算法按某种顺序处理顶点，为每个顶点分配可用的最小颜色编号特征选择从大量特征中选取最有信息量的子集

1.•算法按度数降序处理顶点，同时为所有可能的顶点分配相同颜色神经网络结构搜索确定最优的网络拓扑结构

2.Welsh-Powell•回溯着色算法系统地尝试所有可能的着色方案，找到最优解强化学习中的策略优化在离散动作空间中寻找最优策略

3.•算法优先处理已着色邻居数最多的顶点集成学习中的模型选择从多个基础模型中选择最佳组合

4.DSatur•这些算法在复杂网络分析、资源调度、编译器设计等领域有广泛应用典型综合案例分析网络安全中的密码学应用数据结构设计中的数学基础现代密码学建立在离散数学的多个分支之上高效数据结构的设计直接基于离散数学原理数论加密基于大数因式分解的难度，利用欧拉定理和模图论图数据结构（邻接表矩阵）、最短路径算法•RSA•/运算树二叉搜索树、树、红黑树的平衡性分析•AVL抽象代数椭圆曲线密码系统基于有限域上的代数结构•ECC散列函数基于数论和概率论设计低碰撞哈希表•组合数学密钥空间分析、碰撞概率计算•概率数据结构布隆过滤器、跳表、等•Count-Min Sketch信息论衡量加密算法的安全性和熵•分析数据结构操作的时间复杂度和空间效率离不开递归方程、组合计实际应用如协议、区块链的数字签名、安全多方计算等都数、概率分析等数学工具大数据时代的分布式数据结构设计也依赖TLS/SSL深度依赖离散数学量子密码学也在探索基于量子力学和离散数学结一致性哈希等离散数学概念合的新型安全协议例题图的着色算法演示考虑下面的无向图开始着色G

1.为分配颜色顶点集•C1•V={A,B,C,D,E,F}与相邻，不能用颜色，分配颜色边集•AC12•E={A,B,A,C,A,D,B,C,B,E,C,D,C,E,C,F,D,F,E,F}与相邻，不能用颜色，但可以用颜色（因为与不相邻）•F C12A F使用算法为着色Welsh-Powell G与、相邻，不能用颜色、，分配颜色•BCA123计算每个顶点的度数

1.与、、相邻，不能用颜色、，分配颜色•D CA F123顶点度数•C5与、相邻，不能用颜色、，分配颜色•E CB132•顶点A、F度数

32.最终着色结果顶点、、度数•B DE3颜色顶点•1C按度数降序排列顶点（相同度数可任意排序）

2.C,A,F,B,D,E颜色顶点、、•2A FE颜色顶点、•3B D课程复习与总结重点知识点回顾常见考试题型解析逻辑基础命题逻辑、谓词逻辑、证明方法概念题解释离散数学中的基本概念和定义•

1.集合论集合运算、关系、函数证明题使用各种证明方法证明数学命题•

2.图论图的表示与算法、连通性、路径问题计算题集合运算、组合计数、概率计算等•

3.组合数学计数原理、排列组合、递归与归纳应用题将抽象概念应用到具体问题中•

4.布尔代数逻辑运算、卡诺图、数字电路算法题设计和分析算法，计算复杂度•

5.代数结构群、环、域的基本概念设计题设计逻辑电路、状态机等•

6.算法分析时间复杂度、空间复杂度•考试重点通常集中在理解基本概念、掌握核心算法、概率基础随机事件、条件概率、离散分布灵活应用数学工具解决实际问题•学习建议与资源推荐有效学习离散数学的建议建立系统性理解，注重各章节之间的联系•多做习题，培养抽象思维和问题解决能力•结合编程实践，实现相关算法和数据结构•参与讨论，与同学交流解题思路•关注应用场景，理解离散数学在计算机科学中的作用•课后练习与项目设计一个简单的逻辑电路编写递归算法解决实际问题项目目标设计一个位二进制加法器电路项目目标实现汉诺塔问题的递归解法2要求要求使用基本逻辑门（与门、或门、非门）设计编写递归函数求解盘汉诺塔问题

1.

1.n画出电路图和真值表输出每一步的移动过程

2.

2.使用布尔代数简化电路分析算法的时间复杂度和空间复杂度

3.

3.分析电路的延迟和门数证明移动次数的公式

4.

4.2ⁿ-1提示先设计一位全加器，然后级联两个全加器全加器进阶任务编写带状态可视化的汉诺塔模拟程序，或实现有三个输入（、和进位输入）和两个输出（和和其他经典递归问题如八皇后问题ABCin S进位输出）Cout可使用逻辑电路模拟软件如进行验证Logisim图论相关编程练习项目目标实现图的基本算法并应用到实际问题要求实现图的数据结构（邻接矩阵或邻接表）

1.实现和遍历算法

2.DFS BFS实现最短路径算法

3.Dijkstra应用分析社交网络数据，计算两用户间的最短路径

4.数据集建议使用公开的社交网络数据集（如）Stanford LargeNetwork DatasetCollection参考教材与学习资源经典教材推荐实用学习工具《离散数学及其应用》，著，机强大的数学计算工具，可验证集•Kenneth H.Rosen•Wolfram Alpha械工业出版社译本合运算、逻辑表达式等《离散数学》，屈婉玲，耿素云，张立昂著，高等教在线图论可视化工具，可绘制和分••Graph Online育出版社析图结构《计算机科学中的数学》，，交互式逻辑电路设计工具•Eric LehmanF.•Logic.ly著，人民邮电出版社译本Thomson Leighton形式语言和自动机理论学习工具•JFLAP《组合数学》，著，高等教育出•Richard A.Brualdi概率分布交•Probability DistributionsExplorer版社译本互式探索工具《图论导引》，著，机械工业出版•Douglas B.West开源资源社译本GitHub在线课程资源包含详细教程•Discrete-Mathematics-Tutorials和代码示例同济大学《离散数学》课程，中国大学•MOOC MOOC精选数学资源列表，包含离散数•Awesome-Math平台学部分南方科技大学《离散数学》，学堂在线•算法可视化工具，包含图论•Algorithm-Visualizer的《算法•MIT OpenCourseWareMathematics for》Computer Science大量习题及解答•Discrete-Mathematics-Exercises平台上的《》系列•Coursera DiscreteMathematics实用•Competitive-Programming-Algorithms课程算法实现，基于离散数学概念站视频教程《北京大学离散数学公开课》•B致谢与互动环节欢迎提问与讨论离散数学涵盖内容广泛，抽象概念较多，学习过程中遇到困惑是正常的欢迎随时提问，可以通过以下方式与教师和同学交流课堂讨论时间每周五下午点•3-5线上答疑平台课程微信群和讨论板•预约一对一辅导发邮件至教师邮箱安排时间•对难点问题会在后续课程或补充材料中进一步解释课程反馈与改进建议为持续提升教学质量，诚邀各位参与课程反馈课程内容难度是否适中，知识点是否清晰•教学方式讲解方式是否有效，课堂活动是否有帮助•课程资料教材和补充材料是否充分•评估方式作业和考试是否合理反映学习成果•可通过学期末评教系统或随时发送匿名反馈邮件提供建议期待大家在离散数学的世界中探索无限可能！离散数学不仅是计算机科学的基础，也是培养逻辑思维和问题解决能力的重要工具希望通过本课程，大家能够建立扎实的数学基础，为专业课程学习打下基础•培养抽象思维能力，提高解决复杂问题的能力•发现数学之美，享受思考和解决问题的乐趣•将所学知识应用到实际问题中，创造价值•祝愿每位同学在离散数学的学习旅程中收获知识与成长！本课程是一个起点，而非终点离散数学的知识将伴随你们的整个计算机科学学习和职业生涯希望大家保持好奇心和探索精神，在未来的学习和工作中继续深化对离散数学的理解和应用。