Практическая информатика

Притча, рассказаная Эдгером Дейкстрой (Edsger W. Dijkstra) когда-то в районе 1973 г.

Много лет назад в одной только что основанной железнодорожной компании кто-то из директоров - вероятно, тот тип, что заведовал финансовым отделом - обнаружил, что можно существенно сократить начальные капиталовложения, если оборудовать туалетами только пятьдесят процентов вагонов. Так они и решили сделать.

Однако, как только компания начала перевозить пассажиров, стали стремительным потоком поступать жалобы насчет туалетов. Расследование, организованное компанией, показало, что случилась самое естественное: несмотря на молодость, компания уже начала страдать от неслаженности действий между своими подразделениями. Решение директора о туалетах не было доведено до персонала сортировочной станции, и они со всеми вагонами обращались одинаково. В результате, некоторые поезда компоновались так, что в них, можно сказать, и вообще не было туалетов.

Чтобы разрешить это затруднение, с каждым вагоном связали бит информации, определявший, есть ли в нем туалет, или нет, и сортировочной станции приказали компоновать поезда так, чтобы вагонов двух типов в них было по возможности одинаковое количество. Это было не совсем просто для сортировочной, но когда они все-таки разобрались, то люди, ответственные за процесс сортировки, очень гордились собой.

Несмотря на то, что теперь поезда компоновались по-новому, поток жалоб не иссякал. Организовали новое расследование, и выяснилось, что, хотя примерно в половине вагонов каждого поезда теперь и были туалеты, иногда все такие вагоны оказывались в одном конце поезда. Это положение решили исправить, составив новые инструкции, согласно которым при компоновке вагоны с туалетами и вагоны без туалетов следовало чередовать. Это доставило сортировщикам известные трудности, но, поворчав сперва, они справились и с ними.

Тем не менее, жалобы продолжались. Оказалось, что, поскольку туалеты были у вагонов с одной стороны, расстояние между двумя соседними туалетами могло быть порой и в три вагона. У мамаш с детьми, испытывавшими острую нужду, это зачастую приводило к катастрофическим последствиям, особенно, когда проходы были заставлены багажом. На все вагоны с туалетами тогда повесили еще один бит информации, так что они превратились в направленные объекты, и новые инструкции гласили, что в каждом поезде все вагоны нужно ориентировать в одну и ту же сторону. На этот раз новые инструкции встретили на сортировочной станции, мягко говоря, без всякого энтузиазма, так как поворотных кругов едва хватало; чтобы быть совершенно справедливым по отношению к работникам сортировочной, надо сказать, что их попросту не хватало, и только благодаря хитроумию и смекалке, этим людям удалось разрешить проблему.

Теперь, когда туалеты распределялись равномерно по каждому поезду, в компании решили, что все затруднения преодолены. Но пассажиры продолжали жаловаться - хотя от любого места расстояние до ближайшего туалета не превышало длины одного вагона, пассажиры (испытывавшие нужду) не знали, в какую сторону следовало им отправляться ковылять по корридору! Чтобы устранить это новое затруднение, во всех проходах нарисовали стрелки с надписью "ТУАЛЕТ". В результате, оставшаяся половина вагонов тоже стала асимметричными объектами, которые нужно было ориентировать в правильную сторону при сортировке.

Когда на сортировочной станции прочитали новую инструкцию, там установилась атмосфера отчаяния и вызревавшего бунта: предписания инструкции просто физически невозможно было выполнить. В этой критической ситуации некто, чье имя впоследствии было утеряно, так что теперь его уже невозможно установить, сделал следующее наблюдение. Если к каждому вагону с туалетом, с того конца, где располагался туалет, было прицепить отныне и навеки вагон без туалета, то сортировочной станции пришлось бы иметь дело уже не с N направленными вагонами двух типов, а с N/2 одинаковыми объектами, которые во всех случаях и для любой задачи можно было рассматривать как симметричные. И это решило все проблемы сортировки разом; цена решения была невелика: во-первых, в поездах должно было быть только четное количество вагонов, но немногие недостающие вагоны были куплены на деньги, сэкономленные дурнем-финансистом, а во-вторых, пришлось слегка жульничать насчет равных расстояний между туалетами. Но, в конце концов, последняя пара метров - не в счет.

Во времена, когда случилась эта история, человечество не было еще облагодетельствовано автоматическими компьютерами, однако наш аноним, придумавший это решение, заслуживает считаться первым в мире компетентным программистом.

Дейкстра также добавил: "Я рассказывал эту байку в разной аудитории. Как правило, программисты приходят в восторг, а управляющие неизменно по ходу повествования все более и более раздражаются; что касается настоящих математиков, то они не могут понять, в чем же здесь соль."

Архив публикаций Э. Дейкстры на сайте факультета информатики Техасского Университета