程序设计中的组合数学

作　者：	吴文虎孙贺
出版社：	清华大学出版社
丛编项：	ACM/ICPC国际大学生程序设计竞赛
版权说明：	本书为公共版权或经版权方授权，请支持正版图书
标　签：	暂缺

ISBN	出版时间	包装	开本	页数	字数
未知	暂无	暂无	未知	0	暂无

作者简介

　　孙贺 1984年1月生，现就读于复旦大学。高中时参加信息学奥林匹克竞赛活动，撰写了关于信息学奥赛方面的论文数篇，发表任《信息学奥林匹克》、《数字冲浪》上，并在大学期间参与了多个省市信息学奥林匹克竞赛的命题和培训工作。2002年作为全国世界年龄最小的报告人应邀在第24届国际数学家大会（ICM2002）上做15分钟报告，在ICM2002-SCC上做15分钟报告，其论文摘要入选ICM2002摘要集。2002年获得复旦大学“光华自立奖”。2004年获得复旦大学在校师生及校友的最高荣誉——复旦大学校长奖，成为该校历史上获得这一荣誉的第一位本科生。2005年秋起在复旦大学计算机科学与工程系攻读博士学位，研究方向为计算理论。

内容简介

本书系统地介绍了与程序设计竞赛有关的组合数学的基本理论和算法设计与分析的常用方法。全书共分8章，分别为：算法基础、组合数学初探、排列与组合、容斥原理、母函数、拟阵、贪心算法和Pólya定理。本书突出组合数学算法的设计与优化，从而更便于参加程序设计竞赛的读者学习组合数学。本书可作为ACM/ICPC国际大学生程序设计竞赛和国际信息学奥林匹在竞赛（IOI）的培训教材，也可供从事组合数学与算法研究的人员参考。

图书目录

第1章算法基础 1.1 算法 1.2 时间复杂度与空间复杂度 1.3 P类与NP类习题第2章组合数学初探 2.1 组合数学的起源 2.2 组合数学的研究的问习题第3章排列与组合 3.1 基本概念

3.2 分拆与置换的表示3.3 排列与组合的生成算法3.4 购票问题3.5 “方程的解”问题习题第4章容斥原理4.1 基本概念4.2 “被毁坏的玉米地”问题问题第5章母函数5.1 普通型母函数

5.2 指数型母函数 5.3 质数分解问题 5.4 “红色病毒”问题 5.5 “自共轭Ferrers图”问题 5.6 常见组合计数方法之比较 5.7 NPC问题的代数化习题第6章拟阵 6.1 基本概念 6.2 拟阵的基本性质 6.3 拟阵与贪心算法

习题第7章贪心算法 7.1 贪心算法的概念与特点 7.2 最佳浏览路线问题 7.3 贪心算法与近似计算习题第8章 Pólya定理 8.1 群与置换群 8.2 Burnside引理 8.3 Pólya定理习题