Homework 4

Problem 1

由题目条件知

下考虑证明命题

显然我们能够找到充分大的 ，满足

2. 命题对 的情况都成立

下面设命题对 的情况都满足，则对于 的情况

由于

得到

因此命题对 的情况也成立，由数学归纳法知命题对所有 都成立

综上，证毕

Problem 2

(1)

(2)

我们首先关注矩阵表示意义下 的图论含义，

因此， 的值即与 均建边的点的数量，那么含 的三角形数量就为

考虑到按边统计会对每一个三角形统计三次，另一方面 和 又会重复统计，因此

于是得到目标算法

可见其总体复杂度为

Problem 3

这里我们利用 的 算法。考虑先找小一些的团，其大小控制在不大于 ，随后再通过这些团组成的新图中的三角形得到目标的 。具体的算法如下

首先分析这个算法的正确性：我们需要证明原图中存在 当且仅当算法输出

首先，如果算法输出 1，则必然存在三个满足

1. 顶点不重合
2. 相互完全建边
3. 点数之和为 的团，他们合并起来即为一个

另一方面，如果原图中存在 ，那么将其任意拆分为大小为 的三个不相交点集，他们都构成一个小的团且满足上述的三个性质，因此必然会被上面的子集遍历分别捕获并在最后被找到，因此算法将输出 1

下面我们分析这个算法的复杂度，由于没有分治（小的团用了暴力判断方法），分析是比较直接的：

对每个 ，遍历子集的复杂度为 ，而 的设定严格保证了

且

因此

故这一部分的复杂度为

每个子集内部的判定复杂度为 ，在这一问题中相当于常数，故这一部分的复杂度为

接下来看 算法，每个 的最差情况超顶点（即大小为 的一个团）数为 ，而每两个超顶点之间的建边判定复杂度为 亦为常数

因此，调用三次 的复杂度为

最后，调用 算法，由 Problem 2 得到这一部分的复杂度为

综上，总复杂度为

证毕

Problem 4

(a) 即 7 的原根，可以取 ，此时

且

(b) 先写出所需的矩阵

则 Fourier Transform 的目标结果即为

(c)

此时

但我们还需要施加 这一变换，在同余意义下相当于乘以 的数论倒数 ，得到

那么我们考虑

即见回到了原系数

(d)

依据题意，这里使用正常的傅里叶变换。

由题：

则

最后进行插值

因此最终的系数向量即

直接验证：

在模 7 意义下与上求得的 相吻合