二维欧氏空间内线性凸区域概念的PAC学习算法

实例空间X的一个子集规定一个概念,表现为一个函数c:X→{0,1}。给定X上一个分布D,可能近似正确(PAC)学习算法的目的是基于独立同分布样本S,由算法产生一个近似函数hS,以高概率保证它与目标函数c的误差不超过给定误差值。如果存在这样的算法其样本复杂性及时间复杂性受多项式界,则认为目标概念可以有效PAC学习。本文讨论二维欧氏空间上有界线性凸区域定义的目标概念的学习理论和方法,证明了有界线性凸区域定义的目标概念是有效PAC可学习的,其方法可以推广到n维欧氏空间上由超平面界定的有界凸区域对应的目标概念学习。     

哥德尔不完全定理与数学认知的局限性——基于递归论解读哥德尔不完全定理

哥德尔不完全定理揭示了数学认知的局限性,任何一个含有初等数论及一阶谓词逻辑的形式证明系统中,都存在这样的命题,在此(封闭)系统中,依靠系统中的公理及一阶逻辑演算方法,既不能证明该命题为真,也不能证明它为假。哥德尔在定理的证明中开启可计算理论(递归论)之门,用现在成熟递归论的结果重新认识哥德尔不完全定理,使其变得更容易接受。近年来,机器学习取得突破性成果,由此引发有关人工智能是否可以完全代替人的思维能力等热点问题讨论。针对这一问题,如果承认"人工智能"是在一个交互计算系统中完成的,那么哥德尔不完全定理给出的是否定回答。     

时间规划的关系矩阵法之简化

就张钹等提出的时间规划的关系矩阵法,提出一个简化方法,这里不再分时间关系的单成分与多成分。简化后的方法对一般情形有效,而且不再考虑相容集,由此算法可以求出所有可能的时间安表排,且计算复杂性仍在多项式时间内。     

4杆汉诺塔的最优移动次数

通常汉诺塔问题只带三根杆,当圆盘数为n时,最优移动次数为T3(n)=2n-1.对于带4杆的汉诺塔问题,最优移动次数满足关系T4(n)=2T4(m)+T3(n-m),其中m=arglmin{2T4(l)+T3(n-l)}依赖于n.对于正数整k,当k(k-1)/2+1≤n≤k(k+1)/2,n=k(k-1)/2+l时,T4(n)=(l+k-2)2k-1+1.特别,T4(sk)=2T4(sk-1)+T3(k),其中s0=0,sk=sk-1+k(k≥1).     

在自制钒催化剂上SO_2氧化反应动力学模型识别—(Ⅱ)机理模型的确定

前文报道了采用 Yang—Hongen 方法,从四种机理假设建立了十三个竞争功力学方程。本文则重点解决从上述竞争方程中识别出能适应于以云南硅藻土为载体的钒催化剂上 SO_2氧化机理的本征动力学方程。我们利用线性回归分析方法,用15组实验数据。从十三个竞争方程中,筛选出较为理想的动力学方程,并用6组实验数据进行验证,最后确定了最佳机理模型方程为:r=(KB(Po_2~1/2-P_(so3)/KP_(so2)/(1+(k_BP_(so3)/k_BP_(so2)~(1/2)+k_PP_(so3)~(1/2))~2     

C[0,1]上完备的三角形正交函数系

基于W alsh函数,建立一个新的函数系T n n∈N.它是一个分段线性函数序列,在0,1的子区间上其函数图像呈现三角形。并且证明了它是C[0,1]上一个完备的正交函数系。在此函数系上展成的Fourier级数有许多与三角Fourier级数相似的性质,三角形Fourier级数的部分和在作为函数的逼近工具时确实要比三角Fourier级数优越一些。     

随机图G(2n,p)中k-匹配的相变性质

随机图G(n,p)模型中有两个参数n和p,n表示图中的结点数,p表示图中任意两个不同结点之间独立生成边的概率。证明了随机图G(2n,p)中存在k-匹配的临界值为p=kn-2。实验分析了随机图G(2n,p)实例中10-匹配和25-匹配以及k=n-1匹配的相变。最后总结出临界函数与匹配的边数和结点数有关系。实验表明,理论与实验一致。     

两个参数化匹配计数问题的难度分析

匹配计数问题是一个著名的难问题,考虑它的两个参数化问题p-deg-#MATCHING与p-#MATCHING,证明了p-deg-#MATCHING是固定参数易解的,p-#MATCHING有固定参数易解随机近似方案.     

图论意义下的Laplace定理

根据Valiant图论方法给出的矩阵行列式定义，证明了图论意义下的Laplace定理。