Compressibility (computer science)

Compressibility (computer science)

In computer science a computable object such as a bitstring of size n is called compressible if there is computer program or algorithm that computes the bitstring but has fewer than n bits. The theory of Kolmogorov complexity is concerned with the shortest algorithms for computable objects.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Occam's razor — For the aerial theatre company, see Ockham s Razor Theatre Company. It is possible to describe the other planets in the solar system as revolving around the Earth, but that explanation is unnecessarily complex compared to the modern consensus… …   Wikipedia

  • Algorithmic information theory — is a subfield of information theory and computer science that concerns itself with the relationship between computation and information. According to Gregory Chaitin, it is the result of putting Shannon s information theory and Turing s… …   Wikipedia

  • Beta — may refer to: *Beta (β), the second letter of the Greek alphabetIn finance: * Beta coefficient in Capital Asset Pricing ModelIn mathematics: * Beta function in mathematics * Beta distribution in statistics * False negative rate in statistics *… …   Wikipedia

  • Mathematics and Physical Sciences — ▪ 2003 Introduction Mathematics       Mathematics in 2002 was marked by two discoveries in number theory. The first may have practical implications; the second satisfied a 150 year old curiosity.       Computer scientist Manindra Agrawal of the… …   Universalium

  • Fluid dynamics — Continuum mechanics …   Wikipedia

  • Mathematical beauty — An example of beauty in method a simple and elegant geometrical proof that the Pythagorean theorem is true for a particular right angled triangle. Many mathematicians derive aesthetic pleasure from their work, and from mathematics in general.… …   Wikipedia

  • Portable Network Graphics — PNG A PNG image with an 8 bit transparency channel (top). The same image is overlaid onto a checkered background (botto …   Wikipedia

  • Navier–Stokes equations — Continuum mechanics …   Wikipedia

  • Post-perovskite — is a high pressure phase of MgSiO3, is composed of the prime oxide constituents of the Earth s rocky mantle (MgO and SiO2), and its pressure and temperature for stability imply that it is likely to occur in portions of the lowermost few hundred… …   Wikipedia

  • airplane — /air playn /, n. 1. a heavier than air aircraft kept aloft by the upward thrust exerted by the passing air on its fixed wings and driven by propellers, jet propulsion, etc. 2. any similar heavier than air aircraft, as a glider or helicopter. Also …   Universalium

Share the article and excerpts

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