Еще кое-что о принципе голубей и ящиков
Чарлз Сейфе
Профессор журналистики Нью-Йоркского университета, бывший автор журнала Science; автор книги Proofiness: The Dark Arts of Mathematical Deception («Непроницаемость: темное искусство математического обмана»)
Порой даже простой подсчет может поведать нечто значительное. Однажды, еще в конце 1990‑х, будучи корреспондентом журнала New Scientist, я получил рекламное электронное письмо, воспевавшее какую-то необычайную компьютерную программу. В письме провозглашалось, что эта программа архивирования данных произведет настоящую революцию в цифровом мире, ибо она столь эффективна, что может сжать любой файл на 95 % или больше, не потеряв при этом ни единого бита данных. Может быть, мой журнал не упустит шанс поведать миру об этом софте, который позволит хранить на жестком диске в 20 раз больше информации, чем раньше?
Нет, мой журнал не станет об этом рассказывать, решил я.
Подобный алгоритм сжатия информации не может существовать. Это алгоритмический аналог вечного двигателя. Этот софт – жульничество. Причина – принцип голубей и ящиков.
Принцип голубей и ящиков – по сути, простое правило счета. Если у вас имеется n голубей и вам удалось запихнуть их менее чем в n ящиков, это означает, что по меньшей мере один ящик будет содержать в себе более одной птицы. Очевидно до банальности, не правда ли? Однако этот принцип – весьма полезный и мощный инструмент. К примеру, представим себе, что компрессионный софт, о котором шла речь, соответствует рекламному описанию и сжимает каждый файл в 20 раз без потери информации. Таким образом, каждый файл размером 2000 бит будет стиснут в какие-нибудь 100 бит, а при обращении алгоритма этот стобитный файл примет первоначальную форму, ничуть при этом не пострадав.
Сжимая файлы, вы волей-неволей натыкаетесь на принцип голубей и ящиков. Ведь общее количество 2000-битных голубей намного, намного больше (их 22000, если быть точным), чем 100-битных ящиков (их 2100). Если алгоритм позволяет полностью втиснуть первое во второе, это означает, что по меньшей мере один ящик должен содержать более одного голубя. Возьмем этот ящик (этот 100-битный файл) и попробуем обратить алгоритм сжатия, расширив этот файл до его исходной 2000-битной формы. Это не удастся сделать! Поскольку существует множество 2000-битных файлов, каждый из которых окажется сжатым в один и тот же 100-битный файл, алгоритм не сумеет определить, какой из этих 2000-битный файлов – истинный оригинал, так что компрессию будет невозможно обратить.
Принцип голубей и ящиков кладет непреодолимый предел возможностям компрессионных алгоритмов. Такие алгоритмы действительно способны успешно (без потери информации при распаковке) сжимать некоторые файлы, иной раз весьма значительно, однако все файлы так сжимать нельзя – во всяком случае, если вы настаиваете на идеальном сохранении данных.
Подобного рода «пересчет» открывает перед исследователями обширные горизонты. Немецкий математик Георг Кантор использовал разновидность обратного принципа голубей и ящиков, дабы показать, что действительные числа невозможно упаковать в ящики, предназначенные для целых чисел (по одному ящику на каждое число), хотя целых чисел бесконечно много. Отсюда следовал трудновообразимый вывод: существуют различные уровни бесконечности. Бесконечность целых чисел ничтожна по сравнению с бесконечностью действительных чисел, которая, в свою очередь, смехотворно мала по сравнению с еще одной бесконечностью, а та – по сравнению с еще одной бесконечностью… бесконечное число бесконечностей, которые останутся неисследованными, пока мы не научимся как-то их считать.
Применение принципа голубей и ящиков к исследованию глубин космоса приводит к еще более странным умозаключениям. Один из физических принципов, так называемый принцип голографической ограниченности, гласит: для каждого конечного объема пространства существует лишь конечное число возможных конфигураций массы и энергии. Если, как склонны полагать космологи, Вселенная бесконечна, то в ней существует бесконечное количество объемов пространства размером с видимую вселенную – гигантских космических пузырей, содержащих материю и энергию. Если пространство более или менее гомогенно (однородно), то в пузыре, где мы с вами обитаем, нет ничего такого уж особенного и уникального. Из всех этих допущений, взятых в совокупности, следует ошеломляющий вывод. Бесконечность количества таких пузырей размером со вселенную при конечном числе конфигураций вещества и энергии в каждом означает, что существует даже не одна точная копия нашей Вселенной (и нашей Земли). Согласно космической версии принципа голубей и ящиков, существует бесконечное количество копий каждой (строго выражаясь, «почти каждой»: для этого выражения имеется точное математическое определение) из возможных вселенных. Мало того, что существует бесконечное количество ваших собственных копий на этом бесконечном количестве планет Земля, есть и бесконечное количество вариаций на ту же тему: вы с хватательным хвостом, вы с несколькими головами, вы как профессиональный жонглер хищными кроликоподобными зверьками, получающий драгоценности для украшения одежды в уплату за демонстрацию своего искусства. Как видите, даже простой счет «раз, два, три…» способен привести к причудливым и неожиданным результатам.
Почему в программах встречаются баги
Марти Хёрст
Кибернетик, факультет информации Калифорнийского университета в Беркли; автор книги Search User Interface («Пользовательские поисковые интерфейсы»)
На протяжении всей истории программирования мы то и дело сталкиваемся с неприятной реальностью: никто из специалистов не знает, как создавать программы, заведомо свободные от ошибок.
Почему мы не можем в программировании быть так же успешны, как в других областях техники? Возможно, наиболее романтичным мыслителем из всех, кому следовало бы адресовать такой вопрос, является Фредерик Брукс, автор книги The Mythical Man-Month («Мифический человеко-месяц»). (Если обратить внимание на то, что эта книга со столь неудачным названием, как бы подразумевающим, что «человек» – это лишь «мужчина», man, впервые вышла в 1975 году, легче игнорировать сквозящий в ней сексистский душок: утверждения, которые Брукс сделал 4 десятка лет назад, почти все верны и на сегодняшний день, за исключением того, что программист – не всегда «он», как пишет Брукс, – бывает и «она».)
Делясь с читателями радостями программирования, Брукс пишет:
Программист, как и поэт, работает, почти вплотную соприкасаясь с веществом чистой мысли. Он строит замки в воздухе и из воздуха, создавая их лишь силой собственного воображения. Мало есть творческих инструментов столь гибких, столь удобных для перестройки и отладки, столь готовых к воплощению придуманных нами грандиозных конструкций… И при этом само творение-программа, в отличие от строк поэта, вполне реально в том смысле, что оно движется и работает, давая зримые результаты, отдельные и отличные от собственно конструкции. Программа распечатывает данные, рисует чертежи, издает звуки, двигает манипуляторами. В наше время магия легенд и мифов воплотилась в жизнь.
