Колмогоровская сложность — различия между версиями
| Строка 1: | Строка 1: | ||
'''Колмогоровскую сложность''' можно рассматривать как способ измерения количества информации в строке. | '''Колмогоровскую сложность''' можно рассматривать как способ измерения количества информации в строке. | ||
| − | + | Но как понять, какое ''количество информации'' содержит в себе строка? Один из классических способов {{---}} это подсчет количества битов (число, пропорциональное длине строки). Рассмотрим следующий пример: | |
| − | |||
<pre>00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000</pre> | <pre>00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000</pre> | ||
| + | Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов. | ||
| + | |||
| + | Можем дать следующее определение. ''Количество информации'', которое несет строка {{---}} это размер архива, полученного сжатием строки каким-то конкретным архиватором (например, LZW). Это более нетривиальная задача, но мы можем придумать строку, которая явно несет в себе мало информации, но которую архиватор тем не менее не сожмет. | ||
| + | |||
| + | Еще более сильное определение. ''Количество информации'', которое несет строка {{---}} это размер архива, сжатого максимальным образом, самым лучшим архиватором. Но тогда встает вопрос, почему такой архиватор существует. | ||
Версия 12:43, 4 января 2015
Колмогоровскую сложность можно рассматривать как способ измерения количества информации в строке.
Но как понять, какое количество информации содержит в себе строка? Один из классических способов — это подсчет количества битов (число, пропорциональное длине строки). Рассмотрим следующий пример:
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов.
Можем дать следующее определение. Количество информации, которое несет строка — это размер архива, полученного сжатием строки каким-то конкретным архиватором (например, LZW). Это более нетривиальная задача, но мы можем придумать строку, которая явно несет в себе мало информации, но которую архиватор тем не менее не сожмет.
Еще более сильное определение. Количество информации, которое несет строка — это размер архива, сжатого максимальным образом, самым лучшим архиватором. Но тогда встает вопрос, почему такой архиватор существует.
