就像写程序一样，我的定理被不断重构，不断升级，最后变成了一座山峰。

 

 

第一章 基础：逻辑和证明

 

比较好的地方在于讨论了很多证明，这些是智力小游戏。比较快乐的是骑士骗子与平民游戏。

 

1.试讨论逻辑悖论，包括克里特人Epimenides悖论，Jourdain的纸牌悖论，理发师悖论。

2.模糊逻辑是什么？怎样用于实际应用？

3.实际问题中可满足性问题的建模。

4.不必借助计算机解决数独谜题的技巧。

5.由Layman Allen提出的“WFF’N PROOF, The Game of Modern Logic”的基本规则，给出一些博弈示例。

6.Lewis Carroll关于符号逻辑的一些著作，描述他用于表示逻辑论证的模型和用于论证的推理规则。

7.Prolog的讨论，解释如何使用消解规则。

8.计算逻辑中的技术，Skolem规则。

9.“自动定理证明”的目标和应用，以及开发自动定理证明器的进展。

10.如何使用DNA计算来求解可满足性问题的示例。

11.查找著名的开放问题的错误证明，1970年以来被解决的开放问题，描述每个证明中的错误类型。

12.讨论蚕食游戏中已知的一些获胜策略。

13.George Polya关于推理的著作中所讨论的证明策略（见该页参考论文）

14.用多联骨牌进行拼接的一些问题和结果，如在文章（该页论文）中描述的那样。

 

 

第二章 基本结构：集合、函数、序列、求和与矩阵

 

比较关键的是SB定理，康托尔定理，连续统假设。

 

1.公理化集合ZFC来避免罗素悖论

2.函数这个概念最早是出现在什么场合？当时是如何应用这个概念的？

3.解释《整数序列大百科》的巨大作用。描述其中一些非比寻常的队列。

4.定义最新提出的EKG序列并描述它的某些性质及一些问题。

5.超越数：What，Why存在，How构造，哪些数是超越数，哪些不是。

6.连续统假设的继续讨论。

 

 

第三章： 计数

 

比较关键的是掌握Cnm，多项式定理，帕斯卡定理，范德蒙德恒等式。拓展是康托尔展开式。

 

1.描述狄利克雷和其他数学家对鸽巢原理的应用。

2.目前电话编码计划的方式、如何应对更多的电话增长需求。

3.组合推理在基因测序和基因组相关问题的重要性。

4.探讨更多的组合恒等式和他们的代表性证明。

5.统计力学中质点分布所使用的不同的模型：麦克斯韦—玻尔兹曼、波色—爱因斯坦和费米—狄拉克统计，描述每种情况下所使用的计数技术。

6.定义第一类斯特林数并描述他们的性质和满足的恒等式。

7.描述第二类斯特林数并描述他们的性质和满足的恒等式。

8.描述拉姆齐数及最新发现。

9.描述生成n元素集合所有排列的其他算法，比较他们的算法复杂度。

10.至少描述一种方法生成一个正整数n的所有的部分。

 

 

第四章： 高级计数技术

1.找出斐波那契发表的关于兔子数模型难题的原始材料。讨论斐波那契提出的这个问题和其他问题，并且给出关于斐波那契本人的某些信息。

2.解释斐波那契数怎样在其他应用中出现，如叶序、植物叶片排列的研究、镜子反射的研究等。

3.描述汉诺塔难题的多种不同的变形问题,包括多于3个柱子的(包括课本和练习中讨论的雷夫难题在内)、盘子移动受限制的以及允许有同样大小盘子的。关于求解每种变形问题所要求的移动次数有什么已知的结论?

4.尽可能多地讨论出现卡塔兰数的不同问题。

5.讨论理查德·贝尔曼首先使用动态规划的一些问题。

6.说明动态规划算法在生物信息学中的作用，如 DNA序列比较、基因比较和RNA结构预测。

7.说明动态规划在经济学中的应用，包括优化消费与存款的研究。

8.解释动态规划如何用于解决鸡蛋掉落问题，即确定从多层建筑物的哪一层鸡蛋能安全掉下而不摔坏。

9.描述派尔克发现的与一次谎话搜索相关的乌拉姆问题的解。

10.讨论派尔克发现的与多次谎话搜索相关的乌拉姆问题的变种，关于这个问题你还知道什么?

11.定义平面上一组点集的凸包并描述三个不同的发现平面上一组点集的凸包算法，包括分治算法

12.描述在数论中使用的筛法。使用这种方法已经得到了哪些结果?13.查询古代法国纸牌相遇游戏的规则。描述这些规则并描述皮埃尔·雷蒙德·蒙特莫特关于“相遇问题”的论文。

14.描述怎样使用指数生成函数求解各种计数问题。

15.描述计数的 Poly 理论和可使用这个理论求解的计数问题的种类。

16.管家问题是求解安排n对夫妇围圆桌就座的方法数，使得就座时男女相间并且没有丈夫和妻子相邻。

解释怎样用卢卡斯(E.Lucas)方法求解这个问题。

17.解释怎样使用棋盘多项式(rook polynomial)求解计数问题

 

 

 

第五章： 关系

 

1.讨论模糊关系的概念。怎样使用模糊关系?

2.不限于 5.2节所介绍的内容，描述关系数据库的基本原理。关系数据库与其他类型的数据库相比，使用范围有多广?

3.查找沃舍尔和罗伊(Roy)的原始论文(法文)，在那篇论文中他们提出了求传递闭包的算法。讨论他们的方法。为什么可以认为我们称为沃舍尔的算法是被多人独立发现的?意会

4.描述怎样用等价类把有理数定义为整数对的类，遵照这种方法怎样定义有理数的基本算术运算。

5.解释赫尔姆·哈塞是如何使用我们现在称为哈塞图的图。

6.描述在计算机操作系统中用来执行信息流策略的某些机制。

7.讨论计划评审技术(Program Evaluation and Review Technique，PERT)在安排一个大的复杂项目的任务中的应用。PERT的使用范围有多广?

8.讨论关键路径方法(Critical Path Method，CPM)在找出完成项目的最短时间中的应用。CPM 的使用范围有多广?

9.讨论格中的对偶性的概念。解释怎样用对偶性建立新的结果?

10.解释模格的意义。描述模格的某些性质，描述模格是怎样在投影几何的研究中产生的。

 

 

第六章： 图

 

1.描述在1900年以前图论的起源和发展。

2.讨论图论在生态系统研究中的应用。

3.讨论图论在社会学和心理学中的应用。

4.讨论通过研究网络图的性质可以了解到什么?

5.解释在表示网络的图中，如社交网络、计算机网络、信息网络或生物学网络，社团结构是什么?定义在这些图中的社团是什么?并且解释在表示所列的网络类型的图中，社团表示了什么。

6.描述一些用于在表示第5题中所列网络类型的图中，社团发现的算法。

7.描述给定一个图的顶点和边，在纸面或屏幕上画出这个图的算法。在画图中需要考虑什么，使得其最好地显示了该图的属性。

8.通过学习相关的社交网络和通信网络，解释图论如何帮助发现犯罪或恐怖网络。

9.一个输入、显示和操纵各种图的软件工具应当具有什么功能?现有的工具都具有这些功能中的哪些?

10.描述确定两个图是否是同构的一些可用算法和这些算法的计算复杂度。目前已知最有效的算法是什么?

11.什么是子图同构问题及其在化学、生态学、电子电路设计和计算机视图等方面有哪些重要应用?

12.解释什么是图挖掘(它是数据挖掘的重要领域)，并说明图挖掘中的一些基本技术。

13.描述如何用欧拉通路来帮助确定DNA序列。

14.定义德布鲁因序列并且讨论它们如何出现在应用中。解释如何用欧拉回路来构造德布鲁因序列

15.描述中国邮递员问题并且解释如何解决这个问题。

16.描述表明图具有哈密顿回路的一些不同条件。

17.描述用来解决旅行推销员问题的几个不同策略和算法。

18.描述判定一个图是否是平面图几个不同算法。每个算法的计算复杂度是什么?

19.在建模中，有时把超大规模集成电路(VLSI)图嵌人到一本书中，让顶点都在书脊上而边都在不同的书页上。定义图的书页数并对n=3，4，5和6求包括K，在内的各种图的书页数20.描述四色定理的历史。

21.描述在四色定理的证明中计算机所扮演的角色。如何肯定一个依赖计算机的证明是正确的?

22.就是否产生最少颜色的着色以及复杂度而言，描述并比较给图着色的几个不同算法。

23.解释在各种不同模型中如何使用图的多重着色。

24.描述边着色的应用。

25.解释如何将随机图理论应用在带特定性质的图的非构造性存在性证明中。

 

 

第七章： 树

 

1.凯莱如何用树来枚举

2.解释在研究进化论时，如何使用树表示祖先关系。

3.讨论分层的簇树以及如何使用它们。

4.定义 AVL树(有时也称为高度平衡树)。解释如何以及为什么在许多不同的算法中都用到 AVL树。5.定义四叉树并解释如何用四叉树来表示图像。描述如何通过操纵对应的四叉树来旋转、缩放和转换图像。

6.定义一个堆，并解释如何把树转化成堆。堆为什么在排序中有用?

7:描述针对连续读人字符时字母频率发生变化的数据压缩的动态规划算法，比如自适应哈夫曼编码,

8.解释如何用a-8剪枝来简化对博弈树的值的计算。

9.描述下棋程序(比如深蓝)所使用的技术。

10.为树网这种类型的图下定义。解释这种图如何用在非常大的系统集成和并行计算中。

11.讨论在IP组播中避免路由器之间回路所用的算法。

12.描述基于深度优先搜索来求图的断点的算法。

13.描述基于深度优先搜索来求有向图的强连通分支的算法。

14.描述在Web上不同搜索引擎的网络爬虫和网络蜘蛛所用的搜索技术。

方

15.描述求图的最小生成树的算法，使得生成树上任意顶点的最大度数不超过一个固定的常数k。

16.就复杂度和应用场合而言，对一些最重要的排序算法进行比较。

17.讨论构造最小生成树的算法的历史和起源。

18.描述产生随机树的算法:

 

 

第八章： 布尔代数

 

奎因—莫可拉斯基方法，隐含，布尔函数

 

1.描述早期设计的、用来解逻辑问题的机器，如Stanhope Demonstrator, Jevons的逻辑机，Marquand Machine。

2.组合电路和时序电路的区别，如何用触发器构造时序电路。

3.移位寄存器，如何使用trigger和logic gate构成移位寄存器。

4.构造乘法器。

5.逻辑门的物理构造。在构造电路时，是否要用到NAND和NOR门？

6.用相关性记号描述复杂的开关电路。

7.使用乘法器构造开关电路。

8.用阈值门构造半加器和全加器，解释其构造优点。

9.描述无危险开关电路的概念，给出设计此类电路的原则。：这个东西就是电路，然后各种元件。（完成）根据输入的电压值决定电路是否断开吧

10.卡诺图将六元函数极小化。

11.极小化布尔函数的新方法（如Espresso方法）的思想，解释用这种方法解决高达25元的布尔函数最小化的问题。

12.n元布尔函数的函数分解的含义，讨论他们分解的过程。（完成）

 

EOF