NP难问题的算法和实验性研究

NP难是计算机科学中的一个重要概念和核心问题，自从它的提出到现在， 人们已经得到了很多重要的理论结果。直观上讲，一个问题一旦被证明是NP难 的就意味着我们很难找到该问题的一个多项式时间的有效算法。但从实用的角 度讲，对于应用中遇到的问题，单单是证明它很难（是NP难的）是不够的，如何 在合理的时间内求解实际问题也是必须解决的现实问题。本文主要侧重于NP难 问题的算法和实验性研究，研究对象主要是可满足性问题、图的顶点染色、图 的子图匹配等NP难问题，以及可满足性模理论的解空间计算和体积估算等扩展 问题。 围绕几个著名的问题，本文的主要工作如下： 针对图染色问题，日本研究人员提出了一种通过组合小图单元得到大的难 实例的方法。他们通过试错的方式手工找到了7个小图单元。我们提出了一种新 的构造算法来系统地生成这类小图单元，用我们的算法生成的难图染色实例， 主流的图染色工具需要指数时间才能求解；在一些专门求解色数比较小的图的 图染色工具上我们的算法生成的实例更难求解。针对皇后图染色问题，我们利 用模型查找工具SEM来对这类问题进行求解，在求解过程中提出了新的变量选 择策略，发现比简单地使用可满足性问题工具和图染色工具效果要好。 针对语义Web推理中的关键问题RDF蕴含关系的判定问题，我们利用从子 图同构问题到可满足性问题的编码方案，把它转化为命题逻辑公式的可满足性 判定问题，并采用了启发式的方法对编码过程进行必要的化简得到较少的布尔 公式，然后再利用高效的可满足性问题工具来求解。这种转化为可满足性问题 的方法，是跟RDF简单蕴含的模型论语义结合比较自然的一个方法。在小规模 实例上，这种方法的效果也很好。 针对布尔和数值混合约束的公式，即可满足性模理论（线性理论）公式的 体积计算这一新问题，我们首先给出一个直接计算体积的方法，然后提出一个 改进的算法，并研究了如何通过引入可满足性模理论中的技术来尝试对该算法 进一步地改进。我们实现了工具并做了实验。在一个实际的程序实例上，我们 还就“热门路径”问题做了实例研究和探讨。 体积计算是一个有广泛应用背景的经典难题（#P难的），但以前的方法要 么只能处理线性约束，要么只具有理论价值（不够实用）；针对含非线性约束的 体积计算问题我们提出了实用的算法，并设计了相应的工具，在低维实例有很 好的逼近效果。

纯公钥模型下对NP语言的高效并发零知识证明系统

提出了一种从3轮公开掷币的对任何NP语言的诚实验证者零知识证明系统到纯公钥模型下4轮f轮最优）对同一语言的具有并发合理性的并发零知识证明系统．该转化方法有如下优点：1）它只引起D（1）（常数个）额外的模指数运算，相比DiCrescenzo等人在ICALP05上提出的需要qn）个额外的模指数运算的转化方法孩系统在效率上有着本质上的提高，而所需的困难性假设不变；2）在离散对数假设下，该转化方法产生一个完美零知识证明系统．注意到DiCrescenzo等人提出的系统只具有计算零知识性质．该转化方法依赖于一个特殊的对承诺中的离散对数的3轮诚实验证者零知识的证明系统．构造了两个基于不同承诺方案的只需要常数个模指数运算的系统这种系统可能有着独立价值．

An elasto-plastic constitutive relation of whisker-reinforced metal-matrix composite

A material model for whisker-reinforced metal-matrix composites is constructed that consists of three kinds of essential elements: elastic medium, equivalent slip system, and fiber-bundle. The heterogeneity of material constituents in position is averaged, while the orientation distribution of whiskers and slip systems is considered in the structure of the material model. Crystal and interface sliding criteria are addressed. Based on the stress-strain response of the model material, an elasto-plastic constitutive relation is derived to discuss the initial and deformation induced anisotropy as well as other fundamental features. Predictions of the present theory for unidirectional-fiber-reinforced aluminum matrix composites are favorably compared with FEM results.

透红外大尺寸氧氟化物玻璃研究

锗酸盐和氟铝酸盐透红外玻璃材料作为窗口或头罩材料具有广泛的应用前景。结合锗酸盐玻璃含有少量水的问题，在成分中引入氟化物，实验表明：随氟化物含量增加．玻璃中羟基含量逐渐降低。同时通过对熔制温度的调整，获得了不合羟基的红外玻璃。针对氟铝酸盐玻璃在冷却过程中易析晶的问题，在氟化物组分中加入少量重金属氧化物TeO2，得到析晶性能好的氧氟铝酸盐玻璃。同时给出了两类红外材料的一些物理、化学性质。

鄂尔多斯高原景观要素空间格局及植物与环境关系的定量解析

鄂尔多斯高原是一个多层次、复杂的生态过渡带，具有复杂多样的环境条件、生态特点，因此也就具有复杂多样的植物与环境关系。本文从群落和景观两个尺度水平上研究鄂尔多斯高原植物或植被与环境关系及景观空间格局。利用鄂尔多斯高原野外植物群落样方调坦数据、微生境环境数据、气候数据，以典范对应分析（Canonical Correspondence Analysis, CCA）的方法分析了鄂尔多斯高原植物分布空间格局与环境要素的关系并对秋类环境要素对鄂尔多斯高原植物空间分布格局的贡献进行了定量分解;利用1:500 000 鄂尔多斯高原植被、土壤、土地利用、土地沙漠化类型等专题地图在GIS支持下分析了鄂尔多斯高原景观空间格局、并利用上述专题图数据加上鄂尔多斯高原气候数据库分析了土壤、土地利用、土地利用、土地沙漠化和气候等对鄂尔多斯高原植被空间分布格局的作用。通过分析，得到了以下主要结论： 1 在分析方法上、利用典范对应分析的方法，把植物分布的空间因素与环境因素分离的方法发展为植物分布空间格局不同类型影响因素作用的定量分离，提出了相应的概念模型和实现方法。 2 影响鄂尔多斯高原植物分布空间格局的主要微生境环境要素是基质类型、地下水位、覆沙厚度等，而影响鄂尔多斯高原分布空间格局的主要气候要素中，降水和干湿指标的作用大于温度和热量指标的作用。 3 通过对鄂尔多斯高原植物分布空间格局与环境关系的研究，以植物对微生境环境要素的反应为根据，把鄂尔多斯高原主要植物划分为4个大类群：梁地植物、沙地植物、草甸植物和耐盐植物。根据它们对气候要素的反应，把鄂尔多斯高原主要植物划分为典型草原植物、荒漠草原植物和草原化荒漠植物3大类。进一步，根据鄂尔多劳动保护高原植物与环境关系的研究，进行了鄂尔多斯高原植被功能型划分的尝试，得到了鄂尔多斯高原的12种主要植被功能型。 4 对鄂尔多斯高原植物分布的空间格局的影响环境因素的贡献作了定量地分解。分析结果显示：鄂尔多斯高原植物分布空间格局中有27.02％可由已知环境变量得到解释，其中21.56％与微生境环境要素相关，7.51％与气候要素的作用有关，而气候与微生境环境要素的耦合作用的份额为2.05％。根据植物生长是否直接受到地下水的影响，鄂尔多斯高原存在两大类型生态特点差异明显的生境类型：中性立地和隐域生境，对两大类型生境上影响植物空间分布格局的环境要素的作用也进行了定量分解。分析结果表明：对于植物生长不直接受地下水影响的中性立地，已知环境要素的作用可以解释植物空间分布格局总信息的29.36％，稍大于对总体上鄂尔多斯高原植物分布空间格局的解释，其中9.23％与气候要素相关，22.08％与微生境环境要素相关，而两种类型环境要素的耦合作用则占1.95％。对于植物生长直接受到地下水影响的隐域生境，所有已知环境要素对植物分布空间格局的贡献率为72.28％，其中气候要素的作用为30.31％，微生境环境要素的作用为49.08％，两类环境要素的耦合作用为7.11％。 5 描述景观空间格局的指数多种多样，这些能数在描述特定区域的景观空间格局时是有信息冗余的。本文对利用FRAGSTATS所获得的鄂尔多斯高原植被、土壤、土地利用、土地沙漠化等景观分量的20个景观指数实施了因子分析。通过因子分析，我们可以把描述鄂尔多斯高原景观空间格局的景观指数归并为以下8类：多样性指数、斑块多度指数、斑块类型丰富度指数、斑块面积指数、斑块形状指数、分形维数、空间配置指数和斑块面积变异指数。通过因子分析，还得到了这些景观指数对描述鄂尔多斯景观格局的共性特征：在描述鄂尔多斯高原景观空间格局时，作用最大的是多样性指数、斑块多度指数、面积加权平均斑块形状指数和面积加权平均分形维数，其次是斑块类型丰富度指数、平均分维指数、平均形状指数和斑块面积指数，而空间配置指数（扩散与毗连指数）和斑块面积变异指数的作用则比较微弱。 6 对鄂尔多斯高原景观指数的因子分析是非常有效和成功的。因子分析对鄂尔多斯高原植被、土壤、土地利用、土地沙漠化景观指数的分析分别得到了5-6个主要因子，可以表达原有20个景观指数所表达信息的91.1-96.0％，即可以反应鄂尔多斯高原景观空间格局的大部分信息。本文所进行的因子分析对因子进行了方差最大化(Varimax)正交旋转的处理，因子分析得到的每一个主要因子都有一个或几个与之相关性非常高的景观指数与之对应，因此，就可以用与因子分析所得主要因子相关性最高的景观指数代替该主要因子来表达鄂尔多斯高原的景观空间格局。另外还因为有些景观指数之间具有极高的相关系数，所以对因子分析所得到的景观指数可以进一步精减，最后利用因子分析成功地把原有20个景观指数减少到了11个。最后被选来描述鄂尔多斯高原景观格局的景观指数有下列11个：MSIEI（修正的Simpson均匀度指数）、AWMPFD（面积加权平均斑块分形维数）、AWMSI（面积加权平均形状指数）、NP（斑块数目）、PR（斑块类型丰富度）、MSI（平均形状指数）、MPFD（平均斑块分形维数）、MPS（平均斑块面积）、PSCV（斑块面积变异系数）、DLFD（双对数分形维数）和IJI（扩散与毗连指数）。 7 鄂尔多斯高原植被、土壤、土地利用在景观组成结构上具有一个共同特点，就是各种类型的面积差异极大，少数类型占有极大比重，而其余面积则很小。产生这一情形的原因主要与人为活动的强烈影响有关，表现在地带性的植被与土壤面积所占的比重不高，沙地、沙生植被与风沙土则占有很大比重。 8 以地带性植被和滩地隐域性植被表示的鄂尔多斯高原的原生植被仅占高原面积的不足30％，而以地带性土壤和滩地隐域性土壤表示的原生性土壤占鄂尔多斯高原总面积的近40％，说明土壤退化不如植被退化严重，或滞后于植被退化。 9 鄂尔多斯高原各景观指数的空间变化曲线，植被与土壤很相近，具有非常相似的格局;土地利用景观格局空间变化特征与植被、土壤等明显不同;土地沙漠化的景观格局空间变化曲线介植被曲线、土壤曲线与土地利用曲线之间，说明土地沙漠化不仅是一个受人为活动影响的过程，而且与自然过程密切相关。 10 鄂尔多斯高原景观格局的空间梯度变化表现出了东西向和南北向的梯度，但总体上以东西向的变化比较明显。 11 通过鄂尔多斯高原土壤类型、土地利用、土地沙漠化等景观要素、气候、空间要素与鄂尔多斯高原植被空间分布格局的CCA分析，探讨了它们之间的相互关系。以对鄂尔多斯高原植被组成数据的总方差解释的百分率为标准，土壤对鄂尔多斯植被分布的空间格局的作用最大，其方差贡献率可达44.28％，其次是土地利用与鄂尔多斯高原植被的关系也很密切，土地利用对鄂尔多斯高原植被空间分布格局的方差贡献率为22.45％，空间因素对鄂尔多斯高原植被空间分布格局的贡献率为17.51％，土地沙漠化对鄂尔多斯高原植被空间分布格局的贡献为15.65％，排在第四位;气候因素对鄂尔多斯高原植被空间格局的贡献率为11.95％，居第五位。 12 在气候要素对鄂尔多斯高原植被空间分布格局的作用中，降水与干湿指标的作用大于温度与热量指标的作用。这一点与利用野外调查样方的群落数据植物与气候关系的分析是完全一致的。CCA分析还表明鄂尔多斯高原植被空间格局的东西向变化大于南北向分异。 13 在群落和景观水平上，鄂尔多斯高原植物空间分布或植被格局的影响因素的作用具有相似的格局，即气候因子的作用明显地小于地质、土壤、水文等微生境环境要素（群落水平）或土壤（景观水平）的作用，并在这两个尺度上气候要素对植物空间分布或植被格局的定量解释份额上也是非常相近的，都仅有10％左右。气候因子对鄂尔多斯高原植物空间分布格局的这种弱的解释能力，从侧面说明了人为活动等非自然因素对鄂尔多斯高原植物空间分布格局的强烈作用。 14 在鄂尔多斯高原生态系统管理上，应协调人与自然的关系;加强鄂尔多斯高原的生物多样性保育，对于本区生态和经济对非常重要的滩地，应协调好对其开发利用与保护的关系;在鄂尔多斯高原土地沙漠化防治方面，应把调整人地关系与自然生态背景与条件相结合，如使用“三圈”模式等生态系统管理模式等。

内蒙古锡林河流域空间生态学研究

本文从物种和景观两个组织水平上研究了气候、土壤、地形等自然环境因子和人类活动因子对生物空间分布格局的影响。基于锡林河流域地理信息系统各环境因子的专题数据，利用空间异质性分析方法研究了锡林河流域环境因子的空间分布格局;基于锡林河流域野外调查数据，运用空间异质性分析方法研究了重要物种的空间分布格局，并采用典范对应分析(Canomc Correspondence Analvsis，CCA)方法分析了物种分布与环境因子的关系：基于锡林河流域地理信息系统各环境因子的专题数据，研究了锡林河流域植被斑块的空间格局特征及其与环境因子的关系，并采用典范对应分析方法分析了植被类型组成与环境因子的关系：基于内蒙古草原生态系统定位研究站放牧样地的样方调查数据．采用空间异质性分析方法，研究了放牧压力对物种空间分布格局的影响：基于多年的卫星遥感数据，采用建模和对比等方法，研究了定居放牧方式下植被状况空间变化规律及植被状况时空变化与人类活动、社会经济发展的关系。通过上述分析，得到的主要结论如下： 1、锡林河流域各个环境因子都具有自己的空间特征尺度，共同形成多尺度等级体系，按特征尺度的大小可以分为如下3个组： ·小尺度组(15km左右)：有机暖、全N的较小的特征尺度 ·中尺度组(30～50km)：T1，碳酸钙含量．PER、全N和海拔高度的较小的特征尺度 ·大尺度组(100km左右)：ANNR，PER、全N和海拔高度的较大的特征尺度多尺度等级的生态学意义是它反映生态变量异质斑块的镶嵌和包含特征，环境因子多尺度等级体系反映共性，具有普遍性：反映生态关系，具有生态学意义。 2、对物种空间异质性的Mantel检验和半方差分析得到了一致的结果产即羊草、糙隐子草和星毛萎菱菜在锡林河流域的空间分布呈现随机特征，而大针茅和冷蒿则表现为十分显著的格局特征。按分布格局的显著程度从大到小排列为冷蒿>大针茅>星毛萎菱菜>糙隐子草>羊草。理论半方差图显示大针茅和冷蒿的空间自相关域分别为30．447公里和30公里。物种空间分布格局是受自然条件、人类活动以及它们自身的生理生态特征综合决定的，物种自身的生理生态特征决定了它们对外界环境变化的适应性反应机制，而自然与人类活动这两种因素在空间的交错配置决定了物种适应性反应的方向和程度，从而综合导致物种空间分布格局的形成。 3、对锡林河流域物种分布与环境因子关系的CCA分析和交叉半方差方法分析显示：1)气候因子(11个指标)、土壤性状因子(3个指标)和地形因子(3个指标)对物种分布的贡献率分别为11．2％、9．5％和11％，三者总和为31．7％。2)各个环境因子对物种分布空间作用方向具有一致性，物种分布与环境因子几乎都在135。和157．5。两个方向上具有相对明显的相关性，从锡林河流域来看，这两个方向反映了气候、土壤以及地形从东南往西北的变化梯度方向。 4、对锡林河流域14个植被景观指数进行的PCA分析表明，锡林河流域植被斑块空间分布的物理特征主要表现在斑块的数目和大小方面，其次是在斑块的多样性方面，并可将它们分为4个组，分别反映锡林河流域植被斑块的不同特征： ·第一组：NP、PRD、LPI、MPS、PSSD和TE，主要反映景观斑块在数量和大小方面的特征; ·第二组：SHDI、SIDI、SHEI和SIEI，主要反映景观斑块的多样性特征; ·第三组：PSCV和[J]．主要反映景观斑块之间的相互邻接程度; ·第四组：MSI和AWMSI，主要反映景观斑块的形状特征。 MPS和PSSD两个指数与环境因子无论是在相关系数的性质还是显著程度上都保持了很好的一致性，它们与纬度(LAT)及可能蒸散率(PER)呈极显著的正相关关系，而与经度(LNG)、海拔高度(ALT)、年平均降水量(ANNR)及土壤有机质含量(0RG)呈极显著的负相关关系：平均形状指数(MSI)只与LAT呈显著的正相关关系;多样性指数和扩散毗连指数与任何一个环境因子都没有表现出显著的相关性。 5、锡林河流域植被分布与环境因子的关系CCA排序方法分析表明，气候因子(11个指标)、土壤性状因子(3个指标)和地形因子(3个指标)对植被分布的贡献率分别为19.8%、11.1%和14.5%，三者总和为45.4％。环境因子在植被和物种两个水平上的贡献率表现了相似的特点，自然环境因子不能完全解释植被的空间分布，人类活动的影响应该受到重视。 6、放牧压力对物种空间分布格局的研究表明： ·牧压对温带典型草原物种的空间分布格局有明显的影响。随着牧云的增大，属于原生群落物种的羊草与大针茅空间分布的随机性减小，空间自相关尺度逐渐增大;而对于退化过程中的入侵物种冷蒿和星毛萎菱菜，其空间分布的随机性逐渐增大．空间自相关尺度也呈增大趋势。在牧压胁迫超过一定水平时，冷蒿空间分布的自相关尺度开始下降，而星毛萎菱菜的空间分布格局则表现出强烈的随机性。 ·物种空间格局的变化是反映群落演替过程较为稳定的特征，适用于不同放牧条件下 群落之间的比较。 7、利用遥感数据对人类活动对植被影响的研究表明： ·定居放牧方式下，NDVI随定居点距离的变化格局经历了3个阶段。第一阶段，草场处于原生阶段，NDVI不随距离变化;第二阶段，定居点附近开始局部退化，NDVI随距离增加而增大：第三阶段，退化区域扩大，NDVI不随距离变化。 ·在草场局部退化阶段，NDVI随距离的变化呈对数函数规律，定居点的放牧区具有放牧半径、原生NDVI值、NDVI变化率等特征。根据这些特征、NDVI对数规律以及NDVI与地上生物量的关系可以推测定居点的总载畜量。 ·锡林河流域从87年到85年NDVI值降低最大的区域为流域的中部和南部，这与这一区域人类活动强度以及社会经济发展具有密切关系。

农牧交错区主要植物的氮素利用效率

Berendse&Aerts (1987)认为氮素利用效率(nitrogen use efficiency，NUE)可以分为两部分的乘积，即：①氮素生产力(nitrogen productivity，NP)，②氮素的平均滞留时间(mean residencetime，MRT)。本文利用这一概念对处于我国北方农牧交错带的内蒙古自治区多伦县典型植物的氮素利用策略进行了研究。研究假设：植物在贫瘠生境上所采取的氮素适应策略主要是提高对所吸收氮素的保持能力(较长的MRT)，而不是提高NUE。 在不同土壤生境上，属于不同生活型的不同物种其NP和MRT之间存在负相关关系。在不同生境、生活型和物种之间，作为NP与MRT乘积的NUE比NP、MRT的变化相对要小，结果表明植物主要通过延长MRT来适应氮素贫瘠的生境。因为NP与MRT相反的方向变化，二者不能同时增加或减少，所以NP与MRT之间存在相互协调(trade-off)的关系。 在群落和生态系统水平上，NP与MRT之间也存在相互协调关系，不同水平上的NUE之间也存在一定的联系。除了在种间存在这种关系外，通过对多伦县和十三里滩两种针茅（大针茅、克氏针茅）的氮素利用特征的研究，发现在种内，NP与MRT之间也存在这种相互协调关系。NUE与土壤供氮能力有关，随着土壤供氮能力的下降，NUE呈上升趋势。植物的NUE不仅与土壤的供氮能力有关，其它因素如土壤水分供应状况也会对植物的NUE产生影响，例如，与生长在河岸上的植物相比，生长在河滩湿地上的植物具有较高的NP，但MRT却较低。在群落中，不同植物个体的NUE及其组成参数NP和MRT也存在较大的差异，较大的植株具有较高的NP和MRT，因而NUE也高于个体较小的植株。本文研究结果表明，植物的NUE与氮素回收转移特性密切相关，植物提高氮素回收效率(nitrogen resorption efficiency，NRE)可以延长MRT，从而提高NUE。

A COMPARATIVE-STUDY OF KARYOTYPES OF MUNTJACS BY CHROMOSOME PAINTING

We have used a combination of chromosome sorting, degenerate oligonucleotide-primed polymerase chain reaction (DOP-PCR), chromosome painting and digital image capturing and processing techniques for comparative chromosome analysis of members of the genus Muntiacus. Chromosome-specific ''paints'' from a female Indian muntjac were hybridised to the metaphase chromosomes of the Gongshan, Black, and Chinese muntjac by both single and three colour chromosome painting. Karyotypes and idiograms for the Indian, Gongshan, Black and Chinese muntjac were constructed, based on enhanced 4', 6-diamidino-2-phenylindole (DAPI) banding patterns. The hybridisation signal for each paint was assigned to specific bands or chromosomes for all of the above muntjac species. The interspecific chromosomal homology was demonstrated by the use of both enhanced DAPI banding and comparative chromosome painting. These results provide direct molecular cytogenetic evidence for the tandem fusion theory of the chromosome evolution of muntjac species.

云南保种山羊血液同工酶遗传多样性研究

采用水平式淀粉胶电泳技术 ,对云南龙陵黄山羊、宁蒗黑头山羊、马关无角山羊和路南圭山羊等 4个保种山羊的 1 2 0个个体共 3 9个基因座位的基因多态性进行了研究。结果显示 ,云南 4个保种山羊品种在AKP、CES - 1、ESD、GOI、LAP、MDH、ME和NP基因座位出现多态。多态座位基因在不同保种山羊中分布不同。多态基因座位百分比 (P)在 4个保种山羊中分别为 0 .2 0 51 ,0 .1 53 8,0 .1 2 82和 0 .1 53 8。平均杂合度 (H)分别为 0 .0 95,0 .0 61 4 ,0 .0 4 67和 0 .0 662。用UPGMA法对由基因频率计算得到的Nei氏标准遗传距离进行聚类分析 ,结果表明云南保种山羊具地理分布及品种特点 ,龙陵黄山羊和其它 3个品种的遗传距离最远。