Understanding - Chapitre 1 Lesson 1

Lesson 1: Description Length

The information contained in an object is estimated by the length of its binary representation.Intuitively, if an object contains a lot of information, then it cannot be described in a concise manner and should be considered complex.This definition applies to any object or situation, as long as this object or situation can be coded to be represented in a computer.In this chapter, we will talk a lot about coding, as it is the most basic way to measure information content.Subsequent chapters will introduce alternative ways to assess complexity.

Start

Complexity of objects within sets

Problem: In a collection of objects, do the elements have the same complexity?

On many occasions, the complexity of objects is easy to estimate, just because these objects are already stored in the computer’s memory. Consider, for instance, the alphabet: a, b, c,... , z. It can be retrieved as a list. In Python as in most computer languages, letters can be addressed through their ASCII code:

>>> Alphabet = [chr(c) for c in range(97,123)]>>> print(Alphabet)['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t', 'u','v','w','x','y','z']

Once the alphabet is made available as a list, each letter can be retrieved by its rank on the list. So its complexity is estimated by the length of the binary representation of its rank.For instance, one can designate the letter k by mentioning its position: 11 within the alphabet. An estimate of its complexity is 4, as we can code 11 with 4 bits (1011).

Complexity of objects within sets

Question: Isn’t it easier just to say 'k' instead of 1011?Answer: No. 'k' is just a convenient representation of an ASCII code, 107, which is 1101011 in binary form.

Here is what we are able to do so far:

When an object can be retrieved from a list,its complexity within the list can be estimatedby the length of the binary representation of its rank.

Complexity of objects within sets

Ordered list

About 57 000 people took part in the Paris marathon. You remember a runner and want to check whether you know her. All you know is that she arrived 37th on the finish line. Once the ranking with the names of participants is made available, how many bits do the organizers need to retrieve her name?

Complexity of objects within sets

The letter ‘k’ is a simple character in python.What about the character ‘♖’ (white chess rook)?Its Unicode rank is 9814 (10011001010110 in binary form).So we may estimate the complexity of ‘♖’ as being about 14 (the length of 10011001010110).

Question: Can we assess the complexity of a character if we don’t know its exact Unicode value? Answer: Yes. Since there are a total of 1 114 112 different Unicode characters,we can be sure that the length of its binary representation must be less than 21 bits(you can check: int('100010000000000000000',2) is 1114112, and len('100010000000000000000') is 21).

Complexity of objects within sets

More generally:

When an object belongs to a set of size N,its complexity in that set cannot exceed log2(N).

This is because log2(N) bits are sufficient to represent any rank in the set of size N, ordered by whatever means.Estimating the complexity of an object this way is useful whenever it belongs to a set that has no obvious order.Consider for instance the cups in your grandmother’s cupboard. They may be ordered from left to right and bottom to top (if stacked up), or by colour and size if they are different, and so on. We suppose that you wish to designate one of the cups using such an ordering method.

Complexity of objects within sets

Unordered set

Complexity of objects within sets

For now, what we know about measuring the complexity of an object is this:

• we must find a code to represent the object in the computer (if the object is stored in a list, the code can be the rank in the list),

• we express the code in binary form,
• we measure the length of this binary form.

But it’s not sufficient. The notion of complexity is more demanding. One should find out the shortest possible binary code. So, any code that can spare bits is closer to the complexity of the entity.

Complexity of objects within sets

Description Length within a set

Complexity of objects within sets

Emoji complexity

Complexity of objects within sets

The Ugly Duck paradox

Consider these 12 objects.

Complexity of objects within sets

The Ugly Duckling paradox

Lesson 1 completed !

Score :

Chapter 1: Describing Data :

Lesson 1: Description Length

Lesson 2: Description Complexity of Integers

Lesson 3: Defining Complexity

Lesson 4: Conditional Complexity

Conclusion (4 Questions)

Back to home