[套装书]算法设计编程实验（第2版）+天才与算法：人脑与AI的数学思维（2册）

. 本书为我们展现了人工智能是如何逐步变得强大，以及它们如何开始进行创造性的艺术创作。本书引导读者去认知人类创造力的本质，探索了算法、数学思维和艺术创作之间的关系，并为未来人类与机器的共生关系描绘出一个更加积极、出人意料的愿景。

3.2　求解不定方程和同余的实验范例 82
3.2.1　计算最大公约数和不定方程 82
3.2.2　计算同余方程和同余方程组 89
3.2.3　计算多项式同余方程 99
3.3　特殊的同余式的实验范例 102
3.3.1　威尔逊定理和费马小定理 102
3.3.2　伪素数 105
3.3.3　欧拉定理 112
3.4　积性函数的实验范例 116
3.4.1　欧拉φ函数φ(n) 116
3.4.2　莫比乌斯函数μ(n) 121
3.4.3　完全数和梅森素数 124
3.5　高斯素数的实验范例 129
3.6　相关题库 135
第4章　组合分析的编程实验 152
4.1　生成排列的实验范例 152
4.1.1　按字典序思想生成下一个排列 152
4.1.2　按字典序思想生成所有排列 154
4.2　排列组合计数的实验范例 156
4.2.1　一般的排列组合计数公式 156
4.2.2　两种特殊的排列组合计数公式 167
4.2.3　多重集的排列数和组合数 174
4.3　鸽笼原理与容斥原理的实验范例 178
4.3.1　利用鸽笼原理求解存在性问题 178
4.3.2　容斥原理应用实验 180
4.3.3　Ramsey定理的应用 188
4.4　Pólya计数公式的实验范例 190
4.5　生成函数与递推关系的实验范例 201
4.5.1　幂级数型生成函数 201
4.5.2　指数型生成函数 204
4.5.3　递推关系 207
4.6　快速傅里叶变换的实验范例 211
4.7　相关题库 216
第5章　贪心法的编程实验 229
5.1　体验贪心法内涵的实验范例 229
5.1.1　贪心法的经典问题 229
5.1.2　体验贪心法内涵 236
5.2　利用数据有序化进行贪心选择的实验范例 241
5.3　在综合性的P类问题中使用贪心法的实验范例 249
5.4　相关题库 255
第6章　动态规划方法的编程实验 265
6.1　线性DP的实验范例 266
6.1.1　初步体验线性DP问题 266
6.1.2　子集和问题 270
6.1.3　最长公共子序列问题 271
6.1.4　最长递增子序列问题 273
6.2　0-1背包问题 280
6.2.1　基本的0-1背包问题 280
6.2.2　完全背包 281
6.2.3　多重背包 285
6.2.4　混合背包 287
6.2.5　二维背包 292
6.2.6　分组背包 294
6.2.7　有依赖的背包 298
6.3　树形DP的实验范例 300
6.4　状态压缩DP的实验范例 305
6.5　单调优化1D/1D DP的实验范例 309
6.5.1　经典模型1：利用决策代价函数w的单调性优化 310
6.5.2　经典模型2：利用决策区间下界的单调性优化 313
6.5.3　经典模型3：利用最优决策点的凸性优化 318
6.6　相关题库 322
第7章　高级数据结构的编程实验 353
7.1　后缀数组的实验范例 353
7.1.1　使用倍增算法计算名次数组和后缀数组 353
7.1.2　计算最长公共前缀 356
7.1.3　后缀数组的应用 357
7.2　线段树的实验范例 370
7.2.1　线段树的基本概念和基本操作 370
7.2.2　线段树单点更新的维护 372
7.2.3　线段树子区间更新的维护 375
7.3　处理特殊图的实验范例 387
7.3.1　计算欧拉图 387
7.3.2　计算哈密顿图 393
7.3.3　计算最大独立集 402
7.3.4　计算割点、桥和双连通分支 406
7.4　相关题库 414
第8章　计算几何的编程实验 433
8.1　点线面运算的实验范例 433
8.1.1　计算点积和叉积 433
8.1.2　计算线段交 440
8.1.3　利用欧拉公式计算多面体 449
8.2　利用扫描线算法计算矩形的并的面积的实验范例 453
8.2.1　沿垂直方向计算矩形的并面积 453
8.2.2　沿水平方向计算矩形的并面积 457
8.3　计算半平面交的实验范例 460
8.3.1　计算半平面交的联机算法 461
8.3.2　利用极角计算半平面交的算法 466
8.4　计算凸包和旋转卡壳的实验范例 474
8.4.1　计算凸包 474
8.4.2　旋转卡壳实验 479
8.5　相关题库 482



---------------------------天才与算法：人脑与AI的数学思维---------------------------


赞誉
第1章　洛夫莱斯测试 001
第2章　激发创造力 009
创造力教得会吗 014
第3章　向人类宣战 019
非凡的游戏男孩 023
首战告捷 029
精妙绝伦 031
人类的反击 034
山头还是主峰 039
第4章　算法，网络时代的生活秘诀 043
荒岛算法 047
数学，幸福婚姻的秘诀 055
书商之战 059
第5章　从“自上而下”到“自下而上” 063
看还是不看 067
算法的幻觉 072
第6章　算法的进化 077
如果你喜欢…… 079
如何训练算法 085
偏见和盲点 087
机器之间的战争 090
第7章　数字绘画 095
什么是艺术 099
生物的创造力 105
可视化编码 108
分形：大自然的代码 111
从“亚伦”到“绘画傻瓜” 115
第8章　站在巨人的肩膀上 123
复活伦勃朗 127
创造力竞争 132
算法如何思考 142
算法就是一门艺术 145
第9章　数学的艺术 149
数学证明的游戏 152
数学的起源 154
证明的起源 159
第10章　数学家的望远镜 165
Coq证明助手 169
人脑的极限 171
沃沃斯基的愿景 175
第11章　音乐：声响的数学之旅 179
巴赫：首位音乐程序员 183
艾米：人工智能作曲家 188
模拟游戏：音乐图灵测试 193
“深度巴赫”：从头开始再生作曲家 198
第12章　歌曲的创作公式 203
普希金、诗歌和概率 205
“续作者”：第一个人工智能即兴爵士作曲演奏者 209
“心流机” 211
量子作曲 217
人为何创作音乐 220
第13章　深度数学 223
Mizar的数学 226
数学图灵测试 228
巴别数学图书馆 231
数学寓言 234
意料之外的故事 236
数学的叙述艺术 238
第14章　语言游戏 241
《危险边缘》 248
“华生”的工作模式 251
在翻译中迷失 255
机器人术语 258
受阻于“中文房间”试验 259
第15章　人工智能讲故事 263
如何在一个月内完成一部小说 271
哈利·波特和死亡波特尼克 273
假如…… 275
伟大的“自动化”数学家 279
人工智能新闻 281
第16章　为什么要创造：思想的交流 287

.　　对于第3章“数论的编程实验”和第4章“组合分析的编程实验”的内容和结构，基于数论、组合数学的知识体系，进行全面的加强和改进。其中，第3章从素数运算、求解不定方程和同余方程、特殊的同余式、积性函数的应用、高斯素数5个方面展开实验；而第4章从排列的生成、排列和组合的计数、容斥原理与鸽笼原理、Pólya计数公式、生成函数与递推关系、快速傅里叶变换（FFT）6个方面展开实验。对于数论、组合分析所涉及的知识点，都采用程序设计竞赛的试题作为实验范例，也就是说，基于数论、组合分析的知识体系，实验范例“鱼鳞状”分布在各个知识点中。同时，将数学证明能力和编程解决问题能力的训练相结合，这也是数学类试题的特征。
　　对于第5章“贪心法的编程实验”和第6章“动态规划方法的编程实验”，则增加了经典问题的实验。在第5章中，增加了背包问题、任务调度、区间调度等经典贪心问题的实验；在第6章中，则以“背包九讲”为基础，增加0-1背包问题的实验。这样改进的目的，是使读者能够更好地体验贪心和动态规划的方法。
　　本书可以用于大学的算法及相关数学课程的教学和实验，也可以用于程序设计竞赛选手的系统训练。对于本书，我们的使用建议是：书中每章的实验范例可以用于算法和数学课程的教学、实验和上机作业，以及程序设计竞赛选手掌握相关知识点的入门训练；而每章最后给出的相关题库中的试题则可以作为程序设计竞赛选手的专项训练试题，以及学生进一步提高编程能力的练习题。
　　我们对浩如烟海的ACM-ICPC预赛和总决赛、各种大学生程序设计竞赛、在线程序设计竞赛及中学生信息学奥林匹克竞赛的试题进行了分析和整理，从中精选出314道试题作为本书的试题。其中157道试题作为实验范例试题，每道试题不仅有详尽的解析，还给出标有详细注释的参考程序；另外的157道试题为题库试题，所有试题都有清晰的提示。
　　本书提供了所有试题的英文原版以及大部分试题的官方测试数据和解答程序，有需要者可登录华章网站（http://www.hzbook.com）下载。
　　感谢Stony Brook University的Steven Skiena教授和Rezaul Chowdhury教授，Texas State University的C. Jinshong Hwang教授、Ziliang Zong教授和Hongchi Shi教授，German University of Technology in Oman的Rudolf Fleischer教授，North South University的Abul L. Haque教授和Shazzad Hosain教授，International Islamic University Malaysia的Normaziah Abdul Aziz教授，以及香港理工大学的曹建农教授，他们为本书英文版书稿的试用和改进提供了以英语为母语或官方语言的平台。感谢Georgia Institute of Technology的Jiaqi Chen同学审阅英文版书稿的部分章节。
　　感谢巴黎第十一大学博士生张一博同学、香港中文大学博士生王禹同学和复旦大学已故教授朱洪先生，他们对于第2版的编写提出了建设性的意见。
　　感谢组织程序设计训练营集训并邀请我使用本书书稿讲学的香港理工大学曹建农教授，台湾“东华大学”彭胜龙教授，西北工业大学姜学峰教授和刘君瑞教授，宁夏理工学院副校长俞经善教授，中国矿业大学毕方明教授，以及中国矿业大学徐海学院刘昆教授等。
　　感谢指出书稿中错误的西安电子科技大学朱微、张恩溶和中国矿业大学徐海学院贺小梅等同学。
　　特别感谢和我一起创建ACM-ICPC亚洲训练联盟的国内同仁，他们不仅为本书书稿，也为我的系列著作及其课程建设提供了一个实践的平台。这些年，我们并肩作战，风雨同舟，如莎士比亚《亨利五世》的台词：“今日谁与我共同浴血，他就是我的兄弟！”
　　由于时间和水平所限，书中肯定夹杂了一些缺点和错误，表述不当和笔误也在所难免，热忱欢迎学术界同仁和读者赐正。如果你在阅读中发现了问题，请通过电子邮件告诉我们，以便我们在课程建设和中、英文版再版时改进。我们的联系方式如下：
　　通信地址：上海市邯郸路220号复旦大学计算机科学技术学院吴永辉（邮编：200433）
　　电子邮件：yhwu@fudan.edu.cn
　　吴永辉王建德
　　2019年10月30日于上海
　　注：本书试题的在线测试地址如下：
　　在线评测系统 简称 网址
　　北京大学在线评测系统 POJ http://poj.org/
　　浙江大学在线评测系统 ZOJ http://acm.zju.edu.cn/onlinejudge/
　　http://zoj.pintia.cn/home
　　UVA在线评测系统 UVA http://uva.onlinejudge.org/
　　http://livearchive.onlinejudge.org/
　　Ural在线评测系统 Ural http://acm.timus.ru/
　　HDOJ在线评测系统 HDOJ http://acm.hdu.edu.cn/
　　

.　　本书系统而全面地呈现了在绘画、音乐、文学等领域中AI算法的研究，充满了逻辑性和实证性，展示了多个突破“图灵测试”的成果。对于AI研究者，这是一本AI艺术研究的“全球旅游指南”。对于艺术家，这本书是客观了解AI能力、利用AI技术提高创作效率和激发突破性创新的加速器。
　　杨静 新智元创始人
　　人类的天才创造力跟数学息息相关，而创造力是进化的根本动力。事实上，只有不断探索生物与机器算法的终极奥秘，才能最终打通大脑与AI的壁垒，世界也将迎来创造力指数级爆发的新纪元。
　　吴靖 北京大学新闻与传播学院教授
　　这是一本解释和探究如何激发AI创造力的书。通过对当下AI最新展示出来的与“创造力”相似的能力，反过来解释什么是人类创造力，以及如何理解这种创造力在人类大脑中产生的模式与结构。
　　肖勇波 清华大学经济管理学院教授
　　如果你对AI的工作机理有兴趣，我推荐你阅读《天才与算法：人脑与AI的数学思维》。作者完全未采用数学语言，却形象生动、通俗易懂地描绘了算法、数学思维和艺术创作之间的关系，值得读者从艺术的视角细细品味！
　　周涛 电子科技大学互联网科学中心主任，教授
　　AI可以从打砖块游戏和下围棋中发现妙招并战胜人类，AI还可以用凡·高的风格作画，用巴赫的风格作曲……书中这些进展让我亦喜亦悲。某一天，AI或许能够创造并教会我们参与更加波澜壮阔的“游戏”；AI或许不再模仿，而是成为我们这个时代的凡·高和巴赫！希望这一天来得晚一些。
　　张江 北京师范大学系统科学学院教授，集智俱乐部、集智学园（北京）科技有限公司创始人
　　创造力是人类智慧最后的阵地，然而机器经过上亿次算法的迭代也可能完成创造它的人类无法理解的艺术创作。《天才与算法：人脑与AI的数学思维》带我们通向人类与机器共同创造之路。
　　赵淦森 华南师范大学计算机学院副院长，教授，博士生导师，广东省青年科学家协会常务副会长
　　数学是AI的理论基础，算法是AI的知识载体，但大部分的人觉得抽象的数学和神秘的算法高深莫测、遥不可及。本书把AI背后的数学、算法、模型、技术和应用逐一展开，娓娓道来，让读者可以从更加生活化的角度来理解它们背后的机理。强烈推荐阅读！