代数与组合论
学分: 6
组合论旨在研究离散数学结构（通常具备有穷性）。此类结构不仅出现于各理论数学领域，而且也出现在其他科学领域，如计算机科学、统计物理学和基因学。虽然本理论可追溯至古代时期，但其实在 20 世纪中期才真正得到长足发展，因为当时的科学发现（最主要的发现是 DNA）表明组合论是理解我们身边世界的关键，而且在计算领域取得的很多重大进步均以组合论的基本理论为基础。
组合论占据本课程的一半内容。首先，本课程将讲述素朴集合理论以及分割、等值关系、可数与不可数无穷集合的概念。在讲述图形理论之前，本课程还将学习精确计算方法，而图形理论又为现实世界和虚拟网络中的研究活动构建了一个数学框架。
理论数学领域的一个最重要的方法是抽象法，它帮助我们在看起来不相关的领域之间建立显而易见的深入联系。抽象代数是抽象法的一个重要实例，它抽象概括对称的概念和算术运算的属性，以揭示各种代数结构，如群、环和域。虽然其性质非常抽象，但是这些概念在现实世界的应用却非常重要和广泛，如通信理论和互联网安全。
本课程将通过常见的正整数、实数和多项式范例讲述群、环和域原理，探讨这些数学结构的基本属性。本课程将在课堂上讨论初等数论、欧几里得算法和素数等知识。
本课程的基本主题是证明技巧以及数学写作的重要性。
在课程结课时，学生应能够：
• 掌握基本集合理论，并确定不同集合的可数性或不可数性
• 运用各种方法计算有限集合，包括求和与乘积规则及二项式定理
• 了解并运用图形理论的基本概念和成果
• 证明基础数论的基本表达式，并从不同的定理得出各种推论
• 确定排列的循环类型并计算排列的乘积
• 应用欧几里得算法计算正整数和多项式
• 列举群、环和域的非零解例子
Algebra and Combinatorics 代数与组合论
Credits: 6
Combinatorics is the study of discrete (often-finite) structures that arise not only in areas of pure mathematics, but also in other areas of science, for example computer science, statistical physics and genetics. From ancient beginnings, this subject truly rose to prominence from the mid-20th century, when scientific discoveries (most notably of DNA) showed that combinatorics is key to understanding the world around us, whilst many of the great advances in computing were built on combinatorial foundations. The combinatorics half of this module starts by looking at naïve set theory, introducing the notions of partitions, equivalence relations and the notion of countable and uncountable infinite sets. Sophisticated counting techniques are developed before an introduction to the field of graph theory, which provides a mathematical framework for the study of both real world and virtual networks.
One of the most powerful techniques of pure mathematics is that of abstraction, which allows deep relationships between apparently unrelated areas to become apparent. Abstract algebra is a powerful example of this technique, abstracting notions of symmetry and the properties of arithmetic to reveal algebraic structures such as groups,
rings and fields. Despite their very abstract nature, these ideas have significant real-world applications, for example in communication theory and internet security. Using familiar examples of the natural numbers, real numbers and polynomials as motivation, the axioms for groups, rings and fields are introduced and basic properties of these structures are explored. Elementary number theory, the Euclidean algorithm, and prime numbers are discussed.
Underlying themes throughout this module are techniques of proof and the importance of mathematical writing.
By the end of this module, students should be able to:
• Perform basic set theoretic manipulations and determine the countability or uncountability of various sets.
• Apply various techniques, including the sum and product rules and the binomial theorem to count finite collections.
• Know and use the basic notions and results of graph theory.
• Prove elementary statements in basic number theory and make deductions from axioms.
• Determine the cycle type of a permutation and calculate products of permutations.
• Apply the Euclidean algorithm to both natural numbers and polynomials. • Give non-trivial examples of groups, rings and fields.
