数学符号 , 集合 , 命题 , 条件 , 区间 , 数列 , 取模 , 逆元 , 概率 , 期望

Login to join training plan

第1讲：课堂内容

---

第1讲：课件

---

---

数学符号

$\sum$ : 求和 , $\prod$ : 求积 , $\infty$ : 无穷 , $\forall$ : 所有 , $\exists$ : 任意 , $\lim$ : 极限

$\log$ : 对数 , $\exp$ : $2.7\dot{1}82\dot{8}^x$ , $\mid$ : 整除 , $\bmod$ : 取模 , $\equiv$ : 同余

$\lfloor x \rfloor$ : 下取整 , $\lceil x \rceil$ : 上取整 , $[x]$ : 向 $0$ 取整

---

集合

• 把研究对象称为元素，把元素的总体叫做集合。

• 用 $\{\}$ 表示一个集合：

  • 列举法 $\{1,4,2,3,5\}$
  • 描述法 $\{x |\ x > 5\}$

• 集合的大小：$|A|$。

• 性质：确定性，互异性，无序性。

---

命题

• 概念：表达判断语义的句子，如，若 $p$ 则 $q$；存在三边相等的三角形。

• 命题分类

  • 真命题：若 $x>0$，则 $\dfrac 1x > 0$；
  • 假命题：若 $x<0$，则 $2^x < 0$。

• 关系

  • 原命题：相对而言的概念，任何命题都可以是原命题，确定了原名题之后，才有了逆命题等概念。假设原命题为：若 $p$ 则 $q$。
  • 逆命题：若 $q$ 则 $p$。
  • 否命题：若 $!p$ 则 $!q$。
  • 逆否命题：若 $!q$ 则 $!p$。

原命题和逆否命题同真同假，逆命题和否命题同真同假。

---

条件

• 充分条件：若 $A$ 能推出 $B$，则 $A$ 是 $B$ 的充分条件（$A$ 比 $B$ 小）；
• 必要条件：若 $B$ 能推出 $A$，则 $A$ 是 $B$ 的必要条件（$A$ 比 $B$ 大）。
• 充要条件：$A$ 是 $B$ 的充分条件和必要条件，则则 $A$ 是 $B$ 的充要条件（$A$ $B$ 共存亡）。

---

区间

用小括号或中括号括起来的一堆数字 $a,\ b$，要求 $a<b$，表示 $a$ 到 $b$ 这一段的实数集，用括号的不同来区分是否包含 $a,\ b$。

• $[a, b] : a \le x \le b$
• $[a, b) : a \le x < b$
• $(a, b] : a < x \le b$
• $(a, b) : a < x < b$

---

数列

按照固定顺序排列的一列数字。

项数分类

有穷数列：项数有限。

无穷数列：项数无限。

关系分类

递增数列：每一项都大于后一项。

递减数列：每一项都小于后一项。

常数列：各项都相等。

名称

首项：数列的第一项。

末项：数列的最后一项。

项数：组成数列的数的个数。

等差数列

满足 $a_n - a_{n-1} = d$ 的数列，其中 $d$ 是常数，表示公差。

通项公式：$a_n = a_1 + (n-1) \times d$

前 $n$ 项和：$S_n = \dfrac{n \times (a_1 + a_n)}2$

等比数列

满足 $\dfrac{a_n}{a_{n-1}} = q$ 的数列，其中 $q$ 是常数，表示公比。

通项公式：$a_n = a_1 \times q^{n-1}$

前 $n$ 项和：

$q \ne 1 : S_n = \dfrac{a_1 \times (1 - q^n)}{1-q}$

$q = 1 : S_n = n \times a_1$

$n = +\infty ,|q| < 1 : S_n = a_1 \times \dfrac 1{1-q}$

---

取模

$a\%b,\ a \bmod b$，表示 $a\div b$ 的余数。

数学中，若 $a$ 是负数，对 $b$ 取模后仍会得到一个在 $[0, b)$ 的数字，如 $(-5) \bmod 3 = 1$。实际上是通过加减若干 $b$ 的到一个在 $[0, b)$ 的数字。

计算机中的 $\%$ 对于负数的处理则是先不看符号取模，在取反，如 $(-5)\%3 = (-2)$。

计算机中可以这样处理负数取模：$(a \% b + b)\% b$。

---

逆元

$((a \% p) \div(b \% p)) \ne (a \div b) \% p$，在数学中，我们可以把除以 $k$ 看作乘 $\dfrac 1k$。

现在我们需要找到一个 $c$，满足 $b \times c \equiv a \pmod p$。

费马小定理：在 $p$ 为质数的情况下，有 $\dfrac 1k \equiv k^{p-2} \pmod p$。

所以 $\dfrac ab \% p = a \times (\dfrac 1b \% p) = a \times b^{p-2}$。

---

概率期望

事件

一类（或一种）情况，如骰子的点数是 $5$；太阳从西边升起；骰子的点数大于 $0$ 小于 $7$。

分类

必然事件：一定会发生的事件。

不可能事件：一定不会发生的事件。

关系：

独立事件：若 $A$ 事件和 $B$ 事件的结果互相没有任何关系。

互斥事件：若 $A$ 事件和 $B$ 事件内的情况不可能同时发生。

对立事件：$A,\ B$ 互斥且总是会发生一个内的事件。

概率

一个时间发生的概念，是事件发生可能性的度量。$P(A)$ 表示 $A$ 事件发生的概率。

盒子里有 $5$ 个黑球，$3$ 个白球，一次性摸两个，一黑一白的概率为 $\dfrac{5 \times 3}{C_{8}^{2}} = \dfrac{15}{28}$

条件概念

$P(A\mid B)$ 表示在已知 $B$ 事件发生的基础上，$A$ 事件发生的概率。

$P(A\mid B) = \dfrac{P(AB)}{P(B)}$

期望

用 $E(X)$ 来表示一个随机变量的期望值；$X$ 可以指投一个骰子的点数，一个人的考试成绩等。

$E(X) = \sum P (X = x) \times x$

期望值是一个随机变量无限次输出取值得到的一些数字的平均值。

若一个随机事件的某个结果的概率是 $p$，则期望 $\dfrac 1p$ 次该事件能得到这个结果。

期望的线性性：$E(aX + bY) = aE(X) + bE(Y)$

若 $XY$ 相互独立，则 $E(XY) = E(X)E(Y)$。

$P(A) = \sum P(X = x)$

$P(A) = \sum P(A \mid X = x)P(X = x)$

例题

• 一个 $n$ 个点的完全无向图，起初在 $s$ 点，每秒钟随机走向另一个点，求到达 $t$ 点的期望时间。

设 $f_i$ 表示从 $i$ 点走到 $t$ 点的期望时间。

考虑求解 $f_s$，从它走的第一步入手。由于这是一个完全图，任意两点之间都有直接联通的边，所以走的第一步可以是任意点。

如果走到了 $t$ 点，那么显然期望步数为 $1$，概率为 $\dfrac 1{n-1}$。

如果走到了其它 $n-2$ 个点，假设当前走到了 $k$ 点，那么从 $s$ 点走到 $t$ 点的期望步数为 $f_k + 1$，概率为 $\dfrac 1{n-1}$。而一共有 $n-2$ 个 $k$ 点，所以这样的期望步数为 $\sum_{k \ne s, k \ne t} (f_k + 1)\times \dfrac 1{n-1}$。

所以，将两种方案加起来，得到总期望值为 $1 \times \dfrac 1{n-1} + \sum_{k \ne s, k \ne t} (f_k + 1)\times \dfrac 1{n-1}$。

由于是完全图，所以我们可以看作每个点都是一样的，所以可以将上式中所有的 $f_k$ 替换为 $f_s$，还可以把 $\sum$ 符号去掉，替换为 $(n-2) \times \dots$，所以这个式子就变成了 $f_s = \dfrac 1{n-1} + (n-2) \times (f_s + 1)\times \dfrac 1{n-1}$，解方程得 $f_s = n - 1$。