离散数学

这是关于清华大学出版社的，离散数学基础及实验教程（第三版），第一章准备知识的思维导图。

离散数学

• 准备知识
  • 集合
    • 集合的基本概念
      • 幂集：集合A的所有子集构成的集合；记为：P（）
      • 表示方法：枚举法，表示法
    • 集合的基本运算和性质
      • 交运算、并运算
      • 差运算、对称差运算
        • 差运算：A-B={x|(x属于a)并且（x不属于b）},也称：B相对于A的补集 对称差：两个集合的并集去掉两个集合相交的部分。
    • 集合的笛卡儿集
      • 有序对（序偶）：<x,y>
      • 无序对：（x,y）
      • 不满足交换率和结和率
    • 集合的计算机表示
      • 二进制位串
  • 整数
    • 整除
      • b=ac,a整除b，a|b
      • 素数是构成正整数的跟本
        • 每一个大于1的整数，可以被分解为n个素数相乘。
    • 最大公约数和最小公倍数
      • d是a，b的最小公倍数，记为d=lcm(a,b)
      • d是a,b的最大公约数，记为d=gcd(a,b)
      • 互素：gcd(a,b)=1
      • gcd(a,b)*lcm(a,b)=a*b
      • 欧几里得算法：辗转相除
        • int gcd(int a,int b){ int x,y,r; x=min(a,b); y=max(a,b); while(x!=0){ r=y mod x; y=x; x=r; } return y; } 这是一个伪码描述
    • 模运算
      • a mod m表示a 被m除的余数
  • 序列和递推
    • 序列
      • 按某种顺序排的一张表
      • 元素为有限个，（有限序列）；元素为无限个（无限序列），序列元素可重复
    • 序列求和
      • 常用求和公式
        • 
    • 递推关系
      • Fbonacci
      • Hanoi
  • 矩阵
    • 矩阵的概念
      • 如果一个矩阵除对角线外的每个元素都为零，则称改矩阵为对角矩阵
      • 两个m*n矩阵被称为相等，当且仅当所有对应元素相等
    • 矩阵的运算
      • 大小相同的两个矩阵的和是将它们对应位置上的元素相加得到的，大小不同的两个矩阵则不能相加。
      • 一个矩阵如果所有的元素都是零，则称为零矩阵。
      • 如果A、B都是m*n的矩阵，则有：A+B=B+A;(A+B)+C=A+(B+C);A+0=0+A=A
      • 矩阵相乘：两个矩阵大小相等或第一个矩阵的列数等于第二个矩阵的行数。否则不能相乘。
        • 求矩阵和的乘积。  用伪码表示矩阵乘法： void mult(int a[],int b[],int c[]){ //以二维数组存储矩阵元素，c为a和b的乘积 for(i=1;i<=m;++i) for(j=1;j<=n;j++){ c[i,j]=0; for(k=1;k<=p;++k) c[i,j]+=a[i,k]*b[k,j]; } }
      • 如果AB和C都是n*n的矩阵，则：A*(B*C)=(A*B)*C;A*(B+C)=A*C+A*B;(A+B)*C=A*C+B*C
      • 转置矩阵
        • 如果A和B是矩阵，则 （1） (2) (3)
      • 对称矩阵：一个矩阵的转置矩阵等于自己。
    • 布尔矩阵
      • 所有元素都为0或者1
      • 布尔矩阵的交和并运算
      • 布尔积运算（与一般矩阵求积类似）
        • 用伪码表示布尔矩阵乘法： void mult_Boolran(int a[],int b[],int c[]){ for(i=1;i<=m;i++) for(j=1;j<=n;j++){ c[i,j]=0; for(k=1;k<=p;++k){ c[i,j]v=a[i,j]b[k,j] } } }