?

Log in

No account? Create an account

фтыкатель


хронограф нравственного падения

Recent Entries · Archive · Friends · Profile

* * *

На этом изображении представлена часть множества Мандельброта. Простое хранение 24-битного цвета каждого пикселя этого изображения требует 1,62 миллиона бит; но маленькая компьютерная программа может воспроизвести эти 1,62 миллиона бит используя определение множества Мандельброта. Таким образом, колмогоровская сложность «сырого» файла, кодирующего это изображение, много меньше 1,62 миллиона бит.

В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта.

Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.

Выражает возможность фрактального описания.

К примеру, рассмотрим две строки длиной 64 символа, содержащие только символы в нижнем регистре и цифры:

abababababababababababababababababababababababababababababababab
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf



Первая строка имеет простое описание на естественном языке, а именно ab 32 раза, состоящее из 10 символов. Вторая строка не имеет очевидного простого описания с использованием того же набора символов, кроме собственно самой этой строки, длина которой составляет 64 символа.

Более формально, сложность строки — это длина описания этой строки на некотором универсальном языке описания.

* * *
* * *
* * *
* * *
* * *
* * *
* * *
* * *
– Вы слышали новость? Андропов руку сломал.
– Кому?

– Юрий Владимирович, к вам польский посол.
– Введите.

* * *
* * *
* * *
* * *
* * *
* * *
* * *
* * *

Previous · Next