检索结果-内蒙古大学图书馆

9th International Conference on Mathematics of Program Construction

作者： Backhouse, Roland Ferreira, Joao F. Univ Nottingham Sch Comp Sci Nottingham NG8 1BB England

algorithms can be used to prove and to discover new theorems. This paper shows how algorithmic skills in general, and the notion of invariance in particular, can be used to derive many results from Euclid's algorithm. We illustrate how to use the algorithm as a verification interface (i.e., how to verify theorems) and as a construction interface (i.e., how to investigate and derive new theorems). The theorems that we verify are well-known and most of them are included in standard number-theory books. The new results concern distributivity properties of the greatest common divisor and a new algorithm for efficiently enumerating the positive rationals in two different ways. One way is known and is due to Moshe Newman. The second is new and corresponds to a deforestation of the Stern-Brocot tree of rationals. We show that both enumerations stem from the same simple algorithm. In this way, we construct a Stern-Brocot enumeration algorithm with the same time and space complexity as Newman's algorithm. A short review of the original papers by Stern and Brocot is also included. Crown Copyright (C) 2010 Published by Elsevier B.V. All rights reserved.

关键词： Number theory Calculational method Greatest common divisor Euclid's algorithm Invariant Eisenstein array Eisenstein-Stern tree (aka Calkin-Wilf tree) Stern-Brocot tree algorithm derivation enumeration algorithm Rational number

来源：评论

学校读者我要写书评

暂无评论

enumeration of all wedged equilibrium configurations in contact problem with Coulomb friction

引用

COMPUTER METHODS IN APPLIED MECHANICS AND ENGINEERING 2010年第17-20期199卷 1202-1215页

作者： Fujita, Ryo Kanno, Yoshihiro Univ Tokyo Dept Math Informat Grad Sch Informat Sci & Technol Bunkyo Ku Tokyo 1138656 Japan

For a linear structure subjected to the unilateral contact condition with a fixed obstacle, we refer to a non-trivial equilibrium state as a wedged configuration. Finding a wedged configuration is called a wedging problem. This paper discusses theoretical properties of solution set of the finite-dimensional wedging problem with the Coulomb friction, and presents numerical methods for computing all the wedged configurations. We propose algorithms for enumerating all the finitely many representative solutions, with which we can completely describe the solution set of the wedging problem. There exists a positive critical friction coefficient defined as the minimum value of friction coefficient with which at least one wedged configuration exists. We also propose an algorithm for computing the critical friction coefficient, which is based on the bisection method and the second-order cone program. (c) 2009 Elsevier B.V. All rights reserved.

关键词： Coulomb friction Complementarity problem enumeration algorithm Double description method Second-order cone program

来源：评论

学校读者我要写书评

暂无评论

Efficient enumeration of all ladder lotteries and its application

引用

THEORETICAL COMPUTER SCIENCE 2010年第16-18期411卷 1714-1722页

作者： Yamanaka, Katsuhisa Nakano, Shin-ichi Matsui, Yasuko Uehara, Ryuhei Nakada, Kento Univ Electrocommun Grad Sch Informat Syst Tokyo 1828585 Japan Gunma Univ Dept Comp Sci Gunma 3768515 Japan Tokai Univ Dept Math Sci Kanagawa 2591292 Japan Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan Wakkanai Hokusei Gakuen Univ Fac Integrated Media Wakkanai Hokkaido 0970013 Japan

A ladder lottery, known as "Amidakuji" in Japan, is a common way to choose a permutation randomly. A ladder lottery L corresponding to a given permutation pi is optimal if L has the minimum number of horizontal lines among the ladder lotteries corresponding to pi. In this paper we show that for any two optimal ladder lotteries L-1 and L-2 of a permutation, there exists a sequence of local modifications which transforms L-1 into L-2. We also give an algorithm to enumerate all optimal ladder lotteries of a given permutation. By setting pi = (n, n - 1,..., 1), the algorithm enumerates all arrangements of n pseudolines efficiently. By implementing the algorithm we compute the number of arrangements of n pseudolines for each n <= 11. (C) 2010 Elsevier B.V. All rights reserved.

关键词： enumeration algorithm Family tree Ladder lottery Pseudoline arrangement

来源：评论

学校读者我要写书评

暂无评论

Listing all the minimum spanning trees in an undirected graph

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2010年第14期87卷 3175-3185页

作者： Yamada, Takeo Kataoka, Seiji Watanabe, Kohtaro Natl Def Acad Dept Comp Sci Kanagawa 2398686 Japan

Efficient polynomial time algorithms are well known for the minimum spanning tree problem. However, given an undirected graph with integer edge weights, minimum spanning trees may not be unique. In this article, we present an algorithm that lists all the minimum spanning trees included in the graph. The computational complexity of the algorithm is O(N(mn+n2 log n)) in time and O(m) in space, where n, m and N stand for the number of nodes, edges and minimum spanning trees, respectively. Next, we explore some properties of cut-sets, and based on these we construct an improved algorithm, which runs in O(N m log n) time and O(m) space. These algorithms are implemented in C language, and some numerical experiments are conducted for planar as well as complete graphs with random edge weights.

关键词： minimum spanning tree enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Gene bi-targeting by viral and human miRNAs

引用

BMC BIOINFORMATICS 2010年第1期11卷 1-17页

作者： Veksler-Lublinsky, Isana Shemer-Avni, Yonat Kedem, Klara Ziv-Ukelson, Michal Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

Background: MicroRNAs (miRNAs) are an abundant class of small noncoding RNAs (20-24 nts) that can affect gene expression by post-transcriptional regulation of mRNAs. They play important roles in several biological processes (e. g., development and cell cycle regulation). Numerous bioinformatics methods have been developed to identify the function of miRNAs by predicting their target mRNAs. Some viral organisms also encode miRNAs, a fact that contributes to the complex interactions between viruses and their hosts. A need arises to understand the functional relationship between viral and host miRNAs and their effect on viral and host genes. Our approach to meet this challenge is to identify modules where viral and host miRNAs cooperatively regulate host gene expression. Results: We present a method to identify groups of viral and host miRNAs that cooperate in post-transcriptional gene regulation, and their target genes that are involved in similar biological processes. We call these groups (genes and miRNAs of human and viral origin) - modules. The modules are found in a new two-stage procedure, which we call bi-targeting, and is presented in this paper. The stages are (i) a new and efficient target prediction, and (ii) a new method for clustering objects of three different data types. In this work we integrate multiple information sources, including miRNA-target binding information, miRNA expression profiles, and GO annotations. Our hypotheses and the methods have been tested on human and Epstein Barr virus (EBV) miRNAs and human genes, for which we found 34 modules. We provide supporting evidence from biological and medical literature for two of our modules. Our code and data are available at http://***/similar to vaksler/*** Conclusions: The presented algorithm, which makes use of diverse biological data, is demonstrated to be an efficient approach for finding bi-targeting modules of viral and human miRNAs. These modules can contribute to a

关键词： Gene Ontology Epstein Barr Virus Target Prediction enumeration algorithm Human miRNAs

来源：评论

学校读者我要写书评

暂无评论

Computing Bayes-Nash Equilibria through Support enumeration Methods in Bayesian Two-Player Strategic-Form Games

Computing Bayes-Nash Equilibria through Support Enumeration ...

引用

IEEE/WIC/ACM International Conferences on Web Intelligence (WI)/Intelligent Agent Technologies (IAT),

作者： Ceppi, Sofia Gatti, Nicola Basilico, Nicola Politecn Milan Dipartimento Elettron & Informat I-20133 Milan Italy

ISBN: (纸本)9781424453313

The computation of equilibria in games is a challenging task. The literature studies the problem of finding Nash equilibria with complete-information games in depth, but not enough attention is paid to searching for equilibria in Bayesian games. Customarily, these games are reduced to complete-information games and standard algorithms for computing Nash equilibria are employed. However, no work studied how these algorithms perform with Bayesian games. In this paper we focus on two-player strategic-form games. We show that the most efficient algorithm for computing Nash equilibria with GAMUT data (i.e., Porter-Nudelman-Shoham) is inefficient with Bayesian games, we provide an extension, and we experimentally evaluate its performance.

关键词： algorithmic game theory Bayes-Nash equilibrium enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Extreme Visualisation of Query Optimizer Search Spaces

Extreme Visualisation of Query Optimizer Search Spaces

引用

35th ACM SIGMOD Conference

作者： Nica, Anisoara Brotherston, Daniel Scott Hillis, David William Sybase iAnywhere Waterloo ON Canada

ISBN: (纸本)9781605585543

This demonstration showcases a system for visualizing and analyzing search spaces generated by the SQL Anywhere optimizer during the optimization process of a SQL statement. SQL Anywhere dynamically optimizes each statement every time it is executed. The decisions made by the optimizer during the optimization process are both cost-based and heuristics adapted to the current state of the server and the database instance. Many performance issues can be understood and resolved by analyzing the search space generated when optimizing a certain request. In our experience, there are two main classes of performance issues related to the decisions made by a query optimizer: (1) a request is very slow due to a suboptimal access plan;and (2) a request has a different, less optimal access plan than a previous execution. We have enhanced SQL Anywhere to log, in a very compact format, its search space during the optimization process when tracing mode is on. These search space logs can be used for performance analysis in the absence of the database instances or of extra information about the SQL Anywhere server state at the time the logs were generated. This demonstration introduces the SearchSpaceAnalyzer System, a research prototype used to analyze the search spaces of the SQL Anywhere optimizer. The system visualizes and analyzes (1) a single search space and (2) the differences between two search spaces generated for the same query by two different optimization processes. The SearchSpaceAnalyzer System can be used for the analysis of any query optimizer search spaces as long as the logged data is recorded using the syntax understood by the system.

关键词： SQL.Anywhere Query Optimization Search Space enumeration algorithm Tree Difference algorithm Visualisation

来源：评论

学校读者我要写书评

暂无评论

Topological Patterns Identification for Sneak Circuit Analysis

Topological Patterns Identification for Sneak Circuit Analys...

引用

8th International Conference on Reliability, Maintainability and Safety (ICRMS 2009)

作者： Chen, Bolin NW Polytech Univ Dept Appl Math Xian 710072 Shaanxi Peoples R China

ISBN: (纸本)9781424449033

In sneak circuit analysis, it demands to identify the basic topological patterns which are the causes of sneak circuits. In this paper we formulate the problem of identifying the basic topological patterns into that of enumerating subgraphs homeomorphic to five specific signed trees in signed graphs, and give methods to simplify signed graphs and an algorithm to find all paths from a given vertex to a set of vertices of degree one in a graph. We propose a sketch algorithm for enumerating subgraphs homeomorphic to the specific signed trees and present an example of topological patterns identification using our methods.

关键词： Topological patterns identification sneak circuit analysis enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Topological Patterns Identification for Sneak Circuit Analysis

Topological Patterns Identification for Sneak Circuit Analys...

引用

The 8th International Conference on Reliability,Maintainability and Safety(ICRMS 2009)

作者： Bolin Chen Department of Applied Mathematics Northwestern Polytechnical University Xi'an,Shaanxi,710072,China

In sneak circuit analysis,it demands to identify the basic topological patterns which are the causes of sneak circuits. In this paper we formulate the problem of identifying the basic topological patterns into that of enumerating subgraphs homeomorphic to five specific signed trees in signed graphs,and give methods to simplify signed graphs and an algorithm to find all paths from a given vertex to a set of vertices of degree one in a *** propose a sketch algorithm for enumerating subgraphs homeomorphic to the specific signed trees and present an example of topological patterns identification using our methods.

关键词： Topological patterns identification sneak circuit analysis enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Recounting the rationals: Twice!

Recounting the rationals: Twice!

引用

9th International Conference on Mathematics of Program Construction

作者： Backhouse, Roland Ferreira, Joao F. Univ Nottingham Sch Comp Sci Nottingham NG8 1BB England

ISBN: (纸本)9783540705932

We derive an algorithm that enables the rationals to be efficiently enumerated in two different ways. One way is known and is credited to Moshe Newman;it corresponds to a deforestation of the so-called Calkin-Wilf tree of rationals. The second is new and corresponds to a deforestation of the Stern-Brocot tree of rationals. We show that both enumerations stem from the same simple algorithm. In this way, we construct a Stern-Brocot enumeration algorithm with the same time and space complexity as Newman's algorithm.

关键词： Calkin-Wilf tree Stern-Brocot tree algorithm derivation enumeration algorithm rational numbers

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：