← Back to Home ← 返回主页

Final Review 期末复习

Final Notes Summary 期末笔记摘要

Graph Theory 图论

  • Graphs, vertices, edges图、顶点、边
  • Handshaking Lemma握手引理
  • Eulerian and Hamiltonian paths欧拉路径和哈密顿路径

Number Theory 数论

  • Divisibility, GCD, Euclidean Algorithm整除性、最大公约数、欧几里得算法
  • Primes, Fundamental Theorem of Arithmetic素数、算术基本定理
  • Congruences, Chinese Remainder Theorem同余、中国剩余定理

Logic 逻辑

  • Propositional and Predicate Logic命题逻辑和谓词逻辑
  • Truth Tables, Logical Equivalence真值表、逻辑等价

Set Theory 集合论

  • Set operations, Power Set集合运算、幂集
  • Inclusion-Exclusion Principle容斥原理

Chapter 1: Sets, Functions, and Relations 第一章：集合、函数和关系

  • A set is a collection of distinct objects.集合是不同对象的集合。
  • Set Operations: Union, Intersection, Difference, Complement.集合运算：并集、交集、差集、补集。
  • A function maps inputs to unique outputs; can be injective, surjective, or bijective.函数将输入映射到唯一的输出；可以是单射、满射或双射。
  • A relation is a set of ordered pairs; can be reflexive, symmetric, transitive.关系是有序对的集合；可以是自反的、对称的、传递的。

Chapter 2: Logic and Proofs 第二章：逻辑与证明

  • Propositional Logic: Deals with true/false statements and connectives.命题逻辑：处理真/假陈述和逻辑连接词。
  • Predicate Logic: Introduces variables and quantifiers.谓词逻辑：引入变量和量词。
  • Proof Techniques: Direct, Contradiction, Contraposition, Induction.证明技巧：直接证明、反证法、逆否证法、数学归纳法。

Chapter 3: Number Theory 第三章：数论

  • Euclidean Algorithm: Finds the GCD of two integers.欧几里得算法：求两个整数的最大公约数。
  • Fundamental Theorem of Arithmetic: Unique prime factorization.算术基本定理：唯一的素数分解。
  • Congruences: Arithmetic on remainders.同余：关于余数的算术。

Chapter 4: Graph Theory 第四章：图论

  • Graphs: Consist of vertices and edges.图：由顶点和边组成。
  • Eulerian Path: Traverses every edge exactly once.欧拉路径：每条边只遍历一次。
  • Hamiltonian Cycle: Visits every vertex exactly once.哈密顿回路：每个顶点只访问一次。
  • Trees: Connected graphs with no cycles.树：没有环的连通图。

Chapter 5: Counting 第五章：计数

Permutations and Combinations 排列与组合

  • Permutations: Ordered arrangements. P(n, r) = n! / (n-r)!排列：有序的排列。P(n, r) = n! / (n-r)!
  • Combinations: Unordered selections. C(n, r) = n! / (r!(n-r)!)组合：无序的选择。C(n, r) = n! / (r!(n-r)!)

Binomial Theorem and Inclusion-Exclusion 二项式定理和容斥原理

  • Binomial Theorem: Expands (x + y)^n.二项式定理：展开 (x + y)^n。
  • Inclusion-Exclusion: Counts elements in a union of sets.容斥原理：计算集合并集中的元素数量。

Lab Test 2 Topics 实验二主题

  • Recurrence Relations: Defines a sequence based on its preceding terms.递推关系：根据前几项定义序列。
  • Generating Functions: Power series representation of a sequence.生成函数：序列的幂级数表示。