: : Есть и такая байка из области сжатия данных:
: : Любая последовательность данных может быть рассмотрена как результат работы генератора псевдослучайных чисел. Таким образом задача сжатия произвольного массива данных может быть сведена к задаче нахождения алгоритма генератора псевдослучайных чисел, порождающего его...
:
:
: Маньяков этой идеи раньше можно было встретить на comp.compress. Их характерная особенность - такого совершенно невозможно убедить, что есть лишь 2k варианта заполнения k бит.
Вариантов - да. Но они не о вариантах говорят, а о алгоритмах. А алгоритмов заполнения k битов одним и тем же значением может быть несколько... много... бесконечно много?.
В принципе длина неповторяющейся последовательности для генератора случайных чисел размером в i битов меньше или равна 2i (дерзкая гипотеза)... ну, пусть не i, а i/K, К -константа. Так что резонно ожидать, что для случайной последовательности длиной в m битов, существует некий "идеальный" генератор (он же и свертка) длиной в log2m битов, ну, или K*log2m.
Кстати, квантовые компьютерщики примерно в такие же игры пытаются играть... |
» Альтернативный форум