符号含义 E 表示满足椭圆曲线Weierstrass方程上的点群 K 域，用来限制Weierstrass方程的系数与E中的点 E(K) 定义在K上的点群E E/K 定义在K上的椭圆曲线E End(E) E上的自同态环End(E)模与Z代数 极点首项系数 除子映射及同构 同种映射同态性的解释 Hasse定理之引理证明的补充 挠曲线及其个数 有限域上的椭圆曲线 一种确定型群阶计算法 奇素域上的算法应用 GF域上的群阶计算 Schoof算法正确性根本 一种计算椭圆曲线群的阶的确定型多项式时间算法，确定型是因为算法内部没有随机选择/概率抛币操作，多项式时间是因为域k的乘法与求逆总次数是O((logq)^6)（q为k的大小，乘法与求逆相对加减运算显著耗时）。具体原理及流程详见参考文献[1]中5.2节。这里给出笔者的一些思考​ 1. Hasse定理（Frobenius自同态方程式）在扭点群上的限制亦成立，这决定了t模l的一个同余方程成立，且在模l的最小非负剩余系下解是唯一的​ 2. 孙子定理保证了某取值范围内的一个t模L（L为各素因子l的乘积）的 ...继续阅读 (13)

原本算法 摘抄参考文献1中附录的算法流程如下 例子测验 改正后的算法 改正之前，先理清原本算法判别不可约多项式所用的原理。其原理是若f(x)可约，当且仅当存在次数i<=d=[deg(f(x))/2]的不可约因子g(x)，而此时gcd(xq^i-x, f(x))≠1。 根据参考文献2（详见如下定理），xq^i-x是所有i次不可约多项式的乘积，因此它必定包含g(x)而与f(x)存在公因子。不可约判别算法的思想应该是遍历次数1到d的所有不可约多项式 （没必要检测大于d的不可约多项式，因为若f(x)可约则其分解因子中必定存在不大于d的不可约多项式），检测输入多项式与它们是否存在公因子。所以这个原理是正确的，只是实现不对， 略作改正如下（类c语言描述） 重新测验 参考文献 [1] 算法数论 裴定一、祝跃飞 [2] 代数学基础与有限域 林东岱春秋十二月2024-09-07 23:07发表评论 ...继续阅读 (40)

定义 Berlekamp分解算法 AES有限域 不可约性证明 非本原性验证 找出本原元 不可约多项式个数 线性移位寄存器m序列 根据参考文献1知线生移位寄存器产生m序列的充要条件是特征多项式f(x)为本原多项式。而确立有限域上的本原多项式，主要有两种方法： 一种方法是根据Fq上所有次数为n的本原多项式的乘积正好等于割圆多项式Qe，其中e=qn-1，从而所有次数为n的本原多项式可以通过分解Qe得到。 另一种方法是通过构造本原元再求本原元的极小多项式，先素因子分解qn-1=p1p2...pk，如果对每一pi都有ord(αi)=pi，那么α=α1α2...αk的阶就是qn-1， 因此是Fq上的本原元，则f(x)=(x-α)(x-α2)...(x-αr)，r=qn-1（因为α是本原元，所以n是使αq^n=α成立的最小正整数）。 求解本原多项式 假设线性移位寄存器的级数为4，这里使用上述第二种方法求F16上的本原多项式，过程如下 本原多项式个数 m序列示例 参考文献 ...继续阅读 (66)

经典的复杂性关系 P是多项式时间确定型图灵机可识别的语言类，NP是多项式时间非确定型图灵机可识别的语言类，NPC表示NP完全问题类，coNP表示NP的补，coNPC表示NPC的补。确定型图灵机是一种从不选择移动的特殊的非确定型图灵机，故自然有P属于NP coNP、coNPC的定义之集合表述 上面顶部的图有个假设前提是：coNPC不属于NP，即我们相信NP完全问题的补都不属于NP。但当P=NP或NP=coNP时，可以发现coNPC属于NP ◆ 为什么coNPC属于coNP？ ◆ 为什么NPC 不属于coNP？ ◆ 为什么P属于coNP? ◆ 当P=NP时，为什么NP=coNP？ ◆ 当NP=coNP时，为什么NPC=coNPC？ 前文的关系演变图没考虑多项式空间问题类PS与递归问题类（因为那两个条件不会影响到它们），PS（NPS）是带多项式空间限制的确定型（非确定型）图灵机可接受的语言类，但不限制运行时间可能需超多项式或指数时间，在外围加上PS与递归语言类后如下 ◆ 为什么coNP 属于PS？ 零知识复杂性关系 BPP是可被概率多项式时间图灵机(即随机化算法)识别的语言类，IP是所有具有交互证明系统的语言构成的类，等于多项式空间语言类即前文经典复杂性关系中的 ...继续阅读 (82)

【定理】设多项式，其中q是某个素数的方幂，Fq为有限域，则 若是置换多项式，则【证明】 春秋十二月2023-12-16 21:49发表评论 ...继续阅读 (66)

几何散列(几何哈希,Geometric Hashing)是一种最初在计算机视觉中开发的, 用于将几何特征与这些特征的数据库相匹配的技术, 可用于许多其他领域。 即使可识别的数据库对象经历了变换或仅存在部分信息, 也可以进行匹配。 该技术高效且多项式复杂度低。 ...继续阅读 (68)

1.对于rsa，给定大整数n分解的一对素因子p和q，p或q是否素数决定不了rsa的安全性，但决定rsa算法的正确性，也就是说p或q不能为合数，而安全性取决于n的位数及p、q的距离，因为素数测试是一个P问题，而因子分解是一个NP问题，其耗时是关于n的指数2.对于dh密钥交换，通常选择阶为素数的有限循环(子)群，这时素数决定了安全性。因素数不能再因子分解，故避免了针对阶为合数的质因子分解且利用中国剩余定理求离散对数的(已知最好)攻击3. 周知Shamir门限方案基于多项式的拉格朗日插值公式，普遍的设计采用GF(q)域上的多项式，秘密s为f(0)，q是一个大于n的大素数（n是s被分成的部分数）。正常来讲，参与者个数必须至少是设计时的k，才能恢复出正确的s。如果个数少于k比如k-1，则只能猜测s0=f(0)以构建第k个方程，那么恢复得到的多项式g(x)等同设计时的多项式f(x)的概率是1/q。因为g(x)的项系数可以看作关于s0的同余式即h(s0)=(a+b*s0)mod q的形式，因q为素数，故依模剩余系遍历定理，当s0取GF(q)一值时，则h(s0)唯一对应另一值。所以h(s0)等于f(0)的概率为1/q。由此可见，当q取80位以上，敌手攻击概率不大于1/2^80，这已经很低了。这种门限方案如同RSA加密，再次佐证了素数越大安全性越高4. PGP是密码学经典应用，体现在首先支持保密与认 ...继续阅读 (95)

有理数域的本原多项式与有限域的本原多项式定义不同，前者不要求不可约（由高斯引理知两个本原多项式的乘积还是本原），后者则必须不可约（确保生成的有限域其每个元素有逆元）。aes基于有限域F{0,1}设计，故使用的模8次多项式不可约P(x)=x^8+x^4+x^3+x+1，但不是本原多项式，因为它的阶是51而非255。有限域次数为8的本原多项式有16个、不可约多项式有30个（由莫比乌斯反演推出），具体多项式影响s盒与列混合操作的实现。不可约加之0的逆元规定为0，保证正确加解密。若0的逆元规定为非0比如x，则导致x有两个逆元，便违反了逆元唯一性，除非s盒不用有限域设计。逆元等于其自身的非0元素只有1，原因可类比模素数二次剩余的求解春秋十二月2023-09-13 02:00发表评论 ...继续阅读 (111)

因为一个整数p，若检测为合数，这永远是真命题；而检测为素数，这命题只以较大概率成立。 可构造一种NP检测算法，步骤如下：1. 猜测p（位长度n）的因子列表｛p1,p2,…pi｝，这是非确定的，每个分支耗时O(n)2. 验证p1*p2*…pi？=p-1，耗时不超过O(n^2)3. 若各因子乘积等于p-1，则用当前算法递归验证每个因子都是素数4. 随机选择p最小剩余系内的一个数x，计算x^((p-1)/q) （q遍历上述列表经过步骤3验证过的素因子）是否都不同余于1模p，若是则必有x^(p-1)同余于1模p，则由指数整除p的欧拉数及费马小定理，知p为素数，考虑到有少量的合数也满足费马小定理，故需多次选择x重复验证，选择个数最多为log(p)分析：本算法涉及的数论定理——设p是奇素数，p-1的所有素因子是q1,q2,…qs，那么g为原根的充要条件是，g^((p-1)/qj)不同余1模p，j=1,2…,s结论：第3步可以看成递归调用树，每个顶点为待检测整数，其每个子结点为一个因子，则最多n层，每层至多耗时O(n^4)，所以每个路径即检测p是否素数的非确定任一分支中，总耗时O(n^5)。 2002年，印度科学家发现素检测确定性多项式时间算法，于是从NP前进到了P春秋十二月2023-09-09 08:07发表评论 ...继续阅读 (95)

周知aes有限域同构于系数为F2域一元多项式环的商环，其理想由不可约多项式m(x)=x^8+x^4+x^3+x+1生成，即F2^8≌F2[x]/(m(x))。这次进一步用域扩张的观点分析，可以得知F2[x]/(m(x))正是包涵m(x)零点的扩域，设为K。那么如何理解？令I=(m(x))，则K=F2[x]/I，理解关键是找出m(x)在K上的零点，以及K怎样包涵F2？1. 零点为~x。这里用~g(x)表示多项式在K中的陪集，即~g(x)=g(x)+I，所以~x=x+I。把~x代入m(x)，根据商环定义的加乘运算，代换结果为m(x)+I=~m(x)=~0（~0是K的零元）。那么还有吗？比如~(x+a)（a非0），~x^2，代入这些得到的陪集代表不等于m(x)，所以不是零点。因此零点是唯一的一次多项式x之陪集​2. 构造映射σ，把0对到K中的零多项式即~0，1对到K中的常数多项式即~1，且σ(0+1)=~1=~0+~1=σ(0)+σ(1)，σ(0*1)=~0=~0*~1=σ(0)*σ(1)，又依多项式比较法则得~0不等于~1，故σ是单同态，K包涵F2​小结：商群、商环、商域类似模同余之剩余系，理解这些结构的关键是深入理解等价类、陪集，进而可理解正规子群、理想，最后就是商X之 ...继续阅读 (71)

定理：令K[x]是由次数小于8、系数为0或1的多项式组成的环，m(x)=x^8+x^4+x^3+x+1为不可约多项式，则K[x]/(m(x))（模m(x)剩余类环）同构于元素个数为256的有限域F证明：​1. 构造映射H: P->Z，P表示K[x]中的多项式，Z表示小于256的非负整数，定义函数h(p)=z(mod 256)。显然H为双射；依初等数论同余性质有h(p1+p2)=(z1+z2)mod 256=z1(mod 256)+z2(mod 256)=h(p1)+h(p2)，h(p1*p2)=z1*z2(mod 256)=z1(mod 256)*z2(mod 256)=h(p1)*h(p2)，故H保持加法乘法封闭性。这点保证支持任意明文/密文的运算​2. 由一元多项式环的性质得多项式乘法可以交换，即f(x)•g(x)=g(x)•f(x)，满足域的交换条件。其乘法单位元是常数项1，满足域的单位元条件​3. 因非零多项式f(x)与m(x)互素，由一元多项式环的互素定理知存在g(x)、k(x)使得f(x)•g(x)+m(x)•k(x)=1(系数模2)，即f(x)•g(x)模m(x)余1（这里1表示单位元），故f(x)存在逆元，由群定义知逆元必唯一，满足域的逆元条件。另aes规定零多项式的逆元 ...继续阅读 (91)

多维特征Multiple Features之前课程仅针对单一变量/特征进行回归，但现实中单一变量/调整很少，往往都会存在较多的特征。多维特征是指在数据分析、机器学习和统计学等领域中，用于描述和表示数据的多个属性、变量或特征。每个特征可以看作是数据的一个维度，多个特征共同构成了数据的多维空间。多维特征用于捕捉数据的多方面信息，从而更全面地描述数据。对房价模型增加更多的特征，例如房间数楼层等，构成一个含有多个变量的模型，模型中的特征为多个数值。多维梯度下降Gradient Descent for Multiple Variables与单变量线性回归类似，在多变量线性回归中，也需要构建一个代价函数。同理，代价函数是所有建模误差的平方和，目的要找出使得代价函数最小的一系列参数。代价函数梯度下降所以经过推导等运算，得出下图结果；开始随机选择一系列的参数值，计算所有的预测结果后，再给所有的参数一个新的值，如此循环直到收敛。Python代码def computeCost(X, y, theta): inner = np.power(((X * theta.T) - y), 2) return np.sum(inner) / (2 * len(X))梯度下降法实践——特征缩放Feature Scaling特征缩放是在数据预处理过程中的一个重要步骤，旨在将数据特征的值范围调整到合适的 ...继续阅读 (84)

2006 年，我在博客（当时还是 MSN Space）上发了《什么是 P 问题、NP 问题和 NPC 问题》一文。这是我高二搞信息学竞赛时随手写的一些东西，是我的博客中最早的文章之一。今天偶然发现，这篇现在看了恨不得重写一遍的“科普”竟仍然有比较大的阅读量。时间过得很快。《星际争霸》（StarCraft）出了续作，德国队 7 比 1 大胜东道主巴西，《学徒》（The Apprentice）里的那个家伙当了总统，非典之后竟然出了更大的疫情。现在已经是 2022 年了。这 16 年的时间里，我读了大学，出了书，娶了老婆，养了娃。如果现在的我写一篇同样话题的科普文章，我会写成什么样呢？正好，我的新书《神机妙算：一本关于算法的闲书》中有一些相关的内容。我从书里的不同章节中摘选了一些片段，整理加工了一下，弄出了下面这篇文章，或许能回答刚才的问题吧。有一天，我和老婆去超市大采购。和往常一样，结完账之后，我们需要小心谨慎地规划把东西放进购物袋的顺序，防止东西被压坏。这并不是一件容易的事情，尤其是考虑到各个物体自身的重量和它能承受的重量之间并无必然联系。鸡蛋、牛奶非常重，但同时也很怕压；毛巾、卫生纸都很轻，但却能承受很大的压力。于是，我突然想到了这么一个问题：给定 n 个物体各自的重量和它能承受的最大重量，判断出能否把它们叠成一摞，使得所有的物体都不会被压坏（一个物体不会被压坏的意思就是，它上面的 ...继续阅读 (6)

2006 年，我在博客（当时还是 MSN Space）上发了《什么是 P 问题、NP 问题和 NPC 问题》一文。这是我高二搞信息学竞赛时随手写的一些东西，是我的博客中最早的文章之一。今天偶然发现，这篇现在看了恨不得重写一遍的“科普”竟仍然有比较大的阅读量。时间过得很快。《星际争霸》（StarCraft）出了续作，德国队 7 比 1 大胜东道主巴西，《学徒》（The Apprentice）里的那个家伙当了总统，非典之后竟然出了更大的疫情。现在已经是 2022 年了。这 16 年的时间里，我读了大学，出了书，娶了老婆，养了娃。如果现在的我写一篇同样话题的科普文章，我会写成什么样呢？正好，我的新书《神机妙算：一本关于算法的闲书》中有一些相关的内容。我从书里的不同章节中摘选了一些片段，整理加工了一下，弄出了下面这篇文章，或许能回答刚才的问题吧。有一天，我和老婆去超市大采购。和往常一样，结完账之后，我们需要小心谨慎地规划把东西放进购物袋的顺序，防止东西被压坏。这并不是一件容易的事情，尤其是考虑到各个物体自身的重量和它能承受的重量之间并无必然联系。鸡蛋、牛奶非常重，但同时也很怕压；毛巾、卫生纸都很轻，但却能承受很大的压力。于是，我突然想到了这么一个问题：给定 n 个物体各自的重量和它能承受的最大重量，判断出能否把它们叠成一摞，使得所有的物体都不会被压坏（一个物体不会被压坏的意思就是，它上面的 ...继续阅读

背景有些产品可能需要用到旋钮来调节音量，比如对讲机，收音机等。如何实现呢？常见的一种实现方案是使用电位器接一个ADC输入，通过ADC检测电压的大小变化来调节音量大小，软件实现上需要定时检测ADC的电压变化，检测周期长短影响音量调节体验，设置的周期长，反应速度慢，会出现突然声音大或者突然声音小的情况，检测时间太频繁，系统又会频繁唤醒，无法进入低功耗状态。另一种方式是是使用旋转编码器接几个GPIO，通过旋转编码器可以检测到正转反转，通过其输出信号可以得到旋转角度。电位器实物图：旋转编码器实物图：在某项目中使用ADC+可调电位器的方式实现音量调节功能，电路如下图：在使用ADC时发现一个问题，从ADC读取到的电压值并不是实际电压，从ADC读取的电压值范围是0~184mv，测量得到的实际电压为0~1668mv，所以需要对ADC的原始数据做处理，通过软件拟合得到真实电压。遇到问题，解决问题，学习使用python处理曲线拟合的几种方法。python 调试环境介绍对我的python开发调试环境做个简单介绍，操作系统是win 10，安装的python 是3.8，同时安装了 jupyter lab。平时一些简单的python脚本编写、算法验证通常都是在 jupyter lab环境上编码调试。为什么使用jupyter lab呢？python对我来说是一门辅助性的工具，通常编写的代码量不大，jupyter ...继续阅读 (58)

计算复杂性计算复杂性 (Computational Complexity)是用于对一个问题求解所需的资源 (通常为空间和时间) 的度量。在评估一个算法的时候，除了算法本身的准确性以外，同时需要关注算法运行的时间以及占用的内存，从而根据实际情况选择合适的算法。函数的增长计算复杂性中的空间和时间的评估方法类似，在此我们更多的以时间复杂度为例。算法的运行时间刻画了算法的效率，对于一个输入规模为$n$的问题，定义一个算法求解该问题最坏情况下的运行时间为$T \left(n\right)$，我们可以使用一些渐进记号更加方便地对其进行描述。$\Theta$记号对于一个给定的函数$g \left(n\right)$，$\Theta \left(g \left(n\right)\right)$可以表示如下函数的集合：$$ \Theta \left(g \left(n\right)\right) = \left\{f \left(n\right): \exists c_1 > 0, c_2 > 0, n_0 > 0, s.t. \forall n \geq n_0, 0 \leq c_1 g \left(n\right) \leq f \left(n\right) \leq c_2 g \left(n\right) \right\} $$也就是说当$n$足够大时，函数$f \left(n\right ...继续阅读 (61)

在求循环码的生成多项式和一致性校验多项式时，需要用到模2因式分解，但是自己数学没学好，一个模2因式分解让我摸不着头脑，不知道从何下手。幸运的是我发现可以用wolfram的mathematica软件来辅助求解，使用Factor函数即可计算模2因式分解。这是Factor的语法：打开mathematica软件试试效果：问题解决了？并非如此，软件只是单纯地告诉我一个结果，我还是不知道如何进行模2因式分解！ ...继续阅读 (57)

深度学习的核心问题就是一个非常难的优化问题。所以在神经网络引入后的几十年间，深度神经网络的优化问题的困难性是阻碍它们成为主流的一个重要因素。并导致了它们在20世纪90年代到21世纪初期间的衰落。不过现在已经基本解决了这个问题。在本篇博文中，我会探讨优化神经网络的“困难性”，以及理论上是怎么解释这个问题的。简而言之：神经网络变得越深，优化问题就会变得越难。最简单的神经网络是单节点感知器，其优化问题是凸问题。凸优化问题的好处是所有的局部最小值也是全局最小值。存在各种各样的优化算法来解决凸优化问题，并且每隔几年就会发现更好的用于凸优化的多项式时间的算法。使用凸优化算法可以轻松地优化单个神经元的权重（参见下图）。下面让我们看看扩展一个单神经元后会发生什么。图1 左图：一个凸函数。右图：一个非凸函数。凸函数比非凸函数更容易找到函数曲面的底部（来源：Reza Zadeh）下一步自然就是在保持单层神经网络的情况下添加更多的神经元。对于单层n节点感知器的神经网络，如果存在边权重可以使得神经网络能正确地对训练集进行分类，那么这样的边权重是可以通过线性规划在多项式时间O(n)内找到。线性规划也是凸优化的一种特殊情况。这时一个问题应运而生：我们可以对更深的多层神经网络做出这种类似的保证么？不幸的是，不能。为了可证明地解决两层或多层的一般神经网络的优化问题，需要的算法将会遇到某些计算机科学中最大的未解问题 ...继续阅读 (42)

indianexpress雷锋网AI科技评论按：今天是愚人节，然而学术圈并不平静， 比西方记者跑得都快的AI科技评论编辑整理了今日的一本正经胡说八道 的学术热点，一起来看看都发生了哪些大新闻吧。MIT教授宣布解决P=NP难题，被送精神病院MIT CSAIL 今日在官网上公布了一个惊人的消息：MIT 教授 Erik Demaine 解决了一个数十年的难题 P=NP，而当事人 Demaine 教授则被保全抓走，遣送精神病院。根据视频拍摄者的回忆，事情是这样的：在昏昏欲睡的课堂上，MIT教授 Erik Demaine 正在和学生阐述 P/NP 问题。「数学家们在这个领域已经研究了数十年，而这个问题依然非常困难……你们有什么问题吗？」正在说话间，他突然接到了一个电话。「噢，我现在正上课呢，在和学生们讨论 P/NP 问题……真的吗？P=NP？？真的吗？……这，这意味着什么？也就是说，我刚写了满黑板的这些理论已经被解决了？噢天了你们这些学生是第一个听到这个消息的！」然后两个警察走上前来，老师准备夺门而出，但他未能挣脱保安的魔爪，就被押走了……这时，一名男子走上前来解释，「Demaine 教授已经病得不轻，我们将把他关起来治疗，所以他下节课也不会来了。」说完也离开了现场。欢迎观看 Demaine 老师（戏很足）的视频：以下是科普时间：P/NP 问题被克雷数学研究所收录进千禧年大奖难题中，是理论信 ...继续阅读 (11)

...继续阅读 (21)

...继续阅读 (19)

深度学习的核心问题就是一个非常难的优化问题。所以在神经网络引入后的几十年间，深度神经网络的优化问题的困难性是阻碍它们成为主流的一个重要因素。并导致了它们在20世纪90年代到21世纪初期间的衰落。不过现在已经基本解决了这个问题。在本篇博文中，我会探讨优化神经网络的“困难性”，以及理论上是怎么解释这个问题的。简而言之：神经网络变得越深，优化问题就会变得越难。最简单的神经网络是单节点感知器，其优化问题是凸问题。凸优化问题的好处是所有的局部最小值也是全局最小值。存在各种各样的优化算法来解决凸优化问题，并且每隔几年就会发现更好的用于凸优化的多项式时间的算法。使用凸优化算法可以轻松地优化单个神经元的权重(参见下图)。下面让我们看看扩展一个单神经元后会发生什么。图1 左图：一个凸函数。右图：一个非凸函数。凸函数比非凸函数更容易找到函数曲面的底部(来源：Reza Zadeh)下一步自然就是在保持单层神经网络的情况下添加更多的神经元。对于单层n节点感知器的神经网络，如果存在边权重可以使得神经网络能正确地对训练集进行分类，那么这样的边权重是可以通过线性规划在多项式时间O(n)内找到。线性规划也是凸优化的一种特殊情况。这时一个问题应运而生：我们可以对更深的多层神经网络做出这种类似的保证么?不幸的是，不能。为了可证明地解决两层或多层的一般神经网络的优化问题，需要的算法将会遇到某些计算机科学中最大的未解问题 ...继续阅读 (25)

编者按：本文来自微信公众号“OReillyData”（ID：OReillyData），作者Reza Zadeh，Reza Zadeh是斯坦福大学的兼职教授、Matroid创始人和首席执行官。他的工作主要关注于机器学习、分布式计算和离散应用数学。他曾在Miscrosoft和Databricks的技术顾问委员会任职；36氪经授权发布。深度学习的核心问题就是一个非常难的优化问题。所以在神经网络引入后的几十年间，深度神经网络的优化问题的困难性是阻碍它们成为主流的一个重要因素。并导致了它们在20世纪90年代到21世纪初期间的衰落。不过现在已经基本解决了这个问题。在本篇博文中，我会探讨优化神经网络的“困难性”，以及理论上是怎么解释这个问题的。简而言之：神经网络变得越深，优化问题就会变得越难。最简单的神经网络是单节点感知器，其优化问题是凸问题。凸优化问题的好处是所有的局部最小值也是全局最小值。存在各种各样的优化算法来解决凸优化问题，并且每隔几年就会发现更好的用于凸优化的多项式时间的算法。使用凸优化算法可以轻松地优化单个神经元的权重（参见下图）。下面让我们看看扩展一个单神经元后会发生什么。图1 左图：一个凸函数。右图：一个非凸函数。凸函数比非凸函数更容易找到函数曲面的底部（来源：Reza Zadeh）下一步自然就是在保持单层神经网络的情况下添加更多的神经元。对于单层n节点感知器的神经网络，如果存在 ...继续阅读 (10)

我们有一个多项式需要计算。 朴素算法需要n(n+1)/2次乘法和n次加法，我们知道做乘法的代价是很高的，所以朴素算法是非常低效的。利用归纳法我们可以对多项式进行变形： 这种求值安排称为Horner规则。我们可以基于这个规则来进行运算，最后求得多项式的结果b0：我们可以直接知道，Horner算法共进行了n次乘法和n次加法。伪代码： C++代码： viewplain copy double HornerRule(double a[], int n, double x)  {      double res = 0.0;         for(int i=n; i>=0; --i)          res = x*res + a[i]; &n ...继续阅读 (26)

贝塞尔曲线(Bezier curves)是曲率的一种典型代表，而且在很多应用中都会运用到，比如计算机的图形学中、字体和动画。如果你以前玩过CSS，那么你可能就运到过贝塞尔曲线。例如，在CSS的时间函数(timing function)中就有一个贝塞尔曲线——x轴和y轴的距离用来确定时间。为什么要使用它们从自己的角度来说，我们需要画一条曲线，它可以会消耗100px。画这样的一条曲线是非常的方便。不幸运的是，画这样的曲线会有非常多的原因，最明显的就是存储的开销非常的大。如果我们可以调用一个函数100次，而且每次收集一个点。为了这个目标，我们可以创建一个函数：/** * @param {Number} t Number from 0 to 1. * @return {Array} Point on the curve */ function getCurveLocation(t) { ... }函数需要一个从0到1的数字，这主要是我们需要画100个点，我们把这个函数称之为getCurveLocation，它的值空间将是100次。var points = [] for(var i = 0; i <= 100; i++) { points.push(getCurveLocation(i * .01)) }我们都完成了，这个设置代表我们的曲线在任意的像素位置。这个很简单—— ...继续阅读 (21)

在我们了解了需要解决的机器学习问题的类型之后，我们可以开始考虑搜集来的数据的类型以及我们可以尝试的机器学习算法。在这个帖子里，我们会介绍一遍最流行的机器学习算法。通过浏览主要的算法来大致了解可以利用的方法是很有帮助的。可利用的算法非常之多。困难之处在于既有不同种类的方法，也有对这些方法的扩展。这导致很快就难以区分到底什么才是正统的算法。在这个帖子里，我希望给你两种方式来思考和区分在这个领域中你将会遇到的算法。第一种划分算法的方式是根据学习的方式，第二种则是基于形式和功能的相似性(就像把相似的动物归为一类一样)。两种方式都是有用的。学习方式基于其与经验、环境，或者任何我们称之为输入数据的相互作用，一个算法可以用不同的方式对一个问题建模。在机器学习和人工智能教科书中，流行的做法是首先考虑一个算法的学习方式。算法的主要学习方式和学习模型只有几个，我们将会逐一介绍它们，并且给出几个算法和它们适合解决的问题类型来作为例子。监督学习：输入数据被称为训练数据，它们有已知的标签或者结果，比如垃圾邮件/非垃圾邮件或者某段时间的股票价格。模型的参数确定需要通过一个训练的过程，在这个过程中模型将会要求做出预测，当预测不符时，则需要做出修改。无监督学习：输入数据不带标签或者没有一个已知的结果。通过推测输入数据中存在的结构来建立模型。这类问题的例子有关联规则学习和聚类。算法的例子包括Apriori算法和K- ...继续阅读 (69)

...继续阅读 (22)

老师：“今天我们来做几道智力题。”观察下面的数列，写出下一个数X：11，0，12，0，X大胖同学：“X等于13。”老师：“回答正确。”小胖同学：“老师，我觉得1也可以。”老师：“说说理由。”小胖：“这个数列可以看成是一块整点报时的钟每隔半小时敲响的次数，过了12点当然是1点。”老师：“嗯，也有道理。再看下面一题。”找出下面数列的规律，写出下一个数X：3，1，4，1，5，X大胖受了上题的启发：“6。这是一块整点报时，半点敲一下的钟 每隔半小时敲响的次数。”小胖：“9也可以。这是圆周率的前几位的数字3.1415926…。”老师：“看来都难不倒你们。这次要拿出我压箱底的题目了。”求X：9，5，2，X，7，0写完这几个胡诌的数字，老师的嘴角露出一丝诡异的笑容。大胖同学马上答到：“4。”老师本以为这次两人总要花点时间，不禁吃惊地问大胖理由。“这是一个小数的前几位，9.52470426。”“什么小数，有什么规律 ？”“没什么规律，它就是一个无理数，一个无限不循环的小数。圆周率可以，它也可以啊 。”“ 好吧，那你为什么选4？”“因为今天星期四，而且4是我的幸运数字 。”“ ……好吧，小胖，你有答案吗？”“老师，随便几都可以。”“ 认真点。”“0，1，2，3，4，5，6，7，8，9，10，11……用哪一个呢……老师，要不选你的幸运数字吧 。”“ 我的幸运数字是，嗯，6……不，还是8比较好……不能因 ...继续阅读 (21)

是基于上个博客的内容，将上个博客实现的基本操作组成一个自己的lib，将头文件添加到多项式的头文件中即可，注意：要多有关于Elemtype类型数据的输入输出要进行重写链表的头文件：#defineTRUE 1#defineFALSE 0#defineOK 1#defineERROR 0#defineINFEASIBLE -1#defineMYOVERFLOW -2typedefintStatus;typedefintElemtype;typedefstructLNode{//结点类型Elemtype data;LNode*next;}*Link,*Position;typedefstruct{//链表类型Link head, tail;//分别指向线性链表中的头结点和最后一个结点intlen;//指示线性链表中数据元素的个数}LinkList;Status compare(Elemtype s1, Elemtype s2);//比较两者的大小，相等返回TRUE，否则返回FALSEStatus visit(LinkList L);//若存在，则遍历L返回OK，否则返回ERRORStatus Create_List(LinkList &);//创造一个链表Status MakeNode(Link &p, Elemtype e);//分配由p指向的值为e的结点，并返回OK；若 ...继续阅读 (16)

1. 素域和单扩域1.1 素域域是一种比较“完整”的结构，它的限制条件比较多，结构自然也就不是很多样。现在我们来初步研究一下域的结构，研究的方法当然是从小域向大域扩展，若\(F\)是\(E\)的子域，\(E\)也叫\(F\)的扩域或扩张。扩张当然要从最简单的域开始，我们比较熟悉的简单域有哪些？最简单的无穷域是有理数域，它是最小的数域，任何数域都包含有理数域；最简单的有限域是整数在素数\(p\)下的剩余类域\(Z_p\)。这两种域都不再有真子域，我们把没有真子域的域称为素域，一般记作\(\triangle\)。那么除了这两种熟知的素域外，还有别的素域吗？每个域都含有单位元\(e\)，由\(e\)生成的域就是所有的素域，而它又是某个生成环的商域，故我们可以从\(e\)的生成环\(Z'=\{ne\}\)讨论起。当\(\text{char}\triangle=\infty\)时，\(Z'\)与整数环\(Z\)同构，从而它们的商域同构，即\(\triangle\cong\Bbb{Q}\)。当\(\text{char}\triangle=p\)时，前面已经讨论过，这样的环\(Z'\)都同构于同余环\(Z_p\)，进而有\(\triangle\cong Z_p\)。这样看来，同构意义的下的素域只有\(\Bbb{Q}\)和\(Z_p\)，而且任何域都包含且仅包含一个素域。1 ...继续阅读 (29)