Имя (желательно полное):

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> > > > > > Пусть у нас есть компрессор, позволяющий сжимать и распаковывать без потерь :) произвольные файлы длиной не более N. > > > > > > Предположим, что такой компрессор сжимает как минимум половину исходных файлов как минимум на 1 бит. > > > > > > Тогда: > > > > > > общее количество всех файлов длины не более N бит будет 2^(N+1)-1. Соответственно, наш компрессор будет сжимать не менее 2^N файлов. Общее количество всех файлов длины N-1 (архивов, полученных для сжимаемых файлов) будет 2^N-1. Таким образом, найдется некоторый архив, которому будут соответствовать по крайней мере 2 исходных файла, и однозначно его распаковать не получится. > > А как ты будешь сжимать файлы длиной N1 > Еще раз посмотри на доказательство невозможности суперсжатия, и скажи, где же ошибка -- в твоих рассуждениях или моих? > > > В моих вроде все верно. > > Тогда, стало быть, ошибка в моем доказательстве? Тогда найди ее и скажи, где именно. > Твое доказательство доказывает только то, что все файлы невозможно сжать в один бит. Или сжать в "ничего". > > Опровержением будет считаться работающий (распаковывающий) .exe "суперкомпрессора". Правила тестирования просты -- я беру файл в 1Mb, сжимаю, несу архив и декомпрессор на "чистую" машину и распаковываю. > А почему бы не брать для упаковки файл в 1 или 2 бита и упаковывать его, затем вместе с декомпрессором таскать? Так условия выглядят круче? > Или так: выбери _ЛЮБОЙ_ файл, состоящий из 3-х байт, упакуй его, и вместе с decompress.exe перенеси на другую машину. Я считаю эти условия справедливые, поскольку предоставляю исходный файл выбирать тебе. > Такое рассуждение: > Рассмотрим алфавит А, один символ которого состоит из 8000 бит. Т.е. в этом алфавите будет 2^8000 различных символов. Рассмотрим _ПРОИЗВОЛЬНЫЙ_ файл, длина которого будет 2^8000*1000 символов алфавита А, или 2^8000*1000*8000 бит. Теперь берем любой компрессор А (будь то хоть PPM, или еще какой), который будет оперировать с символами данного алфавита. Если частоты символов в файле различны, тогда наш компрессор А без особых сложностей сожмет этот файл. Теперь рассмотрим второй случай, когда файл содержит в себе "белый шум", т.е. наш компрессор А, который оперирует символами алфавита А, окажеться абсолютно бесполезной вещью, поскольку не обнаружит какую-либо избыточность в файле. Вот тогда то мы берем компрессор B, который будет оперировать с алфавитом, символы которого состоят из 8 бит, а сам алфавит содержит всего навсего 256 символов. Теперь данный файл сожметься, поскольку в нем будет много регулярностей. В нем, например, будет символ из алфавита А, который состоит из одних нулей (причем в среднем их будет 1000), и при рассмотрении его с точки зрения алфавита А он ничем не выделяется среди остальных во всем файле, но если рассмотреть его с точки зрения алфавита B - это целая 1000 подряд идущих нулей! Или если рассмотреть проблему с другого конца, а именно - если компрессор B - не сможет ужать данные файла, то это значит, что их ужмет компрессор A, поскольку при рассмотрении файла в нем не будут встречаться символы, избыточные с точки зрения алфавита B. В итоге получили, что _ЛЮБОЙ_ файл размера 2^8000*1000*8000 бит можно сжать. (Вот и все ;)

Пожалуйста, заполните все поля.
И не нажимайте по два раза на кнопку! Дождитесь ответа сервера.