组合数学机械化通用程序库软件V10用户手册.docx
《组合数学机械化通用程序库软件V10用户手册.docx》由会员分享,可在线阅读,更多相关《组合数学机械化通用程序库软件V10用户手册.docx(30页珍藏版)》请在三一办公上搜索。
1、30组合数学机械化通用程序库软件V1.0用户手册一、 引言本系统的名称为“组合数学机械化通用程序库软件V1.0”,是由南开大学研发的。本软件的首批用户是南开大学组合数学中心的老师和研究生。本用户手册是关于组合数学机械化通用程序库软件的帮助性文件,目的在于描述软件的安装和使用,重点在于阐述程序库中主要函数的理论背景、调用格式及输出结果。预期参考人员包括用户、测试人员、开发人员、项目管理者和其他质量管理人员。 本用户手册中涉及到如下专用术语和外文单词缩写形式:a) 组合恒等式机器证明:Zeilberger在Gosper算法的基础上提出了一套证明组合恒等式的系统方法,后来又提出了WZ-对的方法,不仅
2、能证明许多已有的恒等式,还能发现一些新的恒等式。其主要思想是证明组合恒等式的两边满足相同的递推关系,然后验证等式两边在初值情况下相等。b) 对称函数理论:对称函数理论是代数组合学中的一个重要研究领域,它主要研究对称群和对称多项式的代数性质和组合性质,在数学的其他分支和数学物理中有广阔的应用,是一个受到广泛关注的研究方向。c) 组合双射理论:组合双射是指在同样数量的两个对象之间的对应。该理论是组合计数理论的一个重要研究方向,有助于理解各种组合对象之间的密切联系。d) q-级数:主要内容为超几何级数的q-模拟。利用组合对应、算子理论、基本变换、反演、自动证明等方法研究q-恒等式和q-级数的性质。e
3、) APCI:Autoproof of Combinatorical Identitiesf) SYMF:Symmetric Functionsg) EPPT:Enuemrating Paths, Permutations and Treesh) CPQS:Computation Package for q-Seriesi) EVST:Extremal Value of Set Theoryj) PAPM:Package for Applications in Probability Method相关参考资料包括:a) 组合数学机械化通用程序库软件V1.0技术总结报告b) 组合数学机械化通用程
4、序库软件V1.0概要设计说明书c) 组合数学机械化通用程序库软件V1.0详细设计说明书d) 软件设计文档国家标准GB8567-88二、 功能介绍本软件共完成了六个通用程序库,重点实现了机器证明、q-级数、对称函数和组合计数等四个领域的常用函数包。这些程序库包括了机器证明、q-级数、对称函数、排列和路及树、集合论和概率方法等领域中常用的基本函数和过程。在组合恒等式机器证明方面,我们实现了Sister Celine算法求正则超几何项递归关系、算子消元法、q-Zeilberger算法、Gosper算法、素性判别的随机算法、正交多项式的关联系数求解、求多项式解的多项式算法等内容。其中Gosper算法和
5、q-Zeilberger算法的算法实现尤为重要。在q-级数方面,我们重点实现了有关q-级数等式方面的组合双射算法。主要包括Sylvester 映射、特定分拆生成、Corteel-Lovejoy 映射、Euler 定理的组合证明、Bressoud 映射、Franklin 对合、Durfee 方块和共轭分拆。这些组合双射算法是该领域的基本算法,为进一步构造双射提供了强大的工具。在对称函数方面,我们实现了该领域常用的一些函数和过程,包括置换的(轮换)分解、格排列生成、分拆与杨表表示、分拆与斜分拆的秩、寻找最长递增子序列、RSK 算法、排列的 Growth diagram生成、犹豫杨表和集合划分之间的
6、对应、匹配和 Oscillating tableaux 之间的对应等基本组合对象生成算法和基本组合算法。其中,RSK算法是对称函数的核心算法,具有广泛的应用,它的软件实现将大大有助于我们研究对称函数。在组合计数方面,我们重点研究了有关路、排列和树的程序实现。排列中的基本函数包括PermInsertion、PermPosition、PermList、PermSubseqN、IsPermutation等生成和判断函数。有禁模式的排列是计算机科学中重要的组合结构。在这方面我们编写了PermSamepatternt、PermNbpattern、PermNbpatterns、PermNbpatternT
7、、PermNbpatternsT、PermDistpattern、PermDistpatterns、PermAvoidP、PermAvoidPs等模式排列生成函数。此外我们编写了排列的基本统计量等生成函数。在路的算法实现方面,我们编写了Dyck 路、自由Dyck 路、有2k 个缺陷的n-Dyck 路的生成函数。匹配在生物信息学中有很多应用,我们实现了MatchingList、 MatchingNbpattern、MatchingAvoidP、RNASSN和RNA 二级结构等生成算法。在标号树方面,我们给出了标号树的序列表示和函数表示。在集合论方面,我们实现了具有特定性质的集合的生成函数,包括列
8、出包含某特定集合的子集的函数shade、列出包含于某特定子集的函数shadow、匹配布尔代数元素的函数matchtofirst、布尔代数对称链分解函数schd和寻找特定对称链函数symchain和寻找与集系有特殊性质的特定子集的函数Bondy。组合中的概率方法是通过设定概率空间,将某个存在性稳定转化为概率非零事件问题。在开发的程序库中,我们重点实现了离散随机变量和连续随机变量的期望和方差函数,快速排序算法和超图的二染色算法。这是概率方法中最经典的例子和最基本的算法。三、 运行环境 硬件环境:Intel Pentium III 650 MHz、128M RAM、2G硬盘空间或更高 操作系统:Wi
9、ndows 2000或Windows XP 支持软件:Maple 10四、 安装方法 本系统共有三个安装文件combmech.lib、combmech.hdb和combmech.ind,假设它们位于E盘根目录下,安装步骤如下:(1) 打开数学软件Maple 10。(2) 在Maple命令行内输入如下命令设定程序库路径 libname:=libname,E:;(3) 将程序库combmech.lib读入当前程序库路径readlib(E:combmech.lib);(4) 输入如下命令with(APCI);若显示结果如下Gosper2, Gosper3, Polysolve, Primetest,
10、 Rrop, Tran, cancel_operator, cceline, celine, celine1, re, sequence_to_tree, tree_to_sequence则表示已正确安装软件。五、 数学符号显示说明在Maple中数学的符号显示与实际表达方式不同,如输入“m2”显示为下标m2;输入“matrix(1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0) ”,则显示为.六、 软件使用本系统共包括六个程序库,下面将分别说明每个程序库主要函数如何使用。(1) APCI自动证明程序库(11) 调用软件包 with(APCI);显示结果如下Gosper2,
11、Gosper3, Polysolve, Primetest, Rrop, Tran, cancel_operator, cceline, celine, celine1, re, sequence_to_tree, tree_to_sequence(12) Gosper2和Gosper3函数Gosper算法给出了如下问题的解答:给定一个超几何项tn(相邻两项之比tn+1/tn为有关于n的有理函数),求超几何项zn使得zn+1-zn=tn。其算法可以分为三步:1、求tn相邻两项之比r(n),2、求r(n)的GP表示,3、求Gosper方程的多项式解。函数Gosper2实现了算法的前两步,Gosp
12、er3实现了算法的第三步。Gosper2函数的理论背景如下: 满足上述条件的多项式a(n),b(n),c(n)被称为有理函数r(n)的GP表示。给定超几何项tn,求tn+1/tn的GP表示这一功能由函数Gosper2给出。例如取tn为如下超几何项 t:=binomial(2*n-3,n)/4n; 显示结果如下 调用函数Gosper2 Gosper2(t,n); 显示结果如下 给定多项式a(n),b(n),c(n),关于多项式x(n)的如下方程被称为Gosper方程函数Gosper3实现了求解Gosper方程的功能。以方程nx(n+1)-(n-1)x(n)=1为例,调用如下:Gosper3(n,
13、 n+2, 1, n);显示结果如下 (13) 函数celine和cceline理论背景如下:下面以函数f(n,k)= kn!/(k!(n-k)!)为例进行说明如何调用函数celine和cceline.调用格式celine(n,k)-k*n!/(k!*(n-k)!),1,2);显示结果如下调用格式cceline(n,k)-k*n!/(k!*(n-k)!);显示结果如下(14) 函数re理论算法说明:使用该函数时需要使用软件包qsum9.mpl read:= E:qsum9.mpl;函数调用格式re(qhyperterm(0, , q, z, k), z);显示结果如下 The recurren
14、ce relation satisfies: (15) 函数Tran功能说明:此函数也需要软件包qsum9.mpl的支持,函数调用格式 Tran(qhyperterm(a, b, c, q, z, k), z);显示结果如下The condition that the Transformation Formulas should comply with is: |c/q|Rrop(pochhammer(x,n);显示结果如下 we can get a,b,c,y (17) 函数Polysolve理论背景函数调用格式Polysolve(N-1, n);显示结果如下 the solve of y(
15、n) is: (2) SYMF对称函数程序库(21) 调用软件包 with(SYMF);显示结果如下Bump, Bump2, ConjPar, Expectationplot, Expectv, InvBump, IsStdTab, IsTab, Par2StdTab, RSKcorresp1, RSKcorresp2, RSKinsert, Tab2Mat, Tab2Par, canonical, cellfilling, growthdia, insertone, invRSK, lattpermins, lattpermlist, longestisubs, mat2oscil, one
16、rowinsert, onerowinvinsert, oscil2mat, pair2vacilla, parrank, reducode, skewrank, srank, vacilla2pair(22) 函数pair2vacilla和vacilla2pair理论背景:函数调用格式pair2vacilla(1, 5, 2, 6, 3, 4, 7, 1, 7, 5);显示结果如下, , 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 4, 1, 2, 4, 1, 2, 4, 5, 1, 4, 5, 1, 4, 5, 1, 5, 1, 7, 5 Vacillating
17、 tableau V =, 0, 0, 1, 1, 2, 2, 2, 2, 2, 1,2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1函数调用格式vacilla2pair(0, 0, 1, 1, 2, 2, 2, 2, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1);显示结果如下P=, 1, 5, 2, 6, 3, 4, 7T=, 1, 7, 5(23) 调用函数mat2oscil将一个匹配变成振荡杨表mat2oscil(1,4,2,6,3,5); 显示结果如下 然后调用函数oscil2mat将振荡杨表变回匹配oscil2ma
18、t(, 1, 1, 1, 2, 1, 2, 1, );显示结果如下 这两个函数的理论背景如下:(24) 函数RSKcorresp1和RSKcorresp2理论背景:函数调用格式RSKcorresp1(5,7,1,3,2);显示结果如下 函数调用格式RSKcorresp2(5,7,1,3,2);显示结果:2(25) 函数growthdia理论背景:函数调用格式growthdia(3, 1, 2);显示结果: (26) 函数longestisubs是用来求一个序列的极大递增子列。函数调用格式longestisubs(5, 6, 2, 1, 7, 4, 3, 9, 8);显示结果:(27) 分拆与斜
19、分拆的秩相关函数理论背景:函数调用格式parrank(8, 6, 6, 4, 2);显示结果: 4函数调用格式skewrank(6, 6, 4, 2, 3, 2, 1);显示结果: 3函数调用格式reducode(6, 6, 4, 2, 3, 2, 1);显示结果:0 1 0 1 0 1 0 1 1 11 1 0 1 1 0 1 1 0 0(28) 分拆与杨表相关函数理论背景:函数调用格式IsTab(1,1,2,3,4);显示结果:true函数调用格式IsStdTab(1,5,2,3,4);显示结果:false函数调用格式Par2StdTab(2,1);显示结果:具有形状2,1的标准杨表共有2
20、个: 1, 2, 3, 1, 3, 2函数调用格式Tab2Par(1,2,3,2,3,4);显示结果:3,2,1函数调用格式Tab2Mat(1,2,3,2,3,4);显示结果: (29) 函数canonical给出置换的标准既约分解,其理论背景如下:函数调用格式canonical(5, matrix(1, 5, 3, 4, 5, 2, 1);显示结果:The canonical reduced decomposition of the input permutation is:1 2 1 3 2 4 3(210) 函数lattpermlist理论背景:函数调用格式lattpermlist(2,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 数学 机械化 通用 程序库 软件 V10 用户手册
链接地址:https://www.31ppt.com/p-2068847.html