Glossary⚓︎
这里只选录了部分词汇和结论,仅供考前快速记忆和方便查阅。中文主要是我自己翻译的,未标注中文或未摘录的 ( 也有可能是我漏掉了 ) 词汇不作为考点。
Chap 1 The Foundations: Logic and Proofs⚓︎
- proposition:命题
- proposition variable:命题变量
- truth value:真值
- \(\neg p\), negation:否定
- logical operators:逻辑运算符
- compound proposition:复合命题
- truth table:真值表
- \(p \vee q\), disjunction:析取
- \(p \wedge q\), conjunction:合取
- \(p \oplus q\), exclusive or:异或
- \(p \rightarrow q\):条件语句
- converse of \(p \rightarrow q\):逆命题 \(q \rightarrow p\)
- contrapositive of \(p \rightarrow q\):逆否命题 \(\neg q \rightarrow \neg p\)
- inverse of \(p \rightarrow q\):否命题 \(\neg p \rightarrow \neg q\)
- \(p \leftrightarrow q\), biconditional:双条件语句
- bit:位
- Boolean variable:布尔变量
- bit operation:位运算
- bit string:位串
- bitwise operations:按位运算
- tautology:永真
- contradiction:永假
- contingency:( 可能为真也可能为假 )
- consistent compound propositions:一致复合命题
- satisfiable compound propositions:可满足的复合命题
- logically equivalent compound propositions:逻辑等价复合命题
- propositional function:命题函数
- domain of discourse:域
- \(\exists x\ P(x)\), existential quantification:存在量词
- \(\forall x\ P(x)\), universal quantification:全称量词
- logically equivalence expressions:逻辑等价命题
- free variable:自由变量
- bound variable:约束变量
- scope of a quantifier:量词范围
- argument:论证
- argument form:论证形式
- premise:前提
- conclusion:结论
- valid argument form:合法的论证形式
- valid argument:合法论证
- rule of inference:推理规则
- fallacy:谬误
- circular reasoning or begging the question:循环论证
- theorem:定理
- conjecture:猜想
- proof:证明
- axiom:公理
- lemma:引理
- corollary:推论
- vacuous proof:空证明
- trivial proof:平凡证明
- direct proof:直接证明
- proof by contraposition:反证法
- proof by contradiction:归谬法
- exhaustive proof:穷举证明
- proof by cases:分类证明
- without loss of generality:不失一般性
- counterexample:反例
- constructive existence proof:构造存在证明
- nonconstructive existence proof:非构造存在证明
- rational number:有理数
- uniqueness proof:唯一性证明
- 逻辑等值表
- 量词的德摩根定理
- 推断规则 ( 命题演算、量词语句 )
Chap 2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices⚓︎
- set:集合
- paradox:悖论
- element, member of set:集合的元素或成员
- roster method:枚举法
- set builder notation
- multiset:多重集
- \(\emptyset\), empty/null set:空集
- universal set:全集
- Veen diagram:维恩图
- \(S = T\):集合等价
- \(S \subseteq T\):S 是 T 的子集
- \(S \subset T\):S 是 T 的真子集
- finite set:有限集
- infinite set:无限集
- \(|S|\), the cardinality of S:S 的基数
- \(P(S)\):S 的幂集
- \(A \cup B\), union:A 和 B 的并集
- \(A \cap B\), intersection:A 和 B 的交集
- \(A - B\), difference:A 和 B 的差集
- \(\overline{A}\), complement:A 的补集
- \(A \oplus B\), symmetric difference:A 和 B 的对称差集
- membership table:成员表
- function from A to B:A 到 B 的函数
- domain of f:f 的域
- codomain of f:f 的伴域
- b is the image of a under f, b = f(a):b 是 a 在 f 下的象
- a is a preimage of b under f, f(a) = b:a 是 b 在 f 下的一个原象
- range of f:f 的范围
- onto function, surjection:满射函数
- one-to-one function, injection:单射函数
- one-to-one correspondence, bijection:双射函数
- inverse of f:f 的反函数
- \(f \circ g\), composition:f 和 g 的复合函数
- \(\lfloor x \rfloor\), floor function:底函数
- \(\lceil x \rceil\), ceiling function:顶函数
- sequence:序列
- geometric progression:几何级数 ( 等比数列 )
- arithmetic progression:算术级数 ( 等差数列 )
- string:字符串
- empty string:空字符串
- recurrence relation:递推关系
- cardinality:基数
- countable set:可数集合
- uncountable set:不可数集合
- \(\aleph_0\):表示可数集合的基数
- \(c\):实数集的基数
- Cantor diagonalization argument:康托对角化论证
- computable function:可计算函数
- uncomputable function:不可计算函数
- continuum hypothesis:连续统假设
- matrix:矩阵
- matrix addition:矩阵加法
- matrix multiplication:矩阵乘法
- \(I_n\), identity matrix of order n:n 阶单位矩阵
- \(A^t\), transpose of A:A 的转置矩阵
- symmetric matrix:对称矩阵
- zero-one matrix:零一矩阵
- \(\bm{A} \vee \bm{B}\), join:A 和 B 的并
- \(\bm{A} \wedge \bm{B}\), meet:A 和 B 的交
- \(\bm{A} \odot \bm{A}\), Boolean product:A 和 B 的布尔积
- 集合恒等式
- 序列和公式
- 有理数集是可数的
- 实数集是不可数的
Chap 3⚓︎
Chap 4 Number Theory and Cryptography⚓︎
- \(a\ |\ b\) (a divides b):整除
- a and b are congruent module m: m divides a - b:a 与 b 模 m 同余
- prime:质数
- composite:合数
- Mersenne prime:梅森质数,\(2^p - 1\),p 为质数
- gcd(a, b):a, b 的最大公约数
- relatively prime integers:互质整数
- pairwise relatively prime integers:两两互质整数
- lcm(a, b):a, b 的最小公倍数
- a mod b:a 模除 b
- \(a \equiv b(\text{mod } m)\):a 与 b 模 m 同余
- \(n = (a_ka_{k-1}\dots a_1a_0)_b\):n 的 b 进制表示法
- binary representation:二进制
- octal representation:八进制
- hexadecimal representation:十六进制
- linear combination of a and b with integer coefficients:带整系数的 a, b 的线性组合
- Bezout coefficients of a and b:使 Bezout identity sa + tb = gcd(a, b) 成立
- inverse of a modulo m:a 模 m 的逆,满足 \(a\overline{a} \equiv 1(\text{mod } m)\)
- linear congurence:线性同余,\(ax \equiv b(\text{mod } m)\)
- pseudoprime to the base b:基底 b 的伪质数,合数 n 满足 \(b^{n-1} \equiv 1 (\text{mod } n)\)
- Carmichael number:卡迈克尔数
- primitive root of a prime p
- discrete logarithm of a to the base r modulo p
- division algorithm:除法算法
- b 进制表达扩展
- fast modular exponentiation algorithm:快速指数模算法
- Euclidean algorithm:欧几里得算法
- Bezout's theorem:裴蜀定理
- sieve of Eratosthenes:埃氏筛
- fundamental theorem of arithmetic:算术基本定理
- Chinese remainder theorem:中国剩余定理
- Fermat's little theorem:费马小定理
Chap 5 Induction and Recursion⚓︎
- sequence:序列
- geometric progression:几何级数 / 等比数列
- arithmetic progression:算术级数 / 等差数列
- the principle of mathematical induction:数学归纳法
- basis step:基本步骤
- inductve step:递归步骤
- strong induction:强归纳法
- well-ordering property:良序性
- recursive definition of a function:函数的递归定义
- recursive definition of a set:集合的递归定义
- structural induction:结构化归纳
- recursive algorithm:递归算法
- merge sort
- iteration:迭代
- program correctness
- loop invariant
- initial assertion
- final assertion
Chap 6 Counting⚓︎
- combinatorics:组合学
- enumeration:枚举
- tree diagram:树形图
- r-permutation:r 排列,P(n, r)
- r-combination:r 组合,C(n, r)
- binomial coefficient\(\left(\begin{array}{a} n \\ r\end{array}\right)\):二项式系数
- combinatorial proof:组合证明
- Pascal's triangle:帕斯卡三角形
- S(n, j):( 第二类 ) 斯特林数
- product rule for counting(sets):计数 ( 或集合 ) 的乘积法则
- sum rule for counting(sets):计数 ( 或集合 ) 的和法则
- subtraction rule or inclusion-exclusion for counting(sets):计数 ( 或集合 ) 的减法法则,或者容斥原理
- division rule for counting(sets):计数 ( 或集合 ) 的除法法则
- the pigeonhole principle:鸽巢原理
- the generalized pigeonhole principle:广义鸽巢原理
- Pascal's identity:帕斯卡恒等式
- the binomial theorem:二项式定理
Chap 8 Advanced Counting Techniques⚓︎
- recurrence relation:递推关系
- initial conditions for a recurrence relation:递推关系的首条件
- dynamic programming
- linear homogenous recurrence relation with constant coefficients:常系数线性齐次递推关系
- characteristic roots of a linear homogenous recurrence relation with constant efficients:常系数线性齐次递推关系的特征根
- linear nonhomogenous recurrence relation with constant coefficients:常系数线性非齐次递推关系
- divide-and-conquer algorithm
- generating funcition of a sequence:序列的生成函数
- sieve of Eratosthenes:埃氏筛 ( 又出现了一遍 )
- derangement:错排
- the principle of inclusion-exclusion:容斥原理
- 满射函数的个数
- 错排的个数
Chap 9 Relation⚓︎
- binary relation from A to B:A 到 B 的二元关系
- relation on A:在 A 上的关系
- \(S \circ R\):R 和 S 的复合关系
- \(R^{-1}\):R 的逆关系
- \(R^n\):R 的 n 次幂
- reflexive:自反性
- symmetric:对称性
- antisymmetric:反对称性
- transitive:传递性
- n-ary relation on \(A_1, A_2, \dots, A_n\):n 元关系
- directed graph / digraph:有向图
- loop:环
- closure of a relation R with respect to a property P:R 上关于性质 P 的闭包
- path in a digraph:有向图上的路径
- circuit(or cycle) in a digraph:有向图上的环
- \(R^*\), connectivity relation:连通关系
- equivalence relation:等价关系
- equivalent:等价
- \([a]_R\), equivalence class:关于 R 的 a 的等价类
- \([a]_m\), congruence class modulo m:模 m 的同余类
- partition of a set S:集合 S 的分区
- partial ordering:偏序
- poset(S, R):偏序集
- comparable:可比的
- incomparable:不可比的
- total (or linear) ordering:全序
- totally (or linearly) ordering set:全序集
- well-ordered set:良序集
- lexicographic order:词典序
- Hasse diagram:哈斯图
- maximal element:极大元素
- minimal element:极小元素
- greatest element:最大元素
- least element:最小元素
- upper bound of a set:集合的上限
- lower bound of a set:集合的下限
- least upper bound of a set:集合的最小上界
- greatest lower bound of a set:集合的最大下界
- lattice:格
- compatible total ordering for a partial ordering:对某个偏序兼容的全序
- topological sort:拓扑排序
- reflexive closure:自反闭包
- symmetric closure:对称闭包
- transitive closure:传递闭包
- Warshall's algorithm
- 关于等价关系的 3 条等价语句
- 等价类 & 分区
- the principle of well-ordered induction:良序归纳法
- 拓扑排序算法
Chap 10 Graphs⚓︎
- undirected edge:无向边
- directed edge:有向边
- multiple edges:重边
- multiple directed edges:有向重边
- loop:环
- undirected graph:无向图
- simple graph:简单图
- multigraph:多重图
- pseudograph:伪图
- directed graph:有向图
- directed multigraph:有向多重图
- simple directed graph:简单有向图
- adjacent:相邻的 (2 顶点间 )
- incident:关联的 ( 边和顶点 )
- \(\mathrm{deg}\ v\):顶点 v 的度
- \(\mathrm{deg}^-\ v\):顶点 v 的入度
- \(\mathrm{deg}^+\ v\):顶点 v 的出度
- underlying undirected graph of a graph with directed edges:( 有向图的 ) 潜在无向图
- \(K_n\)(complete graph on \(n\) vertices):完全图
- bipartite graph:二分图
- \(K_{m, n}\)(complete bipartite graph):完全二分图
- \(C_n\)(cycle of size \(n(\ge 3)\)):环
- \(W_n\)(wheel of size \(n(\ge 3)\)):轮
- \(Q_n\)(\(n\)-cube):n 立方
- matching in a graph \(G\):匹配
- complete matching \(M\) from \(V_1\) to \(V_2\):完全匹配
- maximum matching:最大匹配
- isolated vertex:孤立顶点 ( 度为 0)
- pendant vertex:下悬顶点 ( 度为 1)
- regular graph:正则图 ( 每个顶点的度相同 )
- subgraph of a graph \(G = (V, E)\):子图
- \(G_1 \cup G_2\)(union of \(G_1\) and \(G_2\)):交集
- adjacency matrix:邻接矩阵
- indidence matrix:关联矩阵
- isomorphic simple graphs:同构简单图
- invariant for graph isomorphism:图同构的不变量
- path from \(u\) to \(v\) in a graph with undirected/directed edges:路径
- simple path:简单路径
- circuit:回路 / 环
- connected graph:连通图
- cut vertex of \(G\):割点
- cut edge of \(G\):割边
- nonseparable graph:不可分割集
- vertex cut of G:点割集
- \(\kappa(G)\)(the vertex connectivity of \(G\)):点连通度
- \(k\)-connected graph:k 连通度
- edge cut of \(G\):边割集
- \(\lambda(G)\)(the edge connectivity of \(G\)):边连通度
- connected component of a graph \(G\):连通分量
- strongly connected directed graph:强连通有向图
- strongly connected component of a directed graph \(G\):有向图的强连通分量
- Euler path:欧拉路
- Euler circuit:欧拉环 ( 回路 )
- Hamilton path:哈密顿路
- Hamilton circuit:哈密顿环 ( 回路 )
- weighted graph:带权图
- shortest-path problem:最短路问题
- traveling salesperson problem:旅行商问题
- planar graph:平面图
- regions of a representation of a planar graph:平面图表示法的区域
- elementary subdivision:初等细分
- homeomorphic:同胚的
- graph coloring:图着色
- chromatic number:着色数
- the handshaking theorem:握手定理
- Hall's marriage theorem:霍尔婚配定理
- 欧拉环和欧拉路存在的充要条件
- Dijkstra's algorithm
- Euler's formula
- Kuratowski's theorem
- the four color theorem:四色定理
Chap 11 Trees⚓︎
- tree:树
- forest:森林
- rooted tree:有根树
- subtree:子树
- parent of \(v\) in a rooted tree:父节点
- child of \(v\) in a rooted tree:孩子节点
- sibling of \(v\) in a rooted tree:兄弟节点
- ancestor of \(v\) in a rooted tree:祖先
- descendant of \(v\) in a rooted tree:后代
- internal vertex:内部节点
- leaf:叶子节点
- level of a vertex:层级
- height of a tree:高度
- \(m\)-ary tree:\(m\) 叉树
- full \(m\)-ary tree:满 \(m\) 叉树
- binary tree:二叉树
- ordered tree:有序树
- balanced tree:平衡树
- binary search tree:二叉搜索树
- decision tree:决策树
- game tree:博弈树
- prefix code:前缀码
- minmax strategy:极小极大策略
- tree traversal:树的遍历
- preorder traversal:前序遍历
- inorder traversal:中序遍历
- postorder traversal:后序遍历
- infix notation:中缀表示法
- prefix/Polish notation:前缀 / 波兰表示法
- postfix/reverse Polish notation:后缀 / 逆波兰表示法
- spanning tree:生成树
- minimum spanning tree:最小生成树
- Huffman coding:哈夫曼编码
- depth-first search/backtraking:深度优先搜索 / 回溯
- breadth-first search:宽度优先搜索
- Prim's algorithm
- Kruskal's algorithm
评论区
如果大家有什么问题或想法,欢迎在下方留言~