有限元线性过程计数原理

姜咏江

   计算机解题的时间计算问题倍受关注，如何通过数学方法计算，来准确地获得程序运行所需时间，至今尚未得到圆满的解决。计算机程序执行的过程除了出现死循环外，都是一个一个指令执行排列的线性有限过程。如果我们假定每条指令执行时间相同（实际不同可以确定），那么只要计算出指令实际执行的次数，就可以计算出程序运行完成所需要的时间。本文通过对有限元线性集合的计数过程研究，找到了对计算机程序执行所需时间计算的基本方法。

1.              线性有限集与计数过程

   任何一个计算机程序中写出的指令是有限多个，不仅如此，在程序文件中，这些指令出现的顺序也是固定有序的。为了能够突出程序及其执行过程的本质，我们给出线性有限集和线性有限集计数过程的定义。

定义1：有限个元素位置确定的排列，称为线性有限集。

   实际当中的任何计数过程都是在有限集上进行的，因为一旦计数发生在无穷集上，我们就无法用个数的概念来进行准确表达了。线性有限集的元素虽然位置固定，然而计数时可以分段跳跃式进行，也可以重复。

定义2：线性有限集上每个元素都至少计数一次，至多有限次，称为计数过程。

   以计算机程序为背景的程序指令执行次数计数，并不改变程序设计的指令排列顺序。因而规定线性有限集的计数过程并不移动元素的排序。然而计数本身可能包含着重复，也允许选择和跳跃，但不管怎样，这种计数仍然是一个线性有限过程。计数中的元素常常可以被分段来选择和重复计数。

定义3：线性有限集的一个元素或两元素及中间元素组成线性有限集，称为段。

   线性有限集的段是顺序计数的基本单位，段内不允许逆向计数，也不允许漏计段内元素，但允许段选择和段重复，允许段计数的有限次嵌套计数。一个或两个元素组成的段不会出现逆向计数。我们的这些约束条件是为了与计算机程序的执行过程相适应。

定理1：任何段在计数过程中至少被计数一次，至多被计数有限次。

   根据段和计数过程的定义，定理1立即得证。

   由于段允许重复计数，且允许段重复计数的嵌套，故而每个段都具有3个指标。这3个指标分别为：段内元素数、段重复次数和段嵌套的层数。依据这三个指标和乘法原理，我们立即会得到下面的段计数定理。

定理2（段计数定理）：设第j层的循环次数为n_j，所在循环层数为k的一段，段内元素有a个，则该段计数次数m=。

 由段计数定理，立即可以得到如下推论。

推论1：计数过程的第k层循环有最多有m段，则计数结果可由M_k＝计算。

推论2：如果计数过程的最高循环层数是H，且只有一段，那么线性有限集计数过程总结果

M＝，其中a_ki只与层数k和该层的段序i有关，与循环次数n_ij无关，若a_ki=0表示不存在该段。

2.              程序指令重复执行次数计算

  例如有c程序：

x=0;

y=0;

z=10;

t=0;

for (i=0;i<10;i++)

      ｛  x++;

             for (j=0;j<100;j++)

             ｛  y++;

                    for (m=0;m<5;m++) {

                    z++;

                    t+=z;

      }}}

这是一个4层的循环嵌套。第一段包括：

x=0;

y=0;

z=10;

t=0;

i=0;

其层数为1，元素数为5，循环次数是1。

第二段包括：

i<10;

i++;

x++;

j=0;

其层数为2，元素数为4，循环次数是10。

第三段包括：

j<100;

j++;

y++;

m=0;

其层数为3，元素数为4，循环次数是100。

第四段包括：

m<5;

m++;

z++;

t+=z;

其层数为4，元素数为4，循环次数是5。

 我想读者很容易会依据推论2计算出该程序指令重复执行的次数。

定理3：线性有限集的任意计数过程所得结果都是一个有限数。

   证明：根据定义2立得。

定理4：线性有限集至多可划分出有限个段。

   证明：（反证法）假设能够分化出无穷多个段，每个段至少会计数一次，且每个段至少有一个元素，那么计数过程的结果就是一个无穷大。这与定理3矛盾。

3.              计数的幂多项式

   为了研究问题简单，我们给出定理2 的推论3。

推论3：设最高循环层为k，每层循环数相同的只有一段，第j层循环最大数为n_j，那么线性有限集的计数过程结果可以表示成，其中a_ij是段内元素数。

   证明：根据推论2，立即得证。

   我们称上面的公式为幂多项式。由于a_ij可以为0，上式的n_j也可以用n表示。幂多项式是研究P/NP问题的重要概念。

Email:  accsys@126.com

2015-06-08