[第1课] 质数判定

主题:数百年前,伟大数学家欧拉和高斯都曾被质数问题困扰过。如何通过一种简单规律描述质数,至今仍是一个未解之谜。

[第2课] 运行时间

主题:由于质数判定仍然需要计算机来帮助实现,这一节讲解了计算机判定质数和进行质因数分解需要多少时间。

[第3课] 计算存储空间

主题:由于在计算机中,时间和空间存在权衡取舍,这一节讲解了计算机判定质数和进行质因数分解需要多少空间。

[第4课] 算法效率

主题:美国正要派遣新的探测器到火星,而视频作者他们需要为探测器编写质数相关算法,由于限制,这就需要考虑效率问题。

[第5课] 埃拉托斯特尼筛法

主题:埃拉托斯特尼筛法是一种给出小于某数字的所有质数列表的算法,这一节通过例子讲解了这一算法。

[第6课] 筛选判定质数

主题:如果算法中先通过筛选将质数列表列好,然后再通过试除法,这样的效果还没有直接通过试除法好。这一节详细讲解了为何如此。

[第7课] 质数定理

主题:质数定理也就是对正实数x,定义π(x)为不大于x的质数个数,那么π(x)≈x/lnx。这一节详细讲解了这一定理的由来。

[第8课] 时间空间权衡

主题:如果将质数列表事先存好,然后再通过试除法进行。由于质数很多,这势必需要大量空间,时间和空间是存在权衡取舍的。

[第9课]随机化算法

[第10课] 条件概率直观解释

主题:这一节讲解了条件概率和贝叶斯定理。通过一个直观的抛硬币例子,讲解了这些问题。

可汗学院公开课:计算数论

学校: 可汗学院

讲师: Salman Khan

集数: 10

授课语言: 英文

类型: 可汗学院 数学

课程简介: 这部分课程的主讲人以美国国家航空航天局(NASA)所发射的新火星探测器及相关程序为背景,讲解了信息如何传播、如何加密以及相关问题。这就自然而然地引出了应用数学这部分所包括三个内容:一是信息论、二是密码学、三是计算数论。信息论是关于信息的理论,而信息的传播又离不开加密,加密的主要方法目前又是通过数论、质数这方面的知识来实现,这三部分内容有机地结合起来形成应用数学这部分内容。
视频由可汗学院免费提供)