Computational resource

Computational resource

In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.

The simplest computational resources are computation time, the number of steps necessary to solve a problem, and memory space, the amount of storage needed while solving the problem, but many more complicated resources have been defined.

A computational problem is generally defined in terms of its action on any valid input. Examples of problems might be "given an integer n, determine whether n is prime", or "given two numbers x and y, calculate the product x*y". As the inputs get bigger, the amount of computational resources needed to solve a problem will increase. Thus, the resources needed to solve a problem are described in terms of asymptotic analysis, by identifying the resources as a function of the length or size of the input.

Computational resources are useful because we can study which problems can be computed in a certain amount of each computational resource. In this way, we can determine whether algorithms for solving the problem are optimal and we can make statements about an algorithm's efficiency. The set of all of the computational problems that can be solved using a certain amount of a certain computational resource is a complexity class, and relationships between different complexity classes are one of the most important topics in complexity theory.

Describing generally accessible computing equipment

The term "Computational resource" is commonly used to describe accessible computing equipment and software. See Utility computing.

Formal quantification of computing capability

There has been some effort to formally quantify computing capability. A bounded Turing machine has been used to model specific computations using the number of state transitions and alphabet size to quantify the computational effort required to solve a particular problem.[1][2]

References

  1. ^ Gregory J., Chaitin (1966). "On the Length of Programs for Computing Finite Binary Sequences". Journal of the ACM (JACM) 13 (4): 547–569. doi:10.1145/321356.321363. http://www.cs.auckland.ac.nz/CDMTCS/chaitin/acm66.pdf. Retrieved 2007-09-25. 
  2. ^ Sow, Daby; Eleftheriadis, Alexandros (1998). "Representing Information with Computational Resource Bounds". Signals, Systems & Computers. Conference Record of the Thirty-Second Asilomar. Volume 1. pp. 452–456. ISBN 0780351487. 10.1109/ACSSC.1998.750904. http://www.ee.columbia.edu/ln/dvmm/publications/98/daby_eleft_asilomar98.pdf. Retrieved 2007-09-25. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Computational Resource for Drug Discovery (CRDD) — Computational Resources for Drug Discovery (CRDD) is one of the important silico modules of Open Source for Drug Discovery (OSDD). The CRDD web portal provides computer resources related to drug discovery on a single platform. Following are major …   Wikipedia

  • Statistics Online Computational Resource — The Statistics Online Computational Resource (SOCR) [cite journal| first= Ivo D. |last=Dinov |coauthors= Sanchez, Juana; Christou, Nicolas | title=Pedagogical Utilization and Assessment of the Statistic Online Computational Resource in… …   Wikipedia

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

  • Computational — may refer to: Computer Computational algebra Computational Aeroacoustics Computational and Information Systems Laboratory Computational and Systems Neuroscience Computational archaeology Computational auditory scene analysis Computational biology …   Wikipedia

  • Resource (computer science) — A resource, or system resource, is any physical or virtual component of limited availability within a computer system. Every device connected to a computer system is a resource. Every internal system component is a resource. Virtual system… …   Wikipedia

  • Computational neuroscience — is the study of brain function in terms of the information processing properties of the structures that make up the nervous system.[1] It is an interdisciplinary science that links the diverse fields of neuroscience, cognitive science and… …   Wikipedia

  • Computational lexicology — is that branch of computational linguistics, which is concerned with the use of computers in the study of lexicon. It has been more narrowly described by some scholars (Amsler, 1980) as the use of computers in the study of machine readable… …   Wikipedia

  • Computational irreducibility — is one of the main ideas proposed by Stephen Wolfram in his book A New Kind of Science. Contents 1 The idea 2 Implications 3 Analysis 4 See also …   Wikipedia

  • Computational Science and Engineering — is a relatively new discipline of engineering. It is typically offered as a masters or doctorate program at several institutions. This is not to be confused with computer engineering (related to building computers). The benefits of using computer …   Wikipedia

  • Computational economics — Economics …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”