您当前位置: 首页  >  人才培养  >  本科生教育  >  课程简介

课程简介

组合数学

《组合数学》课程介绍

    《组合数学》(又称组合学)是计算机科学与技术专业的模块限制选修课。它是为培养员工的组合思维能力而设置的,是一门研究离散对象的非常有趣和有用的课程。

    通过本课程的学习,员工将做到:

1.    用容斥原理、生成函数和波利亚定理等求解线性(或圆)排列、集合分划、整数分拆等计数问题;

2.    掌握递推关系的计数方法以及常系数线性非齐次递推关系的求解方法;

3.    了解组合数学的存在性证明和恒等式证明的基本方法。

4.    了解组合算法进行组合构造和最优化求解。

    课程内容主要以计数为主,还涉及到组合数学的存在性、构造和优化问题。主要包括鸽巢原理、牛顿二项式定理、容斥原理、生成函数、递推关系、波利亚定理等理论、方法及其应用,特殊计数序列,以及排列与组合的生成算法、组合优化算法。

    通过本课程的学习,使员工系统地掌握组合数学的基本理论和方法,了解组合算法,培养员工的组合计算能力、发散思维能力,为计算机科学中其他课程的学习奠定必要的数学基础。

The introduction of course –Combinatorics

Combinatorics is a foundational and limited-optional specialty course for undergraduates majoring in computer science and technology,; this course is a very interesting and useful course which involves discrete structures and builds up a good combinatorial thinking for computer science students.

  Through this course, students will:

1. Use inclusion-exclusion principle, generating functions, Polya counting etc. to solve the problems such as permutation combination, set partition, integer partitions.

2. Master the counting technique of recurrence relations and how to solve the linear nonhomogeneous Recursive Relation with constant coefficients.     

3. Learn the basics of existence proof and combinatorial identity proof.

4. Learn the constructive algorithms and optimization algorithms.

  This course emphasizes on combinatorial counting techniques. The contents contain the Pigeonhole principle, the binomial coefficients, the inclusion-exclusion principle, recurrence relations, generating functions, Polya counting and their applications, special counting sequences, generating permutations and combinations and combinatorial optimization algorithms.

  Study of this course makes students to grasp the basic theorems, principles and algorithms of Combinatorics, and improve the ability to combinatorial thinking and skill in solving the practical problems.