2018-2019年度市级骨干教师读书心得——信息技术教研组（四）

 

《数论及应用》读书笔记

江苏省江都中学   学科带头人   陈忠（1）

【阅读书目】

《数论及应用》

主编：陈宇

【书目简介】

《数论及应用》系统地介绍了初等数论中最基本、最常用知识和算法，并根据具体的实例来编程实现，在介绍数论基本知识的同时，注重学习方法和实践技巧的讲解。全书共分7章：第1章介绍了数的整除性问题，包括最大公约数及欧几里得算法的实现；第2章主要介绍了素数的定义、性质及分布情况，同时介绍了几种素数判定方法和梅森素数；第3章主要介绍了同余问题的基本概念及求解同余线性方程组；第4章主要介绍了不定方程的解法与一些特殊的不定方程的处理方法；第5章主要介绍了威尔逊定理、欧拉定理、费马小定理三大定理的应用，并给出了素数测试技巧；第6章主要介绍了一些乘性函数，包括欧拉函数、素因子分解和乌斯函数以及莫比乌斯反演公式等问题；第7章主要介绍了初等数论在密码学中的应用问题。此书覆盖了初等数论算法所需的知识点，并附有大量的应用实例。书中的代码规范、简洁、易懂，不仅能帮助读者理解算法原理，还能教会读者很多实用的编程技巧。

【阅读有感】

数学一直是我在信息学奥林匹克竞赛辅导中的短板，特别是当猜想到一个结论时，得不到相关数学的佐证时，心情特别沮丧。有关程序方面的数学，ACM-ICPC丛书还有组合数学、计算几何等，目前从当前的这本《数论》看起，补上这一课。

迄今我刚刚看了其中第一、二章，第一章主要介绍的是整除的基本性质及相关证明，其中一个例题：斐波那契的整除。题目很简单，但数据范围很大，数据n是[1，1000000000]的，一般解法在规定的时间内是不能求解的，必须要用到数论知识。让我想到以后自己在设计题目时，可以用一些常规题，设定其数据范围，让学生必须用到数论的相关知识。由计算最大公约数和最小公倍数的基本算法辗转相除法，再到扩展的欧几里得算法、拉梅定理及推论，让我知道了辗转相除法的“真髓”，在这一节的最后还用了poj网站上的两个题目加以巩固应用。

第二章重点是有关素数的问题。从素数的性质介绍到素数的分布及猜想，同样的也用了一个大数据量的题目让我认识到数论的重要性。键盘输入n，计算小于10的n次方的素数的个数值共有多少位，而n的范围在[1,1000000000]，且是多组数据。这么大的数据量，用以往的常规求素数、线筛、埃氏筛都不能正确求解，充分体验了数学的强大魅力。此外还介绍了比埃氏筛更加强大的6N±1法筛选，真是涨了见识。第三四节讲了算术基本定理和梅森素数及其应用。梅森素数的两个判定方法没有看懂，需要进一步继续阅读，向专家请教。

 

《算法竞赛进阶指南》读书心得

江苏省江都中学   学科带头人   陈忠（2）

【阅读书目】

《算法竞赛进阶指南》

作者简介：李煜东，2017年本科毕业于北京大学信息科学技术学院计算机科学专业，2012年CCF-NOI全国信息学奥林匹克竞赛金牌得主、国家集训队队员，2015年ACM-ICPC国际大学生程序设计竞赛亚洲区域赛冠军、入选世界总决赛，NOI 2015命题人、学生专家，NOI 2014冬令营讲师，ACM-ICPC2016亚洲区域赛北京站命题人、裁判。

　　曾为NOI系列竞赛、NOI导刊培训基地以及全国各地多所学校的选手授课，并在网络上组织模拟赛数十场，经验丰富、讲解透彻、广受好评。多次协助石家庄市第二中学的信息学竞赛集训工作，参与北京大学“数据结构与算法”“算法设计与分析”的课程教学、考试命题工作。

【书目简介】

《算法竞赛进阶指南》主要根据CCF-NOI信息学奥林匹克竞赛涉及的知识体系进行编写，对计算机程序设计的基本技能——数据结构与算法进行了深入的讲解。

此书面向已经掌握至少一门程序设计语言、对于算法设计有入门性认识的读者，以各类知识点之间的贯穿联系为主线，通过各种模型与例题对各种思维方向进行深入引导，让读者在阅读本书后对算法设计初步具有整体掌控性的理解。能够让读者由浅入深地体会算法，学习算法。

此书融合了作者在算法设计教育领域、算法竞赛参赛与指导领域10年来的一线经验，其特色是训练读者算法设计的思维习惯，而非对知识流水的记忆性诵读，能让认真阅读此书并完成所有练习的读者，逐渐具有NOIP竞赛一等奖以上的实力。

【阅读有感】

随着联赛难度的逐年递增，不断觉得自身现有知识结构体系有待丰满，而此书恰好满足了我的需求，特别是对竞赛知识体系的梳理特别到位。主要有三点感触：

1.从知识点到算法模型逐级扩展，由浅入深，举一反三

一般来说对算法的理解有三个层次，第一个层次是弄得懂算法的基本原理，第二个层次是写得出课堂实例代码，第三个层次是理解算法思想并能够灵活运用算法，但是达到第三层次的是比较艰难的。而此书用具体的题目实例导入算法，让算法不再是孤立的代码，方便学生理解记忆。难能可贵的是此书还用不同的实例深入探讨分析算法，从不同角度去研究算法，从而让学生更加灵活掌握算法。每章末尾的知识清单，将本章的知识点大纲自成体系构成框架，可作为用来自检所学内容。

2.课后练习，提供细致的长期训练指南，量的积累，质的飞跃

    让我倍感贴心的是，这本书还结合目前主流OJ，如北京大学的POJ（http://poj.org/）、浙江大学的ZOJ（http://acm.zju.edu.cn/）、杭州电子科技大学的HDUOJ（http://acm.hdu.edu.cn/）、华中科技大学的HUSTOJ（http://acm.hust.edu.cn/）。从中精选了300多道有代表性的题目，标注在线地址，课余我也会在线刷题，提高实战能力。遗憾的是很多在线网站是英文题面，比较难办。

3. 切中要点，巧妙引导思维体系的构建

注重传授“思想”，拒绝照本宣科灌输经典算法。这本书还通过实例展开分析，建立数学模型，将多个算法融合一体。比如对于动态规划算法的讲解，从基本的模型分类，再到时间空间的优化等等，通过同一题，不同的数据范围，逐层深入，逐步优化，将整个知识点整合成一个相互关联的整体。

 

《图论及应用》读书笔记

江苏省江都中学   学科带头人   陈忠（3）

【阅读书目】

《图论及应用》

主编：冯林

【书目简介】

《图论及应用》是ACM-ICPC程序设计系列丛书之一。主要介绍ACM-ICPC比赛中涉及的图论，其中包括许多实际问题的抽象表示与求解，以及部分图论理论内容的证明。全书共分6章，第1章介绍了图论的基础知识，包括基础概念、存储方法和遍历方法；第2章介绍了有关树的问题，着重讲解生成树和一些树上特殊点集的求法；第3章介绍了最短路径问题，包括几种通用算法和特殊图上的算法；第4章介绍图论中有关连通性的问题，包括有向图的强连通、无向图的双连通及其扩展问题；第5章介绍网络流解法，包括几种常用的网络流算法和对于问题如何抽象成网络流模型的经验方法；第6章介绍二分图的相关问题，重点为二分图的匹配及其变种问题。

【阅读有感】

本书补充了我以往noip训练中图论知识部分的盲点，无论是基本概念还是算法应用，都有较大的提升。概念：完全二部图、补图、同构以及同构的性质（对称性和传递性）……。

在一般竞赛丛书中将树和图都是作为独立章节存在，而此书中将树和图联系起来讲解。树的基本概念的定义就是：连通无回路的无向图是一棵树，使得各知识点得到了横向联系。还讲了树的最小支配集，最小点覆盖与最大独立集等概念，以及用贪心法和树形动态规划求相关解的代码，辅以习题巩固。

再比如，以往学习了图论的缩点方法，从未想过展开收缩点，在这本书中也有具体的讲解，以图配合文字讲解对应相关代码，便于理解，在书后还有相关例题，遗憾是此题只有题目，没有数据。

特别是第四章连通性问题和第五章网络流，一直是我知识体系中最薄弱的环节，一直是一知半解的状态，而这本书系统的讲解了强连通分量的三个算法：Kosaraju算法、Tarjan算法、Garbow算法，书中的算法思路以及伪代码框架的讲解辅以源代码，再加上例题练习，让我对这部分的三个算法终于有了较深刻的认识，并能够迁移。

此书目前还未看完，后面的最小点基、双连通、全局最小割以及Stoer-Wagner算法还在阅读中。

总之这本书，将会再次阅读，以上只是从书中得到的一些粗浅认识。需要反复阅读。