组合数学

出版时间：2002-12  出版社：西安电子科技大学出版社  作者：马光思  页数：267  
Tag标签：无  

前言

　　本书根据作者多年讲授研究生和高年级本，干斗生“组合数学”课程的教学笔记整理编撰而成。其中，主要内容取自作者1991年所编《组合数学》讲义。结合多年来在教学工作中积累的素材和现阶段形势发展对“组合数学”课程的新要求，在书中对原讲义的内容作了较大幅度调整，去掉了半群、范畴等章节，增加了递归关系、组合设计及编码、组合算法与计算复杂性等章节，并对原讲义中有些章节的内容作了许多扩充，补充了各章的习题。　　为了保持全书独立性，对“离散数学”等先驱课程中的基本概念和术语在各章节中使用之前都有简要说明。书中所用符号和术语力求保持与“离散数学”的习惯用法一致。其中，对最基本的逻辑符号合取“^”、析取“V”、推导（永真蕴涵）、等价及集合运算符交“n”、并“U”等常用符号的含义和用法不再进一步解释，直接引用。　　计算机科学中包含着大量组合数学的知识。由于教学和应用的需要，组合数学已成为计算机学科及与信息有关学科的基础理论课程。本书涉及组合分析、图论、抽象代数、编码理论、组合算法及算法复杂性等组合数学的几乎全部内容。所选内容基本符合《同等学历人员申请硕士学位计算机科学与技术学科综合水平全国统一考试大纲及指南》中“组合数学”的考试大纲要求。关于部分线性规划问题，一并纳入组合算法统一讨论。　　全书共分八章。第一章数论基础是通读全书的预备知识，内容主要取自参考文献[1]。其中，同余式的一般性讨论是新增加部分。第二章基本计数原理，包括加法原理、乘法原理、鸽巢原理，以及排列与组合及其进一步讨论和应用；对集合元素计数的容斥原理及应用，因篇幅和技术处理上的需要，特别安排在第四章反演公式中，作为筛法公式的特殊情况给出。第三章对由Laplace和Euler提出的生成函数方法进行了全面讨论。第四章是反演公式，该章起点较高，逐渐演绎，最后给出了若干具体应用，部分内容请参考文献[3]。第五章系统讨论了递归关系，主要参考文献[6]。第六章除增加了部分例题之外，基本保持原讲义风貌，主要介绍了群及几个与计数有关的定理：Lagrange定理、Burnside定理、Polya一定理及其应用。第七章组合设计及编码，简要介绍了相异及公共代表组，对均衡不完全区组的设计、正交拉丁方、Hadmard矩阵也有部分论述；最后给出了有关编码、译码的基本理论。该章内容主要参阅本书参考文献[4]。第八章组合算法与计算模型，主要介绍一些经典的组合算法设计技术及优化问题的解决方法，并特别讨论了计算模型Turing机，P及NP类语言和算法复杂性等计算机科学中核心而重要的课题；该章参考文献为[5]、[6]和[8]。

内容概要

随着现代科学技术的发展，组合数学的应用日趋广泛。本书作者1991年所编《组合数学》讲义为基础，并结合多年来的教学实践经验编撰而成。全书比较完整地阐述了组合数学的基本理论。
    全书共8章。第一章介绍数论基础知识，为读者通读全书做一些准备工作；第二章是组合计数方面的经典内容，包括基本计数原理、鸽巢原理、Ramsey定理及排列与组合等；第三章详细讨论了生成函数技术及其应用；第四章反演公式和第五章递归关系是组合数学中深入、关键的技术和方法；第六章通过对群的讨论，引出了著名的Lagrange定理、Burnside定理和Polya定理；第七章概要阐述了组合设计与编码理论基础；第八章主要介绍了组合算法的设计和优化问题的处理方法，并简要介绍了计算模型Turing机、P问题、NP问题与计算复杂性及其相互关系。
    全书理论结合实际，部分章节由浅入深，形成归纳；部分章节综合概括，以高起点结论推出若干应用结果。为了巩固概念，每章最后均有适当数量习题。书中文字叙述生动，实例丰富，注意启发性的同时又考虑了提高总结。

书籍目录

1，数论基础
2，基本计数原理
3，生成函数
4，反演公式
5，递归关系
6，群
7，组合设计及编码
8，组合算法与计算复杂性