某些算法时间复杂性的下界

本文定义了两类机器,并讨论了在这两类机器上完成某类作业所需时间的下界。其中包括:在n个排好序的有理数中同时查询n个数至少需时cn log n;把n个有理数按大小排列分类至少需时cn log n,其中c为某个常数。     

论黄金分割法的最优性

1953年 Kiefer 提出了单峰函数的优选问题.在每次做一个试验,一共做 n 次试验的情况下,他证明了斐波那契级数法是最优的.但是斐波那契级数法有一个很大的缺点,就是做完了预定的 n 次试验还不满意而想继续往下做的时候,会碰到困难,以致完全打乱了步伐.因此,在实际工作中往往用黄金分割法来代替斐波那契级数法.到目前为止,外国     

能用例证法来证明几何定理吗?

本文提出了证明平面几何定理的例证法。根据这一方法,想判定一个几何命题是否为真,只需近似地验证一个数值曲特例就行了。这个特例仅依赖于该几何命题在某种规范形式下表述的长度l以及命题中自由变量的个数s,可以非常简单地表示出来,与几何命题的内容无关。同时还证明了该类平面几何判定问题所需的并行时间是l_s的一个多项式。     

关于p(kp+1)(kp+2)阶的单群

本文证明了:对于任何一个正整数n存在一个正整数m,使得对任何正整数k≤n及任何素数p≥m,阶为p(k_p+1)(k_p+2)的单群都必须同构于LF(2,p+1)或LF(2,2p+1)。     

论计算的相似性与对偶性

本文给出了巡回的统一定义和计算类型的统一定义,证明了在一个固定计算类型下的所有合理的计算模型都是相似的。所谓相似,是指它们之间可以互相模拟,而且模拟者所用的空间和巡回(相应于并行时间)都不超过被模拟者所使用空间的一个多项式和巡回的一个多项式,从而统一了所有的模型。 本文进一步指出巡回(并行时间)是对偶于空间的,如果有一个关于空间和巡回的定理,那末在这个定理中交换了巡回和空间的位置以后,定理仍然成立。事实上,本文列出了一系列以对偶形式出现的元定理。这些元定理包括了这一领域内几乎所有的已知定理和一些全新的结果。     

形式证明的复杂性

本文提出了在形式证明系统中,证明长度、深度和宽度的概念,并且证明了长度的对数、深度和宽度三者之间是线性相关的。说明了任何定理的证明都可以高度地并行化,是一个与确定型计算截然不同的结论。     

实时系统中最急优先调度策略的二进表示模型

本文提出一个实时系统中最急优先调度策略的二进表示Markov过程模型。以减少软实时系统中任务损失率为衡量标准,最急优先调度策略被证明是一个最佳策略,但其效率却极难分析。本文的模型使这一策略的分析变得可行和简单。基于本文的理论,已得到一系列有关最急优先策略的重要的性能评价分析结果。     

近似计算有效位数的增长不超过几何级数

假定我们要用加、减、乘、除开方等运算去计算任何一个实数或复数,并且假定每次运算都是绝对精确的。我们证明了:不论用什么方法,如果不能在有限步之内达到绝对精确的值,则要精确到n位小数,至少需要正比于logn的运算次数。换言之,若不能在常数步之内求得精确解,则计算的有效位数的增长不能超过一个几何级数,中间的情况是不存在的。如果只许可使用四则运算,那末逼近一个无理数的最高速度是平方收敛。     

一个几何的不等式

<正> 令■是 n 维欧氏空间中一个紧致的凸体,有正的体积,O是■的重心,■及■′是两条互相平行的直线并且■通过O.■和■′与■分别交于线段■及(■,长度分别为|■|及|■|.对一切可能的■′,令■.1963年,B.Grünbaumt 指出,当 n=2时,对平面上一切凸区域■而言,■     

论批数不限定情况下一维优选问题的最优策略

1953年以来,Kiefer等人提出了优选法,研究了试验批数预先知道时的最优试验方法(即分数法)。但一般说来,在实践上往往不能精确地预言需要试验的批数,因此,有必要从理论上探讨批数不限定情况下的最优试验方法,本文研究了在第n批可做k_n个试验的情况,指出了:如果k₁,k₂,k₃…中有无穷多个奇数或仅k₁是奇数,我们就能给出一个最优的方法(当k_n=1时就是“0.618”法,即如果每批只做一个试验,“0.618”法就是最优的方法);在相反的情形,最优的方法不存在,但是能设计出“充分接近于最优”的方法。