检索结果-南通市图书馆

Approximation of dense-n/2.subgraph and table compression problems

在线全文

学校读者我要写书评

暂无评论

science China mathematics 2005年第9期48卷 1223-1233页

作者： XU Dachuan~1 HAN Jiye~2.& DU Dongle~3.1. College of applied sciences,{2. University of Technology,{2. 10002.,China 2. institute of applied mathematics,Academy of mathematics and systems science,chinese Academy of sciences,beijing 100080,China 3. Faculty of Administration,University of New Brunswick,P.O.Box 4400,Fredericton,NB E3. 5A3.Canada College of applied sciences Beijing University of Technology Beijing 100022 China institute of applied {2. Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing 100080 China Faculty of Administration University of New Brunswick P.O. Box 4400 Fredericton NB E3B 5A3 Canada

We develop improved approximation algorithms for two NP-hard problems: the dense-n/2.subgraph and table *** on SDP relaxation and advanced rounding techniques,we first propose 0. 5982.and 0. 5970-approximation algorithms respec- tively for the dense-n/2.subgraph problem (DSP) and the table compression problem (TCP). Then we improve these bounds to 0. 62.3.and 0. 6708 respectively for DSP and TCP by adding triangle inequalities to strengthen the SDP *** results for TCP beat the 0. 5 bound of a simple greedy algorithm on this problem,and hence answer an open question of Anderson in an affirmative way.

关键词： dense-n/2.subgraph problem(DSP) table compression problem(TCP) SDP approximation ratio

On the periodic solutions of a type of differential-iterative equations

在线全文

学校读者我要写书评

暂无评论

chinese science Bulletin 1998年第3期43卷 204-206页

作者： GE Weigao 1, LIU Zhengrong 2.and YU Yuanhong 3.1. Department of applied mathematics, {2. institute of Technology, {2. 100081, China 2. Department of mathematics, Yunnan University, Kunming 650091, China 3. institute of applied mathematics, C Department of applied mathematics Beijing Institute of Technology Beijing China Department of mathematics Yunnan University Kunming China institute of applied {2. Chinese Academy of Sciences Beijing China

Sufficient conditions for the existence of periodic solutions to a type of nonautonomous differential_iterative equations are given.

关键词： differential_iterative equation periodic solution fixed point.

Modeling and verifying Web services driven by requirements:An ontology-based approach

在线全文

学校读者我要写书评

暂无评论

science in China(Series F) 2006年第6期49卷 792-820页

作者： HOU Lishan1,3.JIN ZHi1,2.& WU Budan1,4 1. Academy of mathematics and systems {2., chinese Academy of sciences, beijing 100080, China 2. institute of Computing Technology, chinese Academy of sciences, beijing 100080, China 3. institute of Software, chinese Academy of sciences, beijing 100080, China 4. Graduate University of chinese Academy of sciences, beijing 100049, China 1. Academy of mathematics and systems {2. Chinese Academy of Sciences Beijing 100080 China 3. institute of Software Chinese Academy of Sciences Beijing 100080 China 2. institute of Computing Technology Chinese Academy of Sciences Bejing 100080 China 4. Graduate University of chinese Academy of sciences Beijing 100049 China

Automatic discovery and composition of Web services is an important research area in Web service technology, in which the specification of Web services is a key issue. This paper presents a Web service capability description framework based on the environment ontology. This framework depicts Web services capability in two aspects： the operable environment and the environment changes resulting from behaviors of the Web service. On the basis of the framework, a requirement-driven Web service composition model has been constructed. This paper brings forward the formalization of Web service interactions with π calculus. And an automatic mechanism converting conceptual capability description to the formal process expression has been built. This kind of formal specification assists in verifying whether the composite Web service model matches the requirement.

关键词： Web service environment ontology automatic composition π calculus formal verification.

A new DNA algorithm to solve graph coloring problem

在线全文

学校读者我要写书评

暂无评论

Progress in Natural science:Materials International 2007年第6期17卷 733-738页

作者： Jiang Xingpeng1, Li Yin2. Meng Ya3.and Meng Dazhi2.1. National Laboratory of Pattern Recognition,institute of Automation, {3. Academy of {2., beijing 100080, China 2. College of applied {2., beijing University of Technology, beijing 10002., China 3. School of science, beijing institute of Technology, beijing 100081, China) National Laboratory of Pattern Recognition Institute of Automation Chinese Academy of Sciences Beijing 100080 China College of applied sciences Beijing University of Technology Beijing 100022 China School of science Beijing Institute of Technology Beijing 100081 China

Using a small quantity of DNA molecules and little experimental time to solve complex problems successfully is a goal of DNA computing. Some NP-hard problems have been solved by DNA computing with lower time complexity than conventional computing. However, this advantage often brings higher space complexity and needs a large number of DNA encoding molecules. One example is graph coloring problem. Current DNA algorithms need exponentially increasing DNA encoding strands with the growing of problem size. Here we propose a new DNA algorithm of graph coloring problem based on the proof of four-color theorem. This algorithm has good properties of needing a relatively small number of operations in polynomial time and needing a small number of DNA encoding molecules (we need only 6R DNA encoding molecules if the number of regions in a graph is R).

关键词： DNA computing NP-hard problem graph coloring problem.

PROBABILISTIC NUMERICAL APPROACH FOR PDE AND ITS APPLICATION IN THE VALUATION OF EUROPEAN OPTIONS

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Journal of Computational mathematics 2001年第6期19卷 591-600页

作者： Dong-sheng Wu (institute of systems {2., Academy of {3. and systems sciences, chinese Academy of sciences, beijing 100080, China ) 中科院系统科学所北京 100080

Presents a probabilistic numerical approach for a class of probabilistic differential equation. Application of the Brownian motion and Monte-Carlo method; Application in the valuation of European Options.

关键词： Brownian motion probabilistic numerical solution European Options

Integrated precise orbit determination of Shenzhou IV unmanned spacecraft

在线全文

学校读者我要写书评

暂无评论

science China(Technological sciences) 2004年第5期47卷 518-525页

作者： L Congmin1,2. GU Yidong3. LIN Baojun3.& GUO Jiong3.1. Center for Space science and applied Research, {2. Academy of sciences, beijing 100080, China 2. Graduate School of the {2. Academy of sciences, beijing 10003., China 3. General Establishment of Space science and Application, {2. Academy of sciences, beijing 100080, China Correspondence should be addressed to L Congmin 1. Center for Space science and applied Research Chinese Academy of Sciences 100080 Beijing China 2. Graduate School of the chinese Academy of sciences 100039 Beijing China 3. General Establishment of Space science and Application Chinese Academy of Sciences 100080 Beijing China

Considering the characteristic orbit of Shenzhou IV spacecraft and the advantages and disadvantages of several types of domestic orbit measurements, a scheme of IPOD is determined, which uses GPS, SLR and USB observation data jointly plus precise ionosphere corrections to GPS observation data. IPOD system and mathematic models of OD are introduced. The results of different joint OD are analyzed using true observation data, and show that radial accuracy is better than 2.m.

关键词： Shenzhou IV unmanned spacecraft integrated precise orbit determination GPS SLR USB.

On some tests-based projection pursuit for elliptical symmetry of a high-dimensional distribution

在线全文

学校读者我要写书评

暂无评论

chinese science Bulletin 1998年第6期43卷 450-458页

作者： JING Ping 1 and ZHU Lixing 2.1. mathematics Lab, China University of Mining & Technology, beijing 100083. China 2. Probability Lab, {2. of applied mathematics, chinese Academy of sciences, beijing 100080, China mathematics Lab China University of Mining & Technology Beijing China Probability Lab Institute of Applied Mathematics Chinese Academy of Sciences Beijing China

Some test statistics of Kolmogorov type and Cramér-von Mises type based on projection pursuit technique are proposed for the testing problem of sphericity of a high-dimensional distribution. The limiting distributions of the test statistics are derived under the null hypothesis and under any fixed alternative. The asymptotic properties of bootstrap approximation are investigated. Furthermore, for computational reasons, an approximation for the statistics, based on the number theoretic method, is suggested.

关键词： bootstrap approximation projection pursuit type statistic elliptical symmetry.

CONVERGENCE AND SUPERCONVERGENCE OF HERMITE BICUBIC ELEMENT FOR EIGENVALUE PROBLEM OF THE BIHARMONIC EQUATION

在线全文

学校读者我要写书评

暂无评论

Journal of Computational mathematics 2001年第2期19卷 139-142页

作者： Dong-sheng Wu (institute of systems {2., Academy of {3. and systems sciences, chinese Academy of sciences, beijing 100080, China ) 中科院系统科学所北京 100080

Provides information on a study which discussed the convergence and superconvergence for eigenvalue problem of the biharmonic equation using the Hermite bicubic element. Discussion on eigenvalue problem for biharmonic equation; Background on asymptotic error expansions and interpolation postprocessing; Superconvergence approximations to the eigenvalue and eigenfunction.

关键词： Hermite bicubic element biharmonic equation interpolation postprocessing eigenvalue problem

Review on the study of entanglement in quantum computation speedup

在线全文

学校读者我要写书评

暂无评论

chinese science Bulletin 2007年第16期52卷 2161-2166页

作者： DING ShengChao1,3.& JIN Zhi1,2.1 institute of Computing Technology,chinese Academy of {2.,beijing 100080,China 2.Academy of mathematics and systems science,chinese Academy of {2.,beijing 100080,China 3.Graduate University of chinese Academy of {2.,beijing 100080,China institute of Computing Technology Chinese Academy of Sciences Beijing 100080 China

The role the quantum entanglement plays in quantum computation speedup has been widely disputed. Some believe that quantum computation's speedup over classical computation is impossible if entan-glement is absent,while others claim that the presence of entanglement is not a necessary condition for some quantum algorithms. This paper discusses this problem systematically. Simulating quantum computation with classical resources is analyzed and entanglement in known algorithms is reviewed. It is concluded that the presence of entanglement is a necessary but not sufficient condition in the pure state or pseudo-pure state quantum computation speedup. The case with the mixed state remains open. Further work on quantum computation will benefit from the presented results.

关键词：量子论量子纠缠量子计算加速模拟