![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
А вот, оказывается, японцы Мурамацу и Каная придумали обобщение сложности по Колмогорову для lossy compression! Определяется для данной последовательности X^n = (X_1,...,X_n) и для заданного уровня потерь D как минимальная длина программы для универсальной машины Тьюринга, с помощью которой можно получить аппроксимацию X^n с точностью D. Если X^n это кусок стационарного эргодического процесса, то эта сложность равна примерно nR(D), где R(D) -- функция зависимости скорости передачи от искажения по Шеннону. (Связь с эпсилон-энтропией etc.) Круто (хотя и совершенно бесполезно с практической точки зрения)!
no subject
Date: 2005-12-17 01:50 am (UTC)no subject
Date: 2005-12-17 01:54 am (UTC)no subject
Date: 2005-12-17 02:12 am (UTC)no subject
Date: 2005-12-17 02:14 am (UTC)no subject
Date: 2005-12-17 07:50 am (UTC)no subject
Date: 2005-12-17 03:46 pm (UTC)no subject
Date: 2005-12-18 07:33 am (UTC)И чем вам интересны именно оптимальные алгоритмы?
no subject
Date: 2005-12-20 04:06 pm (UTC)Оптимальные алгоритмы интересны во-первых с теоретической точки зрения (теория Шеннона гарантирует их существование, но не предлагает эффективного метода их построения), а во-вторых с практической --- в распределенных вычислениях, скажем, могут быть ограничения на пропускную способность каналов между узлами сети.
no subject
Date: 2005-12-20 05:43 pm (UTC)no subject
Date: 2005-12-17 02:20 am (UTC)no subject
Date: 2005-12-17 02:35 am (UTC)no subject
Date: 2005-12-17 01:51 am (UTC)no subject
Date: 2005-12-17 02:36 am (UTC)no subject
Date: 2005-12-17 02:59 am (UTC)no subject
Date: 2005-12-17 03:35 am (UTC)Колмогоровская сложность -- штука чрезвычайно полезная и увлекательная. Но с ее помощью оптимальный по Шеннону алгоритм сжатия не построишь.
no subject
Date: 2005-12-17 04:12 am (UTC)no subject
Date: 2005-12-17 04:16 am (UTC)