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

On fixed point theory in partially ordered sets and an application to asymptotic complexity of algorithms

REVISTA DE LA REAL ACADEMIA DE CIENCIAS EXACTAS FISICAS Y NATURALES SERIE A-MATEMATICAS 2019年第4期113卷 3233-3252页

作者： Estevan, Asier Minana, Juan-Jose Valero, Oscar Univ Publ Navarra Dept Matemat Campus Arrosadia Iruna Pamplona 31006 Spain Univ Illes Balears Dept Ciencies Matemat & Informat Ctra Valldemossa Km 7-5 Palma De Mallorca 07122 Spain

The celebrated Kleene fixed point theorem is crucial in the mathematical modelling of recursive specifications in Denotational Semantics. In this paperwe discuss whether the hypothesis of the aforementioned result can be weakened. An affirmative answer to the aforesaid inquiry is provided so that a characterization of those properties that a self-mapping must satisfy in order to guarantee that its set of fixed points is non-emptywhen no notion of completeness are assumed to be satisfied by the partially ordered set. Moreover, the case in which the partially ordered set is coming from a quasi-metric space is treated in depth. Finally, an application of the exposed theory is obtained. Concretely, a mathematical method to discuss the asymptotic complexity of those algorithms whose running time of computing fulfills a recurrence equation is presented. Moreover, the aforesaid method retrieves the fixed point basedmethods that appear in the literature for asymptotic complexity analysis of algorithms. However, our new method improves the aforesaid methods because it imposes fewer requirements than those that have been assumed in the literature and, in addition, it allows to state simultaneously upper and lower asymptotic bounds for the running time computing.

关键词： Partial order Quasi-metric Fixed point Kleene asymptotic complexity Recurrence equation

来源：评论

学校读者我要写书评

暂无评论

An Effective Approach to Analyze Algorithms with Linear O(n) Worst-Case asymptotic complexity

引用

INTERNATIONAL JOURNAL OF ADVANCED COMPUTER SCIENCE AND APPLICATIONS 2019年第3期10卷 337-342页

作者： Yousaf, Qazi Haseeb Shah, Muhammad Arif Naseem, Rashid Wakil, Karzan Ullah, Ghufran City Univ Sci & Informat Technol Dept Comp Sci Peshawar Pakistan Sulaimani Polytech Univ Res Ctr Sulaimani 46001 Kurdistan Regio Iraq

A theoretical approach of asymptote analyzes the algorithms for approximate time complexity. The worst-case asymptotic complexity classifies an algorithm to a certain class. The asymptotic complexity for algorithms returns the degree variable of the algorithmic function while ignores the lower terms. In perspective of programming, asymptote only considers the number of iterations in a loop ignoring inside and outside statements. However, every statement must have some execution time. This paper provides an effective approach to analyze the algorithms belonging to the same class of asymptotes. The theoretical analysis of algorithmic functions shows that the difference between theoretical outputs of two algorithmic functions depends upon the difference between their coefficient of 'n' and the constant term. The said difference marks the point for the behavioral change of algorithms. This theoretic analysis approach is applied to algorithms with linear asymptotic complexity. Two algorithms are considered having a different number of statements outside and inside the loop. The results positively indicated the effectiveness of the proposed approach as the tables and graphs validates the results of the derived formula.

关键词： asymptotic complexity interval analysis in-depth analysis Big-Oh crossover point

来源：评论

学校读者我要写书评

暂无评论

Counting spanning trees on fractal graphs and their asymptotic complexity

引用

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL 2016年第35期49卷

作者： Anema, Jason A. Tsougkas, Konstantinos Univ Illinois Dept Math Urbana IL 61801 USA Uppsala Univ Dept Math Uppsala Sweden

Using the method of spectral decimation and a modified version of Kirchhoff's matrix-tree theorem, a closed form solution to the number of spanning trees on approximating graphs to a fully symmetric self-similar structure on a finitely ramified fractal is given in theorem 3.4. We show how spectral decimation implies the existence of the asymptotic complexity constant and obtain some bounds for it. Examples calculated include the Sierpinski gasket, a non-post critically finite analog of the Sierpinski gasket, the Diamond fractal, and the hexagasket. For each example, the asymptotic complexity constant is found.

关键词： fractal graphs spanning trees spectral decimation asymptotic complexity

来源：评论

学校读者我要写书评

暂无评论

Experimental Approach of the asymptotic Computational complexity of Shaders for Mobile Devices with OpenGL ES 13

Experimental Approach of the Asymptotic Computational Comple...

引用

13th Brazilian Symposium on Computer Games and Digital Entertainment (SBGAMES)

作者： Lima, Alex S. C. Junior, Edson A. C. Univ Brasilia Gama Coll Brasilia DF Brazil

ISBN: (纸本)9781479980659

The usage of mobile devices and increasingly realistic graphics is emerging, but the graphics performance is still a critical factor in games. There's more hardware restriction on mobile devices than on a computer. Thus, this paper proposes an experimental approximation of the asymptotic computational complexity of miscellaneous vertex and fragment shaders for Android and iOS platforms. The asymptotic complexities of the shaders will be analyzed based on number of instructions per second and rendering time metrics, depending on the number of polygons rendered. By means of the adjusted curves is also possible to compare the performance of the devices used in this work, which are the Nexus 4, HTC One, iPhone 5s and iPad Air. Besides, an automatic tool - that plots the data and uses the method of least squares to adjust the values obtained - will be presented, being able to estimate which curve has better approximation to the sampled data.

关键词： Android iOS shaders mobile devices computer graphics asymptotic complexity

来源：评论

学校读者我要写书评

暂无评论

A subdivision-based algorithm for the sparse resultant

引用

JOURNAL OF THE ACM 2000年第3期47卷 417-451页

作者： Canny, JF Emiris, IZ Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA INRIA F-06902 Sophia Antipolis France

Multivariate resultants generalize the Sylvester resultant of two polynomials and characterize the solvability of a polynomial system. They also reduce the computation of an common roots to a problem in linear algebra. We propose a determinantal formula for the sparse resultant of an arbitrary system of n + 1 polynomials in n variables. This resultant generalizes the classical one and has significantly lower degree for polynomials that are sparse in the sense that their mixed volume is lower than their Bezout number. Our algorithm uses a mixed polyhedral subdivision of the Minkowski sum of the Newton polytopes in order to construct a Newton matrix. Its determinant is a nonzero multiple of the sparse resultant and the latter equals the GCD of at most n + 1 such determinants. This construction implies a restricted version of an effective sparse Nullstellensatz. For an arbitrary specialization of the coefficients, there are two methods that use one extra variable and yield the sparse resultant. This is the first algorithm to handle the general case with complexity polynomial in the resultant degree and simply exponential in n. We conjecture its extension to producing an exact rational expression for the sparse resultant.

关键词： asymptotic complexity effective Nullstellensatz mixed volume multivariate resultant Newton polytope polyhedral subdivision sparse elimination theory

来源：评论

学校读者我要写书评

暂无评论

Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping

引用

DISCRETE APPLIED MATHEMATICS 1998年第1-3期88卷 147-165页

作者： Grebinski, V Kucherov, G INRIA Lorraine F-54602 Villers Les Nancy France CNRS CRIN F-54602 Villers Les Nancy France

This paper studies four mathematical models of the multiplex PCR method of genome physical mapping described in Sorokin et al. (1996). The models are expressed as combinatorial group testing problems of finding an unknown Hamiltonian cycle in the complete graph by means of queries of different type. For each model, an efficient algorithm is proposed that matches asymptotically the information-theoretic lower bound. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： genome physical mapping combinatorial group testing algorithms asymptotic complexity

来源：评论

学校读者我要写书评

暂无评论

Detector based on the energy of filtered noise

引用

IET SIGNAL PROCESSING 2019年第1期13卷 36-45页

作者： Savaux, Vincent IRT B Com Network Interfaces Lab Rennes France

This study deals with the detection of unknown signals in white noise. The authors present a new detector, based on the difference of a deterministic function of the energy of the signal and the energy of the same signal, which has been filtered. Unlike usual energy detector (ED), the proposed detector consists in exploiting the behaviour of the energy of filtered white noise, which can be a priori determined since the used filter is known. Thus, if the measured energy differs from an expected value, the detector decides that a signal is present in the band. In order to have the same asymptotic complexity as ED, a simple two-tap filter is used. The theoretical expressions of the probabilities of detection and false alarm are developed, and the optimal threshold is deduced. Simulations show that the proposed detector achieves better performance than ED, in both additive white Gaussian noise and Rayleigh channels. Furthermore, the relevance of the analytical results is proved through simulations.

关键词： AWGN channels Rayleigh channels signal detection filtering theory filtered white noise energy unknown signal detection deterministic function asymptotic complexity two-tap filter additive white Gaussian noise channel Rayleigh channel

来源：评论

学校读者我要写书评

暂无评论

Edge-Skeletons in Arrangements with Applications

引用

ALGORITHMICA 1986年第1-4期1卷 93-109页

作者： Edelsbrunner, H. Graz Tech Univ Inst Informat Proc A-8010 Graz Austria

An edge-skeleton in an arrangement A(H) of a finite set of planes in E(3) is a connected collection of edges in A(H). We give a method that constructs a skeleton in O(root n log n) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams in E(2) and space cutting trees in E(3). We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.

关键词： Arrangements of planes Power diagrams Computational geometry asymptotic complexity Dynamic data structures Perturbation

来源：评论

学校读者我要写书评

暂无评论

Comparative study of global color and texture descriptors for web image retrieval

引用

JOURNAL OF VISUAL COMMUNICATION AND IMAGE REPRESENTATION 2012年第2期23卷 359-380页

作者： Penatti, Otavio A. B. Valle, Eduardo Torres, Ricardo da S. Univ Campinas Unicamp RECOD Lab Inst Comp IC Campinas SP Brazil Univ Campinas Unicamp Sch Elect & Comp Engn FEEC Dept Comp Engn & Ind Automat DCA Campinas SP Brazil

This paper presents a comparative study of color and texture descriptors considering the Web as the environment of use. We take into account the diversity and large-scale aspects of the Web considering a large number of descriptors (24 color and 28 texture descriptors, including both traditional and recently proposed ones). The evaluation is made on two levels: a theoretical analysis in terms of algorithms complexities and an experimental comparison considering efficiency and effectiveness aspects. The experimental comparison contrasts the performances of the descriptors in small-scale datasets and in a large heterogeneous database containing more than 230 thousand images. Although there is a significant correlation between descriptors performances in the two settings, there are notable deviations, which must be taken into account when selecting the descriptors for large-scale tasks. An analysis of the correlation is provided for the best descriptors, which hints at the best opportunities of their use in combination. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Comparative study Color descriptors Texture descriptors Web Content-based image retrieval Efficiency and effectiveness asymptotic complexity Correlation analysis

来源：评论

学校读者我要写书评

暂无评论

Verification of minimum-redundancy prefix codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第4期52卷 1399-1404页

作者： Belal, A Elmasry, A Univ Alexandria Dept Comp Engn & Syst Alexandria Egypt

We show that verifying a given prefix code for optimality requires Omega(n log n) time, indicating that the verification problem is not asymptotically easier than the construction problem. Alternatively, we give linear-time verification algorithms for several special cases that are either typical in practice or theoretically interesting.

关键词： asymptotic complexity Huffman codes lower bounds optimal codes verification algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：