Главная страница «Первого сентября»Главная страница журнала «Информатика»Содержание №13/2009


Спецвыпуски

Информатика: Представление данных и алгоритмы. Главы из книги.

A. Введение в алгоритмику

A3. Конструирование алгоритмов

Надо сочинить закон или таблицу, по которой числа росли бы необъяснимыми непериодическими интервалами.

Д.Хармс 7

В разделах А1 и А28 много внимания уделено собственно возможности оценивать временную эффективность алгоритма, но там даже не пытались выяснить, а насколько это нужно практически.

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

Попробуем выяснить это, оперируя некоторыми цифрами. Предположим для определенности, что в нашем распоряжении процессор, способный осуществлять десяток миллионов (107) микроинструкций в секунду (mips), — и порадуемся за читателя, у которого на столе уже стоит компьютер с таким быстродействием9. Еще условимся, что спроектированный нами алгоритм требует в среднем по десять mips на каждый свой шаг. Это не много, если шаг алгоритма включает в себя, скажем, вычисление адреса памяти, где располагается элемент массива, выборку его и какую-то дальнейшую обработку. Очевидно, при таких условиях всего-то одной секунды машинного времени хватит на целый миллион (106) алгоритмических шагов вычислительного процесса!

“Что ж это за алгоритмы такие, где подобного быстродействия может быть недостаточно?” — спросит читатель. “Да много таких алгоритмов!” — ответим мы скептику. И упомянем для начала приводившийся ранее пример отбора треугольников10, исходное “сырье” для которых извлекается из набора отрезков. В самом деле, эффективность напрашивающегося, лобового, решения оценивается как O(n3), и, стало быть, набор из тысячи отрезков (103) будет обрабатываться более четверти часа. Так долго ожидать результат, сидя у экрана компьютера, — занятие малоувлекательное.

Не станем утверждать, что предлагаемый вариант, требующий O(n3) шагов, единственно возможный. Напротив, читателю стоит поразмышлять над тем, как распорядиться ресурсами более экономно и тем самым ступить на путь конструирования эффективных алгоритмов. Но ведь это и требовалось доказать: уже имеющийся в нашем распоряжении алгоритм провоцирует нас на поиски более качественного механизма. Тем более стоит поискать лучшее решение, если временная сложность готового алгоритма оценивается как O(n4) или O(n5). И не говорите, что таких задач не бывает, — ошибетесь.

Однако вас, возможно, удивит, что вычислительные процессы с трудоемкостью O(n3), O(n4) и даже O(n5) отнюдь не обязательно являются продуктами плохой алгоритмизации. Напротив, такие задачи не единичны, хотя здесь пока рано переходить к их постановке. Скажем лишь, что нередко более эффективных алгоритмов либо не сконструировать в принципе, либо их просто до сих пор не придумали. Отметим их общее свойство: все они относятся к классу так называемых алгоритмов с полиномиальной временной сложностьюO(nk), где k — константа и, естественно, не меняется с ростом количества элементов n.

Как же решаются, если в том возникает необходимость, задачи класса O(n4) или O(n5) для “больших” n? Ну, во-первых, не стоит забывать, что мы рассматриваем процессы, в основе которых лежит последовательное выполнение инструкций, а существует ведь и такая альтернатива, как параллельные вычисления. Кроме того, злополучные “четверть часа ожидания” критичны для пользователя, работающего непосредственно за компьютером, но совершенно безразличны ему, если вычислительный процесс идет в фоновом режиме работы его “персоналки” или, тем более, в пакетном режиме большой вычислительной машины.

Гораздо хуже обстоит дело с алгоритмами, трудоемкость которых составляет O(2n), O(n!), O(nn) и более. В этом перечне каждая очередная функция при достаточно больших n перекрывает предыдущие функции того же ряда. Или, как говорят, мажорирует их. Притом любая из них мажорирует трудоемкость полиномиальную. Такие алгоритмы принято характеризовать как имеющие экспоненциальную сложность.

Обратимся к примеру.

Пример A3.1. Ранее мы формулировали задачу, условия которой требовали перебора и рассмотрения всех вариантов выбора пары соседей, претендующих на первую парту в классе11. Тогда алгоритм оценивался как квадратичный относительно числа учеников, и это нас не слишком беспокоило.

Несколько изменив условие, будем рассматривать всевозможные способы рассадки всех n учеников на n местах. Легко заметить, что таких способов существует ровно

n (n – 1) (n – 2) 2 1 = n!.

Уже в маленьком классе, с 10 учениками, количество вариантов превосходит 3,5 миллиона. Предположим, наш компьютер столь хорош, что справится с такой порцией за одну секунду. Но стоит посадить в класс еще 5 учеников — и времени потребуется уже в 11 · 12 · 13 · 14 · 15 = 360 360 раз больше, или более 4 суток непрерывного счета.

Как видим, применять алгоритмы с вычислительной трудоемкостью O(n!) надо очень осторожно, если хотим дождаться конечного результата. Что же делать?

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

Предположим, что в классе из 15 человек, формируя очередное размещение их по партам, мы зафиксировали выбор 5 определенных учеников на места с 1-го по 5-е. Стало быть, на остающиеся 10 мест претендуют остальные 10 учеников, что соответствует 10! возможностям выбора. Если используемый в задаче критерий отбора позволяет зафиксировать нерентабельность уже исходного отбора первой пятерки, то и все семейство из 10! соответствующих ему рассадок нет смысла перебирать.

На этой идее в различных вариациях основано сокращение перебора во многих актуальных для практики задачах. Сам же механизм называется методом ветвей и границ.

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

Приведем пример, когда знакомство с методом частных целей автору пригодилось практически. За несколько дней до написания этого фрагмента текста у него возникла проблема срочного “переезда” из одной комнаты квартиры в другую в связи с ремонтом. Поскольку останавливать “производственный процесс” не хотелось, то пришлось переносить рабочее место, то есть письменный стол, компьютер и пр. Вот и подзадачи: разъединить составные части компьютера, перенести их в места новой дислокации, а там собрать. Каждая из подзадач решается автономно, правда, последовательность нарушать нельзя. Если вы этот текст читаете, значит, метод себя оправдал. Конечно, в описываемой ситуации возникли и другие, столь же неприятные подзадачи, но перечислять их не хочется.

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

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

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

Действительно, никому не удалось точно вычислить значение числа p — по причине невозможности. Однако же сделать это с обусловленной заранее точностью удается, для чего, кстати, существует довольно много различных алгоритмов, и — главное — во всех случаях вычислительный процесс конечен. Два из них описаны в предлагаемом читателю упр. A3.2.

Обсуждаемые алгоритмы относятся к классу приближенных. Их общее свойство — это возможность получения такого, пусть и неточного, решения, которое “сколь угодно мало” отличалось бы от верного. Для практических нужд, как уже сказано, этого может быть достаточно.

Уделив внимание возможностям применения точных и приближенных алгоритмов, мы обязаны, хотя бы конспективно, коснуться алгоритмов эвристических.

К ним относят методы, позволяющие найти некоторое, заведомо неточное, но устраивающее нас решение задачи. Однако в отличие от приближенных методов здесь уже нельзя судить о степени “похожести” результата на решение истинное: ни относительная, ни тем более абсолютная невязка оценке не поддается. Более того, эвристический алгоритм вовсе не обязан использовать итерационный подход, и тогда понятие приближения теряет смысл. Суть же механизма в том, что для слишком трудной задачи часть фигурирующих в ее исход­ной постановке требований просто игнорируют. Можно сказать, что применение эвристического алгоритма либо основано на некотором “знании” того, что должно получиться, либо оправдывается интуицией. (Впрочем, откуда взяться собственно интуиции без накопленного опыта?) В частности, это проявляется при отсеивании “малосущественных” условий из постановки задачи. Решение, которое удается получить при такой “усеченной” постановке, принимается как подходящее.

В поисках иллюстрации вновь обратимся к “незаконным” аналогиям за рамками конечной математики.

Так, мы не сомневаемся (что уже есть эвристика) в существовании конечных пределов физическим возможностям homo sapiens. Скажем, трудно отыскать человека, способного пробить кулаком стенку банковского сейфа. Но, не проводя достаточных исследований, надежность вкладов гарантируют избыточной толщиной.

Или: как высоко может прыгнуть вверх спортсмен, не прибегая к специальным приспособлениям? В качестве приближенного значения кажется разумным принять текущее мировое достижение. Его превышение очередным атлетом дает новую итерацию, уменьшая абсолютную невязку (это понятие объясняется в упр. A3.2) с неким “точным”, но практически недостижимым результатом. В этом смысле, похоже, мы имеем дело с приближенным алгоритмом. С другой стороны, изменение спортивной техники выполнения прыжка может существенно сдвинуть планку высших достижений, как это случилось при переходе от стиля “перекидной” к “фосбюри-флопу”. Не примени американец Фосбюри12 свой “флоп”, и мы вполне могли оставаться в неведении, принимая приближающийся с годами локальный экстремум прежнего стиля за экстремум абсолютный.

Узнавать о новых алгоритмах и учиться их применять — важная часть программистского образования.

Г.Джонстон13

Упражнения

A3.1. Оцените трудоемкость алгоритмов, связанных с перебором следующих комбинаторных объектов:

1) подмножеств n-элементного множества;

2) только его k-элементных подмножеств (k n);

3) последовательностей длины n, состоящих из чисел от 1 до k.

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

A3.2. Классический способ приближенного вычисления числа , вероятно, известен вам из школьного курса геометрии, но на всякий случай напоминаем его. “Точное” значение   есть результат деления длины произвольной окружности на ее диаметр. Если в окружность фиксированного радиуса последовательно вписывать правильные многоугольники, начав, скажем, с квадрата и удваивая на каждом шаге процесса число сторон, то очередное приближение для длины окружности получается как длина периметра соответствующего многоугольника. При этом с каждой очередной итерацией периметр все меньше отличается от окружности. Разница между искомой величиной и очередным приближением называется абсолютной невязкой (погрешностью). Стало быть, абсолютная невязка для приближенного значения числа p уменьшается с очередной итерацией. Разумеется, без знания точного значения нет возможности проверять, достаточно ли мала абсолютная невязка, чтобы удовлетворить заданной точности вычислений. Поэтому взамен проверяется относительная невязка, которая представляет собой разность (без знака) между двумя последовательными приближениями. Соответственно, процесс можно остановить по достижении относительной невязкой заданной точности. Например, для достижения в таком процессе часто используемого в вычислениях значения = 3,14 хочется дождаться, пока невязка станет меньше 0,01. Но принесет ли это успех? 14

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

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

A3.3. Вспомним еще одно хорошо знакомое вам число e — основание натурального логарифма. Для него известно разложение в числовой ряд:

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

A3.4. Похожий по сути механизм применяют для вычисления значения определенного интеграла. Постановка задачи: вычислить площадь под графиком непрерывной неотрицательной функции на заданном конечном интервале. В самой простой интерпретации механизм реализуется как метод левых прямоугольников. Идея состоит в том, что в качестве начального, нулевого, приближения для искомой площади назначается площадь прямоугольника, построенного на основании, равном длине интервала области определения функции, и на боковой стороне, равной ординате в левом конце этой области. На следующем шаге область определения разбивается ровно пополам, и в качестве очередного приближения принимается сумма двух прямоугольников, построенных из соответствующих полуинтервалов и левых ординат. Далее — вновь каждый из интервалов разбивается пополам, а значит, количество прямоугольников удваивается. Вычислительный процесс останавливается, когда разница между двумя последовательными приближениями становится меньше требуемой точности.

Полагаем, читатель без особого труда сформулирует, что собой представляет метод правых прямоугольников или метод средних прямоугольников. Стоит иметь в виду, что методы прямоугольников могут “плохо себя вести”, например, когда функция быстро растет или имеет несколько локальных экстремумов. На практике для ускорения сходимости итераций применяют более совершенные механизмы, такие, как метод трапеций, формула Симпсона и др., но эти темы — из сферы интересов вычислительной математики, а отнюдь не дискретной.

Ваша задача состоит, естественно, в написании программы. Предлагается вычислить методом левых прямоугольников определенный интеграл для функции
y = ax2 + b на интервале [0, c], причем точность и параметры a, b и c > 0 являются входными данными. В качестве ответа выдается количество необходимых итераций.

A4. От алгоритма к структуре данных

Создается впечатление, что на примерах сортировок можно построить целый курс программирования.

Н.Вирт 15

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

В самом деле, “с ходу” написанная программа вполне может оказаться неэффективной. Но всякий ли программист удосуживается выяснить это? К сожалению, с характерными примерами скрытой неэффективности нам неоднократно приходилось сталкиваться, обсуждая с юными кодировщиками предложенные ими алгоритмические и программные решения. Наиболее популярны при этом доводы, что готовая программа, во-первых, работает, во-вторых, работает быстро, и вообще, мол, чего вы от меня (или от нее, то бишь программы) хотите.

Действительно, представленный продукт выглядит работоспособным, и трудно убедить кодировщика, что ему стоит поразмыслить еще. Дело в том, что уровень сложности учебных задач, с которыми начинающие программисты имеют дело, не слишком высок. Если приходится строить алгоритм полиномиальной сложности, то обычно она не превышает O(n2), в крайнем случае — O(n3). А мы уже знаем, что при небольших значениях n реальное время выполнения такого вычислительного процесса не дает повода для поисков лучшего решения. В то же время подготовкой сколько­-нибудь значительного набора данных в целях проверки поведения программы при больших n те же программисты себя не утруждают. Что касается сложности экспоненциальной, то таких задач в учебном плане — мы имеем в виду обыкновенный школьный курс информатики — довольно мало, если они вообще представлены.

Итак, будем исходить из необходимости включить в “джентльменский набор” программиста как можно большее число базовых алгоритмов. Говоря “как можно больше”, мы не планируем просто перенумеровать их, а затем в порядке очередности обсуждать. И все же целесообразно провести некоторую их классификацию.

С одним из вариантов подобной классификации вам пришлось столкнуться уже на раннем этапе знакомства с дисциплиной программирования. Имеется в виду предваряющая алгоритмику классификация программных механизмов по типам — линейный алгоритм, ветвление и цикл.

Разумеется, обсуждение эффективности только начинается с появлением циклической обработки, и нам надо идти дальше. Заманчивой выглядит идея Вирта, вынесенная в эпиграф. Но цель, которую мы преследуем в этом разделе, гораздо скромнее: мы не замахиваемся на “целый” курс, а хотим лишь продемонстрировать различия в алгоритмическом содержании задач, возникающих перед программистом. Что нам мешает проделать нечто подобное (или хотя бы попытаться) на основе объекта, знакомого любому читателю, — таблицы умножения? Итак, предлагаем отнестись к дальнейшим рассуждениям как к некоему развернутому упражнению по конструированию алгоритмов.

Естественно, прежде чем обратиться к таблице, следует поставить задачу. Примем следующую формулировку: вычислить по входным значениям пары натуральных чисел соответствующее выходное значение — их произведение. На ключевое слово вычислить обратите внимание: его присутствие отражается в том, как построен следующий

Алгоритм A4.1. Вернувшись на сколько­то лет назад, каждый из нас вспомнит, как его учили решать сформулированную выше задачу в пер­вом классе. Предположим, что входной тест представлен числами 5 и 6 (очевидно, годится и любая другая пара однозначных чисел).

Возьмем кучку из 5 спичек; добавим к ним еще 5 из второй кучки; затем еще 5 из третьей и т.д., пока не соберем спички из всех шести кучек вместе. Сколько всего у нас получилось спичек? Возможно, для умножения 5 6 вам предлагали в детстве интерпретацию “5 кучек по 6 спичек” (рис. А4.1), но автора учили именно так — впрочем, сути это не меняет.

Номер кучки

1

2

3

4

5

6

Количество спичек в кучке

5

5

5

5

5

5

Рис. A4.1. Детские воспоминания,
или Что такое “умножение”?

Такое объяснение или нечто в этом роде описывает алгоритм умножения двух сомножителей — первого на второй — в классе натуральных чисел. Трудоемкость этого алгоритма составляет O(n), где n — второй сомножитель.

Алгоритм A4.2. Несколько больше проблем вызовет ситуация большого числа кучек (пусть в новом примере их 26) и спичек в них (по 15 в каждой). Теперь уместно вспомнить алгоритм умноженияв столбик.

Умножая здесь 6 на 15, по ходу вычислений мы должны умножить 6 на 5 (или 5 на 6), что позволяет свести многие шаги алгоритма A4.2 к вызовам алгоритма A4.1. Можно предположить, что в свое время этот вариант алгоритма был одним из первых опытов читателя в применении метода сведения задачи к подзадачам.

Алгоритм A4.3. Чем нас не устраивает — или может не устроить при наличии лучшего решения — алгоритм A4.2? Естественно, многократными вызовами алгоритма A4.1, чья эффективность сомнительна. Здесь-то наконец нам и пригодится таблица умножения (рис. A4.2).

Значение, которое постановка задачи предлагает вычислить, таблицей предоставляется непосредственно — на пересечении 5-й строки и 6-го столбца. Все бы хорошо, но остальные строки и столбцы оказываются “лишними”, создавая проблему выбора именно той пары, которая нужна. Так возникают две однотипные подзадачи (вновь декомпозиция!): поиска 5-й сверху строки и, после этого, поиска в ней 6-го слева числа.

Такой поиск отнюдь не является примитивной операцией. Он требует циклической обработки кандидатов в определенной последовательности — в нашем случае перебора и проверки строк с 1-й по 5-ю, затем столбцов с 1-го по 6-й. Легко заметить, что очередность кандидатов в последовательности может быть установлена и иначе: скажем, от нижней строки — вверх и затем от правого крайнего столбца — влево. Но характер этих отличий лишь технический, они никак не влияют на оценку трудоемкости перебора входящих в последовательность элементов.

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

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

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

Алгоритм A4.4. Так, если мы расширим стандартную таб­лицу умножения до 15 строк и 26 столбцов, то интересующее нас произведение обнаружим в нижнем правом ее углу (рис. A4.3).

По существу постановка задачи и знакомство с алгоритмом A4.3 продиктовали выбор структуры, а входные данные определили значения параметрам структуры.

Конечно, не всякое алгоритмическое решение стоит принимать, но мы ведь пока только рассуждаем, а не кидаемся с ходу писать программный код. И здесь несложные рассуждения показывают, что алгоритм A4.4 нас вряд ли устроит. Действительно, с ростом числа строк m и столбцов n, то есть значений входных параметров, размеры таблицы должны быть никак не меньше произведения указанных величин. Приходится вспоминать о емкостной сложности алгоритма, которая связана с хранением информации в выбранной структуре данных и составит O(mn).

Рассуждая далее, замечаем, что и с оценкой временной сложности возникают проблемы. Мало выделить память под структуру; чтобы хранить данные, сначала надо их там разместить, а на это также потребуется время порядка O(mn). Кстати, начальное размещение данных в выбранной структуре часто называют ее инициализацией. Итак, при однократном вычислении произведения 15 26 последний алгоритм нас не устраивает сразу по двум причинам: из-за неэффективности расхода времени на этапе инициализации и из-за емкостной неэффективности выбранной структуры.

Естественно, те же рассуждения актуальны для любой пары значений сомножителей. Как быть: ведь задачу умножения натуральных чисел приходится решать регулярно? В некомпьютерной практике (микрокалькуляторы не в счет) мы нередко пользуемся двумя альтернативными алгоритмами, переключаясь в нужные моменты. Механизм здесь следующий: числа с разрядностью более 1 перемножаем в столбик согласно алгоритму A4.2, а для поразрядных операций обращаемся к таблице умножения из алгоритма A4.3. При таком подходе хранимая “в уме” — но в детстве инициализированная! — таблица умножения имеет привычные размеры 10 10 (или 9 9), и до алгоритма A4.4 дело не доходит.

Однако на размерах таблицы 10 10 свет клином не сошелся. Читателю, наверно, любопытно узнать, что австралийские школьники зубрят таблицу 13 13. Стало быть, и здесь есть место выбору. Ну а при компьютерной обработке, когда используется двоичная система счисления, таблица становится совсем небольшой — 2 2. Есть ли смысл инициализировать ее в оперативной памяти, или используются иные алгоритмы, мы обсудим в главе B нашего курса, где пойдет речь о компьютерной арифметике.

Впрочем, не станем отвлекаться. Надеюсь, читатель не забыл, что наша цель — обрисовать круг задач и алгоритмов, встречающихся в практике программирования и, естественно, в нашем курсе. А таблица умножения служит нам всего лишь модельным объектом. Зато в нашу классификацию добавляется еще один метод решения задач — это компьютерное моделирование. Точнее, численное моделирование, при котором компьютер служит быстродействующим исполнителем и демонстратором результатов обработки. Глубоко вторгаться в эту самостоятельную область информатики мы не намерены, ограничимся лишь одним примером. Имеем в виду визуализаторы алгоритмов, которых на нашем сайте16 немало. В самом деле, это всего лишь модели, и применение их для реализации (в полном объеме) возможностей и целей соответствующих алгоритмов не предусмотрено.

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

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

Язык программирования может допускать или не допускать манипулирование всей структурой как целым, но всегда допускает обработку составляющих ее элементов в отдельности. В алгоритмике актуальны обе возможности. Каждой обрабатываемой структуре приписывается ее собственный набор операций, и в этом смысле возможности языка обычно уже. Так, отдельные алгоритмические операции нередко приходится эмулировать последовательностью операций, допускаемых рамками языка. Подробно эти вопросы также ждут своего обсуждения — мы перейдем к нему в главе C.

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

КСТАТИ

Возможно, ваше знакомство с ЭВМ до сих пор не требовало знания устройства оперативной памяти. В таком случае выясните, что собой представляет оперативная память как структура (размещения) данных.

Наконец (а, возможно, с этого следовало как раз начать), объединение элементов в структуру требует, чтобы они обладали неким — по крайней мере одним — общим свойством. В нашей модельной задаче этим признаком является принадлежность элементов к классу натуральных чисел.

Представим, что в ячейках таблицы умножения, помимо цифрового значения, разместили также и его словесное обозначение, например, “30, thirty”. Этот вариант мог бы нам пригодиться, скажем, как методическое пособие при обучении числительным английского языка. Тогда значением элемента структуры является вся запись “30, thirty”, ключом записи будет “30”, а информационная часть — “thirty” — доступна по ключу.

Для выбранного представления понятия ключ и номер (или индекс) элемента не являются взаимозаменяемыми. Назначение ключа — идентифицировать элемент структуры, назначение индекса — обеспечивать доступ к элементу. Так, в таблице на рис. A4.2 ключи присутствуют в явном виде: в левом столбце размещены ключи строк, а в верхней строке — ключи столбцов. Номера же строк и столбцов связаны со способом отображения структуры на конкретном носителе. Например, из той же таблицы вполне можно левый столбец и верхнюю строку убрать и тем самым оставить ее без ключей.

Здесь внимательный читатель может упрекнуть нас в различном применении понятия элемент при рассмот­рении примеров. Действительно, то мы понимаем под элементом строку (или столбец), то элемент лежит на их пересечении. Фактически таблица из строк, таблица из столбцов и “просто” таблица умножения лишь внешне, на книжной странице, выглядят одинаково, однако с точки зрения доступа они различны. Различие определяется уже типом составляющих структуры элементов, но не только им. Соответственно, речь идет о разных структурах, и манипулировать этими тремя таблицами придется также по-разному.

КСТАТИ

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

— Боюсь, что не сумею вам все это объяснить, — учтиво промолвила Алиса. — Я и сама ничего не понимаю. Столько превращений в один день хоть кого собьет с толку.

Л.Кэрролл 17

Упражнения

A4.1. Если мы задумаемся о способе хранения таблицы умножения, то, вероятно, решим, что нужны еще какие­-то операции. Какие?

A4.2. Можно ли рассматривать ряд натуральных чисел в качестве структуры данных?

A4.3. На какой структуре данных вы остановились бы при описании воинского подразделения на параде?

A4.4. Какой из трех вариантов описания таблиц умножения в конце раздела целесообразнее с точки зрения применения “по назначению” при размещении таблицы в памяти ЭВМ?

A4.5. Можете ли вы предложить иные варианты для структуры “таблица умножения”, кроме трех предложенных выше?

A4.6. (Навеяно задачей из [27].) Напишите программу “изучения английских числительных по таблице умножения”. Результатом ее работы должна быть отображенная на экране (или выведенная в файл) таблица умножения, в которой все числа записаны прописью по-английски.

A5. От структуры данных к алгоритму

Таблица

Умножения

Достойна

Уважения.

С.Я. Маршак 18

Вновь обратимся к нашему модельному объекту — таблице умножения. Очевидно, что стандартные размеры этой структуры — 10 10 — продиктованы используемой системой счисления. Переход к другому основанию, скажем, к шестнадцатеричной системе, потребует, во-первых, расширения таблицы в двух направлениях, во-вторых, инициализации новых элементов (разумеется, если воспользоваться старой таблицей).

Возникает проблема распределения места в памяти под структуру. Ну как, спрашивается, добавить 6 строк к таблице на рис. A4.2? Если текст на бумаге, то, как говорится, написанное пером… То же самое можно сказать и о структуре данных в программе, если описанием заданы фиксированные размеры. Вывод таков: перспективу расширения жизненного пространства для программы планировать надо заранее, на этапе конструирования алгоритма. Не зря печальный опыт истории свидетельствует, что большинство войн начиналось из-за территориальных споров.

К счастью, алгоритмика и вслед за нею архитектура ЭВМ предусматривают возможность увеличивать/уменьшать размеры определенных структур во время исполнения программы. Структуры данных, которые допускают подобные манипуляции, называют динамическими, противопоставляя их неизменяемым — разумеется, только по размерам, а не содержанию — статическим структурам. В постановке задачи не обязательно наличие прямого указания, какой тип структуры предпочтителен, и выбор остается за алгоритмистом.

КСТАТИ

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

Иногда случается в книгах по информатике прочесть о вставке элементов в статическую таблицу, но принимать это за чистую монету не стоит. Речь идет либо о замещении значений элементов в заполненных позициях таблицы, либо об инициализации позиций незаполненных.

Так, предвидя обращение к задаче “15 26”, вместо обычной таблицы умножения можно заранее выделить место под таблицу, соответствующую алгоритму A4.4 (см. рис. A4.3 на с. 8), а инициализацию провести только для стандартного размера, то есть для левого верхнего угла 10 10. В этой ситуации размеры заранее установлены “с запасом” и надо инициализировать остальную часть. Более трудоемким грозит стать процесс вставки строки между ранее размещенными. Он потребует перемещения ряда строк вниз, что означает, собственно говоря, просто переписывание элементов в новые позиции и лишь затем — инициализацию элементов вставляемой строки. Что собой представляет в том же контексте удаление элементов статической структуры, читатель легко догадается сам.

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

А теперь представим себе снова таблицу умножения стандартных размеров, но нестандартного содержания. Скажем, мы рассыпали строки обычной таблицы, а потом собрали их в случайном порядке.

Как технически инициализировать случайный порядок строк — в нашем случае натуральных чисел от 1 до 9? Языки программирования, как правило, предоставляют для этого встроенные средства, вроде известной читателю функции Random. Можно назвать немало задач, решение которых основано на использовании последовательностей случайных чисел. К ним относятся, например, некоторые проблемы криптографии, где возможность (или невозможность) воспроизвести последовательность, которая использовалась при шифровании сообщения, находится в центре внимания алгоритмиста.

Итак, возможность быстрого получения чисел, составляющих некоторую случайную (правильнее говорить псевдослучайную) последовательность, вполне актуальна. Обычно подобные наборы не хранятся в системе программирования, тем более в операционной системе, и при необходимости прибегают к специальным алгоритмам генерации случайных чисел. Пример построения такого набора мы включили в упр. A5.5.

Вернемся к задаче об “испорченной” таблице умножения. Предположим для определенности, что вариант хранения данных оказался таким, как представленный на рис. A5.1. Учтите, что столбцы согласно условию не пострадали. Как искать произведение 5 6 в “испорченной” таблице?

Обратиться — по индексу — непосредственно к нужной нам строке, бывшей 5-й, нельзя, поскольку она могла переместиться. Приходится перебирать строки последовательно, проще всего — сверху вниз. Отличить искомую строку от остальных позволяет ее ключ, расположенный в левом столбце. Однако только при совпадении значения ключа с первым из сомножителей можно далее двигаться вправо по найденной строке. Если же перетасовать и столбцы, то задача рискует стать неразрешимой.

КСТАТИ

Системные оболочки Norton Commander, Far, Windows Commander предоставляют возможность менять в зависимости от цели использования порядок расположения имен каталогов и файлов в панелях, выводимых ими на экран. Информация на эти панели попадает из соответствующих каталогов операционной системы. Вспомните (или выясните), как организованы каталоги, из каких записей состоят, какие поля играют роль ключей.

Что произойдет, если из второй, “испорченной”, таб­лицы изъять столбец и строку с ключами, как на рис. A5.2? Сохранится ли возможность поиска все того же произведения 5 6?

Более того, можно продолжить эксперименты с таблицей и “испортить” ее настолько, что в ней вообще останется только первый столбец (рис. A5.3), но при этом возможность полного ее восстановления сохранится. Это так, поскольку соседние элементы внутри каждой строки представляют собой нарастающие суммы повторяющегося слагаемого (вспомните алгоритм A4.1 и рис. A4.1), причем у каждой строки ее собственное слагаемое содержится в ней в качестве первого элемента.

Иначе говоря, мы имеем дело с зависимостью

si, j + 1 = si, j + si,1 ,                                       (A5.1)

где i — номер строки на рис. A5.2 и A5.3, j — номер столбца на рис. A5.2, si,j — элемент таблицы на пересечении i-й строки и j-го столбца. Соотношения подобного вида принято называть рекуррентными. Применение они находят в разнообразных задачах, в том числе связанных с обработкой таблиц. Методы и задачи, при этом возникающие, относят к так называемому динамическому программированию (см. раздел E1).

Альтернативой методам динамического программирования, основанным на использовании таблиц в явном виде, является применение рекурсивных механизмов. Об использовании рекурсии в ряде задач и необходимой для этого механизма структуре данных — стеке — речь идет в разделе E3 книги.

Однако вернемся к обычному виду таблицы умножения. Вполне естественной выглядит обратная задача, связанная с установлением “адреса” в ней по заданному значению элемента: для натурального числа n выяснить, на пересечении каких строки и столбца оно записано. Кстати, если элемента нет в таблице, то адрес так и не найдется.

Приходит на ум аналогия из некомпьютерной тематики, связанная с установлением хозяина ключей, найденных вблизи многоквартирного дома. Скорее всего поиск квартиры и владельца придется вести последовательно: от подъезда (столбца таблицы) к подъезду и внутри очередного подъезда — по этажам (строкам). Если дом очень большой, то процесс, трудоемкость которого сопоставима с количеством квартир, может затянуться, и энтузиазм иссякнет.

К счастью, для решения нашей задачи можно предложить более экономичные алгоритмы, а именно разлагать входное значение на всевозможные пары сомножителей и проверять их. Так, для n = 30 найдется несколько пар­претендентов: (1, 30), (2, 15), (3, 10), (5, 6), (6, 5), (10, 3), (15, 2) и (30, 1). Сразу отсеиваются пары, включающие в себя числа, большие 9. Соответственно, остаются только (5, 6) и (6, 5). Иначе говоря, вместо алгоритма поиска используется некоторый вычислительный механизм.

В данном примере, когда разрешенный диапазон ограничен узкими рамками нашей таблицы, задача элементарно решается в уме. Но с ростом n проблема усложняется, и желательно прибегнуть к какому-нибудь эффективному механизму. Частично нас выручит — вероятно, знакомый читателю по школьному курсу алгебры — алгоритм Евклида19 (мы к нему еще обратимся позже).

Попутно воспользуемся ситуацией и вновь напомним читателю о “нехороших” задачах, для решения которых алгоритмы полиномиальной сложности не найдены. Такова, к сожалению, и задача факторизации (разложения натурального числа на простые множители), актуальная для современной криптографии. Впрочем, может быть, и “к счастью”: с точки зрения владельца секретного кода — это хорошо, шпион же думает иначе20.

В своих рассуждениях мы уже несколько раз меняли структуру данных, предназначенную для представления таблиц умножения. Чаще всего это диктовалось желанием уменьшить емкостную сложность алгоритма, выделив меньше места для хранения данных. Если при этом преследовать цель не терять данные — а именно так стоял вопрос при переходе от представления на рис. A5.2 к представлению на рис. A5.3, — то возможным подходом будет установление взаимно однозначного соответствия между различными представлениями. Тогда мы можем переходить от одной структуры к другой без ущерба для набора данных.

Удобно, если такой переход удается описать одной формулой. Но зачастую подобные преобразования реализуются многошаговым алгоритмом. Следовательно, при замене “структуры пользователя” на структуру данных в программе для ЭВМ следует учесть накладные расходы (машинное время) на реализацию алгоритма преобразования. Заметим, что временная сложность такого преобразования (в одном направлении) может заметно отличаться от сложности обратного преобразования.

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

1. Таблица симметрична относительно главной диагонали (диаго­нали, идущей из верхнего левого угла к правому нижнему). Следовательно, можно без ущерба для содержимого отказаться от выделения места под левый нижний треугольник исходной квадратной матрицы.

2. Затем строка за строкой перепишем данные из правого верхнего треугольника матрицы в линейный массив. Отличие нового представления от обычного хранения двумерного массива в оперативной памяти определяется тем, что усеченные строки имеют разную длину.

Таким образом, мы осуществили упаковку исходной таблицы в линейный массив, уменьшив емкостную сложность примерно вдвое.

Более широкая постановка задачи кодирования и сжатия данных представлена в главе F. В частности, там рассматриваются разнообразные кодыпостоянной длины и переменной длины — и в связи с последними семейство алгоритмов Хаффмена.

Сразу обращаем внимание искушенного читателя, что мы ограничиваемся в нашем курсе алгоритмами сжатия без потерь, и искать в ука­занной главе описание современных алгоритмов упаковки видео- и аудиофайлов не стоит. А менее искушенному поясним, что речь пойдет только о такой упаковке информации, когда обратное преобразование позволяет восстановить “все как было”.

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

Ф.Брукс21

Упражнения

A5.1. Какова трудоемкость “удаления” k нижних строк при статическом размещении таблицы умножения m n?

A5.2. Напишите программу, раскладывающую на простые множители заданное натуральное число n.

A5.3. В разделе A3 вы уже познакомились с приближенными методами вычисления интеграла. Идею метода Монте-Карло, конкурирующего с описанными там механизмами, сейчас проиллюстрируем на том же примере вычисления площади Sfigure фигуры, ограниченной сверху графиком конечной непрерывной и неотрицательной функции f(x), снизу — конечным интервалом оси абсцисс [a, b], по бокам — ординатами на концах интервала (рис. A5.4). Интересующую нас фигуру можно целиком поместить внутрь прямоугольника, площадь которого ограничена тем же интервалом, теми же ординатами и некоторым значением y0, мажорирующим заданную функцию. Теперь будем поочередно запускать “достаточно большое число раз” (n) датчики случайных чисел для генерации точек с координатами из интервала [a, b] и интервала [0, y0]. Соответственно, можно следить за тем, сколько точек (ninside) “попало” внутрь фигуры и сколько осталось за ее пределами, но, естественно, внутри прямоугольника. По завершении эксперимента чем больше n и “качественнее” датчик, тем ближе к равенству приближенное соотношение

Читателю предлагается написать соответствующую программу и протестировать ее для “табличных” функций, сравнивая результаты со значениями, вычисленными по таблице интегралов. Также представляет интерес сравнительный анализ результатов вычисления методом Монте-Карло и методами прямоугольников (трапеций и подобными).

A5.4. Формула S = r2 наталкивает на мысль об еще одном способе приближенного вычисления — как отношения площади круга к площади квадрата, построенного на его радиусе. Напишите программу, вычисляющую это отношение по методу Монте-Карло.

A5.5. Выбирается произвольное двузначное число и назначается первым элементом n1 последовательности псевдослучайных чисел, а затем каждый очередной элемент ni+1 получается из предыдущего элемента ni. Для этого ni возводится в квадрат, и от 4-значного результата отбрасываются левая и правая цифры. Например: ni = 25 ni2 = 0625 ni + 1 = 62. Поскольку различных чисел в такой последовательности конечное число, то рано или поздно она будет самовоспроизводиться, начиная с некоторого места. Поэтому алгоритм генерирует именно псевдослучайные числа. Напишите программу, генерирующую такую последовательность по заданному входному значению n1. Найдите место первого повтора ранее полученного элемента.

Перебрав всевозможные начальные значения, установите наибольшую длину неповторяющейся псевдослучайной последовательности. Какие n1 оказываются наиболее “продуктивными”?

A5.6. Выведите формулу для прямой адресации к элементу упакованного представления таблицы по заданному адресу исходного представления, то есть по паре (i, j), где i — номер строки, j — номер столбца.

A5.7. Найдите способ восстановления исходного расположения элемента по его индексу в упакованной таблице.

A5.8. Напишите программу, которая по заданному на входе размеру n таблицы умножения n n выводит содержимое упакованной в линейный массив верхней треугольной матрицы, не формируя промежуточный набор — саму таблицу.

A5.9. Получите формулу, связывающую размер исходной таблицы умножения с длиной ее упакованного представления.

A5.10. Напишите программу, осуществляющую распаковку таблицы.

A6. Алгоритмы обмена

— Деньги вперед, — заявил монтер, — утром — деньги, вечером — стулья или вечером — деньги, а на другой день утром — стулья.

— А может быть, сегодня стулья, а завтра деньги? — пытал Остап.

— Я же, дуся, человек измученный. Такие условия душа не принимает.

И.Ильф, Е.Петров22

Всякий раз, когда мы решаем задачу и располагаем не единственным вариантом решения, естественно выбрать из них тот, который потребует меньшего объема работы23. Вольно переиначивая известную сентенцию, можно сказать, что руководством к действию мы выбираем девиз “лень оправдывает средства”.

Соответственно, перекладывая вычислительную работу на “плечи” компьютера, разумно будет проектировать такой алгоритм решения задачи, который потребует меньших ресурсов времени (нередко — и памяти) при работе устройства.

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

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

Пример A6.1. Набор правил, в соответствии с которыми мы действуем, когда переходим через улицу на (не)регулируемом перекрестке. Отметим, кстати, что в этой ситуации допускается определенная степень произвола в осуществлении действий исполнителя, что приводит иногда к весьма драматическим последствиям.

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

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

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

Пример A6.4. Весьма странным выглядел бы и автоматизированный зачет, когда итоговая оценка выставляется до того, как получены ответы на вопросы. (Впрочем, когда в роли экзаменатора выступает человек, подобное встречается.)

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

Пример A6.5. Выполнить умножение двух натуральных чисел 8 9 можно по крайней мере двумя известными способами: либо заглянуть в таблицу умножения, либо сложить 9 восьмерок (или 8 девяток). Какой из вариантов “быстрее”?24

Каков “алгоритм проектирования алгоритма” решения конкретной задачи?

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

Насколько глубоко следует забираться в этом процессе, зависит исключительно от конкретной проблемы. Обычно проектировщик старается довести разбиения до таких подзадач, решение которых либо реализуется стандартным образом (например, применяется готовый вспомогательный алгоритм), либо дальше легко программируется “в лоб”.

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

При переходе же к собственно программированию обычно подзадачи оформляются как подпрограммы. Рассмотрим далее несколько стандартных алгоритмов, часто находящих применение при решении разнообразных задач.

Алгоритм A6.1. Алгоритм обмена № 1.

Имеются 2 переменных a и b. Поменять их значения местами.

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

Проверим работоспособность этого алгоритма на примере, скажем, a = 5 и b = 8:

Полезно оформить приведенный алгоритм как процедуру — она нам еще пригодится.

1 procedure Swap(var a, b: TItem);

2 var tmp: TItem;

3 begin

4 tmp := a; {шаг 1}

5 a := b; {шаг 2}

6 b := tmp {шаг 3}

7 end;

При использовании следует лишь вместо TItem26 подставить соответствующий условию задачи тип данных.

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

Алгоритм A6.2. Алгоритм обмена № 2.

Имеются 2 целочисленных переменных a и b, причем их сумма не выходит за рамки диапазона значений, допускаемого заданным типом. Поменять их значения местами.

В этом случае можно использовать механизм, не требующий дополнительной переменной:

Сравните: при тех же a = 5 и b = 8 получаем

Наконец, есть еще нижеследующий алгоритм.

Алгоритм A6.3. Алгоритм обмена № 3. Он также не требует дополнительной переменной и использует свойство логической операции xor:

Проверьте работоспособность алгоритма на том же числовом примере.

Выше мы отмечали, что понятие шаг алгоритма следует конкретизировать в каждом случае. В трех рассмотренных алгоритмах, очевидно, под шагом надо понимать реализацию оператора присваивания, включая в него (в шаг) все необходимые машинные операции. Таким образом, алгоритм обмена реализуется за 3 шага, то есть имеет трудоемкость O(1).

Применение механизма обмена актуально в большом числе алгоритмов, сошлемся хотя бы на целое семейство обменных сортировок (см. разделы D5 и D6 в книге). Определенное сходство с формальным обменом значениями имеет механизм “обмена ролями” между переменными. Он находит применение в алгоритме Евклида, предназначенном для отыскания наибольшего общего делителя (НОД27) пары натуральных чисел.

Алгоритм A6.4. Алгоритм Евклида.

1 function GCD(a, b: longint): longint;

2 begin

3 while (a > 0) and (b > 0) do

4 if a <= b then

5 b := b - a

6 else

7 a := a - b;

8 GCD := a + b;

9 end;

Улучшенный вариант алгоритма рассмотрен в упр. E6.3 в книге.

КСТАТИ

Механизм “обмена ролями” не столь уж экзотичен. Так, например, действует связка из двух альпинистов при парном восхождении, когда роль ведущего попеременно выполняет то один, то другой скалолаз.

Упражнения

A6.1. Напишите процедуры Swap2 и Swap3, реализующие алгоритмы обмена № 2 и 3.

A6.2. Дана последовательность чисел. Каждое число в ней встречается четное количество раз, за исключением некоторого x, встречающегося нечетное количество раз. Найдите x.

С. СТРУКТУРЫ ДАНЫХ И ОПЕРАЦИИ

С1. Порядки

Порядокъ — совокупность предметовъ, стоящихъ поряду, рядомъ, рядкомъ, врядъ, сподрядъ, не вразбросъ, не враскидъ, а одинъ за другимъ.

Вл. Даль28

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

Как правило, всякая задача поддается разбиению на составные, нередко независимые, части. В разделе A3 мы обращали внимание на технологию декомпозиции задач и композиции решений, связанную с таким разбиением. Степень измельчения на фрагменты и размеры таких “кирпичиков” определяется содержанием конкретной задачи — вот здесь разработчику-программисту как раз и открывается фронт работ. Аналогия с трудом архитектора-проектировщика, работающего в сфере блочного домостроения и ориентирующегося на номенклатуру изделий домострои­тельных комбинатов, кажется здесь вполне уместной. Естественно, умение пользоваться стандартными “кирпичами алгоритмики” повышает эффективность труда программиста. В этой главе мы познакомимся с некоторыми из них.

Но прежде нам понадобится важное понятие — порядок. Для его введения воспользуемся модельным примером, который еще не раз послужит нам, — речь идет о массовой библиотеке.

Работник библиотеки, вознамерившийся протереть книги в одном из шкафов (или на отдельном стеллаже), должен снять их с полок и затем вернуть назад. Предполагается, что книги были до его прихода расставлены в соответствии с неким регламентом. Если его игнорировать, то для n книг мог бы получиться любой из n! вариантов при единственном правильном. Можно вести обработку книг, начав с крайней и далее обрабатывая их поочередно в режиме “достал – протер – вернул”. Это типичный пример поэлементной обработки последовательности. Текущая последовательность впервые появилась как результат расстановки книг на изначально пустой полке. Какими правилами руководствовался тогда библиотекарь?

Рис. C1.1. Двуместное отношение

Например, он мог бы построить таблицу, вроде той, что представлена на рис. C1.1. Значок на пересечении i-й строки и j-го столбца означает, что booki
bookj, то есть книга i должна быть поставлена на полку до книги j. Такую таблицу, задающую набор пар элементов множества, называют двуместным отношением на множестве, в нашем примере — на множестве книг из шкафа. Заметим, что отношение может быть даже пустым, так обстоит дело со шкафом без единой книги. Но эта ситуация нас мало интересует, поэтому речь далее пойдет только о непустых множествах и отношениях.

Как видим, последовательность аргументов в парах (i, j) и (j, i) существенна, здесь нельзя допустить противоречие, указав одновременно booki bookj и bookj booki. Такая ситуация допустима только при совпадении аргументов; тем самым обеспечивается свойство антисимметричности. Но это еще не все, надо проследить за выполнением свойства транзитивности, согласно которому из пары условий booki bookj и bookj bookk необходимо следует booki bookk.

Если заполнение таблицы­-отношения выполнено с соблюдением условий антисимметричности и транзитивности, то отношение R называется порядком.

В нашем примере есть еще одно условие: очевидно, книгу нельзя поставить впереди самой себя: booki booki. Отношение, удовлетворяющее такому свойству, называется антирефлексивным, а порядок — строгим. Напротив, при выполнении условия booki booki отношение называлось бы рефлексивным, а порядок — нестрогим.

Пример C1.1. На полке школьной библиотеки стоят друг за другом n экземпляров какого-то учебника, других книг там нет. В терминологии теории множеств мы имеем множество с повторениями, а в терминологии, приведенной выше, можно говорить о нестрогом порядке.

В принципе выполнение условий антисимметричности и транзитивности легко проверить. Однако стремление проконтролировать заполнение для целого шкафа с n книгами обойдется достаточно дорого, поскольку только просмотр всей таблицы стоит O(n2), а ведь требуется еще проверка условий (см. упр. C1.2).

Имея некоторую не полностью заполненную таблицу-отношение с выполненным условием антисимметричности, можно попытаться ее “достроить” до транзитивного замыкания. Наименее трудоемкий вариант потребует O(n3) шагов, обеспечивается он алгоритмом C1.1.

Алгоритм C1.1. Построение транзитивного замыкания (Уоршелл29, 1962).

1 for k := 1 to n do

2 for i := 1 to n do

3 for j := 1 to n do

4 if R[i, k] and R[k, j] then

5 R[i, j] := true;

Здесь R[i, j] = true, если booki bookj.

На выходе алгоритма получим транзитивное отношение. Если антисимметричность при этом не нарушилась (см. упр. C1.3), то построенная таблица является порядком. При этом возможны две ситуации.

Первая вполне устраивает нашего добросовестного библиотекаря: если исходной информации было достаточно, то таблица допускает единственно возможный вариант расстановки книг. В данном случае (рис. C1.2) в шкафу оказалось лишь 5 книг, и несложный благодаря небольшой мощности этого множества анализ явно укажет последовательность обработки:

3 1 2 5 4. (C1.1)

Но остается альтернативная возможность, когда таблица (рис. C1.3) не дает однозначного выбора “что за чем”. Здесь полная информация о расстановке имеется в отдельности лишь для подмножеств M1 = {1, 2} и M2 = {3, 4, 5}:

11 21, 32 52 42. (C1.2)

О произвольных элементах m1 О M1 и m2 О M2 говорят, что они не сравнимы относительно заданного порядка. В таких случаях в таблице, сформированной алгоритмом C1.1, одновременно остаются незаполненными клетки R[m1, m2] и R[m2, m1]. Библиотекарь волен установить общую последовательность по-разному, но так, чтобы подпоследовательности (C1.2), вошедшие в нее, не нарушались, например:

11 32 52 21 42 (C1.3)

или

32 52 42 11 21. (C1.4)

Отношение R, заданное таблицей на рис. C1.3, называется частичным порядком, таблица на рис. C1.2 соответствует отношению линейного или полного порядка30.

Пример C1.2. Отношение “кто сильнее” на множестве представителей млекопитающих является частичным порядком, в котором далеко не все элементы попарно сравнимы, что делает неразрешимой задачу, сформулированную Л.Кассилем в повести “Кондуит и Швамбрания”31:

— А вот отгадайте сами: если слон и вдруг на кита налезет, кто кого сборет?

— Не знаю, — постыдно признался директор.

Как мы убедились, линейный порядок гарантирует существование32 единственного минимального элемента (для отношения на рис. C1.2 это элемент 3), то есть такого, которому ни один другой не предшествует. Частичный же порядок допускает существование нескольких минимумов (элементы 11 и 32 для отношения на рис. C1.3). Аналогичные рассуждения действительны и для максимального элемента (элементов).

Пример C1.3. Подводя итоги Олимпийских игр, спортивные журналисты обычно сравнивают страны-участницы по собранному урожаю медалей. Сопоставив каждой стране s вектор (as, bs, cs), где as, bs, cs — количество завоеванных ее спортсменами золотых, серебряных и бронзовых медалей, можно построить на множестве стран частичный порядок следующим образом:

s1 s2, если (as1 < as2) and (bs1 < bs2) and (cs1 < cs2).

Полученный порядок в общем случае не является линейным, поскольку существуют не сравнимые в нем вектора, например, (1, 2, 3) и (3, 2, 1). Таким образом, однозначно определить наиболее результативную (максимальную в предложенном порядке) страну нельзя: максимумов может быть несколько.

Пример C1.4. Кстати говоря, минимум и наименьший элемент — разные объекты. Наименьший элемент определяется как элемент, предшествующий всем остальным (автоматически предполагается его сравнимость с ними). Наименьший элемент всегда является минимальным, однако обратное неверно.

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

Иногда оказывается полезным понятие доминирования, актуальное для пар элементов (m1, m2) частично упорядоченного множества M. Элемент m2 доминирует над элементом m1, если m1 m2 и в том же множестве не существует таких элементов m, что для них выполняется m1 m m2.

Для линейного порядка характерна возможность сопоставить — единственным образом, в соответствии с доминированием — каждому элементу, кроме минимального, предыдущий, и каждому, кроме максимального, следующий элемент. Для частичного порядка это не так, однако всегда существует возможность дополнить его до линейного, правда, как показывают варианты (C1.3) и (C1.4), уже не единственным образом.

Пример C1.5. Вот ситуация, типичная для обыденной жизни: две очереди рядом независимо обслуживаются двумя операторами, причем люди, стоящие в очередях, самостоятельно поддерживают в каждой линейный порядок. По какой-то причине один из операторов объявляет о продолжительном перерыве в обслуживании своей очереди, и тогда ее “элементы” встраиваются, согласно достигнутой (это, пожалуй, уже не столь типично) договоренности, внутрь оставшейся очереди, например, “через одного”.

Как видим, понятия линейного и частичного порядка вполне актуальны. Иногда используют словосочетание “случайный порядок”, но не в качестве математического понятия33, а лишь как обозначение факта, что никакого упорядочения не производилось. Если порядок на множестве элементов не задан, то нельзя указать правило, задающее их взаимное расположение в структуре, выбранной для представления множества. Подобный пример нам уже встречался: последовательность строк на рис. A5.1 и A5.3 выбрана случайно, значения элементов первого столбца таблицы не связаны с текущими номерами строк. Напротив, линейный порядок внутри каждой строки на тех же рисунках обеспечивается заданным рекуррентным соотношением (A5.1).

Упражнения

C1.1. Докажите, что если в некотором конечном частично упорядоченном множестве имеется единственный максимум, то он является наибольшим элементом.

C1.2. Пусть отношение задано квадратной таблицей R булевских значений. Наличие true в клетке R[i, j] означает, что пара элементов (i, j) принадлежит отношению.

Напишите программу, которая проверяет, что данное отношение является:

· рефлексивным,

· антирефлексивным,

· транзитивным,

· симметричным,

· антисимметричным,

· строгим (частичным) порядком,

· строгим линейным порядком.

C1.3. Приведите пример антисимметричного отношения, которое после применения к нему алгоритма Уоршелла перестает быть таковым.

C1.4. Напишите программу, которая для заданного частичного порядка R выводит все минимальные элементы.

C1.5. Напишите программу, которая для заданного частичного порядка R и чисел i и j проверяет, что i-й элемент доминирует над j-м.

C1.6. Напишите программу, которая для заданного частичного порядка R подсчитывает количество вариантов его дополнения до линейного порядка.

C2. Информационно-поисковый язык: пример

Понятие о языке далеко не покрывается понятием о членораздельной речи, ибо сюда входит еще речь письменная, язык мимики, язык жестов, язык рисунка, язык красок и музыкальных тонов, язык природы, язык фактов и т.п. Но наиболее зафиксированной формой языка является язык письменный и язык рисунка.

П.А. Флоренский34

Наиболее востребованной операцией при обработке информации является поиск данных в доступном хранилище. Удовлетворение типовых и, что существенно, массовых поисковых запросов является основополагающей функцией информационно-поисковых систем (ИПС). Широко известных примеров ИПС можно назвать немало: почтовая служба в целом и отдельно взятое почтовое отделение, интернет-поисковик Яндекс и подобные ему, телефонная сеть и другие.

Таким же примером является уже знакомая нам публичная библиотека. Но нам нет нужды обсуждать здесь ее функционирование как системы, ограничимся одной из составляющих — информационно-поисковым языком (ИПЯ). Именно он позволяет формулировать поисковые запросы, ориентированные на установленный порядок хранения и эффективные алгоритмы доступа.

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

Рис. C2.1. Каталожная карточка

Каждой “единице хранения” библиотечного фонда соответствует в картотеке своя карточка, и не одна, поскольку каталогов в библиотечном хозяйстве несколько [5]: алфавитный, систематический, предметный, генеральный; в некоторых библиотеках есть и другие. Посетителю разрешен свободный доступ к картотеке, но, разумеется, не в помещение книгохранилища, из которого заказанную книгу доставляет читателю работник библиотеки.

Крупные массовые и научно-технические библиотеки постепенно оснащаются компьютерами и получают возможность перехода к работе с электронными каталогами. В целях унификации систем ввода и хранения записей о книгах и документах разработан специальный международный коммуникативный формат UNIMARC35, детище Библиотеки Конгресса США36. Его локализация — формат RUSMARC — выполнена совместно Российской государственной библиотекой (РГБ) и Российской национальной библиотекой (РНБ).

Сейчас наш библиотекарь занят наведением порядка37 в книгохранилище. В массовых библиотеках, как правило, принята систематическо-алфавитная расстановка библиотечного фонда. Систематическая означает, что книги, классифицируемые в рамках одной предметной области, размещают также в одном разделе: отдельно — естественные науки, отдельно — прикладные науки, техника, отдельно — искусство и т.д. В массовых библиотеках руководствуются классификацией ББК38, в научно-технических библиотеках обычно используется УДК39. Подробнее о классификациях мы поговорим в разделе C4, а пока следуем за библиотекарем.

Он как раз достиг отдела художественной литературы и подошел к стеллажу с многочисленными изданиями Шекспира, которые занимают не одну полку. Книг здесь гораздо больше, чем было в примере на рис. C1.2, потому следует соблюдать аккуратность, дабы не нарушить установленный порядок. Внутри отдела расстановка книг уже алфавитная40, здесь применяется порядок, принятый для карточек в одноименном каталоге. Друг за другом выстроились восемь одинаково оформленных томов полного собрания сочинений Шекспира 1957–1960 гг. издания, чья маркировка на корешках: 1, 2, …, 8 — не оставляет сомнений в том, что при их расстановке учитывался соответствующий линейный порядок. Тут же, слева и справа от восьмитомника, — другие издания того же автора. Как осуществлялась их расстановка?

Каждая книга снабжена уникальным шифром, обозначающим ее место на полке книгохранилища и записываемое как дробь, тот же шифр указывается в верхнем левом углу каталожной карточки на эту книгу. В числителе дроби помещается полочный классификационный индекс, в знаменателе — авторский знак. Последний присваивается изданию согласно специальной таблице. Книги одного автора получают один и тот же авторский знак, в нашем примере — Ш41 или Ш416. По существу, авторский знак формируется как табличный код подстановки, и с рядом аналогичных примеров, но относящихся к другим предметным областям, мы встретимся в разделе F2.

В данной предметной области использовать такой признак, удобный для работы с каталогами, предложил еще в XIX в. американский библиотековед Ч.Кеттер41. Естественно, для отечественных библиотек понадобилась кириллическая адаптация — впервые появившиеся в 1916 г. таблицы Л.Б. Хавкиной42. В сущности идея достаточно простая: первый символ авторского знака заимствуется из начального символа фамилии автора книги или, при отсутствии указания на такового, из ее названия; далее следует двузначное (для двоичных таблиц) или трехзначное (для троичных таблиц) число — оно соответствует следующим нескольким буквам того же “кодируемого” слова. Числа назначаются из диапазонов 11 . . 99 или 111 . . 999 соответственно.

Рис. N2.2. Фрагмент двоичной таблицы Хавкиной

На рис. C2.2 представлен фрагмент из двоичной таб­лицы Хавкиной [48], иллюстрирующий появление индекса Ш41. Авторский знак Ш416, как нетрудно догадаться, получен из троичной таблицы.

Очевидно, что предыдущим индексом Ш40 помечены, в частности, книги американского писателя-фантаста Р.Шекли43, а следующим знаком Ш42 маркированы сочинения как английского поэта-романтика П.Шелли44, так и его супруги писательницы М.Шелли45.

ИСТОРИЧЕСКИЙ ЭКСКУРС

Сейчас имя П.Шелли стоит в ряду классиков поэзии, а литературное творчество М.Шелли почти забыто, однако при жизни они могли поспорить популярностью в читательских кругах. Принесший Мэри известность роман “Франкенштейн, или Современный Прометей” некоторые критики склонны даже считать первым в истории жанра научной фантастики. Но большинство из нас обязаны знакомством с его персонажами, доктором Франкенштейном и порожденным им монстром, скорее не первоисточнику, а многочисленным голливудским экранизациям.

Как мы уже указывали, расстановка книг на полках отдела нашей библиотеки совпадает с последовательностью соответствующих им карточек в алфавитном каталоге. Перебирая содержимое каталожного ящика на букву Ш, встречаем группами и поодиночке маркированные карточки в порядке, показанном на рис. C2.3. Но не все книги отнесены к отделу художественной литературы, поэтому наш библиотекарь, находящийся сейчас в книгохранилище, увидит на полке лишь некоторые из перечисленных изданий — это книги Шекли и Шекспира.

Не вполне корректно говорить, что индексы в таблице Хавкиной размещены в алфавитном порядке, поскольку, как видим, они являются строками, имеющими разную длину, например, у Шек она составляет 3, а у Шесто — 5. Правильнее использовать термин лексикографический порядок. Мы здесь употребили несколько интуитивно понятных терминов, которым пора дать формальные определения.

Авторский
знак

Заголовок библиографической записи

Ш405

Шекли

Ш405

Шеклтон

Ш408

Шекова

Ш416

Шекспир

Ш416

Шекспир, рассказанный детям

Ш416

Шекспировская энциклопедия

Ш418

Шехтер

Рис. N2.3. Маркировка каталожных карточек

Определение. Строкой sA (над алфавитом A) называется конечная последовательность элементов sk этого алфавита, то есть

sA = s1sksL, 0 k L < Ґ, sk Prin.gif (117 bytes) A.

Нередко используют другой термин — слово или даже слово над алфавитом, которые следует считать синонимами в смысле данного определения.

Определение. L называется длиной строки, s1skпрефиксом строки, sksLсуффиксом строки. При L = 0 строка называется пустой.

Введенное определение позволяет рассматривать сами префикс и суффикс как строки. Очевидно, при k = L такой префикс строки совпадает с самой строкой; при k = 0 мы имеем дело с пустым префиксом.

Можно говорить и об общем префиксе нескольких строк. Например, набор строк Шекли, Шекспир, Шелли, Шестов имеет, не считая пустого, два общих префикса — Ш и Ше, а для пары строк Шекли и Шекспир к перечисленным добавляется еще Шек. Поскольку общие префиксы заданного набора строк различаются по длине, то можно выделить среди них самый длинный, наибольший общий префикс.

Чтобы наращивать строку по заданному префиксу, разрешим следующую операцию со строковыми аргументами.

Определение. Для строк sA = s1sL и tA = t1tM (над алфавитом A) результатом операции сцепления является строка

sA + tA = s1sLt1tM.

КСТАТИ

Сравните приведенные определения с тем, что вам известно о типе string языка Pascal.

Вернемся к таблице на рис. C2.2. В левой колонке для фамилии-строки Шекспир обнаруживаем сразу два подходящих префикса: Шек и Шекс, однако авторский знак для этой строки установлен по второму варианту, тогда как для строки Шекли — по первому. Дело в том, что в подмножество, маркированное как Шек*46, отнесены такие фамилии с префиксами Шек + s4 (с 4-й буквой s4), что результат этого сцепления предшествует строке Шекс в некотором порядке, который формализует следующее определение.

Определение. Порядок lex на множестве непустых строк называется лексикографическим47, если для всякой пары строк

sA = s1sL, tA = t1tM,

находящихся в отношении sA lextA и обладающих наибольшим общим префиксом длины k, либо этот префикс совпадает с sA, либо sk + 1 tk+1.

Как видим, префиксы в левой колонке таблицы Хавкиной (см. рис. 2.2) размещены в лексикографическом порядке, что является обязательным условием применимости дихотомического поиска; подробнее мы поговорим о нем в разделе D3 книги. В данном случае такой порядок в левой колонке позволяет быстро находить искомый префикс кодируемой фамилии (слова) в самой таблице, а тот же порядок в правой колонке обеспечивает быстрый поиск карточки по соответствующему авторскому знаку в алфавитном каталоге (задача 1-1).

Но если один и тот же авторский знак присвоен разным книгам, как обстоит дело в нашем случае многочисленных книг с индексом Шекс, ситуация не столь очевидна. Напрашивается вариант последовательного “склеивания” всех элементов библиографической записи (включая межсловные разделители) в одну строку. Размещение совокупности таких строк, сопоставленных набору книг, в лексикографическом порядке, казалось бы, вполне обеспечивает применимость дихотомического поиска. Однако в отечественных библиотеках в рас­становке карточек принят [5] несколько иной порядок: пословно-лексикографический. В этом порядке межсловные разделители не являются элементами сравниваемых строк, а регулируют расстановку слов в лексикографическом порядке. Поэтому, например, книга

должна занять место (инициалы В. и У. считаются равноправными48) впереди книги

Но и это правило не последнее. Еще принято объединять книги одного автора в группы, следующие друг за другом в порядке “убывающей полноты” изданий: впереди — полные собрания сочинений, затем — собрания сочинений, еще дальше — сочинения, потом — избранные произведения и, наконец, — избранные сочинения. Лишь за ними следуют, уже в пословно-лексикографическом порядке, отдельные издания независимо от своего состава, будь то книга, включающая в себя лишь одно произведение или же являющаяся сборником. Вот как будут расставлены несколько карточек, оформленных49 для различных изданий “шекспирианы”:

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

В других каталогах, используемых в библиотеках и связанных с описываемым нами ИПЯ, встречаются и иные порядки. Их рассмотрение не является сейчас нашей целью. Однако не хотелось бы обойти вниманием обратный лексикографический порядок, находящий применение внутри отдельных изданий (см. пример C2.3).

Выше мы ввели понятие общего и наибольшего общего префикса, связанное с началами строк. Аналогичным образом, рассматривая хвосты строк, можно говорить об их общем суффиксе и наибольшем общем суффиксе.

Определение. Порядок inverse на множестве непустых строк называется обратным лексикографическим (инверсным)50, если для всякой пары строк

sA = s1sL, tA = t1tM,

находящихся в отношении sA inversetA и обладающих наибольшим общим суффиксом длины k, либо этот суффикс совпадает с sA, либо sLk tMk.

Пример C2.1. Запишем несколько цифровых строк одинаковой длины, соответствующих десятичным числам, в лексикографическом порядке:

123, 132, 213, 231, 312, 321.

Эта последовательность отвечает обычному числовому порядку. Теперь, применив к тем же строкам обратный лексикографический порядок, получим:

321, 231, 312, 132, 213, 123.

Пример C2.2. Для чисел-строк разной длины результат оказывается еще более неожиданным. Так, из лексикографического набора

1, 10, 1010, 200

получим инверсный

200, 10, 1010, 1.

Пример C2.3. Обратный лексикографический порядок лежит в основе “Грамматического словаря” [21]. Подобные словари незаменимы при изучении слово-образования, фонетики, для расшифровки текстов. Их достоинства проявляются заметнее, если располагать слова, выравнивая их не по левому, а по правому краю: в таблице на рис. C2.4 мы поместили в левую колонку начальные слова “Грамматического словаря”, в правую — последние (кстати, всего в нем около 100 000 слов).

Рис. N2.4. Начало и конец “Грамматического словаря”

Упражнения

C2.1. Ознакомьтесь со структурой и алгоритмом поиска нужного телефона по имеющемуся у вас телефонному справочнику. Сколько каталогов и уровней индексирования вы обнаружите?

C2.2. Расставьте в обратном лексикографическом порядке слова

аджика, архаика, гвоздика, ежевика, логика, методика, периодика

C2.3. Напишите программу, выполняющую инверсное упорядочение входного набора слов. Читателю, незнакомому с алгоритмами сортировки, можно пропустить это упражнение, вернувшись к нему после изучения главы D.

C2.4. Предложите алгоритм построения полного порядка для примера C1.3.

C3. Словари

— Что вы читаете, принц?

— Слова, слова, слова.

У.Шекспир51

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

Задача 1-1. Посетитель библиотеки выясняет, имеется ли в фондах интересующая его книга, например, цитируемая в эпиграфе:

Конечно, можно прибегнуть к услугам библиографа, однако в массовой библиотеке это не всегда рационально, учитывая интенсивный поток читателей. Квалифицированному читателю проще самостоятельно воспользоваться библиотечными каталогами. Построение любого из них рассчитано на предполагаемый алгоритм поиска в нем нужной информации, применение иного алгоритма вполне может оказаться неэффективным. Закройте книгу, которую держите сейчас перед собой, не запоминая страницу. Как вновь найти ту же главу C, название которой представляет собой поисковый образец? Разумеется, по страничной ссылке из оглавления, а не листая страницы друг за другом. Или: в примерах с таблицами умножения из главы A функцию оглавления брали на себя индексы строк и столбцов.

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

Располагая образцом — Шекспир в нашем примере, — читатель должен найти соответствующую каталожную карточку среди нескольких тысяч (а то и десятков тысяч) других. Первым делом удается среди всех каталожных ящиков — на них имеется алфавитная маркировка! — довольно быстро локализовать искомый. Внутри него наверняка обнаружатся несколько специальных разделителей, вставленных перед каждой группой карточек однородной тематики. В нашем примере следует ожидать разделитель Шекспир, поскольку в книгохранилище много изданий этого автора. Все карточки из группы, следующей за этим разделителем, маркированы одинаково — Ш41.

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

Задача 1-2. Успешное решение предыдущей задачи влечет переход ко второму этапу, когда уже с полной информацией о единице хранения посетитель обращается к библиотекарю с просьбой выдать книгу. Библиотекарь, в свою очередь, реализует новый поисковый запрос, относящийся к фондохранилищу. Для локализации области поиска он воспользуется полочным индексом, указанным в найденной каталожной карточке.

Общее в задачах 1-1 и 1-2 — это запрос на поиск элемента по ключу (образцу). Организация хранения информации, очевидно, предполагает различимость и доступность отдельных ее элементов, записей. Механизм реализации соответствующего запроса зависит от организации хранения данных и алгоритма обработки. И то и другое может оказаться весьма нетривиальным.

Но, очевидно, не в нашем примере. Работники библиотеки резонно полагают, что (1-1) квалифицированный посетитель умеет пользоваться каталогом, а читатель, в свою очередь, не сомневается, что (1-2) библиотекарь сумеет отыскать на стендах хранилища запрошенную книгу. Инициатора каждого из поисковых запросов при этом не интересует, как исполнитель его реализует. Уместно говорить, что информационно-поисковый язык предполагает наличие интерфейса между пользователем и компетентным исполнителем запроса, а в случае проектирования программного комплекса — между разработчиком и программистом, пусть даже они сосуществуют в одном лице. Далее, когда проектное решение принято, можно уже заняться собственно реализацией названной макрооперации.

Итак, пользователь, вообще говоря, не обязан знать, как организовано хранение данных (то же книгохранилище), достаточно предоставить в его распоряжение алгоритмическую операцию52 Find с указанием ключа записи (key) в качестве параметра запроса: Find(key).

Организация структуры данных диктует соответст­вующую реализацию операции Find.

Задачи 2-1 и 2-2. Фонд нашей библиотеки периодически пополняется новинками. Подготовив карточку на новую книгу, библиотекарь должен (2-1) вставить ее на законное место в каталоге, соблюдая принятый порядок следования, и (2-2) разместить саму книгу с учетом порядка в книгохранилище. Между прочим, авторов у книги может быть и несколько, тогда на каждого из них полагается по соответствующей карточке. И еще: мы ведь помним о существовании нескольких каталогов, в них также надо отразить вновь поступившие издания.

Как видим, операции Insert(item) здесь потребуются неоднократно.

Задачи 3-1 и 3-2. К сожалению, нерадивые читатели иногда теряют взятые в библиотеке книги. Кроме того, экземпляры, находящиеся в плохом состоянии, списываются. В этих случаях приходится изымать соответствующие каталожные карточки из каталога (3-1), а испорченные книги — из книгохранилища (3-2).

Назначение операции Delete(item) вполне очевидно. Заметим, однако, что алгоритмическая операция Delete вовсе не обязательно означает удаление физическое, в буквальном смысле. Если каталожную карточку можно изъять из каталога, то в следующих примерах столь решительные действия противопоказаны.

Пример C3.1

1. Запись в гостиничной книге о выбывшем госте или личное дело уволившегося работника лишь маркируются принятым способом, но не ликвидируются.

2. При ведении хеш-таблиц (см. раздел E8 в книге) удаленные записи не просто стираются, но и оставляют после себя специальные метки.

3. На сайте интернет-провайдера, предоставляющего услуги связи с помощью интернет-карт, пользователь может обратиться за справкой об оставшемся ресурсе времени к “своей” странице. При исчерпании ресурса страница в отличие от услуги некоторое время остается доступной.

Мы уже обратили внимание на то, что организация данных отражается на эффективности конкретной алгоритмической операции. Можно, например, так организовать хранение данных, что операция Insert станет выполняться с трудоемкостью O(1), но это скорее всего не лучшим образом отразится на других важных операциях. В самом деле, обеспечить такую эффективность для вставки новой карточки в библиотечный каталог нетрудно — достаточно размещать ее самой первой, но вот найдем ли мы ее спустя некоторое время? Ведь каталог уже потеряет свойства “алфавитного”, существовавшие алгоритмы обработки перестанут в нем работать.

Что из этого следует? Проектируя структуру (хранения) данных, целесообразно предварительно установить, какие операции будут востребованны и какие из них — чаще остальных. Если не удается обеспечить малую трудоемкость для всех операций, то целесообразно сделать это хотя бы в отношении наиболее востребованных. В практических приложениях разработчику вовсе нет необходимости начинать все “с пустого места”, развитие алгоритмики уже обеспечило наличие некоторых рецептов.

Попробуем оценить для нашего примера массовой библиотеки, как часто приходится решать каждую из перечисленных выше задач. Любой библиотечный работник сразу скажет, что основные сервисы следует предоставлять посетителю. Стало быть, ухудшать трудоемкость поиска по каталогу никак нельзя. Однако и вставка новой карточки в каталог предполагает лишь поиск места для очередной записи, а это значит, что в качестве предварительной обработки вновь вызывается та же операция. Наконец, удаление карточки опять потребует сначала отыскать то, что удаляется. Следовательно, трудоемкость всех перечисленных процедур в данном примере полностью зависит от эффективности алгоритма Find. Его механизм мы уже обсудили выше и выяснили, что он многоуровневый: первый уровень — выбор каталожного ящика, второй — локализация в нем группы между двумя последовательными разделителями, а третий — локализация внутри группы. Благодаря существенному сокращению области поиска на первом уровне и дихотомическому поиску на последнем общую трудоемкость можно оценить как O(log2n).

Пример C3.2. Можно ли построить одноуровневый каталог для аналогичных целей? Скажем, имея дело с электронным библиотечным каталогом, организуем хранение в нем записей на базе упорядоченных списков. Вот как это будет выглядеть:

1 type

2 PListNode = ^TListNode;

3 TListNode = record

4 item: TItem;

5 prev: PListNode;

6 next: PListNode;

7 end;

8 TDictionary = object

9 head: PListNode;

10 constructor Init();

11 function Find(const key: TKey): TItem;

12 procedure Insert(const item: TItem);

13 procedure Delete(const item: TItem);

14 end;

15

16 constructor TDictionary.Init();

17 begin

18 head := nil;

19 end;

20

21 function TDictionary.Find(const key: TKey): TItem;

22 var cur: PListNode;

23 err: TItem;

24 begin

25 cur := head;

26 while cur <> nil do begin

27 if cur^.item.key = key then begin

28 Find := cur^.item;

29 exit;

30 end;

31 cur := cur^.next;

32 end;

33 err.key := '';

34 err.value := '';

35 Find := err;

36 end;

37

38 procedure TDictionary.Insert(

const item: TItem);

39 var cur, node: PListNode;

40 begin

41 new(node);

42 node^.item := item;

43 if (head = nil) or

44 (item.key <= head^.item.key) then begin

45 node^.prev := nil;

46 node^.next := head;

47 if head <> nil then

48 head^.prev := node;

49 head := node;

50 end else begin

51 cur := head;

52 while (cur^.next <> nil) and

53 (cur^.next^.item.key < item.key) do

54 cur := cur^.next;

55 node^.prev := cur;

56 node^.next := cur^.next;

57 if cur^.next <> nil then

58 cur^.next^.prev := node;

59 cur^.next := node;

60 end;

61 end;

62

63 procedure TDictionary.Delete(

const item: TItem);

64 var cur: PListNode;

65 begin

66 cur := head;

67 while cur <> nil do begin

68 if (cur^.item.key = item.key) and

69 (cur^.item.value = item.value) then begin

70 if cur^.prev <> nil then

71 cur^.prev^.next := cur^.next;

72 if cur^.next <> nil then

73 cur^.next^.prev := cur^.prev;

74 dispose(cur);

75 exit;

76 end;

77 cur := cur^.next;

78 end;

79 end;

Как видим, принятая структура работоспособна. Но: эффективность поиска по списку оценивается как O(n), все типовые запросы, кроме, конечно, инициализации, будут обрабатываться в среднем с линейной трудоемкостью. При большой мощности набора этот вариант далеко не идеален, и в действительности электронные каталоги построены иначе — на основе баз данных.

Описанная выше организация алфавитного библиотечного каталога подходит под следующее общее

Определение. Структура данных, рассчитанная на выполнение над ее элементами (записями с ключами) операций Find, Insert и Delete, называется словарем.

Разумеется, практически в любой структуре удается реализовать указанный набор операций, хотя бы перебрав все элементы и, возможно, переставив их на новые места. Так, например, можно обрабатывать линейный массив, о чем пойдет речь в главе D. Но отнюдь не всякую структуру принято относить к словарям: принимается во внимание трудоемкость операций. Оказывается, в нашем определении существенную роль играет характеристика структуры как “рассчитанной на выполнение”. Обычно в словаре обеспечивается трудоемкость его операций не хуже O(log2n). Используются для этого ассоциативные массивы, реализуемые либо как деревья поиска (см. раздел C6), либо как хеш-таблицы (см. раздел E8). Собственно понятие ассоциативный означает, что доступ к элементу такой структуры осуществляется не по его индексу (порядковому номеру) внутри структуры, а по его ключу; адрес размещения элемента в этой структуре нельзя заранее указать в обрабатывающей программе в явном виде.

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

Пример C3.3. Будем представлять полином массивом его коэффициентов. Можно вычислить значение полинома при заданном x за время O(n), где n — степень полинома. Нижеприведенный алгоритм известен под именем схемы Горнера53:

1 function EvaluatePolinomial(const a: array of double;

2 const x: double): double;

3

4 var i, n: longint;

5 v: double;

6 begin

7 n := Length(a);

8 v := a[n – 1];

9 for i := n – 2 downto 0 do

10 v := x * v + a[i];

11 EvaluatePolinomial := v;

12 end;

Еще один важный случай обработки упорядоченных списков рассматривается в упр. C3.1.

Таким образом, в состав рабочих средств программиста введена специальная структура данных с присущими именно ей, “родными”, операциями. В дальнейшем нам следует четко различать “словари” в обычном значении слова и в алгоритмическом; впрочем, контекст редко дает повод для ошибки.

Упражнение

C3.1. Напишите процедуру, осуществляющую построение упорядоченного списка элементов по двум исходным упорядоченным спискам.

C4. Классификации

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

В.Я. Пропп54

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

Классификация есть система деления понятий (классов) на основе соподчинения. Класс (или род), объединяющий некоторую совокупность элементов, разделяется на подклассы (или виды) согласно признаку, меняющему свое значение при смене подкласса. Если в качестве множества значений признака принимается лишь один вариант и его отрицание, то мы имеем дело с дихотомической классификацией.

Дихотомической является самая известная в истории наук классификация — “древо Порфирия”55. Нисходя по древу Порфирия, мы наблюдаем увеличение количества видовых отличий (рис. C4.1). Понятие “человек” дихотомически уже не делится, а представляет собой совокупность индивидов, которые различаются по случайным признакам, индивидуальным отличиям. Например, одним из индивидуальных отличий у Сократа56 является лысина на голове.

КСТАТИ

Ныне проблема перечисления индивидуальных отличий решается на государственном уровне — выдачей гражданину паспорта. Не так давно в нашей стране нашли более радикальное решение, введя ИНН, идентификационный номер налогоплательщика. Это двенадцатизначный цифровой код вида NNNNXXXXXXCC, в котором начальные цифры NNNN соответствуют коду налогового органа, присвоившего этот номер, XXXXXX — собственно порядковый номер записи о физическом лице в территориальном разделе единого государственного реестра, CC — рассчитанное по специальному алгоритму двузначное контрольное число.

Порфирий указывает, что при делении понятия в качестве признака можно выбрать как собственный (устойчивый) признак, так и случайный (неустойчивый). Теперь­-то мы понимаем, что объективный выбор устойчивого признака не является простой задачей и степень объективности зависит от уровня развития науки, а вовсе не от наличия растительности на голове. Вот несколько тому примеров.

Пример C4.1. Шведский естествоиспытатель Карл Линней57 создал классификацию Systema naturae, разделив мир природы на три царства: неорганическое, растительное и животное, а далее использовав такие уровни: классы, отряды, роды и виды. При этом он впервые (1753) применил так называемую бинарную номенклатуру (предложенную, впрочем, задолго до того58). Согласно ей каждый вид обозначается парой латинских слов: сначала — род (с прописной буквы) в единственном числе, затем — видовое название; например, Lepus europaeus (заяц­-русак), Viola tricolor (фиалка трехцветная).

Классификация Линнея не выдержала испытания временем. С позиций современной биологии, система родо-видовых отношений живого мира выглядит гораздо сложнее: домен (надцарство) — царство — тип (отдел) — класс — отряд (порядок) — семейство — род — вид. Напомним читателю, что он относится к домену эукариоты, царству животные, типу хордовые, подтипу позвоночные, классу млекопитающие, подклассу плацентарные, отряду приматы, подот­ряду высшие обезьяны, семейству человекообразные, роду люди (homo) и, наконец, гордо именуемому виду Homo sapiens. Впрочем, нет полной уверенности, что нас куда-нибудь не переместят, поскольку, согласно авторитетному источнику59, “разные исследователи выделяют от 4 до 26 различных царств, типов — от 33 до 132, классов — от 100 до 200”. Кстати говоря, если бы на голове Сократа была шерсть, то владельца растительности по этому характерному признаку наверняка можно было бы отнести по крайней мере к классу млекопитающих, поскольку этот “классовый признак” современная биология в отличие от представлений Порфирия считает устойчивым.

Пример C4.2. Широко и заслуженно признанной классификацией химических элементов является ныне Периодический закон, впервые представленный Д.И. Менделеевым60 научному сообществу в 1869 г.

Однако к указанному времени уже существовало около 50 конкурирующих классификаций, большинство из которых также основывались на табличной форме. Любопытно замечание, обращенное к английскому ученому Дж. Ньюлендсу61 одним из его оппонентов на заседании Лондонского химического общества (1865): “Не пробовал ли докладчик расположить в таблице элементы в алфавитном порядке и не заметил ли при таком расположении каких-либо новых закономерностей?”62 Впрочем, встречались и оригинальные геометрические конструкции, вроде цилиндрической спирали (“теллуровый винт”) А. де Шанкуртуа63 (1862).

Классификации, вводимые для описания объектов мира природы, принято именовать естественными. Необоснованный выбор оснований деления понятий (признаков) чреват дальнейшими ошибками. Так, следуя классификации Порфирия, к людям (“разумным животным”) приходится причислить и гуигнгнмов64. Или: в “октавной” классификации химических элементов Дж. Ньюлендса на несколько позиций претендовали по два элемента одновременно.

Альтернативу естественным представляют классификации искусственные, предназначенные обычно для систематизации создаваемых человеком предметов. Здесь исследователь гораздо менее ограничен в выборе признаков деления.

Пример C4.3. Известно немало классификаций музыкальных инструментов65. В Китае издавна делили их на четыре группы, учитывая материал: каменные, деревянные, шелковые, металлические. В Древней Индии классификация иная: струнные инструменты, духовые инструменты, ударные инструменты из дерева или металла и, отдельно, ударные инструменты с кожаной мембраной (барабаны). Европейская классическая традиция выделяет три основных типа: духовые, струнные и ударные инструменты, к которым в наше время добавляются электронные.

Есть ли практическое значение, например, у последней из классификаций? Судите сами: в консерватории такая типизация находит отражение в делении на учебные кафедры, в оркестре по аналогичной схеме рассаживаются исполнители.

Очевидно, задачи классифицирования представляют практический интерес. Что же касается теоретического аспекта, то он проявляется как в исследованиях, посвящаемых классификации конкретных предметных областей, так и в фундаментальных работах на тему “классификации классификаций”.

Наиболее простой классификацией, как мы уже видели выше, является дихотомическое дерево, в котором деление класса производится по некоторому признаку ровно на два подкласса. Соответствующая конструкция оператора ветвления if–then–else знакома любому программисту. Дихотомический механизм деления обобщается вполне естественным образом, если предположить, что класс может порождать более двух подклассов. Иначе говоря, признак может принимать несколько разных значений. Практическое значение такого разбиения также не обошли вниманием разработчики языков программирования, введя оператор выбора case .

КСТАТИ

В главе A обсуждались способы записи алгоритмов. Один из упомянутых способов — диаграммы Насси–Шнейдермана. Вид конструкции case на языке этих диаграм ясен из примера на рис. C4.2.

Рис. С4.2. Блок case

Классификационные системы подобного рода относят к перечислительным [44]. Простейшие из них, “одноуровневые”, называют порядковыми.

Пример C4.4. Нумерация домов вдоль улицы — типичный пример перечислительной классификации. Порядок здесь, очевидно, линейный, определяемый последовательностью перечисления домов; хотя даже в этой простой типизации дополнительно выделены два подкласса: нечетные номера — по правой стороне улицы, четные — по левой. При последующей застройке встраивание нового дома может нарушить имеющийся порядок, поэтому используют дополнительный индекс: так, между домами 3 и 5 появляется дом 3a или дом 3, корпус 2.

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

Пример C4.5. Если в населенном пункте несколько улиц, то адрес дома формируется из названия улицы (первый уровень перечислительной классификации) и номера дома (второй уровень).

Пример C4.6. Помещение, в котором размещается дисплейный класс, имеет порядковый номер 462. Это не значит, что в здании имеются помещения со всеми меньшими номерами: в действительности начальная цифра 4 соответствует этажу, а номер 62 — порядковый для данного этажа. В данном случае можно предположить, что на этаже не более 99 помещений, либо привлекаются дополнительные индексы, как в примере C4.4.

В отличие от дихотомического деления для полного представления о множестве подклассов делимого класса следует либо указывать диапазон их значений, либо явно перечислять все значения. Наглядным способом представления иерархической классификации служит иерархическое дерево, естественным образом обобщающее вариант дерева дихотомического. Обычно перечисление вершин-детей требует определенного порядка. Чтобы локализовать место какого-то вида (значения) внутри иерархии, достаточно указать все родовые признаки деления в последовательности от прародителя к данному виду. Такая последовательность задает путь для реализации поискового запроса.

Пример C4.7. В представленном на рис. C4.3 дереве порядок “на детях” (подклассах) каждой вершины задается перечислением имен-значений традиционным способом “слева направо”. Это иерархическое дерево иллюстрирует оглавление полного собрания сочинений Шекспира [74]. Место в нем пьесы “Гамлет, принц Датский” локализуется как ПСС Шекспира || т. 6 || Гамлет, принц Датский .

Рис. С4.3. Иерархическое дерево

КСТАТИ

Аналогичным образом формируется полное имя файла на диске.

Далеко не всегда удобно использовать столь длинное имя. Зачастую проще оказывается ввести маркировку подклассов делимого класса элементами какого-либо общеупотребительного алфавита. В этом смысле любопытна классификация, представленная в примере C4.8.

Пример C4.8. В.Я. Пропп выделил и классифицировал сюжетные элементы, из которых строится любая “волшебная сказка” [37]. Так, за классом A закреплена функция “вредительство”, за классом Б — борьба с вредителем, П — победа над вредителем, Л — ликвидация беды или недостачи и т.д. Одного уровня не хватает, и каждый класс делится на подклассы, что отражается в наращивании индекса. В частности, для класса A:

· А1 — похищение человека;

· А2 — похищение волшебного средства или помощника;

· АII — насильственное отнятие помощника;

· А3 — порча посева;

· А4 — похищение дневного света;

· А5 — хищения в иных формах;

·…

· А17 — каннибализм или его угроза;

· АXVII — то же между родственниками;

· А18 — вампиризм (болезнь);

· А19 — объявление войны.

Любопытно, что многим из перечисленных пунктов сей сказочной классификации соответствуют отдельные статьи вполне реального Уголовного кодекса. Собственно говоря, в основе законодательно принимаемого Уголовного кодекса лежит определенная классификация всевозможных преступлений.

Проппу явно не хватало набора десятичных номеров, и он слегка “разбавил” перечисление, использовав заодно римскую нумерацию. В данном случае автор, специалист в области гуманитарных наук, несколько вольно обошелся с индексирующим алфавитом, однако в более серьезных классификациях смешение алфавитов для индексирования элементов одного уровня не принято. Чаще других для индексирования привлекают либо латинский алфавит, либо десятичную нумерацию. Очевидно, популярность десятичного алфавита изначально объясняется исключительно антропологическими особенностями нашего организма. Алфавитный порядок значений индексов однозначно определяет последовательность подклассов-элементов внутри делимого класса.

Как мы успели заметить, для отдельных предметных областей обычно создаются частные классификации. Но для межпредметного применения, для документирования информации и организации ИПС они явно не подходят, здесь требуется уже универсальная классификация. Таковых в современной международной практике признано сразу несколько, и вполне обычным делом является их параллельное использование66.

В Российской Федерации действует ГОСТ 7.59–2003 [13], который допускает к применению с учетом вида и назначения документа лишь семь классификационных ИПЯ, согласно определенному перечню. В числе прочих в него входят Универсальная десятичная классификация (УДК), Библиотечно-библиографическая классификация (ББК) и Десятичная классификация Дьюи (ДКД).

Читатель наверняка обращал внимание на специальную маркировку книг, размещаемую на обороте титульного листа: в его левом верхнем углу, непосредственно перед библиографическим описанием, имеется один или два классификационных индекса. В отечественном книгоиздании принято в эту маркировку включать индексы УДК и ББК, они же дублируются в библиотечных каталожных карточках. Однако еще более распространенной является ДКД — ее индексами маркированы большинство зарубежных изданий.>

ИСТОРИЧЕСКИЙ ЭКСКУРС

В своих воспоминаниях М.Дьюи67 утверждал, что рождение ДКД стало результатом озарения, связанного с религиозным опытом. Так это или нет, уже не имеет значения, но со свойственной американцам практичностью Дьюи не преминул, публикуя “ниспосланные свыше” знания, пометить их собственным копирайтом. Разработка Десятичной классификации Дьюи (Dewey Decimal Classification) датируется 1873 г., первое издание было опубликовано в 1876 г. С тех пор ДКД постоянно обновляется, в 2003 г. вышло уже 22-е издание. В сферу распространения ДКД входят более 135 стран, доступны переводы на три с лишним десятка языков. В нашей стране опубликован перевод 21-го издания [18].

Формально-логическое устройство ДКД выглядит достаточно просто. Дьюи принял за основу схему деления предметных областей, восходящую к Бэкону68. Все пространство знания он поделил на 9 основных классов, занумерованных цифрами от 1 до 9 (поначалу 0 ему не понадобился, однако в дальнейшем нулевому классу нашли применение), основной класс — на 10 разделов, каждый раздел — на 10 секций.

Пример C4.9. Нетрудно догадаться, что Дьюи не имел представления о компьютерных дисциплинах, так что свободный раздел 00 оказался весьма кстати: в нем нашли пристанище Компьютеры, Интернет и системы. Среди секций этого раздела есть, в частности, 004 = Обработка данных. Вычислительная техника, а также 005 = Компьютерное программирование, программы, данные.

Начальную триаду класс–раздел–секция при дальнейшем уточнении понятия принято отделять точкой, после которой справа добавляются новые цифры без формального ограничения их количества и без введения каких­либо синтаксических разделителей.

Пример C4.10. В секции 746 = Роспись по ткани имеется много­-много подуровней; так, 746.14043708997 = Индейские шерстяные одеяла, а еще ниже 746.140437089972 = Шерстяные накидки индейцев навахо.

Классификация не может оставаться статичной, вновь возникающие понятия не только требуют ее расширение, но и провоцируют противоречия в ее структуре. Потому очевидна необходимость регулярного обновления используемой версии ДКД, выпуска новых изданий. Существенно, что некоторые поправки вносятся и публикуются даже в период между переизданиями полной классификации.

Пример C4.11. Секция 652 = Процессы письменного общения понесла потери: понятие 652.5 = Word processing получило в 22-м издании новую прописку 005.52. В нем же пополнилась секция 006 = Специальные компьютерные методы: понятие 006.74 = Языки разметки возникло совсем недавно.

Даже из одного лишь примера C4.10 видно, как может разрастаться индекс, который приписывается некоторому понятию, нашедшему свое место в иерархической классификации. Чем больше признаков участвовало в последовательных делениях понятия, тем больше уровней учтено в полученном индексе. Выше мы отмечали, что выбор признаков деления в искусственных классификациях достаточно произволен. А значит, для некоторого индексированного понятия иная последовательность признаков деления породила бы другое значение индекса. Собственно говоря, C4.11 иллюстрирует подобную ситуацию. Таким образом, с ростом мощности множества вошедших в иерархическую классификацию понятий указанные недостатки все более тормозят ее расширение.

При иерархическом делении на каждом уровне учитывается лишь один признак, остальные рассматриваются как несущественные и отбрасываются. Почему бы не попытаться “параллельно” учесть некоторые из них? Новая идея состояла в том, чтобы собрать наборы одинаковых второстепенных признаков и строить на их основе дополнительные таблицы типовых делений. Соответствующие индексы должны добавляться к индексу основному. Разумеется, соединение нескольких значений в общем индексе понятия требует включения в ИПС расширенного синтаксиса. Подобные идеи нашли отражение в развитии ДКД, начиная с 13-го издания. С этого момента на смену иерархическим пришли более удобные комбинационные классификации.

В полной мере комбинационный подход проявился в Универсальной десятичной классификации (1895–1905), детище П.Отле и А.Лафонтена69. В российской практике книгоиздания систематизация по УДК введена в 1963 г. Но еще задолго до официального признания и внедрения УДК, начиная с 1930-х гг., в нашей стране разрабатывалась собственная система — ББК (1-е издание осуществлено в 1960–1968 гг.).

ИСТОРИЧЕСКИЙ ЭКСКУРС

Бельгийские ученые-юристы Поль Отле и Анри Лафонтен более известны как основатели (1895) Международного библиографического института, после многих трансформаций превратившегося спустя столетие (1988) в Международную федерацию по [информации и] документации (МФД)70. Между прочим, каталожная карточка размером 125 75 мм (5" 3") — тоже их изобретение.

Дальнейшие шаги специалистов в области классификаций связаны с развитием идей Ш.Р. Ранганатана71, разработавшего основы фасетного анализа, специальный язык и фасетную систему классификации [38] (1-е издание появилось в 1933 г.)72. В современных версиях УДК и ББК “фасетность” тоже имеет место, но лишь “в малых дозах”. Как мы отмечали, обе эти классификации применяются параллельно, в естественно-научных областях знания приоритет за первой из них, в остальных — за второй.

Пример C4.12. Классификационные индексы книги [25] выглядят следующим образом: УДК 681.142.2 и ББК 32.973.26-018.2я75; у книги [33] — УДК 512+519.6 и ББК 22.14+22.19. Синтаксические связки-разделители +, , я сигнализируют о переключении таблицы типовых делений.

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

КСТАТИ

Древовидную структуру имеют иерархии классов в объектно-ориентированных языках программирования (при условии, что множественное наследование запрещено или не используется). В корне дерева находится самый общий класс (в Delphi — TObject), а классы-потомки наследуют его свойства и добавляют новые. В качестве примера приведем часть иерархии классов среды программирования Delphi (рис. C4.4).

Рис. C4.4. Иерархия классов среды программирования

C5. Деревья

Один сын — не сын, два сына — полсына, а три сына — сын.

Пословица73

В предыдущем разделе мы познакомились с иерархическими деревьями. Также были рассмотрены иерархические деревья с заданным порядком на детях, или упорядоченные. Однако изложение было неформальным, поэтому целесообразно ввести несколько более строгих определений. Воспользуемся для этого тем же аппаратом теории отношений, что и в разделе C1. Тогда мы ввели отношение предшествования для пар книг (см. рис. C1.1).

Сейчас нам будет удобнее говорить об отношении “отец–сын” на некотором конечном множестве. В двуместном отношении (то есть в таблице) парам элементов этого множества будет сопоставляться 1 на пересечении строки-отца и столбца­-сына (отец сын), остальные клетки заполним 0. Потребуем, чтобы отношение:

1) являлось антирефлексивным (запрет на пары вида (i, i) = 1);

2) являлось антисимметричным (то есть одновременно не может быть пар (i, j) = 1 и (j, i) = 1);

3) не содержало пар вида (i, k) = 1 и (j, k) = 1 для i j (то есть у каждого сына не более одного отца);

4) было таким, что во всех парах вида (i, j) = 1 выполнялось i j (без этого условия возможны циклы
i j, j k, k i).

Построенное отношение называется (ориентированным) лесом, его элементы — узлами (или вершинами), пары (i, j) = 1 — ветвями. Заметим, что таблица­отношение принимает вид верхнетреугольной матрицы, поскольку нижний левый треугольник заполнен только нулями; также лишь нули и на главной диагонали.

В отсутствие единичных элементов в таблице­отношении “лес” мы имеем дело с вырожденным лесом, который особого интереса не представляет. Упомянем еще возможность пустой таблицы­-отношения (мощность множества вершин равна 0), которой соответствует понятие пустой лес. Но и в случае невырожденного леса преобладание нулевых элементов делает нерациональным табличное представление (рис. C5.1), нагляднее оказывается графическая иллюстрация (рис. C5.2).

Рис. N5.1. Лес

Рис. N.5.2. Тот же лес

Непустая последовательность из m + 1, 0 m узлов леса

v0, v1, …, vm – 1, vm,

в которой каждая пара соседних узлов (vi, vi+1) соединена ветвью “отец–сын”, называется путем из v0 в vm. Значение m называется длиной пути. При отсутствии ветвей (m = 0) путь имеет нулевую длину74. Всякий путь ненулевой длины ведет от некоторого предка к его потомку, путь от отца к сыну является просто частным случаем.

Если существует совокупность путей, начинающихся в некоторой вершине v0 и проходящих через все остальные вершины леса, то такой лес называется (корневым) деревом с вершиной v0 в роли корня. В системе парных отношений “отец–сын” корень стоит особняком — он “сирота”; каждому из корней леса в таблице соответствует столбец из нулей, на рис. C5.1 таковы столбцы a и b. Очевидно, что всякий невырожденный лес состоит из конечного числа корневых деревьев. Также очевидно, что все узлы дерева являются потомками корня, кроме него самого.

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

Степенью узла дерева называется число его сыновей75. Узел, не имеющий сыновей, называется листом. Листья также именуют внешними вершинами дерева, а остальные узлы — внутренними.

Узлы j и k являются братьями, если (i, j) = 1 и (i, k) = 1, то есть имеют общего отца. Длина пути от корня дерева до узла называется глубиной этого узла. Наибольшая из глубин листьев есть высота дерева. Еще для удобства изложения вводится понятие уровня — общего для группы вершин с одинаковой глубиной, для отдельной вершины ее уровень совпадает с глубиной.

Пример C5.1. На рис. C5.2 дерево слева имеет высоту 1, справа — высоту 2; у левого 2 листа, у правого — 3. Корни деревьев лежат на нулевом уровне. Глубина вершины h составляет 2. Степень вершины a равна 2, вершины b — 3, вершины f — 1. Вершины c, d и f — братья. Иногда76 актуальным оказывается понятие дядя: у вершины h их двое — c и d.

КСТАТИ

Попробуйте дать определение узлу-дяде.

Для формализации понятия упорядоченное дерево остался последний шаг: надо лишь ввести линейный порядок на детях каждого узла дерева. Теперь вполне естественной оказывается традиционная терминология, отражающая “порядок рождения”: старший сын и т.д. Заметим, что внутренняя вершина по определению имеет степень больше 0, среди ее детей старший сын наличествует обязательно.

Пример C5.2. На рис. C5.2 мы специально разместили братьев визуально в произвольном порядке. Иллюстрируя упорядоченные деревья, обычно перечисляют братьев в лексикографическом порядке слева направо, но следует всегда оговаривать, какого типа деревья изображены. Убирая метки вершин правого дерева на том же рисунке, можем получить сразу три разных изображения формально одного и того же корневого дерева (рис. C5.3). Но стоит лишь сказать, что это упорядоченные деревья, как сразу имеем 3 разных дерева.

Рис. C5.3. Одно и то же дерево или три разных дерева?

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

Пример C5.3. В Полное собрание сочинений Шекспира [74] включены все его исторические хроники. На рис. C5.4 (сравните с рис. C4.3), иллюстрирующем структуру ПСС, порядок на детях первого уровня определяется нумерацией томов, на втором уровне — оглавлением соответствующего тома. Какими же критериями руководствовались составители собрания при выборе порядка? Оказывается, они разместили пьесы по томам, сообразуясь с традицией шекспироведения, которая во главу угла ставит время их написания:

· Генрих VI, ч. 1–3 (1590–1592) и Ричард III (1593) — вошли в том 1,

· Король Иоанн (1596) и Ричард II (1595) — в том 3,

· Генрих IV (1597–98) и Генрих V (1598) — в том 4,

· Генрих VIII (1613) — в том 8.

Если бы в постановке задачи составители приняли за основу хронологический принцип и учли даты жизни и владения престолом английскими королями77, давшими имена шекспировским хроникам, то последовательность стала иной (в круглых скобках — годы жизни, в квадратных — годы царствования):

· Иоанн I Безземельный (1167– [1199–1216] ),

· Ричард II (1367– [1377–1399] –1400),

· Генрих IV Болингброк (1366– [1399–1413] ),

· Генрих V Ланкастер (1387– [1413–1422] ),

· Генрих VI Ланкастер (1421– [1422–1461; 1470–1471] ),

· Ричард III Йоркский (1452– [1483–1485] ),

· Генрих VIII (1491– [1509–1547] ).

Наконец, в лексикографически организованный индекс пьесы должны войти опять в иной последовательности:

· Генрих IV,

· Генрих V,

· Генрих VI (Часть 1, Часть 2, Часть 3),

· Генрих VIII,

· Король Иоанн,

· Ричард II,

· Ричард III.

Рис. N5.4. Различные представления упорядоченного дерева

Графические представления упорядоченных деревьев не ограничиваются лишь “древесной” картинкой (рис. C5.4, a иллюстрирует пример C5.3 с шекспировскими хрониками; номера томов сохранены, а названия пьес заменены метками). Другие варианты78, дублирующие дерево, также находят применение. Вложенные множества в сти­ле рис. C5.4, b (здесь, впрочем, упорядоченность не отражается) часто представляют подобным образом в логике и теории множеств, где они фигурируют как диаграммы Венна и круги Эйлера79. По существу, и диаграммы Насси–Шнейдермана (см. рис. C4.2) — того же рода. Структура вложенных скобок (рис. C5.4, c) актуальна в связи с задачами разбора выражений, в стековой арифметике — см. разделы E3 и E4 в книге. Форматирование отступами (рис. C5.4, d) типично для оглавления книги, этот же стиль практически обязателен для текста программы на языке высокого уровня.

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

1 type

2 PTreeNode = ^TTreeNode;

3 TTreeNode = record

4 firstChild: PTreeNode;

5 nextSibling: PTreeNode;

6 item: TItem;

7 end;

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

Пример C5.4. Обратимся вновь к рис. C4.3 и создадим здесь структуру с оглавлением. Для этого разместим в “основном” массиве последовательно, руководствуясь порядком томов, все произведения, включенные в этот десятитомник. Очевидно, области, соответствующие разным томам, не будут одинаковыми по длине. А теперь создадим массив-“оглавление” из записей фиксированной длины, поместив в качестве i-й записи адрес начала области для i-го тома в основном массиве. По существу это самый обычный, не алгоритмический, словарь с единственной операцией — поиска, где “ищется” содержание i-го тома.

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

Когда все внутренние вершины корневого дерева (необязательно упорядоченного) имеют степени не более некоторого k > 0, можно говорить о k-дереве80. Такие деревья нам недавно встречались: устройство 10-деревьев классификации Дьюи (эти, кстати, упорядочены) описано в разделе C4. Если степень k одинакова для всех внутренних вершин, то дерево называют полным.

Рис. N5.5. Генеалогическое дерево

Пример C5.5. Полное k-дерево можно хранить в линейном массиве фиксированной длины. Индекс i родителя при нумерации элементов массива с нуля позволяет обнаружить его сыновей по адресам i · k + 1, i · k + 2, …, i · k + k. Такая адресация позволяет отказаться от хранения массива с явными ссылками, примененного в структуре с оглавлением. Полезное применение этого механизма отражено в упр. D6.4 в книге.

Наиболее востребованными оказываются полные двоичные (k = 2) деревья, бинарные деревья, неслучайно в нашей книге они встречаются неоднократно. Таковы генеалогические деревья, в них пару детей узла (человека) составляют его настоящие отец и мать (рис. C5.5); конечно, с позиции деления понятий это представление выглядит странным, но на базе отношений оно вполне уместно. Так же устроены таблицы соревнований, проходящих по системе “с выбыванием” (рис. C5.6). Того же типа деревья выражений, об их обходе идет речь в разделе E4 в книге. Наконец, аналогично устроены кодовые деревья Фано и Хаффмена (разделы F4 и F5 в книге).

Рис. C5.6. Кубок ФИФА-2006

Рис. C5.7. Два разных двоичных дерева

Принято старшего сына двоичного дерева называть левым, второго сына — правым. В отличие от упорядоченного дерева в двоичном дереве вполне допустимо пустое поддерево (рис. C5.7) и даже оба пустых. Для перевода структуры упорядоченного дерева в дерево двоичное применяется довольно простой

Алгоритм C5.1. Преобразование упорядоченного дерева в двоичное:

1. Старший сын каждого узла упорядоченного дерева становится левым потомком того же узла в бинарном дереве.

2. Каждый нестарший сын узла упорядоченного дерева становится в новом дереве правым потомком своего предыдущего по старшинству брата.

При графическом отображении полученного дерева левые связи обычно рисуют вертикально, правые — горизонтально. На рис. C5.8 представлены упорядоченное дерево (слева) и соответствующее ему двоичное дерево. Обратите внимание на отсутствие правого поддерева у корня построенного двоичного дерева: действительно, прежний корень не мог иметь младших братьев.

Рис. C5.8. Преобразование упорядоченного дерева в двоичное

Упражнения

C5.1. В школьной библиотеке имеется несколько экземпляров каждого из учебников. В доступном читателю каталоге не принято размещать множество одинаковых карточек для данного учебника, достаточно лишь одной — с указанием полочного индекса. Однако библиотекарь хочет иметь сведения о наличии экземпляров на полках книгохранилища, чтобы не ходить по запросу посетителя за учебником, все экземпляры которого на данный момент выданы. Как модифицировать логическое описание упорядоченного дерева, чтобы отражать соответствующие сведения в рабочем каталоге библиотекаря (первый уровень дерева — ящики каталога, второй — разделители в ящике, третий — собственно карточки, также без дублирования одноименных)?

C5.2. Напишите программу, реализующую алгоритм C5.1.

C5.3. Напишите программу, строящую на экране упорядоченное дерево в фор­мате рис. C5.4, a, без пересечений ветвей. Входной набор представлен структурой вложенных скобок, аналогично рис. C5.4, c.

C5.4. Напишите программу, строящую на экране двоичное дерево в фор­мате рис. C5.8, без пересечений ветвей, полученное из заданного упорядоченного дерева. Входной набор представлен структурой вложенных скобок, аналогично рис. C5.4, c.

КСТАТИ

Отдельный интерес представляют объекты, относящиеся к так называемым L-системам. В 1968 г. эту математическую модель предложил А.Линденмайер81. Среди возникающих в ее рамках конструкций немало древовидных, не только в алгоритмическом смысле, но и визуально вполне схожих с растительными объектами. Для знакомства с L-системами рекомендуем читателю замечательную книгу [51].

На сайте http://algorithmicbotany.org доступны многочисленные материалы данной тематики, включая электронную версию названной книги (http://algorithmicbotany.org/papers/abop/abop.pdf).

C6. Деревья поиска

Представление — суть программирования.

Ф.Брукс82

В разделе C3 мы отметили, что для поддержания структуры словарь могут применяться ассоциативные массивы на базе деревьев поиска.

Почему нас не устраивают уже знакомые нам упорядоченные деревья? Дело в том, что в общем случае их определение ничего не говорит о связи ключа с его носителем, узлом дерева.

Пример C6.1. В иерархическом дереве на рис. C4.3 слишком мало информации для эффективного поиска пьесы по ее названию.

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

Пример C6.2. Стоит попробовать вставить или удалить какой­-нибудь внутренний узел в дереве классификации Дьюи, как мы немедленно сталкиваемся с проблемами, которые иллюстрируются примерами C4.9 и C4.11.

Пример C6.3. Проппу для вставки “пропущенных” ключей AII и AXVII (см. пример C4.8) даже потребовалось расширение алфавита.

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

Пример C6.4. Многим читателям знакома ситуация замены номера автоматической телефонной станции. Эта мера связана или с переходом на новый тип АТС, или с модификацией общего пространства номеров. Результатом же оказывается изменение телефонных номеров всех абонентов данной АТС.

Если в примере C6.4 массовая замена префиксов вынуждается экстраординарными обстоятельствами, то для рутинного использования словаря такая обработка представляется неоправданно дорогостоящей. Наша задача состоит в реализации словаря, менее чувствительного к операциям вставки и удаления.

Итак, будем опираться на двоичные деревья поиска, кратко именуемые BST83.

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

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

Предваряя словарные алгоритмы для BST, введем следующие объявления:

1 type

2 PTreeNode = ^TTreeNode;

3 TTreeNode = record

4 item: TItem;

5 left: PTreeNode;

6 right: PTreeNode;

7 end;

8 TBST = object

9 root: PTreeNode;

10 procedure Traverse(const node: PTreeNode);

11 procedure Search(const item: TItem;

12 var node, parent: PTreeNode);

13 procedure Insert(const item: TItem);

14 procedure Delete(const item: TItem);

15 function DeletePredecessor(parent:

16 PTreeNode): TItem;

17 end;

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

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

Алгоритм C6.1. Поиск в BST.

1 procedure TBST.Search(const item: TItem;

2 var node, parent: PTreeNode);

3 begin

4 parent := nil;

5 node := root;

6 while node <> nil do begin

7 if node^.item = item then exit;

8 parent := node;

9 if item < node^.item then

10 node := node^.left

11 else

12 node := node^.right;

13 end;

14 end;

Похожим образом реализуется операция вставки элемента в BST. Как и при поиске, спускаемся вниз, но не останавливаемся в случае совпадения ключа с уже имеющимся в дереве элементом, а продолжаем движение, как при неудаче. Так добираемся до листа с пустой ссылкой, куда и помещаем новую вершину. Входной параметр у процедуры Insert один: элемент для вставки (ключ).

Алгоритм C6.2. Вставка в BST.

1 procedure TBST.Insert(const item: TItem);

2 var newNode, node: PTreeNode;

3 begin

4 new(newNode);

5 newNode^.item := item;

6 newNode^.left := nil;

7 newNode^.right := nil;

8 if root = nil then begin

9 root := newNode;

10 exit;

11 end;

12 node := root;

13 while true do

14 if item <= node^.item then

15 if node^.left = nil then begin

16 node^.left := newNode;

17 break;

18 end else

19 node := node^.left

20 else

21 if node^.right = nil then begin

22 node^.right := newNode;

23 break;

24 end else

25 node := node^.right;

26 end;

Пример C6.5. Построим BST для символов входной строки крокодил . Начав с пустого дерева и вставляя символы поочередно, получим последовательно деревья, представленные на рис. C6.1.

Обратите внимание, что узлы с равными ключами могут размещаться отнюдь не по соседству. Тем не менее дерево упорядочено, что проявляется, если обойти его согласно правилу инфиксного или внутреннего обхода: “левое поддерево узла — узел — правое поддерево узла”84. На выходе получаем перечень вершин в порядке ключей. Вот соответствующая процедура Traverse, на входе ей нужен лишь указатель на корень дерева.

Алгоритм C6.3. Инфиксный обход BST.

1 procedure TBST.Traverse(const node: PTreeNode);

2 begin

3 if node = nil then exit;

4 Traverse(node^.left);

5 { обработка node }

6 Traverse(node^.right);

7 end;

Пример C6.6. Применив процедуру Traverse к дереву, представленному на рис. C6.1, получим на выходе последовательность символов дикклоор. Легко заметить, что она соответствует алфавитному порядку для символов входной строки.

Рис. С6.1. Посимвольная вставка в BST букв слова крокодил

Дерево поиска можно строить на данных любого порядкового типа. Независимо от последовательности ввода и “развешивания” ключей при построении дерева про­цедура Traverse выведет их в нужном порядке. Таким образом, построение BST с последующим инфиксным обходом может служить альтернативой сортировке входного набора. Не случайно в компьютерном сленге к этому алгоритму приклеилось забавное имя обезьяньей сортировки.

Очевидно, максимальная стоимость операций поиска и вставки зависит от высоты дерева. И здесь входная последовательность играет свою роль. На рис. C6.2 представлены все возможные варианты диаграмм двоичного дерева поиска для множества из трех ключей. Мы видим, что при вводе последовательности ключей ABC или CBA строится дерево с наибольшей возможной высотой, в остальных случаях — высота меньше.

Нетрудно догадаться, что упорядоченность входного потока не лучшим образом отражается на поисковых качествах BST. При больших мощностях множества ключей это существенно. Если для случайного входного потока высота дерева оценивается как O(log2n), то в указанных случаях стоимость операций уже линейная.

Рис. С6.2. Различные BST для множества символов {A, B; C}

КСТАТИ

Избежать подобные ситуации позволяют сбалансированные деревья поиска. В современной практике программирования прижились несколько таких структур (см. [25; 26; 41]) с примерно одинаковыми свойствами. При вставке и удалении элемента в них поддерживается логарифмическая высота сбалансированного дерева. Разумеется, это требует дополнительных накладных расходов, однако стоимость удается ограничить указанной оценкой.

Наконец дошла очередь до последней из триады словарных операций — удаление элемента. Здесь-то нам и пригодится “лишний” выходной параметр процедуры Search, поскольку удаление узла дерева связано с изменением соответствующей ссылки у его родителя.

Для простоты будем игнорировать дубликаты удаляемого ключа, находящиеся в дереве ниже. Это позволяет ограничиться одним входным параметром для про­цедуры удаления: значением ключа. Запустив процедуру Search, мы найдем нужную пару указателей на удаляемый элемент и его родителя, если, конечно, элемент с таким ключом существует. Если же для удаляемого элемента допускаются дубликаты, то надо уточнить, кого из них планируется ликвидировать, изменив соответствующим образом поисковую процедуру (оставим эту ситуацию читателю в качестве упражнения; см. упр. C6.1).

Иллюстрировать механизм помогут диаграммы на рис. C6.3 (удаляемый элемент помечен) из знакомого нам примера C6.5. Первые два случая элементарны. Если дерево состоит из единственного, корневого узла, то его ликвидация сводится к получению пустого дерева (рис. C6.3, a). Если же удаляется лист, то аналогичные рассуждения действительны для поддерева с корнем в указанном листе (рис. C6.3, b). В третьем случае (рис. C6.3, c) удаляемый узел имеет лишь одного сына, поэтому достаточно переставить на внука освобождающийся указатель от деда.

А вот случай удаления узла, имеющего обоих детей, несколько сложнее. В этой ситуации будем сначала отыскивать предшественника удаляемого узла в данном порядке ключей. Заметим, что такой узел-предшественник, во-первых, лежит в левом поддереве удаляемого узла и, во-вторых, сам не может иметь правых потомков (иначе кто-то из них претендовал бы на роль предшественника). Найдя такого (единственного!) претендента (рис. C6.3, d), запомним его адрес и удалим этот узел из левого поддерева, не забыв, разумеется, исправить ссылки аналогично вариантам C6.3, b или C6.3, c.

Рис. N6.3. Удаление узла двоичного дерева поиска

Алгоритм C6.4. Поиск и удаление предшественника узла в BST.

1 function TBST.DeletePredecessor(parent:

2 PTreeNode): TItem;

3 var node, tmp: PTreeNode;

4 begin

5 node := parent^.left;

6 while node^.right <> nil do begin

7 parent := node;

8 node := node^.right;

9 end;

10 DeletePredecessor := node^.item;

11 if parent^.left = node then

12 parent^.left := nil

13 else

14 parent^.right := nil;

15 dispose(node);

16 end;

Теперь остается подставить элемент-предшественник вместо удаляемого узла, установив соответствующие ссылки. Резюмируя сказанное, для процедуры Delete получаем следующий

Алгоритм C6.5. Удаление из BST.

1 procedure TBST.Delete(const item: TItem);

2 var node, parent: PTreeNode;

3 ref: ^PTreeNode;

4 begin

5 Search(item, node, parent);

6 if node = nil then exit;

7

8 { запоминаем указатель на node }

9 if parent = nil then

10 ref := @root

11 else if parent^.left = node then

12 ref := @parent^.left

13 else

14 ref := @parent^.right;

15

16 { удаляем node и корректируем указатель }

17 if node^.left = nil then begin

18 ref^ := node^.right;

19 dispose(node);

20 end else if node^.right = nil then begin

21 ref^ := node^.left;

22 dispose(node);

23 end else

24 ref^^.item := DeletePredecessor(node);

25 end;

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

Итак, мы рассмотрели все словарные операции на двоичном дереве поиска и убедились в том, что их трудоемкость оценивается как O(log2n). Завершая обсуждение манипуляций с BST, остается обратить внимание читателя на простой механизм поиска в BST минимального и максимального ключей (см. упр. C6.2). Первый из искомых узлов либо совпадает с корнем, не имеющим левого поддерева, либо является последним узлом этого поддерева на пути от корня, проходящем только по левым ветвям. Для второго экстремума ситуация симметрична.

КСТАТИ

Стоит указать на возможность реализации словаря на недвоичных, сильноветвящихся деревьях поиска. Их достоинством является меньшая высота и, соответственно, алгоритмическая стоимость операций. Продвинутому читателю рекомендуем обратиться за подробностями к упоминавшимся выше книгам [25; 26; 41].

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

А. и Б. Стругацкие85

Упражнения

C6.1. Напишите процедуру удаления узла из BST при наличии повторяющихся ключей. В качестве дополнительного параметра укажите порядковый номер элемента из числа подходящих на поисковом пути.

C6.2. Напишите процедуры Min и Max, возвращающие, соответственно, минимальный и максимальный ключи в BST.

C6.3. Напишите процедуру удаления узла из BST, в которой вместо удаляемого элемента подставляется не предшественник, а следующий элемент.

C6.4. Напишите программу, строящую и выводящую в заданном порядке ключей двоичное дерево поиска. На вход программы подается последовательность пар (команда, ключ), где в качестве команды допускается либо I (вставить), либо D (удалить). Считаем, что при наличии одинаковых ключей удаляется ближайший к корню.

В главе D книги рассматриваются алгоритмы, работающие непосредственно с массивами. Теперь же уделим внимание структурам и алгоритмам, для которых массив является лишь удобным, но не всегда единственно возможным “носителем”. Нам предстоит обсудить такие важные темы, как динамическое программирование, стеки и хеширование.

E1. Динамическое программирование

— Чтобы продать что-нибудь ненужное, — сердится кот, — надо сначала купить что-нибудь ненужное. А у нас денег нет.

Э.Успенский86

В конце 50-х гг. XX в. американский математик Р.Беллман87 предложил новый метод теории управления, получивший имя динамическое программирование. Задача теории управления, решаемая этим методом, заключается в определении последовательности управляющих воздействий, обеспечивающих оптимальное течение некоторого управляемого процесса.

Динамическое программирование, обсуждаемое в рамках алгоритмики, не имеет прямого отношения к упомянутому математическому методу, хотя основано на схожих соображениях и часто используется в задачах оптимизации. Динами­ческим программированием мы называем подход, представляющий собой развитие идеи “разделяй и властвуй”88. С последней мы сталкивались, если помните, в разделе D6, когда обсуждали механизм разделения массива на части в процессе быстрой сортировки. Динамическое программирование также предполагает разбиение исходной задачи на подзадачи, из решений которых потом “собирается” окончательный ответ. Есть, однако, и отличие (на то оно и развитие): теперь подзадачи не являются полностью независимыми, но могут содержать некоторые общие “подподзадачи”, которые желательно решать только один раз.

Пример E1.1. Обратимся к уже знакомой нам последовательности Фибоначчи. Вычисление n-го ее элемента fn (при n > 2) сводится к нахождению чисел fn – 2 и fn – 1, так как по определению fn = fn – 2 + fn – 1. (Фибоначчиево дерево представлено на рис. E1.1.) В последней формуле каждое слагаемое также раскладывается в сумму:
fn = (fn – 4 + fn – 3) + (fn – 3 + fn – 2). Здесь появляется первая общая подзадача: fn – 3. При дальнейшем развертывании формулы количество таких общих подзадач быстро растет.

Рис. A1.1. Дерево Фибоначчи (fn = fn – 2 + fn – 1)

Рассмотрим разные подходы к вычислению fn.

Вспомним, что рекуррентное соотношение, подобное имеющему место для чисел Фибоначчи, встречается, например, в определении факториала: n! = n(n – 1)!. Функция, вычисляющая факториал и традиционно приводимая в учебниках по программированию как пример рекурсивной функции (рекурсии посвящены разделы E6 и E7), может быть записана следующим образом:

1 function Factorial(const n: longint): longint;

2 begin

3 if n = 0 then

4 Factorial := 1

5 else

6 Factorial := n * Factorial(n - 1);

7 end;

Почему бы просто не списать это решение, пользуясь “принципом повторного использования кода”? Получится такая программа89:

1 function Fibonacci(const n: longint): longint;

2 begin

3 if (n = 1) or (n = 2) then

4 Fibonacci := n

5 else

6 Fibonacci := Fibonacci(n - 2) +

7 Fibonacci(n - 1);

8 end;

К сожалению, теоретические оценки (да и непосредственный эксперимент) показывают ее крайнюю неторопливость. Время работы приведенной функции есть O( fn), а числа Фибоначчи растут почти так же быстро, как последовательность 2n. Возникает необходимость искать другое решение.

Здесь-то и приходит на помощь динамическое программирование. Действительно, наше решение никак не учитывает наличие общих подзадач, демонстрируемых примером E1.1. Чем меньше номер k, тем больше раз во время работы программы заново вычисляется число fk. Гораздо рациональнее единожды вычислить fk и записать полученное значение в память, откуда его при необходимости можно извлечь практически “бесплатно”. Модифицируем программу соответствующим образом (значение константы FN обсуждается в упр. E1.1):

1 var f: array [1..FN] of longint;

2 function FibonacciDP1(const n: longint): longint;

3 begin

4 if f[n] = 0 then begin

5 if (n = 1) or (n = 2) then

6 f[n] := n

7 else

8 f[n] := FibonacciDP1(n - 2) +

9 FibonacciDP1(n - 1);

10 end;

11 FibonacciDP1 := f[n]

12 end;

Это решение имеет временную сложность O(n), и мы удовлетворенно констатируем значительный выигрыш в скорости (правда, за счет дополнительного расхода памяти).

Примененная здесь техника называется динамическим программированием сверху вниз: решение начинается с исходной задачи, которая рекурсивно разбивается на подзадачи. Существует и другой подход, снизу вверх, при котором сначала рассматриваются самые мелкие подзадачи, решения которых последовательно объединяются для получения решений все более и более крупных90. Продемонстрируем идею второго метода все на той же задаче:

1 function FibonacciDP2(const n: longint): longint;

2 var prev, next, k: longint;

3 begin

4 if (n = 1) or (n = 2) then

5 FibonacciDP2 := n

6 else begin

7 prev := 1;

8 next := 2;

9 for k := 3 to n do begin

10 next := prev + next;

11 prev := next - prev;

12 end;

13 FibonacciDP2 := next;

14 end;

15 end;

Здесь в процессе вычисления переменные prev и next содержат пару соседних чисел Фибоначчи fk – 1 и fk, что заменяет громоздкую таблицу; k в цикле увеличивается. Трудоемкость решения вновь составляет O(n), однако нам удалось сэкономить память, избавившиcь от таблицы и рекурсивных вызовов.

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

Упражнения

E1.1. Выясните, начиная с какого по счету числа Фибоначчи возникает переполнение паскалевского типа longint. От этого зависит, в частности, насколько большой массив имеет смысл заводить для работы функции FibonacciDP1.

Вряд ли вы будете считать десятки чисел последовательности в уме или даже на калькуляторе, поэтому для ответа на вопрос придется написать программу. Подумайте, что и как она должна проверять и/или выводить, если автоматическая проверка диапазона (range checking) во время исполнения отключена.

E1.2. Для чисел Фибоначчи имеет место формула

,

где .

Число j называют золотым сечением. Напишите программу, использующую для вычисления fn указанное соотношение и алгоритм дихотомического возведения в степень.

E1.3. Известно, что Леонардо Фибоначчи получил последовательность, названную впоследствии его именем, когда исследовал численность популяции кроликов. В своих рассуждениях Фибоначчи опирался на следующие предположения:

· кролики способны к размножению через два месяца после рождения;

· каждый месяц взрослая пара животных производит новую пару;

· кролики не умирают;

· на момент начала наблюдения есть только одна пара новорожденных кроликов.

Вам предлагается написать программу, решающую эту задачу при более общих предположениях:

· кролики способны к размножению через p месяцев после рождения;

· кролик умирает после m месяцев жизни;

· m-месячная пара кроликов перед смертью успевает дать потомство.

Получив на вход числа p, m и n, ваша программа должна вывести количество пар кроликов через n месяцев после начала наблюдения.

E2. Примеры задач

— Однако мне тоже хочется, господа, задать вам одну загадку, — продолжал он. — Стоит четырехэтажный дом, в каждом этаже по восьми окон, на крыше — два слуховых окна и две трубы, в каждом этаже по два квартиранта. А теперь скажите, господа, в каком году умерла у швейцара бабушка?

Я.Гашек91

Разобрав в предыдущем разделе пример с числами Фибоначчи, вы должны были усвоить основные идеи динамического программирования. Однако для настоящего овладения этим (как и любым другим) методом требуется практика. Поэтому рассмотрим еще несколько задач.

Пример E2.1. Представим себе плоскость, на которой заданы декартова система координат и правила “дорожного движения”: из любой точки (x, y) разрешено перемещаться вправо, в (x + 1, y), или вверх, в (x, y + 1). Требуется подсчитать количество способов добраться из начала координат (0, 0) в точку с координатами (m, n).

Подкованный в комбинаторике читатель, без сомнения, сразу даст ответ в виде простой формулы (а для остальных — упр. E2.1), однако мы сначала приведем решение, использующее динамическое программирование. Вообще практика показывает, что программисту, не искушенному в тонкостях математики, бывает легче написать программу, чем вывести формулу. Такую программу мы и напишем, прокомментировав несколько общих моментов.

Обозначим через ways(x, y) количество путей, ведущих из начала координат в точку (x, y). Тогда справедливо рекуррентное соотношение

ways (x, y) = ways (x – 1, y) + ways (x, y – 1). (E2.1)

Действительно, в соответствии с правилами попасть в точку (x, y) можно слева или снизу; количество путей при этом суммируется. Кроме того, ways(0, y) =
= ways(x, 0) = 1.

Таким образом, мы можем завести одноименную таблицу ways и постепенно заполнить ее, получив интересующее нас значение ways[m, n]. Все готово для применения динамического программирования. Но остается выбор: решать задачу сверху вниз или снизу вверх? Мы предпочтем второй способ, поскольку он не потребует рекурсии (и соответствующих накладных расходов), а заодно позволит, как мы увидим в дальнейшем, уменьшить требования к памяти с O(mn) до O(n).

Итак, вот первый вариант программы, где таблица заполняется построчно с учетом граничных условий и полученного рекуррентного соотношения:

1 function CountWays(const m, n: longint): longint;

2 var ways: array of array of longint;

3 x, y: longint;

4 begin

5 { установка размеров массива }

6 setlength(ways, m + 1, n + 1);

7 { инициализация нулевой строки }

8 for y := 0 to n do

9 ways[0, y] := 1;

10 { вычисление следующих строк }

11 for x := 1 to m do begin

12 ways[x, 0] := 1;

13 for y := 1 to n do

14 ways[x, y] := ways[x - 1, y] +

15 ways[x, y - 1];

16 end;

17 CountWays := ways[m, n];

18 end;

Прежде чем заниматься оптимизацией, обратим внимание на содержимое заполненного массива ways (рис. E2.1). На том же рисунке приведен треугольник Паскаля92, и можно обнаружить его сходство с массивом.

Рис. E2.1. Массив ways и треугольник Паскаля

Сходство это неслучайное, ведь для треугольника Паскаля справедливы те же граничные условия и рекуррентное соотношение, что и для динамической таблицы ways. Необходимо лишь отметить, что индексация элементов треугольника производится иначе, в соответствии с его традиционным графическим представлением: элемент адресуется номером i строки (бывшей диагонали массива) и позицией j в этой строке. Индексация начинается с нуля. Проход по строкам треугольника порождает обход массива в порядке, который мы уже встречали в упр. D10.4. Обозначив элементы треугольника Паскаля через , запишем для них граничные условия и рекуррентное соотношение в “родной” индексации:

Числа называют биномиальными коэффициентами, что связано с формулой бинома Ньютона

В решении упр. A3.1 приведено выражение биномиального коэффициента через факториалы.

Заметим, что на каждой итерации внешнего цикла (строки 10–15 программы) просматривается лишь пара строк таблицы с номерами x – 1 и x. Аналогичная ситуация имеет место и во внутреннем цикле (строки 12–14 программы), где ячейки ways[x, k] при k < y уже не представляют интереса. Именно эти наблюдения позволяют, как и было обещано, сэкономить память и хранить в памяти только одну строку таблицы. Каким образом? Внимательно изучите следующий листинг:

1 function CountWays(const m, n: longint): longint;

2 var ways: array of longint;

3 x, y: longint;

4 begin

5 { установка размера массива }

6 setlength(ways, n + 1);

7 { инициализация нулевой строки }

8 for y := 0 to n do

9 ways[y] := 1;

10 { вычисление следующих строк }

11 for x := 1 to m do

12 for y := 1 to n do

13 ways[y] := ways[y] + ways[y - 1];

14 CountWays := ways[n];

15 end;

Теперь массив ways[0 . . y] содержит соответствующую часть строки ways(x, 0 . . y), в то время как
ways[y + 1 . . n] еще совпадает с частью предыдущей строки ways(x – 1, y + 1 . . n).

Хочется упомянуть еще одно замечательное свойство треугольника Паскаля, которое вновь возвращает нас к числам Фибоначчи. На рис. E2.2 демонстрируется небольшая модификация, приводящая треугольник к “косому” виду. Последовательность сумм в строках теперь в точности совпадает с рядом Фибоначчи93.

Рис. E2.2. Треугольник Паскаля и числа Фибоначчи

Выше мы уже говорили, что динамическое программирование применяется для решения задач оптимизации, однако примеров до сих пор не привели.

Пример E2.2. На прямой задано множество отрезков S (| S | = n). Каждому отрезку si S присвоен вес v(si). Требуется найти максимальное по суммарному весу подмножество попарно непересекающихся отрезков.

Задача вполне реальна. Представим себе ученика или студента, которому на выбор предложен набор факультативных занятий S, идущих в определенное время. Предположим, что каждому из факультативов si можно сопоставить численную величину v(si), характеризующую его полезность (и/или интересность). В таком случае хочется знать, какое подмножество всех факультативов надо выбрать, чтобы получить максимальную пользу от их посещения. При этом очевидно, что нельзя посетить два факультатива, идущих одновременно.

Полный перебор всех подмножеств S требует времени O(2n), поэтому желательно найти другое решение. Для применения динамического программирования необходимо разбить задачу на подзадачи. Определим функцию

где запись sj < si означает, что отрезок sj лежит левее отрезка si и они не накладываются друг на друга. В случае если таких отрезков нет, полагаем Profit(si) = v(si).

Таким образом, Profit(si) — максимальный вес подмножества непересекающихся отрезков, которое содержит Si и, возможно, некоторые отрезки из расположенных левее.

1 type

2 indexN = 0..N-1;

3 TWeightedSegment = record { взвешенный отрезок }

4 a, b: double; { его начало и конец }

5 v: double; { его вес }

6 end;

7

8 var p: array [indexN] of double;

9 f: array [indexN] of longint;

10 seg: array [indexN] of TWeightedSegment;

11

12 function Profit(const i: indexN): double;

13 var j: indexN;

14 k: longint;

15 m: double;

16 begin

17 if p[i] = 0 then begin

18 k := -1;

19 m := 0;

20 for j := 0 to N - 1 do

21 if (seg[j].b <= seg[i].a) and

22 (Profit(j) > m) then begin

23 k := j;

24 m := Profit(j);

25 end;

26 f[i] := k;

27 p[i] := m + seg[i].v;

28 end;

29 Profit := p[i];

30 end;

Если мы определим максимум функции Profit по всем отрезкам, то получим ответ на исходную задачу. В некоторых случаях (как в рассмотренном выше примере с учеником) больший практический интерес представляет не максимальный вес, а дающее его множество отрезков (в нашем примере — факультативных занятий). Для того чтобы восстановить набор отрезков, в программу введен массив f, в котором для каждого отрезка хранится предшествующий ему в оптимальном наборе.

Основная программа выглядит следующим образом:

1 var i: indexN;

2 k: longint;

3 m: double;

4 begin

5 { заполнение массива seg }

6 { ... }

7 { поиск максимума }

8 k := 0;

9 m := p[0];

10 for i := 1 to N - 1 do

11 if m < Profit(i) then begin

12 k := i;

13 m := Profit(i);

14 end;

15 { вывод ответа }

16 writeln('Max profit = ', m);

17 write('Used segments:');

18 repeat

19 write(' ', k);

20 k := f[k];

21 until k = -1;

22 end.

Упражнения

E2.1. Получите формулу (E2.1).

E2.2. Реализуйте решение задачи из примера E2.1 методом динамического программирования сверху вниз. Проследите порядок, в котором рекурсивная функция будет посещать точки плоскости.

E2.3. Усложним формулировку примера E2.1. Присвоим каждой точке плоскости (x, y) вес v[x, y] и поставим вопрос: какую максимальную сумму весов можно набрать, пройдя из начала координат в точку (m, n)? Напишите программу, решающую эту задачу. Как восстановить сам путь, дающий максимальную сумму?

E2.4. Напишите программу, которая строит на экране треугольник Паскаля и выделяет в нем, используя цвет, все “фибоначчиевы” диагонали (см. рис. E2.2 и E2.1).

Список литературы

Что касается меня, то я знаю только то, что ничего не знаю.
А когда хочу узнать, ищу в книгах, потому что книги забывать не умеют.

А.Перес-Реверте94

Научно-технические издания

1. Андреева Е. Системы счисления и компьютерная арифметика: учебное пособие / Е.Андреева, И.Фалина. М.: Лаборатория базовых знаний, 1999. — 247 с. — (Информатика).

2. Ахо А.В. Структуры данных и алгоритмы : [учеб. пособие] / Альфред В. Ахо, Джон Э. Хопкрофт, Джерри Д. Ульман ; [пер. с англ. и ред. к. ф.-м. н. А.А. Минько]. — М. и др. : Вильямс, 2000. — 382 с.

3. Бауэр Ф.Л. Информатика : ввод. курс. В 2 ч. Ч. 1. / Ф.Л. Бауэр, Г.Гооз; перевод с нем. М.К. Валиева и др.; под ред. А.П. Ершова. — 2-е изд., полностью перераб. и расшир. — М. : Мир, 1990. — 324, VIII с.

4. Бентли Д. Жемчужины творчества программистов / Д.Бентли; перевод с англ. М.Г. Логунова; под ред. И.Г. Шестакова. — М.: Радио и связь, 1990. — 224, [1] с.

5. Библиотечные каталоги : [учеб. для библ. фак. ин-тов культуры, пед. ин-тов и ун-тов / Г.Г. Фирсов, Г.И. Чижкова, Э.В. Марченко и др.]; под ред. Г.И. Чижковой. — 2-е изд., перераб. и доп. — М.: Книга, 1977. — 303 с.

6. Ботвинник М.М. Алгоритм игры в шахматы / М.М. Ботвинник. — М.: Наука, 1968. — 96 с.

7. Брудно А.Л. Московские олимпиады по программированию / А.Л. Брудно, Л.И. Каплан ; под ред. Б.Н. Наумова. — 2-е изд., перераб. и доп. — М.: Наука, 1990. — 208 с.

8. Брукс Ф. Мифический человеко-месяц, или Как создаются программные системы / Фредерик Брукс ; [пер. с англ. С.Маккавеева. — 2-е изд., доп. и испр.]. — СПб.: Символ, 2000. — 298 с. — (Профессионально).

9. Варга Б. Язык, музыка, математика / Б.Варга, Ю.Димень, Э.Лопариц; пер. с венг. Ю.А. Данилова. — М.: Мир, 1981. — 248 с.

10. Вирт Н. Алгоритмы и структуры данных / Н.Вирт; пер. с англ. Д.Б. Подшивалова. — М.: Мир, 1989. — 360 с.2

11. ГОСТ 7.1-2003. Библиографическая запись. Библиографическое описание : общие требования и правила составления. — Взамен ГОСТ 7.1-84, ГОСТ 7.16-79, ГОСТ 7.18-79, ГОСТ 7.34-81, ГОСТ 7.40-82 ; введ. 01.07.2004. — М.: Изд-во стандартов, 2004. — III, 47, [1] с. — (Система стандартов по информа­ции, библиотечному и изд. делу). — (Межгос. стандарт).

12. ГОСТ 7.12-93. Библиографическая запись. Сокращение слов на русском языке : общие требования и правила. — Взамен ГОСТ 7.12-77 ; введ. 01.07.1995. — М.: Изд-во стандартов, 1995. — IV, 17 с. — (Система стандартов по информации, библиотечному и изд. делу). — (Межгос. стандарт).

13. ГОСТ 7.59-2003. Индексирование документов: общие требования к систематизации и предметизации. — Взамен ГОСТ 7.59-90 ; введ. 01.01.2004. — Минск: Межгос. совет по стандартизации, метрологии и сертификации ; М.: Изд-во стандартов, 2003. — II, 6 с. — (Система стандартов по информации, библиотечному и изд. делу). — (Межгос. стандарт).

14. ГОСТ 7.79-2000 (ИСО 9-95). Правила транслитерации кирилловского письма латинским алфавитом. — Взамен ГОСТ 16876-71 ; введ. 01.07.2002. — Минск : Межгос. совет по стандартизации, метрологии и сертификации ; М.: Изд-во стандартов, 2002. — IV, 19 с. — (Система стандартов по информации, библиотечному и изд. делу). — (Межгос. стандарт).

15. Гудман С. Введение в разработку и анализ алгоритмов / С.Гудман, С.Хидетниеми ; пер. с англ. Ю.Б. Котова и др. ; под ред. В.В. Мартынюка. — М.: Мир, 1981. — 366 с.

16. Даль В. Толковый словарь живого великорусского языка. [В 4 т.] Т. 1. А–З / Владимир Даль ; [вступ. статья А.М. Бабкина]. — М.: Рус. яз., 1981. — LXXXVIII, 699 с.

17. Даль В. Толковый словарь живого великорусского языка. [В 4 т.] Т. 3. П / Владимир Даль. — М.: Рус. яз., 1982. — 555 с.

18. Десятичная классификация Дьюи и Отно­сительный указатель: [в 4 т.] / пер. с англ. творч. коллектива ГПНТБ России под общ. рук. д. т. н. Я.Л. Шрайберга ; отв. ред. к. филол. н. Е.М. Зайцева. — 21-е изд. — М.: ГПНТБ России, 2000.

19. Джонстон Г. Учитесь программировать / Г.Джонстон; перевод с англ. С.В. Арутюнова и др.; под ред. и с предисл. Г.В. Сенина. — М.: Финансы и статистика, 1989. — 367 с.

20. Жуков В.П. Словарь русских пословиц и поговорок : [ок. 1200 пословиц и поговорок] / В.П. Жуков. — 4-е изд., испр. и доп. — М.: Рус. яз., 1991. — 536 с. — (Малая библиотека словарей русского языка).

21. Зализняк А.А. Грамматический словарь русского языка: словоизменение : ок. 100 000 слов / А.А. Зализняк. — 2-е изд., стереотип. — М.: Рус. яз., 1980. — 879 с.

22. Кулинария / [сост. Л.В. Кирилинская]. — Минск: Аурика, 1994. — 559 с.

23. Кнут Д.Э. Основные алгоритмы = Fundamental algorithms /До­нальд Э. Кнут; [пер. с англ. к. ф.-м. н. С.Г. Тригуб и др.]. — 3-е изд. [испр. и доп.]. — М. и др.: Вильямс,
2000. — 720 с. — (Искусство программирования : [в 3 т.: учеб. пособие] / Дональд Э. Кнут ; под общ. ред. д. ф.-м. н. проф. Ю.В. Козаченко ; т. 1) (Классический труд).

24. Кнут Д.Э. Получисленные алгоритмы = Seminumerical algorithms / Дональд Э. Кнут; [пер. с англ. Л.Ф. Козаченко и др.]. — 3-е изд. [испр. и доп.]. — М. и др. : Вильямс, 2000. — 828 с. — (Искусство программирования : [в 3 т. : учеб. пособие] / Дональд Э.Кнут ; под общ. ред. д. ф.-м. н. проф. Ю.В. Козаченко ; т. 2) (Классический труд).

25. Кнут Д.Э. Сортировка и поиск = Sorting and searching / Дональд Э. Кнут; [пер. с англ.: к. т. н. В.Т. Тертышного, к. т. н. И.В. Красикова]. — 2-е изд. [испр. и доп.]. — М. и др. : Вильямс, 2000. — 822 с. — (Искусство программирования : [в 3 т.: учеб. пособие] /Дональд Э. Кнут; под общ. ред. д. ф.-м. н. проф. Ю.В. Козаченко ; т. 3) (Классический труд).

26. Кормен Т. Алгоритмы: построение и анализ / Т.Кормен, Ч.Лейзерсон, Р.Ривест ; [пер. с англ. под ред. А.Шеня]. — М.: МЦНМО, 1999. — 955 с. — (Классические учебники : Computer science).

27. Лавров П.С. Задачи Ленинградских олимпиад по информатике и вычислительной технике : метод. указания / П.С. Лавров, Ю.В. Матиясевич. — Л. : Изд-во Ленингр. мех. ин-та, 1988. — 92 с.

28. Мартин Д. Организация баз данных в вычислительных системах / Дж. Мартин; пер. с англ. под ред. А.А. Стогния, А.Л. Щёрса. — 2-е изд., доп. — М.: Мир, 1980. — 662 с.

29. Массо С.О. Мясные и грибные блюда / С.Массо, О.Рельве ; перевели с эст. В.Давыдова, Т.Правдина. — 2-е изд. — Таллин : Валгус, 1984. — 368 с.

30. Математическая энциклопедия : в 5 т. / Гл. ред. И.М. Виноградов. — М.: Сов. энцикл., 1977—1985. — (Энциклопедии, словари, справочники).

31. Мидоу Ч. Анализ информационно-поисковых систем: введение для программистов / Чарльз Мидоу ; пер. с англ. Б.Е. Вербицкого и Л.А. Какунина; [предисл. канд. техн. наук Л.А. Какунина]. — М.: Мир, 1970. — 368 с.

32. Новый большой англо-русский словарь = New English–Russian dictionary: [ок. 250 000 слов. В 3 т.]. Т. 1. А — F / [Ю.Д. Апресян и др.]; под общ. руководством Э.М. Медниковой и Ю.Д. Апресяна. — М.: Рус. яз., 1993. — 832 с.

33. Ноден П. Алгебраическая алгоритмика : с упражнениями и решениями: для студентов вузов по спец. “Приклад. математика” и “Приклад. математика и информатика” / Патрис Ноден, Клод Китте ; пер. с фр. В.А. Соколова под ред. Л.С. Казарина. — М.: Мир, 1999. — 719 с.

34. Петцольд Ч. Код : Тайный язык информатики : [пер. с англ.] / Чарльз Петцольд. — М.: Рус. ред., 2001. — 494 с.

35. Пойа Д. Как решать задачу : пособие для учителей / Д.Пойа ; пер. с англ. В.Г. Звонаревой и Д.Н. Белла ; под ред. Ю.М. Гайдука. — 2-е изд. — М.: Учпедгиз, 1961. — 207 с.

36. Правила карточных игр = The United States playing card company, USA : офиц. правила карточ. игр / пер. с англ. Ю.Донца. — Л.: ЭКАМ : Гринтех : Амфион, 1991. — 328 с.

37. Пропп В.Я. Морфология волшебной сказки. Исторические корни волшебной сказки : (Собр. тр.) / В.Я. Пропп ; [коммент. В.М. Мелетинского, А.В. Рафаевой ; сост., науч. ред., текстол. коммент. И.В. Пешкова]. — М.: Лабиринт, 1998. — 512 с.

38. Ранганатан Ш.Р. Классификация двоеточием. Основная классификация : пер. с англ. / Ш.Р. Ранганатан ; под ред. Т.С. Гомолицкой [и др.]. — М.: ГПНТБ СССР, 1970. — 422 с.

39. Реньи А. Трилогия о математике / Альфред Реньи ; пер. с венг. под ред. и с предисл. Б.В. Гнеденко. — М.: Мир, 1980. — 376 с. — (В мире науки и техники ; 75). — Содерж.: Диалоги о математике; Письма о вероятности; Дневник. Записки студента по теории информации; Статьи.

40. Романовский И.В. Стеки и стековые языки : [в 2 ч. : учеб. пособие] / Романовский И.В., Столяр С.Е. — СПб. : ЦПО “Информатизация образования”, 2002. — 35+30 с. — (Рос. интернет-школа информатики и прогр.; гл. J).

41. Седжвик Р. Фундаментальные алгоритмы на C++: [пер. с англ.]. Ч. 1–4. Анализ. Структуры данных. Сортировка. Поиск / Роберт Седжвик. — [3-я ред.] — М. и др.: ДиаСофт, 2001. — 687 с.

42. Семишин В.И. Периодическая система химических элементов Д.И. Менделеева / В.И. Семишин. — М. : Химия, 1972. — 187 с.

43. Смаллиан Р.М. Как же называется эта книга? / Рэймонд М. Смаллиан; перевод с англ. Ю.А. Да­нилова. — М.: Мир, 1981. — 239 с.

44. Сукиасян Э.Р. Классификационные системы в их историческом развитии: проблемы терминологии и типологии / Э.Р. Сукиасян // Науч. и техн. б-ки. — 1998. — № 11. — С. 5–16.

45. Сэломон Д. Сжатие данных, изображений и звука : учеб. пособие для студентов вузов, обучающихся по направлению подгот. “Приклад. математика” / Д.Сэломон ; пер. с англ. В.В. Чепыжова. — М.: Техносфера, 2004. — 365 с. — (Мир программирования. Цифровая обработка сигналов).

46. Флоренский П.А. Имена : [сочинения] / Павел Флоренский; [сост., вступ. ст. и примеч. С.Филоненко]. — М. : ЭКСМО-Пресс ; Харьков : Фолио, 1998. — 911 с. — (Антология мысли).

47. Фоли Д. Энциклопедия знаков и символов: [пер. с англ.] / Джон Фоли. — М.: Вече: ACT, 1997. — 428 с.

48. Хавкина Л.Б. Таблица авторских знаков двоичных : [рус. вариант]: практ. пособие для библиотекарей / Л.Б. Хавкина; под ред. проф. Ю.Н. Столярова. — 25-е изд. — М.: Либерея, 1992. — 24 с.

49. Штейнгауз Г. Задачи и размышления : пер. с польск. / Гуго Штейнгауз ; сост. и пер. Ю.А. Данилов ; под ред. Я.А. Смородинского. — М.: Мир, 1974. — 400 с.

50. Nassi I. Flowchart techniques for structured programming /I.Nassi, B.Shneiderman // ACM SIGPLAN Notices. — 1973, August. — Vol. 6. N2. — P. 12–26.

51. Prusinkiewicz P. The Algorithmic Beauty of Plants/P Prusinkiewicz, A.Lindenmayer. — New York: Springer-Verlag, 1990.

Художественные издания

52. Блох А. Законы Мерфи : юбилейное издание / Артур Блох; перевел с англ. Е.Г. Гендель. — Минск: Попурри, 2004. — 256 с.

53. Вудхауз П.Г. Дживс, вы — гений! : [роман] / Пэлем Грэнвил Вудхауз ; [пер. с англ. Ю.Жуковой]. — М.: ЭКСМО, 2005. — 335 с.

54. Гашек Я. Похождения бравого солдата Швейка: [роман] / Ярослав Гашек; пер. с чеш. [и примеч.] П.Богатырева; [вступит. ст. О.Малевича] ; ил. Й.Лады. — М. : Худож. лит., 1977. — 463 с.

55. Григорьев О.Е. Птица в клетке: стихи и проза / Олег Григорьев; [сост., вступ. ст. М.Д. Яснова; рис. Мика Куусела и др.]. — СПб. : Изд-во Ивана Лимбаха, 1997. — 271 с.

56. Ильф И. Двенадцать стульев : [роман] ; Светлая личность ; Не­обыкновенные истории из жизни города Колоколамска ; 1001 день, или Новая Ша­херезада / Илья Ильф, Евгений Петров. — М.: Худож. лит., 1994. — 526 с. (Собрание сочинений : в 5 т. / Илья Ильф, Евгений Петров ; [вступ. ст. Б.Галанова ; коммент. А.Вулиса, Б.Галанова]; т. 1).

57. Ионеско Э. Между жизнью и сновидением : [пьесы, роман, эссе : пер. с фр.] / Эжен Ионеско ; сост. и предисл. М.Д. Яснова ; худож. Михаил Занько. — СПб.: Симпозиум, 1999. — 455 с. — (Ех Libris). — (Собрание сочинений).

58. Кассиль Л. Собрание соч. В 5 т. Т. 1 / Лев Кассиль. — М.: Дет. лит., 1987. — 670 с.

59. Кэрролл Л. Алиса в Стране чудес. Сквозь зеркало и что там увидела Алиса, или Алиса в Зазеркалье / Льюис Кэрролл ; изд. подгот. Н.М. Демурова; [Рос. акад. наук]. М.: Наука, 1978. — 360 с. — (Литературные памятники / редкол.: … Д.С. Лихачева (пред.) и др.).

60. Кэрролл Л. Охота на Снарка / Льюис Кэрролл; пер. с англ. Григория Кружкова; [ил. Леонида Тишкова]. — Б. м. : Рукитис, 1991. — 87 с.

61. Лагин Л.И. Старик Хоттабыч : повесть ; Патент “АВ” : роман ; Остров разочарования: роман / Л.Лагин. — М.: Сов. писатель, 1956. — 817 с.

62. Ларошфуко Ф. де Мемуары. Максимы / Франсуа де Ларошфуко; изд. подгот. А.С. Бобович и др. ; [Рос. акад. наук]. — М. : Наука, 1993. — 280 с. — (Литературные памятники / редкол.: … Н.И. Конрад (пред.) и др.).

63. Лермонтов М.Ю. Поэмы и повести в стихах, 1837–1841 / М.Ю. Лермонтов. — М.: Современник, 1985. 735 с. — (Собрание сочинений : в 4 т. /
М.Ю. Лермонтов ; вступ. ст. и коммент. И.Л. Андроникова ; т. 2).

64. Маршак С.Я. Надпись на часах: эпиграммат. стихи / С.Я. Маршак ; сост., вступ. ст. и коммент. В.Д. Берестова ; ил. М.С. Тыкоцкой. — М.: Книга, 1987. — 319 с.

65. Ницше Ф. Сочинения. В 2 т. : [пер. с нем.]. Т. 1 / Ф.Ниц-
ше ; [сост., ред., вступ. ст. и примеч. К.А. Свасьяна]. — М. : Мысль, 1990. — 831 с.

66. Перес-Реверте А. Клуб Дюма, или Тень Ришелье: [роман] / Артуро Перес-Реверте ; [пер. с исп. Н.Богомоловой]. — М.: Иностранка, 2003. — 557 с. — (The Best of Иностранка).

67. Русский сонет : сонеты рус. поэтов нач. XX в. и сов. поэтов / [сост., вступ. ст., подгот. текстов и примеч. Б.Романова]. — М.: Сов. Россия, 1987. — 606 с.

68. Свифт Д. Избранное : пер. с англ. / Джонатан Свифт ; сост. и коммент. В.Рака и И.Чекалова; предисл. В.Рака. — Л.: Худож. лит. Ленингр. отд-ние, 1987. — 446 с.

69. Стругацкий А.Н. Понедельник начинается в субботу ; Сказка о Тройке : повести / Аркадий Стругацкий, Борис Стругацкий ; [худож. В.Любаров]. — М. : Текст : Лит.-изд. фирма “РИФ”, 1992. — 319 с. — ([Собрание сочинений]: [в 10 + 3 доп. т.] / Ар­кадий Стругацкий, Борис Стругацкий ; [т. 4]).

70. Успенский Л.В. Слово о словах : [очерки о языке] ; Имя дома твоего : [очерки по топонимике] / Лев Успенский ; вступит. ст. А.Федорова. — Л.: Лениздат, 1974. — 719 с. — (Юношеская библиотека Лениздата).

71. Успенский Э.Н. Дядя Федор, пес и кот : повести-сказки [для дошк. и мл. шк. возраста] / Э.Успенский ; рис. М.Беломлинского. — Мурманск: Кн. изд-во, 1989. — 206 с.

72. Хармс Д. Рассказы и сцены; Драмы ; Письма; Дневниковые записи / Даниил Хармс. — [М.]: Виктори, печ. 1994. — 319, [1] с. — (Даниил Хармс : [в 2 т. / худож. Капранова О.А., Локшин В.В.; т. 2]).

73. Шекспир В. Гамлет, принц Датский; Мера за меру; Отелло; Ко­роль Лир / Уильям Шекспир. — М.: Искусство, 1960. — 687 с. — (Полное собрание сочинений : в 8 т. / Уильям Шекспир ; под общ. ред. А.Смирнова и А.Аникста; [примеч. А.Смирнова ; грав. А.Гончарова]; т. 6).

74. Шекспир В. Гамлет : избр. переводы / Уильям Шекспир ; [сост., предисл. и коммент. А.Н. Горбунова ; худож. М.М. Верхоланцев]. — М.: Радуга, 1985. — 640 с.


7 Даниил Хармс (псевд.; наст. имя Даниил Иванович Ювачёв; 1905–1942); см. [72, с. 130]

8 Напомним, что данная публикация составлена из фрагментов книги, полное содержание которой приведено на с. 1. Таким образом, ряд ссылок на другие разделы по отношению к газетной версии являются “внешними”. — Прим. ред.

9 Пожалуй, следовало бы указать не 107, а 10k, поставив значение k в зависимость от года чтения этого текста.

10 Для набора из n попарно неравных отрезков подсчитать количество всевозможных “троек”, из которых получаются невырожденные треугольники.

11 Независимый выбор пары соседей для первой парты в классе из n учеников можно осуществить n(n – 1) способами.

12 Дик Фосбюри (Richard Douglas (“Dick”) Fosbury; р. 1947); победитель Олимпиады 1968 г. в Мехико по прыжкам в высоту.

13 Говард Джонстон (Howard Johnston); см. [19, с. 276].

14 В общем случае — нет. За подробностями обратитесь к разбору этого упражнения в книге.

15 Никлаус Вирт (Niklaus Wirth; р. 1934); швейцарский ученый в области информатики, разработал несколько языков программирования; см. [10, с. 11].

16 http://rain.ifmo.ru/cat/

17 Льюис Кэрролл (Lewis Carroll, псевд.; наст. имя Чарльз Лютвитдж Доджсон, Charles Lutwidge Dodgson; 1832–1898); английский писатель и математик; см. [59, с. 40].

18 Самуил Яковлевич Маршак (1887–1964); см. [64, с. 172].

19 Большая часть жизни греческого математика Евклида (ок. 325–265 до н.э.), жившего в Александрии, пришлась на период правления Египтом Птолемея I. Указанный алгоритм описан в геометрической форме в “Началах” Евклида.

20 С формальной точки зрения факторизация выполняется за время O(n) (см. упр. А5.2), однако в практической криптографии число n столь велико, что даже линейный по временной сложности алгоритм оказывается неприемлемым. Поэтому речь идет о трудоемкости, полиномиально зависящей от длины двоичной записи числа n, то есть log2n.

21 Фредерик Брукс (Frederick Phillips Brooks, Jr.; р. 1931); американский специалист в области информатики, руководил разработкой операционной системы OS/360; см. [8, с. 98].

22 Илья Ильф (псевд.; наст. имя Илья Арнольдович Файнзильберг; 1897–1937), Евгений Петров (псевд.; наст. имя Евгений Петрович Катаев; 1903–1942); см. [56, с. 284].

23 Меньшего объема работы компьютера. А вот программисту для этого зачастую приходится потрудиться.

24 Опытные программисты конечно же вспомнят еще о побитовом сдвиге: 9 shl 3.

25 Обычное для программ сокращение от temporary (англ.) — временный.

26 Item (англ.) — здесь: элемент данных.

27 GCD — greatest common divisor.

28 Владимир Иванович Даль (1801–1872); писатель, лексикограф, почетный академик Петербургской АН (1863); см. [17, с. 327].

29 Стефен Уоршелл (Stephen Warshall

30 Понятия линейный и полный порядок совпадают только в случае конечных множеств. Линейный порядок, установленный на бесконечном множестве, может не быть полным.

31 Лев Абрамович Кассиль (1905–1970); см. [58, с. 162].

32 Во избежание недоразумений напомним, что мы ведем речь о конечных множествах.

33 Напротив, понятие беспорядок — вполне математическое. О борьбе с беспорядками мы поговорим позже (см. раздел D5 в книге).

34 Павел Александрович Флоренский (1882–1937); религиозный философ, ученый-энциклопедист; см. [46, с. 189].

35 MARC = MAchine-Readable Cataloging.

36 The Library of Congress (http://www.loc.gov/).

37 Обратите внимание: эта функция входит в состав ИПС, а ее реализация не должна нарушить условия функционирования ИПЯ!

38 Библиотечно-библиографическая классификация.

39 Универсальная десятичная классификация.

40 Дальше мы увидим, что термин не вполне верен, но так уж принято в библиотечном деле.

41 Чарльз Кеттер (Charles Ketter; 1837–1903).

42 Любовь Борисовна Хавкина (1871–1949); библиотековед, библиограф.

43 Роберт Шекли (Robert Sheckley; 1928–2005).

44 Перси Шелли (Percy Bysshe Shelley; 1792–1822).

45 Мэри Шелли (Mary Wollstonecraft Shelley; 1797–1851).

46 Формально надо бы вести речь о бесконечном (под)множестве фамилий (и вообще слов) вида Шек*, поскольку к префиксу Шек можно приклеивать сколь угодно длинные суффиксы из символов алфавита. Однако реалии естественного языка явно свидетельствуют о конечности существующего множества всех слов (и, разумеется, фамилий) и, соответственно, любого его подмножества.

47 Или словарным.

48 В современном написании принято “Уильям”, прежде действовала норма “Вильям”.

49 На наших “карточках” приведены библиографические описания с учетом ныне действующего ГОСТа [11]. У самих библиотек редко хватает времени на подобную корректировку ранее размещенных карточек — слишком велик фронт работы.

50 Иногда [9] такой порядок называют обратным алфавитным, что в связи со строками так же сомнительно, как и “алфавитный порядок”.

51 “Гамлет, принц Датский” (акт II, сцена 1; пер. М.Лозинского); см. [74, с. 53].

52 В литературе наравне с термином “операция” используется и “оператор”, но обычно без смещения в рамках отдельного издания.

53 Уильям Джордж Горнер (William George Horner; 1786–1837); английский математик.

54 Владимир Яковлевич Пропп (1895–1970); русский фольклорист, один из основоположников современной теории текста; см. [37, с. 7].

55 Порфирий (ок. 233 – ок. 304); греческий философ-неоплатоник. Проблема универсалий и родо-видового деления обсуждается в его трактате “Введение в “Категории” Аристотеля”.

56 Сократ (470–399 до н.э.); древнегреческий философ.

57 Карл Линней (Carolus Linnaeus, с 1762 г. Carl Linne; 1707–1778); шведский естествоиспытатель, иностранный почетный член Петербургской АН (1754).

58 K.Baugin, 1620.

59 http://bio.fizteh.ru/student/files/biology/biolections/.

60 Дмитрий Иванович Менделеев (1834–1907); химик, член-корреспондент Петербургской АН (1876).

61 Джон Ньюлендс (John A.R. Newlands; 1837–1898); первым предложил термин “порядковый номер” элемента (1875).

62 См. [42, с. 22].

63 Александр Бегуйе де Шанкуртуа (Chancourtois A.E. Beguyer; 1819–1886); французский геохимик, профессор Парижской высшей горной школы.

64 “…согласно английской орфографии его можно написать как houyhnhnm. Произношение этого слова давалось мне не так легко <…>, но после двух или трех попыток дело пошло лучше, и оба коня были, по-видимому, поражены моей смышленостью” [68, с. 147].

65 http://metodolog.ru/00268/00268.html.

66 Пришлось специалистам в области классификаций совместно с компьютерщиками разработать специальные коммуникативные форматы UNIMARC, RUSMARC, MARC21, обеспечивающие адекватное конвертирование данных.

67 Мелвил Дьюи (Melville Louis Kossuth Dewey; 1851–1931); американский библиотековед.

68 Фрэнсис Бэкон (Francis Bacon; 1561–1626); английский философ и политик. Согласно его классификации наук, “главными” являются история, поэзия, философия. Любопытно, что среди литературоведов уже лет триста то утихают, то вновь разгораются дискуссии относительно авторства шекспировских произведений, и среди альтернативных кандидатур фигурирует также сэр Фрэнсис Бэкон.

69 Поль Отле (Paul Otlet; 1868–1944), Анри Лафонтен (Henri La Fontaine; 1854–1943).

70 International Federation for Information and Documentation (FID).

71 Шиали Рамамрита Ранганатан (Shiyali Ramamrita Ranganathan; 1892–1972); индийский ученый.

72 К сожалению, обсуждению этой интересной темы мы не можем уделить здесь достаточно места.

73 См. [20, с. 235].

74 Иногда говорят о пути нулевой длины от узла к самому себе в допущении, что “любой узел одновременно является и предком, и потомком самого себя” [2, с. 78], но в нашем варианте определения — через отношение-таблицу — этому препятствует свойство антирефлексивности.

75 Встречается иное название: полустепень исхода узла, подчеркивающее наличие еще одной его связи — с родителем.

76 Например, в связи с перестроениями сбалансированных деревьев, но их обсуждение здесь не входит в наши планы.

77 http://en.wikipedia.org/wiki/English_monarchs_family_tree.

78 См., напр., [10, с. 246] или [23, с. 357].

79 Нередко близкие по функциональности конструкции объединяют под общим именем диаграмм Венна – Эйлера. Леонард Эйлер (Leonhard Euler; 1707–1783), родом из Швейцарии; математик, механик, физик; в 1727–1741 и 1766–1783 гг. жил и работал в Петербурге. Джон Венн (John Venn; 1834–1923); английский логик.

80 Или “k-арное дерево” от англ. k-ary (arity — количество аргументов отношения).

81 Аристид Линденмайер (Aristid Lindenmayer; 1925–1989); австрийский биолог.

82 См. [8, с. 98].

83 От англ. binary search tree.

84 В разделе Е4 мы познакомимся с другими вариантами обхода двоичного дерева, для BST они не применяются.

85 См. [69, с. 42].

86 Эдуард Успенский (р. 1937); детский писатель; см. [71, с. 21].

87 Ричард Беллман (Richard Bellman; 1920–1984).

88 А иногда, не вдаваясь в подробности, и любой алгоритм, вычисляющий некую величину при помощи динамически заполняемой таблицы. Например, можно назвать динамическим программированием заполнение таблицы умножения по рекуррентной формуле А5.1.

89 Напомним, что мы начинаем последовательность Фибоначчи с f1 = 1 и f 2 = 2. Тем не менее в современной математике часто встречается вариант f0 = 0, f1 = 1.

90 Подобным образом методы проектирования программного обеспечения подразделяются на восходящие и нисходящие.

91 См. [54, с. 37].

92 Блез Паскаль (Blaise Pascal; 1623–1662); французский математик, физик, философ.

93 Обоснование и еще несколько вариаций с паскалевским треугольником см. в [39].

94 См. [66, с. 143].

95 В 2001 г. вышло 2-е издание книги Н.Вирта “Алгоритмы и структуры данных” (СПб.: Невский Диалект, 2001). Авторы ссылаются на с. 11, 105 и 246 указанной в списке литературы книги, которым соответствуют с. 9, 99 и 236 нового издания. — Примеч. ред.

С.. Е.. Столяр

TopList