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

Insert and delete algorithms for maintaining dynamic Delaunay triangulations

PATTERN RECOGNITION LETTERS 1982年第2期1卷 73-77页

作者： Devijver, Pierre A. Dekesel, Michel Philips Res Lab Brussels Belgium

We recall that optimal condensing of nearest neighbor data requires the construction of the Delaunay triangulation of the training set. We argue that, from the viewpoint of computational complexity, an iterative approach using a dynamic triangulation is most desirable. We describe two algorithms, INSERT and DELETE, which permit to maintain a dynamic Delaunay triangulation.

关键词： Nearest neighbor condensing computational geometry Delaunay triangulation algorithmic complexity insertion deletion

来源：评论

学校读者我要写书评

暂无评论

A graded mesh refinement approach for boundary layer originated singularly perturbed time-delayed parabolic convection diffusion problems

引用

MATHEMATICAL METHODS IN THE APPLIED SCIENCES 2021年第16期44卷 12332-12350页

作者： Kumar, Kamalesh Podila, Pramod Chakravarthy Das, Pratibhamoy Ramos, Higinio Visvesvaraya Natl Inst Technol Dept Math Nagpur Maharashtra India Indian Inst Technol Dept Math Patna 801103 Bihar India Univ Salamanca Dept Appl Math Salamanca Spain

In this work, we consider a graded mesh refinement algorithm for solving time-delayed parabolic partial differential equations with a small diffusion parameter. The presence of this parameter leads to boundary layer phenomena. These problems are also known as singularly perturbed problems. For these problems, it is well-known that one cannot achieve a convergent solution to maintain the boundary layer dynamics, on a fixed number of uniform meshes irrespective of the arbitrary magnitude of perturbation parameter. Here, we consider an adaptive graded mesh generation algorithm, which is based on an entropy function in conjunction with the classical difference schemes, to resolve the layer behavior. The advantage of the present algorithm is that it does not require to have any information about the location of the layer. Several examples are presented to show the high performance of the proposed algorithm.

关键词： adaptive mesh algorithm algorithmic complexity boundary layer phenomena entropy graded mesh parabolic convection– diffusion problems time delay

来源：评论

学校读者我要写书评

暂无评论

Is there a universal image generator?

引用

APPLIED MATHEMATICS AND COMPUTATION 2012年第16期218卷 8151-8159页

作者： Calude, Cristian S. Lewis, J. P. Univ Auckland Dept Comp Sci Auckland New Zealand Weta Digital Wellington New Zealand Massey Univ Wellington New Zealand

Synthetic pattern generation procedures have various applications, and a number of approaches (fractals, L-systems, etc.) have been devised. A fundamental underlying question is: will new pattern generation algorithms continue to be invented, or is there some "universal'' algorithm that can generate all (and only) the perceptually distinguishable images, or even all members of a restricted class of patterns such as logos or letterforms? In fact there are many complete algorithms that can generate all possible images, but most images are random and not perceptually distinguishable. Counting arguments show that the percentage of distinguishable images that will be generated by such complete algorithms is vanishingly small. In this paper we observe that perceptually distinguishable images are compressible. Using this observation it is evident that algorithmic complexity provides an appropriate framework for discussing the question of a universal image generator. We propose a natural thesis for describing perceptually distinguishable images and argue its validity. Based on it, we show that there is no program that generates all (and only) these images. Although this is an abstract result, it may have importance for graphics and other fields that deal with compressible signals. In essence, new representations and pattern generation algorithms will continue to be developed;there is no feasible "super algorithm'' that is capable of all things. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Image generation algorithm algorithmic complexity Natural image

来源：评论

学校读者我要写书评

暂无评论

Measuring complexity in Financial Data

引用

FRONTIERS IN PHYSICS 2020年 8卷

作者： Yadav, Gaurang Singh Guha, Apratim Chakrabarti, Anindya S. Indian Inst Management Ahmedabad Ahmadabad Gujarat India Xavier Sch Management XLRI Prod Operat & Decis Sci Area Jamshedpur Bihar India Indian Inst Management Ahmedabad Prod & Quantitat Methods Area Ahmadabad Gujarat India Indian Inst Management Ahmedabad Econ Area Ahmadabad Gujarat India

The stock market is a canonical example of a complex system, in which a large number of interacting agents lead to joint evolution of stock returns and the collective market behavior exhibits emergent properties. However, quantifying complexity in stock market data is a challenging task. In this report, we explore four different measures for characterizing the intrinsic complexity by evaluating the structural relationships between stock returns. The first two measures are based on linear and non-linear co-movement structures (accounting for contemporaneous and Granger causal relationships), the third is based on algorithmic complexity, and the fourth is based on spectral analysis of interacting dynamical systems. Our analysis of a dataset comprising daily prices of a large number of stocks in the complete historical data of NASDAQ (1972-2018) shows that the third and fourth measures are able to identify the greatest global economic downturn in 2007-09 and associated spillovers substantially more accurately than the first two measures. We conclude this report with a discussion of the implications of such quantification methods for risk management in complex systems.

关键词： complex systems networks spectral analysis mutual information interaction Granger causality algorithmic complexity

来源：评论

学校读者我要写书评

暂无评论

Program-size versus Time complexity Slowdown and Speed-up Phenomena in the Micro-cosmos of Small Turing Machines

引用

INTERNATIONAL JOURNAL OF UNCONVENTIONAL COMPUTING 2011年第5期7卷 353-387页

作者： Joosten, Joost J. Soler-Toscano, Fernando Zenil, Hector Univ Barcelona Dept Log Hist & Filosofia Ciencia E-08007 Barcelona Spain Univ Seville Dept Filosofia Log & Filosofia Ciencia Grp Log Lenguaje & Informac Seville Spain Univ Sheffield Regent Court Kroto Res Inst Sheffield S14DP S Yorkshire England

The aim of this paper is to undertake an experimental investigation of the trade-offs between program-size and time computational complexity. The investigation includes an exhaustive exploration and systematic study of the functions computed by the set of all 2-color Turing machines with 2 states -we will write (2,2)- and 3 states -we write (3,2)- with particular attention to the runtimes, space-usages and patterns corresponding to the computed functions when the machines have access to larger resources (more states). We report that the average runtime of Turing machines computing a function increases -with a probability close to one- with the number of states, indicating that machines not terminating (almost) immediately tend to occupy all the resources at hand. We calculated all time complexity classes to which the algorithms computing the functions found in both (2,2) and (3,2) belong to, and made comparison among these classes. For a selection of functions the comparison is extended to (4,2). Our study revealed various structures in the micro-cosmos of small Turing Machines. Most notably we observed "phase-transitions" in the halting-probability distribution. Moreover, it is observed that small initial segments fully define a function computed by a TM.

关键词： small Turing machines Program-size complexity Kolmogorov-Chaitin complexity space/time complexity computational complexity algorithmic complexity

来源：评论

学校读者我要写书评

暂无评论

Zipf's Law, unbounded complexity and open-ended evolution

引用

JOURNAL OF THE ROYAL SOCIETY INTERFACE 2018年第149期15卷 20180395-20180395页

作者： Corominas-Murtra, Bernat Seoane, Luis F. Sole, Ricard IST Austria Campus 1 A-3400 Klosterneuburg Austria MIT Dept Phys 77 Massachusetts Ave Cambridge MA 02139 USA UPF PRBB ICREA Complex Syst Lab Dr Aiguader 88 Barcelona 08003 Spain UPF CSIC Inst Evolutionary Biol Pg Maritim Barceloneta 37 Barcelona 08003 Spain Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA

A major problem for evolutionary theory is understanding the so-called open-ended nature of evolutionary change, from its definition to its origins. Open-ended evolution (OEE) refers to the unbounded increase in complexity that seems to characterize evolution on multiple scales. This property seems to be a characteristic feature of biological and technological evolution and is strongly tied to the generative potential associated with combinatorics, which allows the system to grow and expand their available state spaces. Interestingly, many complex systems presumably displaying OEE, from language to proteins, share a common statistical property: the presence of Zipf's Law. Given an inventory of basic items (such as words or protein domains) required to build more complex structures (sentences or proteins) Zipf's Law tells us that most of these elements are rare whereas a few of them are extremely common. Using algorithmic information theory, in this paper we provide a fundamental definition for open-endedness, which can be understood as postulates. Its statistical counterpart, based on standard Shannon information theory, has the structure of a variational problem which is shown to lead to Zipf's Law as the expected consequence of an evolutionary process displaying OEE. We further explore the problem of information conservation through an OEE process and we conclude that statistical information (standard Shannon information) is not conserved, resulting in the paradoxical situation in which the increase of information content has the effect of erasing itself. We prove that this paradox is solved if we consider non-statistical forms of information. This last result implies that standard information theory may not be a suitable theoretical framework to explore the persistence and increase of the information content in OEE systems.

关键词： complexity algorithmic complexity open-ended evolution Zipf's Law

来源：评论

学校读者我要写书评

暂无评论

A modal μ perspective on solving parity games in quasi-polynomial time 18

A modal μ perspective on solving parity games in quasi-poly...

引用

33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) held as part of the Federated Logic Conference (FLoC)

作者： Lehtinen, Karoliina Univ Kiel Kiel Germany

ISBN: (纸本)9781450355834

We present a new quasi-polynomial algorithm for solving parity games. It is based on a new bisimulation invariant measure of complexity for parity games, called the register-index, which captures the complexity of the priority assignment. For fixed parameter k, the class of games with register-index bounded by k is solvable in polynomial time. We show that the register-index of parity games of size n is bounded by O(log n) and derive a quasi-polynomial algorithm. Finally, we give a descriptive complexity account of the quasi-polynomial complexity of parity games: The winning regions of parity games with p priorities and register-index k are described by a modal mu formula of which the complexity, as measured by its alternation depth, depends on k rather than p.

关键词： parity games modal mu calculus algorithmic complexity descriptive complexity

来源：评论

学校读者我要写书评

暂无评论

Index Set of Linear Orderings that are Autostable Relative to Strong Constructivizations

引用

Journal of Mathematical Sciences (United States) 2017年第6期221卷 840-848页

作者： Goncharov, S.S. Bazhenov, N.A. Marchuk, M.I. Sobolev Institute of Mathematics SB RAS 4 pr. Akad. Koptyuga Novosibirsk 630090 Russian Federation Novosibirsk State University 2 ul. Pirogova Novosibirsk 630090 Russian Federation

We prove that a computable ordinal α is autostable relative to strong constructivizations if and only if α ω+1. We obtain an estimate of the algorithmic complexity for the class of strongly constructivizable linear... 详细信息

We prove that a computable ordinal α is autostable relative to strong constructivizations if and only if α < ω^ω+1. We obtain an estimate of the algorithmic complexity for the class of strongly constructivizable linear orderings that are autostable relative to strong constructivizations. © 2017, Springer Science+Business Media New York.

关键词： algorithmic complexity If and only if SET bibliography Ordinal Family Members

来源：评论

学校读者我要写书评

暂无评论

Performance Modeling of In Situ Rendering 16

Performance Modeling of In Situ Rendering

引用

International Conference on High Performance Computing, Networking, Storage and Analysis (SC)

作者： Larsen, Matthew Harrison, Cyrus Kress, James Pugmire, David Meredith, Jeremy S. Childs, Hank Univ Oregon Eugene OR 97403 USA Lawrence Livermore Natl Lab Livermore CA 94550 USA Oak Ridge Natl Lab Oak Ridge TN USA Lawrence Berkeley Natl Lab Berkeley CA USA

ISBN: (纸本)9781467388153

With the push to exascale, in situ visualization and analysis will continue to play an important role in high performance computing. Tightly coupling in situ visualization with simulations constrains resources for both, and these constraints force a complex balance of trade-offs. A performance model that provides an a priori answer for the cost of using an in situ approach for a given task would assist in managing the trade-offs between simulation and visualization resources. In this work, we present new statistical performance models, based on algorithmic complexity, that accurately predict the run-time cost of a set of representative rendering algorithms, an essential in situ visualization task. To train and validate the models, we conduct a performance study of an MPI+ X rendering infrastructure used in situ with three HPC simulation applications. We then explore feasibility issues using the model for selected in situ rendering questions.

关键词： Rendering (computer graphics) Data models Computational modeling Data visualization Pipelines Graphics processing units Supercomputers supercomputer data models Data visualisation pipeline PERFORMANCE MODELING Computational modeling Rendering Graphics Processing Unit piping Visualization algorithmic complexity simulating

来源：评论

学校读者我要写书评

暂无评论

NONCROSSING SUBGRAPHS IN TOPOLOGICAL LAYOUTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 1991年第2期4卷 223-244页

作者： KRATOCHVIL, J LUBIW, A NESETRIL, J CHARLES UNIV DEPT APPL MATH CS-11000 PRAGUE CZECHOSLOVAKIA UNIV WATERLOO DEPT COMP SCI WATERLOO N2L 3G1 ONTARIO CANADA

The computational complexity of the following type of problems is studied. Given a topological layout (i.e., a drawing in the plane) of a graph, does it contain a noncrossing subgraph of a given type? It is conjectured that such problems are always NP-hard (provided planar subgraphs are looked for) regardless of the complexity of their nonplanar versions. This conjecture is verified for several cases in a very strong sense. In particular, it is shown that deciding the existence of a noncrossing path connecting two given vertices in a given topological layout of a 3-regular subgraph, as well as deciding the existence of a noncrossing cycle in such a layout are NP-complete problems. It is also proved that deciding the existence of a noncrossing k-factor in a topological layout of a (k + 1)-regular graph is NP-complete for k = 2, 3, 4, 5. For k = 1, this question is NP-complete in layouts of 3-regular graphs, while it is polynomial solvable for layouts of graphs with maximum degree two.

关键词： TOPOLOGICAL GRAPHS PLANAR LAYOUT algorithmic complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：