January 2019

M T W T F S S
 123456
78 910111213
14 151617181920
21222324252627
28293031   

За стиль благодарить

Развернуть метки

No cut tags
Saturday, February 10th, 2007 03:00 pm
Может ли существовать обратимый архиватор данных (типа Zip-а), который гарантированно сжимает d=10% всех файлов не менее чем на c=20% (т.е. до 80% процентов прежней длины)? Остальные файлы могут не меняться или увеличиваться. Независимо от ответа (на или нет) - попробуйте дать более точную оценку для c и d (т.е. если ответ да - назовите как можно бОльшие d и c, для которых ответ еще да, если нет - как можно меньшие).

Уточнение: для бесконечного множества непонятно, что такое d. Считаем, что это утверждение верно для всех множеств файлов длины N для любого N, начиная с некоторого N0.

Комменты скринятся.