感谢猫冬同学给予我这个再次学习算法的机会,本系列笔记主要以章节形式划分,内容以我认为的重难点及部分习题的探讨为主,希望能给各位带来启发,在此表示感谢!

本书附录A以复习数学知识为主,在下数学水平有限,但此章节内容应该并不难,所以我会将部分我个人觉得比较有意思的课后习题进行整理,我给出的习题答案及过程不一定正确,希望也在看这本书的朋友们能一起探讨,谢谢!


A.1.符号

本节要点:

  1. 上取整、下取整符号

  2. 约等于、不等于符号

  3. 求和符号(级数)

  4. 无穷大符号

A.1.习题:

T2. 在此引入数论中的记号进行证明:

  • 不超过实数x的最大整数称为x的整数部分,记作[x]或INT(x)。 x-[x]称为x的小数部分,记作{x}。

  • (需要注意的是,对于负数,[x]并非指x小数点左边的部分,{x}也并非指x小数点右边的部分,例如对于负数-3.7,[-3.7]=-4,而不是-3,此时{x}=-3.7-(-4)=0.3,而不是-0.7.)

  • 以上定义来自“取整函数_百度百科”

  • A.1.T2

T3. 原命题A.1.T3

考虑,显然:
时,有,且
时,有,且
综上,得证。

T4.
(a) 对n=2k和n=2k+1进行分类.
(b)考虑带余数除法,其中余数为零时显然成立,而余数不为零时,进行整数部分和小数部分的展开,n=ak+t,k=bq+r,左右分别展开到底,注意到,且,因q是整数,则原命题等价于证明。其中,显然小于1,则只要证明也小于1即可,而对于正整数b和小于1的,这显然成立。
综上得证。

T6.(d)用二项式展开。

A.2.函数

本节要点:

  • 一个函数确定一个有序对的集合。
  • 一个函数的曲线是该函数所确定的所有有序对组成的集合。

A.2.习题:

T8. 化简分式,转换为平移问题。

A.3.数学归纳法

本节要点:

  • 数学归纳法可类比多米诺骨牌。
  • P345最下方的方法以前没见过,特此记录。
  • 注意有两种归纳法,见P346 A.4.上方。

A.3.习题

T11.常规3步。

T12.我的想法是先建立正负整数差2n的联系,再使用归纳法。

T13.将步骤三中的2*2^n拆分成两个2^n之和后再缩放,与n^2+2n+1比。

*T14.参考作业帮上的解答,好像比较有技巧。发现立方和公式_百度百科中的证明更有多元性。

A.4.定理和引理

本节要点:略

A.4.习题:略

A.5.对数

A.5.1.对数的定义和性质

本小节要点:

  • 注意:在某些数学领域,比如复变函数中,0的0次幂也被定义为1。
  • 注意P348第6条对数的性质:。用法见例A.8,证明如下:

A.5.2.自然对数

本小节要点:

  • *本小节最后的对于ln n的估计的证明有待补上
    • 右侧的这个不等号可以用x>ln(1+x)轻易得到
    • 左侧的还待查找资料

A.5.习题:

T21.可化简为f(x)=x^3,此书中lg为以2为底数.
T22.考虑同时把等号左右两边作为指数?还是用分类讨论好一些,n是2的整数次幂/n是2的整数次幂减一/其他情况(n比某个整数k次幂小2及以上,且比k-1次幂要大).
T23.应该是直接代入Stirling公式即可.

A.6.集合

本节要点:略

A.6.习题:

*T26.此题的证明应该怎么写比较符合数学?

A.7.排列与组合

本节要点:略,注意一下二项式、排列、组合的具体意义。

A.7.习题

T33.左右分别将组合数展开为阶乘形式
*T35.直接根据提示我没想清楚,考虑从实际意义出发,要注意此题中集合的顺序是有关系的,感觉陷阱在于当连续的多个集合是一样的时候,它们的顺序就消失了。 尝试套了一下组合数的公式,但是找不到对应的意义,此题以后继续考虑。
T36.左右分别将组合数展开为阶乘形式,用到了

A.8.概率

本节要点:

  • 注意结合排列组合的乘法原理、加法原理。
  • P355-356,从“置信度”的角度来理解概率,个体信心的函数,

A.8.1.随机性

本小节要点:

  • 随机事件E的所有基本结果组成的集合为E的“样本空间”,通常是一个有序的元组。
  • “随机”=“不可预测”=不存在一个“特殊”的子序列与整个序列在投注上结果不同,详见P356
  • 即“采样时从来不会偏向任意特定个体”
  • 一个可预测的/非随机过程,当且仅当,允许存在某种成功的赌博策略。
  • 新概念:用“可压缩序列”给出“随机”的严格数学定义 +“不可压缩”==没有更高效的表示方式==随机序列是没有规则或模式的序列
  • 样本数目的多少,决定其结果是否接近真实的总体
  • “将随机过程定义为一定能生成随机序列的过程”当时存在一些困难,据说已解决

A.8.2.期望值

本小节要点:

  • 随机变量被称为“随机”,是因为随机过程可以确定随机变量的值
  • 样本空间中的每一个结果e_i,与一个实数f(e_i)关联,所以,随机变量f(e_i)是抽象的结果e_i的实数量化

A.8.习题

T40.[1/(n+1)](1+2+...+n)=n/2
T41.(1/n)
[(n-1)+...+1+0]=(n-1)/2

本文使用CKEditor将数学公式转换为图片。感谢猫冬同学的指导。