只是随便写写3月份以来的各种经历. 按时间顺序是北大数学, 软件所, 北大信科.
点估计——最大似然估计、最大后验概率估计和贝叶斯估计
在北大听xlr老师的《经济与计算》课程时有一个小问题没有搞明白, 课后花了一些时间, 算是复习了之前数理统计学的MLE, 顺便研究了一下MAP和Bayes估计.
一枚硬币，掷14次，有10次正面向上. 请估计接下来两次都出现正面向上的概率. (如下图所示)
算法拾遗[5]——Java大数
比较重要的几条是:
add, subtract, multiply, divide, mod, remainder加减乘除取模取余—注意取模中 \(b\) 必须为正!a.compareTo(b)\(a=b\) 返回 \(0\), 否则返回 \(a>b\) 的值.a.toString(b)将 \(a\) 转换为 \(b\) 进制字符串.
另外注意 Scanner 的写法:
- 输入接口:
Scanner cin = new Scanner(System.in); - EOF写法:
while(cin.hasNext()) {} - 输入:
BigInteger a = cin.nextBigInteger();
以及变量的声明(注意 new):
- 单个变量:
BigInteger a = new BigInteger("0"); - 声明数组:
BigInteger a[] = new BigInteger[size]; - 静态方法:
BigInteger a = BigInteger.valueOf(x);
算法拾遗[1]——动态规划
夏令营复习算法, 感到自己对之前学过的算法略有生疏, 写篇流水账, 权当复习.
- 最长上升子序列
- 最长公共子序列
- 最大子段和与最大子矩阵
- 背包问题
- 合并石子/矩阵链乘
- 一些其他的题目
论文笔记[2]——AKS素性测试
文章: Agrawal M, Kayal N, Saxena N. PRIMES Is in P[J]. Annals of Mathematics, 2004, 160(2):781-793.
文章分为正确性和复杂度两部分:
- 正确性: 素数显然会返回
PRIME, 只需证返回PRIME的是素数. 返回素数的地方只有Step 2和Step 6, 分别讨论之.Step 4: 若 \(n\) 是合数则会在Step 3中返回, 矛盾.Step 6: 分段考虑.- 先考虑
Step 2中 \(r\) 的范围, 可得 \(r\leqslant\lceil\log^5n\rceil\). - 定义多项式之间的关系introspective: \([f(x)]^m=f(x^m)~({\rm mod}~x^r-1,p)\), 则该性质对 \(m\) 和 \(f\) 都满乘积性质.
- 由于在
Step 5没有返回COMPOSITE, 故 \(\frac{n}{p},p\) 对 \(x+a\) 是introspective的. 故 \(\frac{n}{p}\) 与 \(p^j\) 的任意乘积对 \(x+a~(0\leqslant a\leqslant l)\) 的任意乘积是introspective的. - 进一步, 通过建立两个群 \(G\) 和 \(\mathcal{G}\), 可得到 \(|\mathcal{G}|\) 的下界和一个由条件的上界. 并可最终得到 \(n=p\), 即 \(n\) 是素数.
- 先考虑
- 至此算法正确性得证.
- 复杂度: 逐步分析可知
Step 5复杂度最高, 为 \(O^\sim(\log^\frac{21}{2}n)\).