ББК 22.19 Г 93 УДК 681.142.2 Гудман С., Хидетниеми С. Г 93 Введение в разработку и анализ алгоритмов.—М.: Мир, 1981. 368 с. Монография американских авторов, посвященная общим принципам решения задач на ЭВМ, разработке и анализу алгоритмов. Подробно описываются основные этапы реше- ния задач, даются конкретные примеры, иллюстрирующие теоретические выводы и упражнения (общим числом более 300). По тематике книга пересекается с «Искусст- вом программирования» Д. Кнута (М.: Мир, т. 1—3, 1976—78), но рассчитана на пер- воначальное знакомство с предметом. Для пользователей ЭВМ и студентов, изучающих программирование. 20204—022 041(01)—81 22—81' ч- 1- 2405000000 ББК 22.19 6Ф7.3 Редакция литературы по математическим наукам © 1977 by McGraw-Hill, Inc. All rights reserved © Перевод на русский язык, «Мир», 1981 ОТ РЕДАКТОРА ПЕРЕВОДА Алгоритм представляет собой строгую систему правил, определяю- щую последовательность действий над некоторыми объектами. Следуя такой системе правил как инструкции, различные исполнители будут действовать одинаково и получат одинаковые результаты. В част- ности, алгоритмом является всякая последовательность действий, выполнение которой можно поручить вычислительной машине. Таким образом, подготовка и решение задачи на ЭВМ сводятся к разработке, описанию и выполнению алгоритма. В предлагаемой книге излагается с привлечением многочисленных и представительных примеров комплекс общих методов организации решения задач, относящихся к различным областям знания. Последо- вательно проводится выделение основных этапов решения задачи (постановка, выбор модели, разработка алгоритма, проверка его правильности, реализация алгоритма, анализ алгоритма и его слож- ности, проверка программы и документация). Несомненным достоинством книги является то, что при сравни- тельно небольшом объеме она покрывает обширный фактический материал, причем благодаря продуманной методике и живому, непри- нужденному стилю авторам, как правило, удается наглядно излагать нетривиальные математические результаты. Методически удачным представляется выбранный авторами язык для полуформального описания алгоритмов — в рамки стандартных синтаксических конст- рукций с использованием алголоподобных служебных слов заклю- чаются неформальные фразы на естественном языке. В ряде случаев алгоритмы доведены до программ на Фортране. Книга будет ценным пособием для студентов, работа которых связана с использованием ЭВМ. Для тех студентов, которые специа- лизируются по программированию, она может послужить вводным курсом при подготовке к изучению более обширных монографий, в частности многотомного труда Д. Кнута «Искусство программиро- вания для ЭВМ». В методическом и терминологическом плане данная книга находится в определенной близости с более специальным иссле- дованием А. Ахо, Дж. Хопкрофта и Дж. Ульмана «Построение и ана- От редактора перевода лиз вычислительных алгоритмов», перевод которого опубликован издательством «Мир» в 1979 году. При переводе мы, как правило, сохраняли в алгоритмах англий- ские идентификаторы, чтобы у читателей не возникало затруднений при сопоставлении этих алгоритмов с приводимыми программами на Фортране. Авторское предисловие, гл. 1, 3, разд. 5.1, а также приложения А и Б перевела Л. В. Сухарева. Гл. 2 перевел Л. В. Ухов. Гл. 4, 5 (кроме разд. 5.1) и 6 перевел Ю. Б. Котов. В переводе гл. 7 участвовали все три переводчика. В. В. Мартынюк ПРЕДИСЛОВИЕ Учебные программы по вычислительной математике и програм- мированию обычно содержат следующие типичные курсы (возможно, под несколько иными названиями): 1) введение в программирование, чаще всего на основе Фортрана, Бэйсика или ПЛ/1; 2) программиро- вание на языке ассемблера; 3) структуры данных; 4) дискретные структуры; 5) организация машины; 6) численные методы; 7) обзор языков программирования; 8) обработка финансовой и администра- тивной информации; 9) прикладное программирование и 10) системное программирование. В этой книге мы предлагаем курс разработки и анализа алгоритмов. В начальном курсе программирования особое внимание обычно уделяется таким темам, как работа ЭВМ, подготовка и перфорирова- ние данных, синтаксис языка программирования, кодировка про- граммы, ввод/вывод, элементарные аспекты и применения структур данных, понятия подпрограммы и функции, отладка программы, разработка относительно простых программ, некоторые понятия ма- шинного языка, а также примеры прикладных программ. Существует несколько дополнительных разделов программирования, которые не рассматриваются ни в начальном курсе, ни сколь-нибудь подробно в других студенческих курсах по вычислительной математике и про- граммированию. К числу этих разделов относятся: 1. Полная подготовка, от начала до конца, достаточно сложной задачи для решения на ЭВМ. 2. Такие методы разработки алгоритма, как метод частных целей, наискорейшего подъема, отхода назад и работы в обратном направлении, ветвей и границ, рекурсия и эвристика. 3. Эффективная и правильная реализация перечисленных алго- ритмов. 4. Правильность алгоритма и программы (то, что часто заставляет задумываться, правильно ли выглядит распечатка?). 5. Критерии эффективности и сложности алгоритма, вопросы об- щей эффективности. 6. Проверка программы, включающая тесты на правильность, сложность и общее поведение программы. 7. Более изощренный математический аппарат (включающий, например, теорию вероятностей), требующийся при разработке и анализе достаточно сложных программ. В этой книге рассматриваются все указанные аспекты программиро- вания. Предисловие Хотя курс разработки и анализа алгоритмов, конечно, содержит в значительном объеме программирование, он не был задуман как просто второй (или третий) курс программирования. Поэтому некото- рые разделы, которые можно отнести к разработке и анализу алгорит- мов, здесь не рассматриваются; эти разделы включают вопросы ввода/ вывода, методы отладки, оптимизацию компиляторов и работу с биб- лиотечными программами. Эта книга служит как бы мостом между практическими, ориентированными на программирование курсами и более теоретическими, математически ориентированными курсами по вычислительной математике и программированию. Подобная ориентация курса, а также учебный характер представленных алго- ритмов объясняют их выраженный математический оттенок. Схема на стр. 10 показывает, как можно включить курс разра- ботки и анализа алгоритмов в типичный учебный план по специаль- ности «вычислительная математика». В известной степени мы рассмат- риваем этот курс как замену курса «введение в дискретные струк- туры», который содержится в учебной программе 68 АСМ (Сотт АСМ, март 1868). Хотя рассматриваемый нами материал имеет полноценное математическое содержание, его уровень ниже, он имеет менее тео- ретический, менее формальный характер, чем введение в диекретные структуры, а его приложения к вычислительной математике более очевидны. Математический аппарат, применяемый при разработке и анализе алгоритмов, содержит вводные сведения из теории сетей (графов), комбинаторики, теории вероятностей и статистики. Эти разделы рас- сматривались не сами по себе, а скорее в плане использования для алгоритмических приложений. Для установления правильности не- которых алгоритмов или их свойств на протяжении всей книги при- водятся доказательства, многие из которых опираются на метод мате- матической индукции. Мы не задавались целью научить студентов доказывать теоремы, но надеемся, что они смогут следовать логике доказательств. Мы полагаем также, что предмет, рассматриваемый в этой книге, играет центральную роль в вычислительной математике и программи- ровании. Помимо того что этот материал может послужить основой первого теоретического курса учебной программы, он имеет близкое отношение к курсам по структурам данных, языкам программирова- ния, прикладному программированию и численному анализу. В принципе студент, прошедший односеместровый курс математи- ческого анализа, начальный курс программирования и хорошо вла- деющий понятиями комбинаторики и теории множеств на уровне сред- ней школы, вполне подготовлен для чтения этой книги. Средства ана- лиза используются не часто, но его знание в известной степени свиде- тельствует о математической зрелости. Мы обнаружили, что материал несколько трудноват для большинства студентов второго, курса и, по-видимому, больше соответствует уровню третьего или четвертого курса. Предисловие Так как составление и проверка программы являются важной частью процесса создания алгоритма, мы включили в книгу тексты машинных программ. Хотя некоторые коллеги могут не согласшься с нашим выбором, мы решили дать все__пр_о граммы на Фортране — по той простой причине, что это единственный язык программирова- ния, который известен почти всем. Похоже, что любое другое решение либо накладывает дополнительные требования на подготовку чита- теля, либо делает книгу настолько объемной, что ее основное содер- жание оказывается размытым. Выбранная нами форма представления алгоритмов — это нечто среднее между стилем пошагового описания алгоритма с большим количеством комментариев, который популяризовал Кнут в первых трех томах Искусства программирования, и алголоподобным форма- том, который в настоящее время часто используется в литературе. Такие конструкции, как do-while и if-then-else, регулярно приме- няются в их обычном смысле. Были приложены определенные усилия, чтобы не отступать от принципов структурного программирования. В приложении А собраны правила и условные обозначения, употреб- ляемые в этой книге для изложения алгоритмов. В первой главе в основном содержится качественное описание понятия алгоритма и описание основных шагов процесса полного построения алгоритма. К сожалению, ограниченный объем книги не позволяет описать большинство алгоритмов с такой степенью под- робности. В последующих главах некоторые шаги построения алго- ритмов оставлены в качестве упражнений. Во второй главе излагаются некоторые принципы и средства, полезные для разработки и анализа алгоритмов. В ней также рассмот- рены элементарные понятия структурного программирования, теории сетей (графов), структур данных, теории вероятностей и статистики. Для полноты в конце книги дано приложение, посвященное теории множеств и элементарным методам доказательств. Была сделана попытка во всей главе и приложениях сохранить «алгоритмический оттенок» и везде, где только возможно, для иллюстрации основных понятий вводились новые алгоритмы. По поводу элементарных понятий теории вероятностей и статис- тики, изложенных в гл. 2, следует сделать некоторое пояснение. Многие интересные и важные вопросы разработки и анализа алгорит- мов по своей природе вероятностные; например, имеются веские доводы в пользу того, что наиболее эффективным критерием качества алгоритма является его средняя или ожидаемая производительность. С другой стороны, мы осознаем, что J\iHoriie_ студенты .сталкиваются с трудностями при изучении теории вероятностей и статистики. По этой причине книга составлена так, что преподаватель может почти безболезненно опустить материал, носящий вероятностный характер. В третьей главе рассмотрены некоторые полезные приемы разра- ботки алгоритмов, в каждый раздел главы включены по крайней мере одна новая задача и (или) ал г ори'см.. В гл„ 4 полностью построен Предисловие____________ ____ 11 алгоритм нахождения остовного дерева минимального веса. Этот алгоритм иллюстрирует некоторые простые процедуры проверки программ. В гл. 5 и 6 содержатся примеры и приложения, большинство кото- рых подкрепляет идеи, выдвинутые в первых четырех главах. Пре- подаватели могут выбирать материал из этих глав в зависимости от интересов и математического уровня аудитории, длительности курса и т. д. Гл. 7 построена как справочник. В книгу включены почти 300 упражнений. Они весьма различны по трудности, многие из них носят экспериментальный характер и допускают дальнейшее развитие. Упражнения представляют собой важную часть книги, и мы надеемся, что преподаватели найдут время для обсуждения наиболее интересных и трудных задач на занятиях. Заметим, что, чем больше звездочек (*) стоит перед упражнением, тем выше его трудность. Упражнения с пометкой «L» отличаются значи- тельной трудоемкостью. Некоторые упражнения «озаглавлены», чтобы показать охват определенных тем или понятий. Преподаватели могут образовывать группы из двух-трех студентов для выполнения наибо- лее громоздких и трудных заданий, в особенности тех, которые тре- буют большой работы с программами. Было бы трудно перечислить всех, кого мы хотим поблагодарить, кто вложил в эту книгу силы и время. Многие прочли ее и высказали свои замечания, конструктивную критику и одобрение. Прежде всего мы благодарим Диану Гудман, нашу машинистку и главного «кор- ректора». Дане Ричарде принадлежит более половины разд. 6.1, Брусу Чартресу мы обязаны экологической моделью в разд.3.6.В число тех, кто внес наиболее значительный вклад, входят Линвуд Фергю- сон, Ричард Арментраут и Клей Пендерграст. Мы благодарим Арта Флека, Гарольда Стоуна, Кена Боумана, Вэйн Медисон, а также ано- нимного читателя за их полезные замечания. Издательство «Моутон Паблишере» любезно разрешило нам заимствовать около 12 рисунков и несколько страниц текста в разд. 2.2. Диана Спрессер, Санди Мит- челл и Дженнифер Уорд помогли с упражнениями и корректурой книги. Наконец, но не меньше, чем остальных, мы хотели бы поблаго- дарить слушателей нашего курса по разработке и анализу алгорит- мов, которые на протяжении последних трех лет охотно высту- пали в роли «подопытных кроликов». Никакая книга подобного рода не может быть совершенно свобод- ной от опечаток. Несмотря на усилия многих людей, несомненно, в тексте остались ошибки. Мы будем благодарны, если читатели до- ведут их до нашего сведения. С. Гудман С. Хидетниеми Глава I. Полное построение алгоритма 1.1. Введение Для начала следовало бы рассказать о том, чего мы хотим достичь. В своей теоретической и практической деятельности вы будете иметь дело с задачами, для решения которых потребуются знания в области математики и программирования. Для этого часто нужно будет пост- роить алгоритм. Цель нашей книги — помочь вам научиться 1) поста- вить задачу, 2) построить работающий алгоритм, 3) реализовать алго- ритм как машинную программу и 4) оценить эффективность алгоритма. Такую цель легче сформулировать, чем реализовать. Мир програм- мирования усеян останками программ, которые когда-то считались готовым продуктом, но впоследствии оказались неправильными, неэффективными, непонятными или непригодными по какой-то другой причине. Возможно, простейшее объяснение этого факта заключается в том, что ЭВМ — относительно новый и сложный инструмент, и тре- буется время для того, чтобы научиться хорошо им пользоваться. Не так легко овладеть ЭВМ как мощным инструментом для решения задач, особенно математических. Цель этой главы — сделать первую попытку объяснить понятие полного построения алгоритма, основными этапами которого явля- ются: 1. Постановка задачи. 2. Построение модели. 3. Разработка алгоритма. 4. Проверка правильности алгоритма. 5. Реализация алгоритма. 6. Анализ алгоритма и его сложности. 7. Проверка программы. 8. Составление документации. Остальные главы книги посвящены детальному изучению и иллюст- рации этих фундаментальных этапов. Пока мы ограничимся кратким обсуждением алгоритмов (разд. 1.2) и этапов, ведущих к их полному построению (разд. 1.3). 1.2. Алгоритмы Каждый, кто решал задачи с помощью ЭВМ, имеет некоторое интуитивное представление о значении слова «алгоритм». Кое-кто даже утверждает, что это одно из важнейших понятий вычислительной математики. «Официальное» определение из последнего (1971) издания 14 Гл. 1. Полное построение алгоритма Оксфордского словаря английского языка гласит, что «algorithm» — это ошибочное написание слова «algorism», в свою очередь algorism счи- тается более или менее синонимичным алгебре и арифметике, и это определение датируется девятым веком. Очевидно, современное употребление термина пока еще ограничено кругом людей, связанных с ЭВМ. Попытаемся сначала выразить наши интуитивные соображения. Мы можем нестрого определить алгоритм как однозначно трактуемую процедуру решения задачи. Процедура—это конечная последова- тельность точно определенных шагов или операций, для выполнения каждой из которых требуется конечный объем оперативной памяти и конечное время. Дополнительно потребуем, чтобы алгоритм работал конечное время для любых входных данных. Одно из неудобств этого определения состоит в том, что термин «однозначная трактовка» весьма неоднозначен. «Однозначен» для кого? Или по отношению к чему? Поскольку ничто не является абсолютно ясным или абсолютно неясным, должен быть указан, хотя бы неявно, исполнитель. Алгоритм вычисления производной кубического поли- нома может быть вполне ясен тем, кто знаком с анализом, но для прочих он может оказаться совершенно непонятным. Таким образом, следует также указать вычислительные возможности исполнителя. Существуют и другие трудности с определением. Может слу- читься, что алгоритм заведомо существует для конкретной задачи, но его трудно или невозможно описать в некоторой заданной форме. Человечество разработало эффективный алгоритм завязывания шнур- ков на ботинках. Многие дети с пятилетнего возраста могут зашну- ровывать свои ботинки. Но дать чисто словесное описание такого алгоритма без картинок и демонстрации — очень трудно (попробуйте). Очевидно, что в нашем определении есть некоторые недостатки. Можно избежать большинства этих недостатков, определив «матема- тические машины» с очень точно указанными возможностями. Тогда мы скажем, что алгоритм — это некоторая процедура, которая может выполняться такой машиной. Подобные попытки определения алго- ритма очень глубоки и трудны математически, и они слишком негибки для наших целей. Нам хотелось бы сохранить некоторую гибкость и интуитивную привлекательность первого определения и в то же время, хотя бы частично, устранить некоторые из его неопределенностей. Это легко сделать, описав «типичный» современный компьютер и язык общения с ним и определив затем алгоритм как процедуру, которая может быть реализована на этом компьютере при помощи данного языка. Этот компьютер будет иметь неограниченную память с произволь- ным доступом, в которой могут храниться действительные и целые числа, а также логические константы. В одном слове этой памяти можно хранить произвольное конечное число, и можно извлечь любое слово за фиксированное, постоянное время (это удобное предположе- ние, может быть, немного нереалистично, но на практике это почти 1.2. Алгоритмы 15 так). Такой компьютер может выполнять хранимую программу, кото- рая состоит из допустимой последовательности команд, охватываю- щих все стандартные арифметические операции, операции сравнения, переходы и т. д. Обычно мы будем считать, что каждая такая команда выполняется за единицу времени. Простыми описаниями часть памяти может быть организована в одно-, двух- и трехмерные массивы (мат- рицы). Мы будем пользоваться языком Фортран в качестве модели возможностей нашей машины, когда нужно будет что-то конкретизи- ровать. По сути дела мы утверждаем, что только тогда имеется алгоритм для решения задачи, когда можно написать программу для ЭВМ, решающую эту задачу. Это спорный вопрос. Программы на описанном выше компьютере не могут зашнуровывать ботинки. Среди точно оп- ределенных шагов не содержатся шаги, необходимые для завязывания шнурков. Имеются весомые аргументы в пользу того, что мы на самом деле оперируем ограниченным понятием алгоритма. Человек, как машина, способен выполнять множество тонких операций, которые лежат за рамками возможностей нашего типичного компьютера. Од- нако ограниченное определение — это как раз то, что нам требуется в данной книге. Следующий пример алгоритма иллюстрирует уровень детализации, согласующийся с нашим определением. В приложении А содержится подробное обсуждение правил и условных обозначений, использо- ванных в книге для описания алгоритмов. Рассмотрим простую задачу нахождения максимального числа в списке из N действительных чисел R(l), R(2), . . ., R(N}. Основная идея алгоритма заключается в том, чтобы перебирать по очереди все числа списка и запоминать наибольшее до сих пор встретившееся чис- ло. К тому моменту, когда весь список будет проверен, запомнится наибольшее число. Попробуйте нарисовать блок-схему этого алго- ритма прежде, чем читать дальше. Запись А*-В означает оператор присваивания, т. е. переменной Л присваивается текущее значение В. Algorithm MAX. Даны N действительных чисел в одномерном массиве R(\), R(2), . . ., R(N), найти такие М и J, что M=R(J)= max R(K). 1 <К< N В случае когда два или более элементов R имеют наибольшее значение, запоминается наименьшее значение J. Шаг 0. [Установка в начальное состояние, или инициализация] Set M^R(\); and J^-1. Шаг 1. W==1?] If N=\ then STOP fi ". ! • • " 1) В этом алгоритме fi и od используются соответственно для обозначения кон- ца конструкций if и do. Более детально это будет обсуждаться в разд. 2.1. 16 Гл. I. Полное построение алгоритма Шаг 2. [Проверка каждого числа] For K-<-2 to N do шаг 3 od; and STOP. Шаг 3. [Сравнение] If M<.R (К) then set M^R(K); and J-^-K fi (теперь M — наибольшее число из прове- ренных, а К — его номер в массиве). Алгоритм МАХ не закодирован на каком-то языке, а записан в форме, которую легче воспринять; он выражен в виде шагов, кото- рые, легко реализуются в каждом общепринятом языке программиро- вания. От такого представления нетрудно перейти к кодовой форме. Однако так бывает не всегда. Некоторые алгоритмы слишком сложны, чтобы перейти за один шаг от предварительного словесного описания к кодам машины. Может потребоваться ввести по крайней мере один промежуточный этап разработки. 1.3. Основные этапы полного построения алгоритма Теперь мы кратко рассмотрим основные этапы, перечисленные в конце разд. 1.1. Прежде всего определим назначение каждого этапа и выясним, как эти этапы объединяются в единое целое. Постановка задачи Прежде чем мы сможем понять задачу, мы должны ее точно сфор- мулировать. Это условие само по себе не является достаточным для понимания задачи, но оно абсолютно необходимо. Обычно процесс точной формулировки задачи сводится к поста- новке правильных вопросов. Перечислим некоторые полезные воп- росы для плохо сформулированных задач: Понятна ли терминология, используемая в предварительной фор- мулировке? Что дано? Что нужно найти? Как определить решение? Каких данных не хватает и все ли они нужны? Являются ли какие-то имеющиеся данные бесполезными? Какие сделаны допущения? Возможны и другие вопросы в зависимости от конкретной задачи. Часто после получения полных или частичных ответов на некоторые из вопросов их приходится ставить повторно. Пример. Джек — агент по продаже компьютеров (коммивояжер); на его территории 20 городов, разбросанных по всему Техасу. Компа- ния возмещает ему только 50% стоимости деловых автомобильных поездок. Джек вычислил, сколько ему будет стоить переезд на машине 1.3. Основные этапы полного построения алгоритма 17 между каждыми двумя городами на его территории. Ему, естественно, хотелось бы снизить свои дорожные расходы. Что дано? Исходная информация задана в виде перечня городов на территории Джека и соответствующей матрицы стоимостей, т. е. двумерного массива с элементами сц, равными стоимости переезда из города i в город /'. В данном случае матрица стоимостей имеет 20 строк и 20 столбцов. Что мы хотим найти? Мы хотим помочь Джеку снизить его дорож- ные расходы. Это звучит несколько туманно. Действительно, вопрос о том, каким будет решение, выглядит неуместным. Обдумав ситуа- цию, мы придем к выводу, что ничего не можем сделать без дополни- тельной информации от Джека. Имеет ли Джек в одних городах боль- ше покупателей, чем в других? Если да или если есть какие-то особые покупатели, то Джек, возможно, захочет посещать какие-то города чаще. Могут быть и такие города, в которые Джек специально не поедет, а заедет туда, когда окажется в соседнем городе. Другими словами, нам надо знать больше о приоритетах Джека и учитывать предпочтения при составлении графика поездок. Поэтому мы возвращаемся к Джеку и требуем у него дополнитель- ную информацию. Он сообщает, что хотел бы иметь маршрут, начи- нающийся и оканчивающийся в его базовом городе и проходящий по одному разу через все остальные города на его территории. Следо- вательно, нам требуется список городов, содержащий каждый город только один раз, за исключением базового города, который стоит в списке первым и последним. Порядок городов в этом списке пред- ставляет собой маршрут, по которому Джек должен объезжать города на своей территории. Сумма стоимостей проезда между каждыми двумя последовательными городами списка — это общая стоимость маршрута, представленного списком. Мы решим задачу Джека, если представим ему список с наименьшей возможной общей стоимостью. Это хорошая исходная постановка задачи. Мы знаем, что мы имеем и что хотим найти. Построение модели Задача четко поставлена, теперь нужно сформулировать для нее математическую модель. Это очень важный шаг в процессе реше- ния, и его надо хорошо обдумать. Выбор модели существенно влияет на остальные этапы в процессе решения. Как вы можете догадаться, невозможно предложить набор правил, автоматизирующих стадию моделирования. Большинство задач долж- но рассматриваться индивидуально. Тем не менее существует не- сколько полезных руководящих принципов. Выбор модели — в боль- шей степени дело искусства, чем науки, и, вероятно, эта тенденция сохранится. 'Изучение удачных моделей — это наилучший способ приобрести опыт 'в' моделировании. 18 Гл. 1. Полное построение алгоритма Приступая к разработке модели, следует задать по крайней мере два основных вопроса: 1. Какие математические структуры больше всего подходят для задачи? 2. Существуют ли решенные аналогичные задачи? Второй вопрос, возможно, самый полезный во всей математике. В контексте моделирования он часто дает ответ на первый вопрос. Действительно, большинство решаемых в математике задач, как пра- вило, являются модификациями ранее решенных. Большинство из нас просто не обладает талантом Ньютона, Гаусса или Эйнштейна, и для продвижения вперед нам приходится руководствоваться накоп- ленным опытом. Сначала нужно рассмотреть первый вопрос. Мы должны описать математически, что мы знаем и что хотим найти. На выбор соответст- вующей структуры будут оказывать влияние такие факторы, как: 1) ограниченность наших знаний относительно небольшим количест- вом структур, 2) удобство представления, 3) простота вычислений, 4) полезность различных операций, связанных с рассматриваемой структурой или структурами. Сделав пробный выбор математической структуры, задачу следует переформулировать в терминах соответствующих математических объектов. Это будет одна из возможных моделей, если мы можем ут- вердительно ответить на такие вопросы, как: Вся ли важная информация задачи хорошо описана математиче- скими объектами? Существует ли математическая величина, ассоциируемая с иско- мым результатом? Выявили мы какие-нибудь полезные отношения между объектами модели? Можем мы работать с моделью? Удобно ли с ней работать? Пример. Возвращаемся к задаче агента по продаже компьютеров, рассмотренной ранее в этом разделе. Начинаем с постановки задачи, данной в конце примера. Решали ли мы ранее аналогичные задачи? В математическом смысле, вероятно, нет. Однако все мы сталкивались с задачами вы- бора пути по дорожным картам или в лабиринтах. Можем ли мы прийти к удобному представлению нашей задачи наподобие карты? Очевидно, нужно взять лист бумаги и нанести на нем по одной точке, соответствующей каждому городу. Мы не собираемся изобра- жать точки так, чтобы расстояние между каждой парой точек, соот- ветствующих городам t и /, было пропорционально стоимости проезда сц. Расположим точки любым удобным способом, соединим точки i и / линиями и проставим на них «веса» Сц. 1.3. Основные этапы полного построения алгоритма 19 Схема, которую мы только что изобразили,— это частный случай известного в математике графа, или сети.. В общем случае сеть — это множество точек (на плоскости) вместе с линиями, соединяющими некоторые или все пары точек; над линиями могут быть проставлены веса. Для простоты предположим, что у Джека только пять городов, для которых матрица стоимостей показана на рис. 1.3.1, а. Тогда сете- вая модель может быть изображена, как на рис. 1.3.1, б. Предполо- жим также, что стоимость проезда из города t в город / такая же, как и из / в f, хотя это и необязательно. 2345 1 Город 1 „ 1275 2 1 - 4 4 3 3 2 4-12 4 7 41-3 5 5 323- Рис. 1.3.1. Задача коммивояжера с пятью городами. Что мы ищем в задаче? В терминах теории сетей список городов (который мы ранее описали) определяет замкнутый цикл, начинаю- щийся с базового города и возвращающийся туда же после прохож- дения каждого города по одному разу. Такой цикл соответствует не- отрывному движению карандаша вдоль линий сети, которое проходит ,че]зез каждую точку только один раз и начинается и оканчивается в одной и той же точке. Обход такого рода назовем туром. Стоимость тура определяется как сумма весов всех пройденных ребер. Задача решена, если мы можем найти тур с наименьшей стоимостью. На рис. 1.3.1,6 обход 1—5—3—4—2—1 есть тур со стоимостью 5+2+1 +4+1 ==13. Является ли он туром с минимальной стоимостью? Рассмотренная задача известна в литературе как задача комми- вояжера; она стала в какой-то мере классической. Это один из наибо- лее известных примеров таких задач, которые очень легко поставить и промоделировать, но очень трудно решить. Время от времени мы будем возвращаться к этой задаче в целях иллюстрации. Разработка алгоритма Как только задача четко поставлена и для нее построена модель, мы должны приступить к разработке алгоритма ее решения. Выбор метода разработки, зачастую сильно зависящий от выбора модели, 20 Гл. 1. Полное построение алгоритма может в значительной степени повлиять на эффективность алгоритма решения. Два разных алгоритма могут быть правильными, но очень сильно отличаться по эффективности. В одном из следующих разделов этой главы обсуждаются критерии эффективности. Пример. Вернемся к коммивояжеру из предыдущего раздела. По- становка задачи и модель, описанные ранее, наводят на мысль о сле- дующем алгоритме. Сначала произвольно перенумеруем п городов целыми числами от 1 до п, присваивая каждому городу свой номер. Базовому городу приписываем номер п. Заметим, что каждый тур однозначно соответст- вует перестановке целых чисел, 1, 2,r. . ., п—1. Действительно, каждый тур соответствует единственной перестановке, и каждая перестановка соответствует единственному туру. Такое соответствие называется взаимно-однозначным. Таким образом, для любой данной перестановки мы можем легко проследить соответствующий тур на сетевой модели и в то же время вычислить стоимость этого тура. Можно решить задачу, образуя все перестановки первых п—1 целых положительных чисел. Для каждой перестановки строим соот- ветствующий тур и вычисляем его стоимость. Обрабатывая таким образом все перестановки, запоминаем тур, который к текущему моменту имеет наименьшую стоимость. Если мы находим тур с более низкой стоимостью, то производим дальнейшие сравнения с этим туром. Algorithm ETS (Исчерпывающий коммивояжер). Решить задачу ком- мивояжера с N городами, последовательно рассматривая все переста- новки из N—1 положительных целых чисел. Таким образом мы рас- смотрим каждый возможный тур и выберем вариант TOUR с наимень- шей стоимостью MIN. Алгоритм ETS требует в качестве входных дан- ных число городов N и матрицу стоимостей С. Шаг 0. [Инициализация, т. е. установка в начальное состояние] Set TOUR<-0; and MIN<-oo. Шаг 1. [Образование всех перестановок] For /•<-! to (N—I)! do through шаг 4 od; and STOP. Шаг 2. [Получение новой перестановки] Set Р-—/-Я пере- становка целых чисел 1,2,..., N—1. (Заметим, что здесь нужен подалгоритм.) Шаг 3. [Построение нового тура] Строим тур Т(Р), соот- ветствующий перестановке Р; and вычисляем стои- мость COST (Т (Р)). (Заметим, что здесь' нужны два других под алгоритма.) Шаг 4. [Сравнение] If COST (T(P))<х. (б) Покажите, что /(ге)=2"/100—100 имеет порядок 0(2") при п—г со. (в) Покажите, что я! имеет порядок 0(ге") при я—»-оо. (г) Покажите, что 2" возрастает при п —>- w быстрее, чем любой полином от га конечной степени. 1.3.9. Предположение в задаче коммивояжера (модель и разработка). Рассмотрим мат- рицу стоимостей С задачи коммивояжера с п городами. Если мы выберем п элементов из С таким образом, что в точности один элемент будет выбран из каждой строки и каждого столбца, будут ли отрезки пути, соответствующие этим элементам, образо- вывать тур? 1.3.10. Римские цифры, (полное построение). Постройте алгоритм, преобразовываю- щий произвольное положительное целое число, записанное в арабских цифрах, в систему римских цифр и наоборот. 1.3.11. Стороны треугольника (полное построение). Для произвольной тройки чисел (х, у, г) полностью постройте алгоритм, определяющий, существует ли треугольник Т со сторонами х, у к г. *1.3.12. Перестановки (сравнение алгоритмов). Разработайте и реализуйте два раз- ных алгоритма для генерирования случайных перестановок. Сравните их эффектив- ность. *1.3.13. Факториалы (разработка). Разработайте алгоритм, вычисляющий значение функции F(n)=m, где те—число знаков, содержащихся в десятичной записи п\ 1.3.14. Экспоненциальные функции (сложность). Разработайте алгоритм, который будет определять, сколько времени потребуется вашей ЭВМ для выполнения 2", га" и п\ элементарных операций, для га=1, 2, 3, ... , 50. *1.3.15. Экспоненциальные функции (сложность). Разработайте алгоритм для вы- числения G(m, n)==k, где k определяется следующим образом: nl{~l•^.m\. УМ. а ребра — метками ei, ga, • • ., е^, то 1) Если G — взвешенная сеть, то элемент а,, равен весу ребра между верши- нами i и /'. Гл. 2. Некоторые основные приемы и алгоритмы матрица инцидентности MxN определяется следующим образом: 1(0)=[Ьц], где bi,==\, если у; инцидентна е,; Ь^^О в противном случае. На рис. 2.2.8 приведена матрица инцидентности /(G) сети G с рис. 2.2.7. Заметим, что каждый столбец в / (G) содержит ровно две единицы и что никакие двТ столбца не идентичны. Заметим также, что число а Ь с d e f a G: 2 KG1: 1100010 1010101 0001001 00001 10 0111000 Рис. 2.2.8. Представление в форме матрицы инцидентности. единиц в 1-й строке равно степени di для и; в G. Матрица инцидент- ности полезна для решения различных сетевых задач, касающихся циклов7'С другой стороны, матрица инцидентности требует больше 'памяти (М Х N, т. e. порядка М3 слов) и использует ее менее эффек- тивд^, поскольку (M—2)xN слов заполнены нулями. Векторы смежности. Вместо представления сети матрицами (О, 1) можно воспользоваться матрицей, в которой элементы соответствуют непосредственно меткам Vi, v^, . . ., v^, приписанным вершинам G. В такой матрице i-я строка содержит вектор, компонентами которого являются все вершины, смежные с У]. Порядок элементов в таком век- торе, называемом вектором смежности, обычно определяется поряд- ком, в котором представлены ребра в G (например, порядок ввода в программу). На рис. 2.2.9 мы приводим сеть G, список ребер G в слу- чайном порядке и представление G в форме векторов смежности. Раз- мер матрицы, содержащей векторы смежности, никогда не превышает MxD, где D—максимальная степень вершины из G. Векторы смежности особенно удобно представляют сеть, когда задача может быть решена за небольшое число просмотров каждого ребра в G. Ниже приведена небольшая программа на Фортране, которую можно использовать (с незначительными модификациями в операторе READ) для представления в форме векторов смежности сети с рис. 2.2.9, а, причем порядок ребер указан на рис. 2.2.9, б. 2.2. Сети 55 4 1 3 5 2 4 1 2 5 2 1 5 2 3 4250 4 1 В 3 5200 1200 3210 "' IS в Рис. 2.2.9. Представление в форме векторов смежности. МЫ ПРЕДПОЛАГАЕМ, ЧТО ЭЛЕМЕНТАМ МАССИВОВ NET\V(I, J) И DEGREE (I) ПРИСВОЕНЫ НАЧАЛЬНЫЕ ЗНАЧЕНИЯ О ПРОЧЕСТЬ ЧИСЛО ВЕРШИН М И ЧИСЛО РЕБЕР N READ( )M, N ПРОЧЕСТЬ РЕБРА (U, V) ИЗ G DO IK=1, N READ( ) U, V DEGREE (U) =DEGREE (U)-j-l NETW(U, DEGREE (U))=V DEGREE (V)-DEGREE (V)+1 NETW(V, DEGREE (V))=U CONTINUE Еще одно полезное представление сети, с помощью списков смежно- сти, обсуждается в разд. 2.3. Воспользуемся некоторыми из рассмотренных нами сейчас понятий при разработке алгоритма определения связности сети и идентифика- ции ее компонент, в случае когда сеть не связна. Такой алгоритм может оказаться очень полезной подпрограммой для более сложных процедур. Главная идея алгоритма CONNECT (связывание) очень проста. Интуитивно хотелось бы свести компоненту к одной вершине- Это мо- жет быть сделано в процессе последовательного сведения, когда все смежные с данной вершины «сливаются» с ней. Вершина и сливается 56 Гл. 2. Некоторые основные приемы и алгоритмы с соседней вершиной и при удалении ребра (и, и), и отождествлении v с. и. Одна результирующая вершина, обозначаемая через и, является смежной для каждой вершины, которая была смежной для и и/или v перед слиянием. Эта операция проиллюстрирована на рис. 2.2.10. Рис. 2.2.10. Процесс сведения (о) перед и (б) после слияния осу. Процедура будет состоять из выбора начальной вершины v» и слия- ния с ней соседней вершины. Эта операция повторяется до тех пор, пока у &о не останется смежных вершин. К этому моменту сведенная таким образом сеть будет состоять либо из одной вершины Vy, и в этом случае первоначальная сеть G была связной, либо у нас будет выделе- на одна из компонент G. Во втором случае выбирается новая началь- ная вершина и процедура повторяется. Таким образом можно выде- лить все компоненты. Algorithm CONNECT (СВЯЗЫВАНИЕ) для определения связных компонент произвольной сети G. Переменная С — 'счетчик числа ком- понент. Шаг 0. [Инициализация] Set Н -<- G; and С -<— 0. Шаг 1. [Получение очередной компоненты] While H=/=<& do through шаг 5 od; and STOP. Шаг 2. [Выбор в Н вершины Vo\ Set Vo -<— произвольная вершина из Н. Шаг 3. [Слить вершины с V»] While V» смежна по крайней ..- мере с одной вершиной U в Н do шаг 4 od. Шаг 4. [Слияние] Пусть U — смежная с '/о вершина в Н. Set Н -<- результирующая сеть после слияния U с Vo. (В этом цикле следует вести учет всех вершин, слитых с Vo. Для про- стоты здесь эту операцию учета мы опус- каем.) Шаг 5. [Удаление V«] Set Н -<- H—Vo; and С^-С+1. Блок-схема для алгоритма CONNECT приводится на рис. 2.2.11. Доказательство правильности, реализация и анализ этого алгоритма оставлены в качестве упражнения. 2.2. Сети_______ 57 Деревья Дерево — это неориентированная связная сеть без циклов. Любая сеть без циклов называется лесом, а ее связные компоненты — деревь- ями. На рис. 2.2.12 приводятся все различные деревья с шестью вер- шинами. Весь рисунок можно считать лесом, состоящим из 36 вершин и 6 компонент. i Начало ) Инициализация H<-G, С<-0 Г-^ Выбор V >'\/ смежна -\ Нет \——*<. вершине U .>———| "s.^ H? ^" 1^ |_____ Слияние I U с V Удаление V г.ч-с+1 _____Нет ^-^н=Й^^\, [Да \ Окончание ) Ориентированная сеть является деревом тогда и только тогда, когда она дерево с дугами, рассматривае- мыми как неориентированные реб- ра. Ациклическая ориентирован- ная сеть не обладает ориентиро- ванными циклами. Ориентирован- ная с?ть на рис.2.2.13 ациклична, но не является деревом. Следую- щая ниже теорема дает несколько других описаний деревьев. Теорема 2.2.4. Пусть Т — сеть с М~^2 вершинами. Тогда все сле- дующие утверждения эквивалентны (т. е. если верно одно, то верны и все остальные): (а) Г — дерево. Иначе говоря, Т связно и не имеет циклов. (б) В сети имеется Л1-—1 ребро и нет циклов. (в) В сети Т имеется М—1 ребро и Г связна. (г) Сеть Т связна, и каждое ее ребро — это мост. (д) Любые две вершины в Т со- единяются единственным путем. (е) В сети Т нет циклов, но добав- ление любого нового ребра создает ровно один цикл. Доказательство. Из утвержде- ния (а) следует утверждение (б). Так как Т не содержит циклов, удаление любого ребра разбивает Г на два дерева. Это следует из того факта, что ребро есть мост ^ ^^ Блок-схема для алгоритма тогда и только тогда, когда оно не CONNECT (СВЯЗЫВАНИЕ). содержится ни в одном цикле (тео- рема 2.2.3). Индукцией по М легко показать, что число ребер в каж- 58 Гл. 2. Некоторые основные приемы и алгоритмы дом из этих двух деревьев на 1 меньше числа вершин. Отсюда сле- дует утверждение (б). Из утверждения (б) следует утверждение (в). Если сеть Г несвязна, < Рис. 2.2.12. Все различные деревья с шестью вершинами. то каждая компонента Т связна и не имеет циклов. Поэтому из утвер- ждения (б) число вершин в каждой компоненте превышает число ребер на 1. Далее следует, что общее число вершин в Г по крайней мере на 2 больше, чем общее число ребер, что противоречит предположе- нию (б). Рис. 2.2.13. Ациклическая ориентированная сеть. Из утверждения (в) следует утверждение (г). Сначала докажем следующую лемму. Лемма. Если в сети G имеется М вершин, N ребер и К компонент, то M—K-^N. Доказательство. Проведем индукцию по числу ребер. Для N=l утверждение леммы очевидно. Пусть G содержит наименьшее возмож- ное количество ребер, скажем No. Удаление любого ребра изС должно поэтому увеличивать К. на единицу, оставляя в сети М вершин, /С+1 компоненту и No—1 ребро. Из предположения индукции следует, что No—1>Л1—(/С+1), т. е. Na^sM—К- Это доказывает лемму, так как N>N». 2.2. Сети 59 Из утверждения (в) и доказанной леммы путем сведения к проти- воречию получаем утверждение (г), так как /<=1 и удаление любого ребра оставляет М — 2 ребра и М вершин. Из утверждения (г) следует утверждение (д). Каждая пара вершин соединяется по крайней мере одним путем, так как сеть Т связна. Если каждая пара вершин соединяется двумя или более различными путя- ми, то любые два таких пути образуют цикл; отсюда следует противо- речие, так как никакое ребро в таком цикле не может быть мостом по теореме 2.2.3. Из утверждения (д) следует утверждение (е). Если Т содержит цикл, то любые две вершины в этом цикле должны быть связаны по крайней мере двумя путями. Если к Г добавляется ребро /, то в Т+/ между тупиковыми вершинами / будут существовать два пути [ребро / и единственный путь, задаваемый утверждением (д)1. Это единственный цикл в Г+/, потому что любой другой цикл также должен был бы со- держать ребро /. Отсюда следовало бы существование двух вершин в Т, между которыми имеется по крайней мере два различных пути,— противоречие с утверждением (д). Из утверждения (е) следует утверждение (а). Предположим, что сеть Т несвязна. Если мы добавим к Г ребро, которое соединяет вер- шины в двух компонентах, то цикла создать нельзя; это противоречит утверждению (е). Поэтому Т должна быть связна, и теорема 2.2.4 до- казана. Следствие 2.2.4. Каждое дерево с М^2 вершинами имеет по край- ней мере две тупиковые вершины. Доказательство непосредственно следует из теорем 2.2.1 и 2.2.4. Дерево, у которого одна вершина выделяется среди всех других, называется корневым деревом; выделенная вершина называется кор- нем дерева. Как правило, корневые деревья изображаются так, что корень оказывается наверху, а все остальные вершины — ниже его, на уровнях, соответствующих расстоянию от корня. Иллюстрация при- ведена на рис. 2.2.14, а. Мы будем предполагать, что каждое дерево с корнем имеет по крайней мере три вершины. Максимальный уровень любой вершины в дереве с корнем известен как высота дерева. Среди наиболее широко используемых математических структур употребляется один специальный класс корневых деревьев, известных как двоичные корневые деревья. С ними нам часто придется встречаться в этой книге. Двоичное корневое дерево — это корневое дерево, у ко- торого степень корня равна 2, а степень всех остальных вершин 1 или 3. Одно такое дерево приведено на рис. 2.2.14, б. Теорема 2.2.5. Пусть Т — двоичное корневое дерево, у которого М вершин, высота L и Q тупиковых вершин. Тогда (а) М нечетно; (б) Q=^-1; Корень Уровень О Корень Уровень О Рис. 2.2.14. (а) Корневое дерево высоты 4; (б) двоичное корневое дерево высоты 5. Рис. 2.2.15. Сеть с весами и некоторые из ее остовных деревьев. 1 2.2. Сети 61 В)(г) [log, (М- М< s i 2.;t=0H^L^-1 ^1)- I\^L^ ^ Доказательство теоремы оставлено в качестве упражнения. Остовное дерево для сети G есть остовная подсеть, являющаяся де- ревом. На рис. 2.2.15 приведены взвешенная сеть G и некоторые из ее остовных деревьев с их весами. Сколько у сети остовных деревьев? Легко показать следующее. Теорема 2.2.6. Сеть G связна тогда и только тогда, когда она со- держит остовное дерево. Изоморфизм Этот раздел мы завершим кратким рассмотрением следующей важ- ной задачи. Если у нас есть два представления сети, то, как узнать, не описывают ли они одну и ту же сеть? Очевидно, сначала нужно определить, что подразумевается, когда мы говорим, что «две сети одинаковы». Две сети G и G' изоморфны, если существует взаимно-однозначное соответствие между вершинами G и G', такое, что две вершины и и v смежны в G тогда и только тогда, когда в G' смежны соответствующие им вершины. Точнее, G=(V, E} изоморфна С'=(У, E'} —это записывается в виде G^G',— если су- ществует взаимно-однозначная функция ft из У в V, обладающая тем свойством, что (и, и) (^Е тогда и только тогда, когда (h(u), h (u)) (:?". Проблема определения, являются ли две сети изоморфными, не- ожиданно оказывается трудной. Для произвольных сетей все извест"- ныедлгоритмы, гарантирующие правильный ответ, экспоненциальные. Фактически даже для небольших сетей эту задачу решить нелегко. Все три сети на рис. 2.2.16 изоморфны друг другу. Если вам это кажет- ся очевидным, попытайтесь определить, какие сети изоморфны друг другу (если такие есть) из приведенных на рис. 2.2.17. Итак, проблема изоморфности очень трудна, как можно к ней подступиться? Хотя может и не оказаться возможным разработать ал- горитм изоморфизма, являющийся полиномиальным в худшем случае, попытаемся сделать нечто полезное. Рис. 2.2.16. Три изоморфные сети. 62 Гл. 2. Некоторые основные приемы и алгоритмы Начнем с совершенно очевидного замечания. Из определения сле- дует, что если сети G и G' изоморфны и изоморфизм h найден, то любая вершина v степени d в G должна отображаться на вершину v'==h(v) в G' той же самой степени. Что если мы попытаемся построить на этом наблюдении процедуру исчерпывающих проб и ошибок? Рассмотрим, например, две сети G и G': у каждой 10 вершин и каждая вершина степени 3. Любая из воз- можных взаимно-однозначных функций h из V в V будет удовлетво- рять указанному выше ограничению на степень; имеется 10! таких функций. Поэтому для решения вопроса об изоморфности G и G' нам нужно было бы испытать каждую из 10! возможных функций, чтобы найти одну, удовлетворяющую требованию изоморфизма. Перед лицом этого комбинаторного взрыва исследователи часто отказываются от поиска эффективного алгоритма изоморфизма и вза- мен этого строят простые процедуры, от которых ожидается хорошая работа в большинстве случаев. Предпочитают также алгоритмы изо- морфизма, пригодные для специальных классов сетей, появляющихся в некоторых приложениях. Инвариантом сети G называется параметр, имеющий одно и то же значение для всех сетей, изоморфных G. Среди самых очевидных ин- вариантов отметим следующие: 1. Число вершин. 2. Число ребер. 3. Число компонент. 4. Последовательность степеней, т. е. список степеней всех вершин в убывающем порядке значений. 2.2. Сети 63 В контексте данной книги эвристический алгоритм обладает сле- дующими двумя свойствами: 1. Он находит, как правило, хорошие, хотя и не обязательно опти- мальные, решения. 2. Его легче и быстрее реализовать, чем любой из известных точ- ных алгоритмов (т. е. алгоритмов, гарантирующих оптимальное решение). Более полное рассмотрение таких алгоритмов можно найти в разд. 3.2. Эвристики для решения задач изоморфизма обычно состоят в попытках показать, что две рассматриваемые сети не изоморфны. "Для этого составляется список различных инвариантов в порядке, определяемом сложностью" вычисления инварианта. Затем последовав тельно сравниваются значения параметров сетей. Как только обна- руживаются два различных значения одного и того же параметра, при- ходят к заключению, что данные сети неизоморфны. К сожалению, не известно множества инвариантов, которое позво- лило бы этой процедуре установить за полиномиальное время, что сети изоморфны. Такое множество (неизвестно, будет ли оно когда- нибудь найдено) называется кодом сети. По существу, эвристический алгоритм рассматриваемого типа сводится к сравнению неполных ко- дов двух сетей. Конечно, рассмотрение большего числа инвариантов увеличивает вероятность правильного заключения об изоморфизме при совпадении всех значений параметров, но в общем случае ничего не гарантирует. Например, для двух пятивершинных сетей на рис. 2.2.18 все четыре из перечисленных выше инвариантов совпадают, но эти сети не изоморфны. Рассмотрим теперь пример достаточно сложной эвристики, рабо- тающей с матрицей смежности Л (G). Сама по себе матрица смежности не является инвариантом, хотя если G и Gi изоморфны, то при некото- ром переупорядочивании столбцов и строк Л (G) мы получаем A(Gi). Если у сетей G и Gi M вершин, то поиск нужной последовательности перестановок строк и столбцов требует в худшем случае 0(М\) опера- ций. Впрочем, описываемая ниже полиномиальная процедура справ- Рис. 2.2.18. 64 Гл. 2. Некоторые основные приемы и алгоритмы ляется вроде бы достаточно хорошо с задачей отсеивания неизоморф- ных сетей. Вычисляется A'l{Gi) для f=l, 2. Затем переставляются строки и столбцы A2{Gl) и Л^Сг) так, чтобы элементы на главной диагонали ока- зались в нисходящем порядке. Если Gi и Ga изоморфны и все диаго- нальные элементы различны, то при этой перестановке должны полу- читься идентичные матрицы. Если нет, то данные две сети не могут 12345 1'2345 '12345 12345 1 01101 1 01011 1 31120 1 30300 2 10100 2 101-00 2 12111 2 02022 3 11010 3 01011 3 11302 3 30300 4 00101 4 10100 4 21020 4 02022 5 10010 5 1 0 1 0 0 5 01202 5 02022 A(G,) AfG;) A^G,) A'tG,) 12345 12345 12345 12345 1 31120 1 33000 1 15 1 18 2 13102 2 33000 2 8 2 12 3 11211 3 00222 3 15 3 18 4 20120 4 00222 4 9 4 12 5 02102 5 00222 5 9 5 12 Переуторяяяенная A (G, Переулорядоченная A'tG;) Рис. 2.2.19. быть изоморфными. Если матрицы идентичны, можно продолжить про- верку с A'^Gi}, Л^С;), . . . , Л^С,) для f==l, 2. Значение k определяет- ся имеющимся бюджетом машинных ресурсов. Если все из проверен- ных матриц совпадают, то весьма правдоподобно, но не обязательно истинно, что Gi и Сг изоморфны.В дальнейшем эту процедуру мы бу- дем называть методом СПС (сравнение порядков смежности). . Окончательная формулировка алгоритма, использующего метод СПС, и некоторые другие вопросы, касающиеся этого метода, остав- ляются читателю в качестве упражнения. В упр. 2.2.25 содержится важная теоретическая интерпретация элементов возведенной в степень матрицы смежности. На рис. 2.2.19 работа метода СПС проиллюстрирована на примере двух сетей с рис. 2.2.18. Факт неизоморфности Gi и Ga становится яс- ным достаточно рано на основании следующего: 1) переупорядоченные матрицы Л^С,) не совпадают по элементам вне главной диагонали и 2) не равны диагональные элементы AЗ(Gi). Как для A^Gi), так и для Л^Сг) переупорядочение выполнено заменой строк и столбцов 2 и 3. Обратите внимание на перемещение элементов, стоящих на пересечении пар строк — столбцов. 2.2. Сети 65 Упражнения 2.2 2.2.1. Изобразите все неизоморфные сети с пятью вершинами. Их 34. 2.2.2. Изобразите все неизоморфные деревья с восемью вершинами. Их 23. 2.2.3. Докажите теорему 2.2.1 методом математической индукции. 2.2.4. Докажите следствие 2.2.1. 2.2.5. Алгоритм СВЯЗЫВАНИЕ (правильность). Проверьте правильность алгорит- ма СВЯЗЫВАНИЕ. *L2.2.6. Алгоритм СВЯЗЫВАНИЕ (реализация, проверка). Реализуйте и проверьте алгоритм СВЯЗЫВАНИЕ. Один интересный способ реализовать операцию слияния использует матрицу смежности и операцию двоичного ИЛИ (см. приложение Б). Для слияния вершины Vj с вершиной и, просто добавьте строку R(j), соответствую- щую У], к строке, соответствующей v„ используя форму двоичного сложения ИЛИ. Затем добавьте столбец C(j) к столбцу C(i) и занесите нуль в диагональный элемент строки R(i). После удаления R(j) и С(/') результирующая матрица будет представ- лять сеть после слияния. 2.2.7. Алгоритм СВЯЗЫВАНИЕ (анализ). Используя реализацию из упр. 2.2.6, произведите анализ сложности алгоритма СВЯЗЫВАНИЕ. 2.2.8. Алгоритм ПРОВЕРКА ДЕРЕВА (разработка). Воспользуйтесь алгоритмом СВЯЗЫВАНИЕ при разработке алгоритма ПРОВЕРКА ДЕРЕВА, определяющего, является ли данная сеть деревом. 2.2.9. Разделяющие вершины и мосты (доказательство). Докажите следующие две теоремы (критерии). Теорема. Вершина v связной сети G является разделяющей вершиной тогда и только тогда, когда существуют две вершины fi и Уц, где о, Oi и Ug — различные вершины, такие что v принадлежит каждому пути из v^ в Оз- Теорема 2.2.2. Ребро е связной сети G является мостом тогда и только тогда, ког- да существуют две вершины v^ и v^, такие, что е принадлежит каждому пути из fi в УЗ. L2.2.10. Представление преобразования (разработка, реализация). Разработайте и реализуйте алгоритм, который преобразует матрицу смежности в матрицу инцидент- ности и наоборот. *2.2.11. Двудольные сети (доказательство). Сеть G==(V, E) называется двудольной, если V можно разбить на два непересекающихся подмножества V^ и V^, такие, что каждое ребро в Е соединяет вершину в V^ с вершиной в V^. Докажите, что сеть дву- дольная тогда и только тогда, когда каждый цикл содержит четное число ребер. 2.2.12. Полные двудольные сети. Двудольная сеть (см. определение в упр. 2.2.11) называется полной, если для любых y^V\ и v^V-s, (и, v)^:V. Пусть Кт,п обозна- чает единственную полную двудольную сеть, где ll^i|=m и 11^1=="-'Выведите формулу для числа ребер в Km п- 2.2.13. Изобразите две неизоморфные сети с шестью вершинами, имеющие одинако- вые последовательности степеней. *2.2.14. Как можно было бы использовать представление в форме характеристиче- ского вектора, введенное для множеств (см. приложение Б), чтобы сэкономить па- мять при представлении сетей? Какими недостатками обладают ваши предложения? 2.2.15. Полные сети. Сеть с М вершинами называется полной и обозначается через Км, если каждые две вершины смежные. Такие сети использовались при моделирова- нии задачи о коммивояжере. Покажите двумя различными способами, что число ребер в ^М задается формулой ,-2. М(М——\} С~м =;• 16 2668 66 Гл. 2. Некоторые основные приемы и алгоритмы 2.2.16. Перерисуйте Къ я Кз.з (см. упр. 2.2.12 и 2.2.15) так, чтобы в каждой сети имелось только одно пересечение ребер, т. е. только одно пересечение в точке, не являющейся вершиной сети. *L2.2.17. Алгоритм РАЗДВЕР (полная разработка). Полностью постройте алго- ритм, который находит все разделяющие вершины в данной сети. **2.2.18. Реализуемая последовательность степеней (доказательство). Невозрастаю- щая последовательность положительных чисел называется реализуемой, если суще- ствует сеть, для которой эта последовательность является последовательностью степе- ней. Докажите, что последовательность^, а^ . . . , d^ (где d^d^s. . .>d/n>0) реализуема тогда и только тогда, когда последовательность а^—1, dy—1, . . . , drfi+i, drfi+21 • • • , ri/ц реализуема. **2.2.19. Алгоритм РЕАЛИЗУЕМОСТЬ (разработка). Разработайте алгоритм, основывающийся на теореме из упр. 2.2.18, который определяет, является ли конеч- ная последовательность положительных целых чисел реализуемой. *2.2.20. Какие из сетей на рис. 2.2.17 изоморфны? **L2.2.21. Метод СПС (разработка, реализация). Разработайте и реализуйте под- программу для метода СПС. Что вы сделаете, когда два или более из диагональных элементов будут иметь одинаковые значения? **L2.2.22. Эвристика изоморфизма (разработка, реализация, проверка). Разрабо- тайте, реализуйте и проверьте эвристический алгоритм для обнаружения изоморфиз- ма. Ограничьтесь сетями не более чем с 12 вершинами. *2.2.23. Инварианты. Попытайтесь составить список из 10 или больше сетевых инвариантов. *2.2.24. Докажите теорему 2.2.5. **2.2.25. Докажите следующую теорему. Если А ~ матрица смежности невзвешен- ной сети G и V(G)= {v^, v^, ... , v^}, то (t, /)-й элемент матрицы Л", где »>!,— это число различных маршрутов из у; в v, длины п в G (считайте, что у каждого ребра длина равна единице). 2.2.26. Докажите теорему 2.2.6. 2.3. Некоторые структуры данных В гл. 1 мы высказали утверждение о том, что выбор структур дан- ных может существенно повлиять на скорость и эффективность реали- зованного алгоритма. В этом разделе мы введем несколько структур данных (связанные списки, стеки и очереди) и процедуры для работы с ними, которые часто оказываются полезными. Рассмотрим преимущества и недостатки использования массивов. Среди преимуществ отметим следующие: 1. Массивы помогают объединять множества данных в осмыслен- ные группы. 2. Имена массивов с индексами минимизируют потребность в сле- жении за многими элементами данных с различными именами. 3. Использование индексов обеспечивает непосредственный и ав- томатический доступ к любому элементу в массиве. 4. Индексация позволяет также производить с помощью циклов DO и FOR автоматическую, быструю и эффективную обработку всех данных или выделенных подмножеств данных, хранимых 2.3. Некоторые структуры данных 67 в массивах. В эту обработку входит инициализация, поиск, хранение и модификация. Недостатки массивов не так очевидны. Лучше всего массивы го- дятся для данных, значения которых не изменяются, порядок которых (важен он или не важен) также не изменяется. Если порядок элемен- тов в массиве подвергается изменению, то каждый раз, когда порядок меняется, перестановка элементов требует очень много времени. CS100 CS100 12 3 4 5 6 7 Ь8 9 10 ADAMS BUCHANAN GRANT HARR1SON JACKSON KENNEDY LINCOLN ROOSEVELT. TRUMAN WASHINGTON ADAMS BUCHANAN HARR1SON JACKSON JEFFERSON KENNEDY LINCOLN TRUMAN WASHINGTON a 6 Рис. 2.3.1. Переорганизация линейного списка. Рассмотрим, например, ЛУ-элементный массив CS100 (N), в котором содержатся лексикографически упорядоченные имена студентов, слу- шающих в данный момент курс программирования CS100 (рис. 2.3.1, а). Если студенты ГРАНТ и РУЗВЕЛЬТ перестают посещать курс, а но- вый студент ДЖЕФФЕРСОН добавляется, то нам бы хотелось полу- чить новый список слушателей, приведенный на рис. 2.3.1, б. Поду- майте о трудности и стоимости написания и выполнения программы, которая смогла бы перестроить массив CS100 в соответствии с этими изменениями. С другой стороны, связанный.список представляет собой структуру данных, которая требует дополнительной памяти, но позволяет легко вносить такие изменения. Связанные списки На рис. 2.3.2, а массив CS100 преобразован из одномерного в дву- мерный массив CS100L. В столбце 1 массива CS100L по-прежнему со- держатся фамилии студентов, зачисленных на курс CS100, хотя, как з* 68 Гл. 2. Некоторые основные приемы и алгоритмы явствует из рис. 2.3.2, б, теперь уже не требуется, чтобы эти фамилии были упорядочены по алфавиту. В столбце 2 массива CS100L содер- жатся неотрицательные целые числа, называемые связями или указате- лями, значениями которых являются номера строк массива, содержа- щих фамилию следующего студента (в алфавитном порядке) в текущем CS1001 OL12ьз4 Б67»S S 1011 ИНФО СВЯЗЬ 1 2 ADAMS 2 BUCHANAN 3 GRANT 4 HARR1SON 5 JACKSON 6 KENNEDY 7 LINCOLN 8 ROOSEVELT 9 TRUMAN 10 WASHINGTON 0 0112 3 4 Б 6 7 8 Э 1011 ИНФО СВЯЗЬ 1 2 ADAMS 2 BUCHANAN 4 ^'^^ш. ^ . HARRISOM 5 JACKSON 11 KENNEDY 7 LINCOLN 9 %ROOSEVELT^% •т TRUMAN 10 WASHINGTON 0 JEFFERSON 6 в <5 Рис. 2.3.2. Переорганизация связанного списка. списке. Звездочкой (*) мы отметили те указатели, значения которых из- менились в связи с удалением фамилий GRANT и ROOSEVELT и до- бавлением JEFFERSON. Заметим, что на рис. 2.3.2, б: ADAMS указывает на BUCHANAN [CS100L (1, 2)=2 и CS100L (2, 1)=BUCHANAN]. BUCHANAN указывает на HARR1SON [CS100L (2, 2)=4 и CS100L (4, 1)=HARRISON]. JACKSON указывает на JEFFERSON. JEFFERSON указывает на KENNEDY и т. д. Массив CS100L (/, J) размера NX2 работает как линейный свя- занный список. Лцнеицый связанный список — это конечный набор пад, каждая из Которых состоит из информационной части INFO (ИН- ФО) и указующей части LINK (СВЯЗЬ). Каждая jrapa называется ячейкой. Если мы хотим расположить ячейки в порядкесц, Сц, . . . . . . , с,», то СВЯЗЬ (ij)=i,+i для /=!,... , ге—1, а СВЯЗЬ (t„)=0 и указывает на конец списка. На рис. 2.3.3, а приведена стандартная диаграмма линейного свя- занного списка; на рис. 2.3.3, б приведена диаграмма связанного спи- ска с рис. 2.3.2, б. Заметим, что GRANT и ROOSEVELT отсутствуют в списке на рис. 2.3.3, б, хотя они присутствуют на рис. 2.3.2, б как 2.3, Некоторые структуры данных 69 заштрихованные элементы. При реализации связанных списков участ- вует переменная FIRST (ПЕРВЫЙ) или HEAD (ГОЛОВА), значение которой есть адрес первой ячейки списка (рис. 2.3.3, а). Как было указано выше, одно из главных преимуществ связанных списков заключается в том, что можно легко удалять и добавлять эле- менты списка. Далее мы приводим два алгоритма, которые можно использовать при выполнении модификаций, требуемых для преобра- зования рис. 2.3.2, а в 2.3.2, б. ПЕРВЫЙ ИНФО СВЯЗЬ ИНФО СВЯЗЬ ИНФО СВЯЗЬ ИНФО СВЯЗЬ ИНФО СВЯЗЬ С, GZ Сз CN-I CM ADAMS 2 - BUCHANAN 4 - HARR1SON 5- Ряй 1 РяЭ 2 РЯВ4 ^ JACKSON 11 - JEFFERSON 6 - KENNEDY 7- ЯяЭ 5 РяЭ 11 РяЭ 6 L LINCOLN 9 - TRUMAN Ю- WASHINGTON 0 Ря07 РяВЭ—i \ ~ Вы6о.Г\ \^ека^ —— следующей ^г ячейки _____"___ Y t УЗалать \ Увалить f/anewmamii спереди \ изнутри, что не S списке ——^—1L I——————W5<-————— (0/{о//увш\ Рис. 2.3.5. Блок-схема алгоритма DELETE (УДАЛЕНИЕ). Шаг 3. [Предшествует ли новая ячейка выбранной?] It VALUE^INFO(PTR) then [вносится спереди?! if PREV=0 then [внести новую ячейку спе- реди! set FIRSTS-ROW; LINK(ROW) <- PTR; and STOP else [внести новую ячейку внутрь] set LINK (PREV) ^-' ^- ROW; LINK (ROW) ^- 72 Гл. 2. Некоторые основные приемы и алгоритмы ^- PTR; and STOP fi else [Выбрать очередную ячейку] set PREV <-PTR; PTR ^ LINK(PTR) fi. Шаг 4. [Список пуст?] If PREV=0 then [внести новую ячейку как единственную ячейку в списке] set FIRSTS-ROW; LINK(ROW) s- 0; and STOP else [внести новую ячейку в конец списка] set LINK(PREV)<-ROW; LINK(ROW) -<- 0; and STOP fi. Списки смежности В одном из эффективных способов представления сети G-==(V, E) используются связанные списки смежности. Это представление сильно напоминает векторы смежности (см. разд. 2.2), но, как правило, тре- SUSROUTINE DELETE IFlRSTiINFO.LlNK.VALUE:) INTE6ER INFOi500)»l.INK(500>ifIRSTiVALU?«PREViPlR ВЫБОР ПЕРВОЙ ЯЧЕЙКИ С с ^•s с С 10 асов 39 S3 t с с 60 с PTR я FIRST FREV = О ПРОВЕРКА, НЕ ПУСТА /1И ЯЧЕЙКА IF ( PTR ] ДВА - ——> ЧЕТЫРЕ OJ t ^-^ ————— PREV PTR ТРИ а один ДбА ЧЕТЫРЕ о ^PREV t PTR ТРИ ЧЕТЫРЕ 0 Аt ' А Т PREV I DTO • ПК 1—-—-, L-^ ТРИ • Рис. 2.3,7. Внесение ячейки в связанный список. бует меньше памяти. На рис. 2.3.10, в приведено представление сети G с рис. 2.3.10, а в форме связанного списка. Это представление зависит как от разметки вершин Ui, Уз, • • ., УЛ!, так и от порядка, в котором задаются ребра G (случайное упорядочение ребер приведено на рис. 2.3.10, б). Чтобы определить, какие вершины являются смежными для данной вершины при представлении в форме связанного списка, мы должны следовать указателям в столбце с названием NEXT. Например, для того чтобы найти вершины, смежные с вершиной 3, мы определяем, что ^^Х^З)^^. Проверяя двенадцатую строку, мы видим, что ADJ (12)=4, т. е. вершина 3 смежна вершине 4. Мы также видим, что NEXT(12)=7. Так как ADJ(7)==1, вершина 3 смежна с вершиной 1. 74 Гл. 2. Некоторые основные приемы и алгоритмы ^HcwMO) Выбрать~ первую ячейку .^•Ячейка\. Да <, пуста >>———————-———-—————— \Нвл1 .^mffiy\. л„ ^г теика , •-:" , ^^лреишестт^- ^^^ \Hein ВыЛр 1— сле^ш/еи ячейки Да ^W&ihmiS^^m Ла ^Опшж^^Нет •=—< спереди .>—i |—<„ м/ет .>—i ЛЩцрь | [ AolfaSurni, \ Добс&т ДоЛНигт, mSi/ю WeSKU новую ячейку ячеику ячейку спереЗа внутрь как еЗинетоеит/ю в кони.е списка ^^—"•—г-^ (Окончание) Рис. 2.3.8. Блок-схема алгоритма INSERT (ВНЕСЕНИЕ). И наконец, так как NEXT(7)=0, вершина 3 не смежна ни с какой дру- гой вершиной. Это представление требует 2(M-}-2N) слов памяти, где М — число вершин и Л" — число ребер в G, Заметим, что 2М этих слов ADJ(l), i . . , ADJ (М} и М слов, для которых NEXT (;')=(), имеют значение, р'авное 0. Впрочем, первые М слов массива ADJ могут быть использо- ваны для хранения полезной информации о вершинах Ui, 02, . . . , Ущ. Например, в них можно запоминать значения степеней di для о,. 2.3. Некоторые структуры данных 7 SUBROUTINE INSERT tFIRST,INPO.LINK«ROW«V6LUEl INTEGER INFO(500)«LINK(500 If FIRST'ROW,VALUE,PREV»PTR С С ВЫБОР ПЕРВОЙ ЯЧЕЙКИ. С Р"ТР = FIRST PREV = О С С ПРОВЕРКА, ПУСТА ЛИ ЯЧЕЙКА. 5 IF ( PTR .NE. О » GOTO ЦО С С ТОГДА (ПУСТ ЛИ СПИСОК) с 10 IF I PREV «NE. 0 ) GOTO 30 С С ТОГДА (ВКЛЮЧЕНИЕ ЯЧЕЙКИ КАК ЕДИНСТВЕННОЙ В СПИСКЕ) С 20 FIRST = ROW LINK(ROW) s 0 flETURN С С ИНАЧЕ (ДОБАВЛЕНИЕ ЯЧЕЙКИ В KOHU,E СПИСКА) С 30 LINK(PREV) = ROW LINK(ROW) = О RETURN С „ ^ С ПРОВЕРИТЬ, ПРЕДШЕСТВУЕТ ЛИ НОВАЯ ЯЧЕЙКА ВЫБРАННОЙ. С 40 IF ( VALUE .GT. INFO(PTR) ) GOTO 60 С С ТОГДА (ВНОСИТСЯ ЛИ ОНА СПЕРЕДИ) С 50 IF ( PREV .NE. 0 ) GOTO 70 С ТОГДА (ДОБАВИТЬ ЯЧЕЙКУ СПЕРЕДИ) С 60 FIRST = ROW HNK(ROW) s PTR RETURN С С ИНАЧЕ (ДОБАВИТЬ ЯЧЕЙКУ ВНУТРЬ) С 70 LINK(PREV) s ROW LINKIROW) = PTR, RETURN С С ВЫБОР НОВОЙ ЯЧЕЙКИ С 60 PREV = PTR PTR = LINK1PTR) GOTO 5 С END Рис. 2.3.9. Реализация алгоритма INSERT (ВНЕСЕНИЕ), 76 Гл. 2. Некоторые основные приемы и алгоритмы 13 41 25 34 2) 45 42<У ADJ NEXT 1 23 4 S 6 7 8 Э 10 11 12 •13 14 15 16 17 18 19 20 21 15 19 12 18 17 3 0 1 0 1 0 4 6 5 0. 2 0 4 7 3 8 1 10 2 9 5 13 4 11 2 16 4 14 Рис. 2.3.10. Представление сети в форме связанного списка, На рис. 2.3.11 приведен фрагмент программы на Фортране, с по- мощью которого можно получить списки смежности на рис. 2.3.10, б по ребрам, заданным в порядке, указанном на рис. 2.3.10, б. Стековые списки и стеки Мы увидели, что (линейные) _связ^шные списки — это эффективная структура данных для моделирования ситуаций, в которых подверга- ются изменениям 'упорядоченные массивы элементов данных. В част- ности, это справедливо для случая, когда модификациями являются главным образом внесение элементов в'середину массивов или удале- ние элементов из середины массива. Когда модификации касаются лишь начала и конца, необходимость в связанных списках исчезает, и становятся достаточными простые линейные (одномерные) массивы. В качестве примера рассмотрим следующую задачу. Во всех ком- пиляторах с языков программирования требуется узнавать, является 77 2.3. Некоторые структуры данных ли произвольное выражение правильно построенным. В частности, нужно определять, правильно ли расставлены в выражении скобки. Например, последовательность ()(()()) представляет правильную последовательность скобок, а ()((()()) неправильную (есть лишние левые скобки). В более широком матема- тическом контексте в арифметическом выражении обычно встречаются также квадратные скобки [ ] и фигурные скобки { },. 00 1 I s 1.100 ADJ(I) в О NEXT(I) s 0 1 CONTINUE С С ВВОД ЧИСЛА ВЕРШИН Р С REAOIS.IOOOIP 1000 FOR4AT(2I3) С I s P+1 • , ВВОД РЕБЕР (M,N) ДЛЯО 100 READ(5flOOO)M»N , ЕСЛИ М ОТРИЦАТЕЛЬНО, С БОЛЬШЕ РЕБЕР НЕТ IF ( Н .LT. О ) GOTO 200 С *OJ(I» a N NEXTCI» s NEXT(H». NEXTtH) s I I s I+l AOJ(I) s M MEXTtI» = NEXT(N» NEXT(N) s I I s X+1 С С ВВОД НОВОГО РЕБРА С GOTO 100 С С ПРОДОЛЖЕНИЕ ПРОГРАММЫ 200 • • Рис. 2.3.11. Фрагмент программы для представления сети в форме связанного списка. Предположим, что вас попросили разработать алгоритм определе- ния того, что произвольная последовательность круглых, квадратных и фигурных скобок является правильно построенной. Что мы понима- ем под правильно построенной последовательностью? Обычное опреде- ление состоит в следующем: 78 Гл. 2. Некоторые основные приемы и алгоритмы 1. Последовательности ( ), [ ] и { } являются правильно построенными. 2. Если последовательность х правильно построенная, то правиль- но построены и последовательности (х}, [х] и {х}. 3. Если последовательности х и у правильно построенные, то тако- ва же и последовательность ху. 4. Правильно построенными являются лишь те последовательно- сти, правильность которых следует из конечной последова- тельности применений правил 1, 2 и 3. Это определение определяет правильно построенные последова- тельности конструктивно. Например, следующие последовательности являются правильно построенными: Элемент Последовательность Образована с помощью правил а ( ) 1 б [( )] 2 и а в {[( )]} 2 и б г {[( )]}{ } 1, 3 и в д ({[( )]}{ }) 2 и г е 1 ]({[( )]}{ }) 1, з и а ж {[ ]({[( Ш{ })} 2 и е Обычно, чтобы установить, являются ли выражения такого типа правильно построенными, используют стековую память (или просто стек), которая представляет собой бесконечную в одну сторону после- довательность слов памяти, как изображено на рис. 2.3.12. •Вершина Для запоминания элемента данных в стеке элемент заносят в верхнее слово ТОР (ВЕРШИНА), сдвигая тем самым вниз (по одному слову) все другие слова, хранящие- ся в стеке (совершенно аналогично тому, как в столовой складывают подносы в стоп- ку). Выбор элементов данных из стека воз- можен лишь считыванием по одному за раз из слова ТОР, причем все остальные эле- менты данных сдвигаются вверх. Рис. 2.3.12. Диаграмма сте- ковой памяти. Мы не имеем права выбирать элементы данных внутри стека. (В столовой мы обыч- но не выбираем двадцатый поднос из стоп- ки подносов.) Иногда термин «стек» обоз- начает стековую память, когда нам разре- шено считывать элементы, находящиеся ниже слова ТОР, но не раз- решается изменять их значения или добавлять новые элементы ниже слова ТОР. 2.3. Некоторые структуры данных 79 Покажем на примере, как стековая память помогает нам легко определить, является ли такая последовательность, как g=={[ ] ({U )Ш })}> правильно построенной. Элементы g будем обозначать Xi, Хз, . . . , Хп, где Xi есть одна из скобок {, }, (, ), [ или ]. Элементы {, ( и [ назовем ЛЕВЫМИ символами; скажем, что Xi — левый партнер х,, если Xi==[ и х,=], или х;=( и Х]==), или х,-={ и х,=}. Algorithm WELLFORMED (ПРАВИЛЬНО ПОСТРОЕННАЯ). Оп- ределяет, является ли произвольная последовательность символов XiXi. . .XN, где каждый Xi — одна из скобок {, }, (, ), [, или ], правильно построенной. Шаг 0. [Инициализация] Set ТОР-«-0; /-<-!. Шаг 1. [Читается последовательность слева направо] While /<Л/ do through шаг 3 od. Шаг 2. [Записывается в стек ЛЕВЫЙ символ] If Xi ЛЕВЫЙ символ then [записывается л:;] else [выбирается символ из стека] if TOP левый партнер Xi then выбрать элемент ТОР из памяти else НАПЕЧАТАТЬ «НЕПРАВИЛЬНО ПО- СТРОЕННАЯ»; and STOP fi fi. Шаг 3. [Прочесть следующий символ] Set /-<- /+1. Шаг 4. [Память пуста?] If TOP=0 then PRINT «ПРАВИЛЬНО ПОСТРОЕННАЯ»; else PRINT «НЕПРАВИЛЬНО ПОСТРОЕННАЯ» fi; and STOP. Применим теперь алгоритм ПРАВИЛЬНО ПОСТРОЕННАЯ к по- следовательности ({[()]}{ } ) } 456 7 8 9 10 11 12 13 14 На рис. 2.3.13 приведено содержимое стека, соответствующее операци- ям чтения элементов из g слева направо. Целое значение над /-и конфи- гурацией стека указывает на то, что в данный момент читается х,-й символ. Для реализации стека на Фортране мы возьмем одномерный массив STORE [описанный как STORE (М}] и целую переменную с именем ТОР. Всегда, когда нам нужно поместить на вершину стека элемент •X (/), мы выполняем следующие простые команды: ТОР=ТОР+1 IF (TOP. ОТ. М) GO TO 100 STORE (TOP) =X(I) GO TO 200 100 PRINT «ПЕРЕПОЛНЕНИЕ СТЕКА» 80 Гл. 2. Некоторые основные приемы и алгоритмы 200 CONTINUE ( "о" —— 2 { о — 3 С { о \ { о — S ( { о в { ( { о Г 1: { < { о 1 ( с { ( { о 9 г 1 t { о А { t { о {Л1 ( { о 12 { ( { о — 13 ( { о — л { о w_ о Рис. 2.3.13. Конфигурации стековой памяти при работе алгоритма WELL-FORMED (ПРАВИЛЬНО ПОСТРОЕННАЯ). Далее для выбора элемента выполняются следующие команды: IF (TOP. EQ. 0) GO TO 300 X(I)=STORE(TOP) TOP = TOP—1 GO TO 400 300 PRINT «СТЕК ПУСТ» 400 CONTINUE Очереди В стековой памяти для внесения и удаления элементов можно поль- зоваться только сливом ТОР. В очереди_.элементы добавляются с_од- ного_кон11а1^_выби1)аются с другого. Эти элементы обычно~называются началом (FRONT) и концом (REAR) очереди. Термин «очередь» вы- 2.3. Некоторые структуры данных 81 бран потому, что эти структуры данных часто используются для моде- лирования обслуживающих линий, например люди в очереди к парик- махеру, автомобили у светофора, очередь заданий операционной сис- темы. F-OJ R=0 '234 Б 0 FR 1А FR 2А В 3 FR 4В F БВ F R 6В fR 7 С R F 8GСD R F eG H F A R В С С R С С СD D D D D E E L/' E Рис. 2.3.14. Реализация очереди с использованием линейного массива. Для моделирования очереди, как правило, используют линейный массив [например, QUEUE (500)] и две целые ^теременные FRONT и REAR, которые указывают на первые й"Тюслёдние элементы очереди соответственно. Вначале REAR^FRONT, но когда к очереди добавит- ся свыше 500 элементов, то, по-видимому, некоторые записи будут уда- лены из начала очереди. Если это так, то, чтобы не допустить пере- полнения массива, мы присваиваем REAR=1 и продолжаем заполнять очередь с начала массива. Впрочем, REAR никогда не должен перего- нять FRONT. На рис. 2.3.14 показано то, что называется ситуацией одна оче- редь — одно обслуживание. В этом примере емкость очереди 5, конкрет- ные клиенты помечены метками от Л до H, первый ожидающий в оче- реди клиент обслуживается за три единицы времени, после чего он покидает очередь. В момент Г=0 очередь пуста, и значения FRONT (F) и REAR (F) равны нулю. В момент Т=1 прибывает Л, ждет 3 единицы времени и покидает очередь в момент Т==4. Клиенты В, С, D, E, G и Я прибывают в моменты времени 2, 3, 4, 7, 8 и 9 соответственно. С ждет 4 единицы, прежде чем продвинуться в начало очереди, и покидаётее в момент Т=10. Когда прибывает G, в момент Т=8, конец очереди находится в массиве в положении 5. Здесь мы помещаем G в положение 1 очереди и присваиваем R=l. Когда в момент Т=9 прибывает H, в R засылается 2, в этот момент очередь полностью заполнена. Теперь конец очереди сравнялся с ее началом, и, пока С не покинет очередь, в нее становиться нельзя. Подпрограмма QADD (рис. 2.3.15) добавляет элемент VALUE к очереди. Предполагается, что, когда очередь пуста, FRONT == REAR== =0. Процесс удаления элемента из очереди аналогичен. Подпрограм- ма QDELET (рис. 2.3.16) выполняет эту работу; при удалении из оче- 82 ________ Гл. 2. Некоторые основные приемы и алгоритмы реди последнего элемента программа присваивает величинам FRONT и REAR значения, равные 0. В разд. 3.6 очереди будут рассмотрены с точки зрения моделирования. SUBROUTINE QAOD (QUEUE.N.FRONTiREARiVAt.UE» INTEGER QUEUE! Nil FRONT iREAR.VAl.UE С С ПРОВЕРКА, ПУСТА ЛИ ОЧЕРЕДЬ. IF t REAR .N?. 0 » GOTO 20 С С ТОГДА (ДОБАВИТЬ ПЕРВЫЙ ЭЛЕМЕНТ) , 10 FRONT s 1 REAR s 1 QUEUEtl} S VALU? RETURN С ПРОВЕРКА, REAR=N? С 20 IF С REAR ,NE> N 1 GOTO 40 С С ТОГДА (УСТАНОВИТЬ ЗНАЧЕНИЕ REAR=0) 30 REAR = О С С ПЕРЕДВИНУТЬ REAR. С 40 REAR s REAR+1 С С ПРОВЕРКА, НЕ ПЕРЕПОЛНИЛАСЬ ЛИ ОЧЕРЕДЬ. IF { REAR •NE. FRONT ) еоТО 60 С ТОГДА, С SO WRITE(6ilOOO» 1000 FORMAT114H QUEUE IS FULL) REAR = REAR-1 IF ( REAR .Ев» 0 ) REAR s N RETURN С С ИНАЧЕ (ДОБАВИТЬ К REAR) 60 OUEUE(REAR) s VALUE RETURN END1 ' Рис. 2.3.15. Подпрограмма, добавляющая к очереди один элемент. (Текст в операторе 1000: «Очередь полна».) Деревья Линейные массивы можно также использовать для компактного представления деревьев определенного вида. Пусть Т — дерево с М вершинами, в котором вершины помечены целыми числами 1, 2, ... , М. Говорят, что дерево Т рекурсивно помечено (или рекурсивное), если каждая вершина с меткой больше 1 смежна ровно с одной вершиной, у которой метка имеет меньшее значение. На рис. 2.3.17 приведены примеры рекурсивного дерева Ti и нерекурсивного дерева Га. QQ 2.3. Некоторые структуры данных___________________——————2? SUBROUTINE QDELET tQUEUE.N.FRONTfREARiVALUE» INTEGER QUEUE(N>»PRONTiREARiVALUE С С ПРОВЕРКА, ПУСТА ЛИ ОЧЕРЕДЬ, IF ( REAR .NE. О » GOTO 20 С С ТОГДА С 10 URITE(6»1000» 1000 FORHftTdSH QUEUE' IS ЕИРТУ» RETURN ^ ПРОВЕРКА: ОСТАЛСЯ ТОЛЬКО ОДИН ЭЛЕМЕНТ? 20 IF { FRONT .NE. REAR » GOTO 40 С ТОГДА (УСТАНОВИТЬ ПУСТУЮ ОЧЕРЕДЬ) 30 VALUE = QUEUEtFRONT» REAR = О RETURN ^ УДАЛИТЬ ИЗ ОЧЕРЕДИ ЭЛЕМЕНТ И ПЕРЕДВИНУТЬ' с T"RONT 40 VALUE = CUEUEIFRONT» FRONT e FRONT+l ^ ЕСЛИ FRONTON, ТО УСТАНОВИТЬ FRONTS 1. IP ( FRONT .GT. N » FRONT = I RETURN С END Рис 2.3.16. Подпрограмма, удаляющая из очереди один элемент. (Текст в операторе 1000: «Очередь пуста»). ^ Рис. 2.3.17. Рекурсивное дерево Tf и нерекурсивное дерево Га. 84 Гл. 2. Некоторые основные приемы и алгоритмы. На примере линейного массива ДЕРЕВО показано, как компакт- но можно представить рекурсивное дерево 7\; ДЕРЕВО (1)=1 обоз- 'начаёт, что вершйна'~/*смежна'вер'шине J. 123456789 10 011124545l| TREE Упражнения 2.3 2.3.1. Какие структуры данных вы использовали бы для каждого из следующих множеств данных: (а) план посадочных мест; (б) таблица среднего роста как функции веса, пола и возраста; (в) множество всех подмножеств М элементов; (г) колода карт; (д) множество А людей и отношение Х знаком с У; (е) играв шашки; (ж) л,=3,14159... ; (з) организационная иерархия; (и) множество значений одной случайной переменной? Заметьте, что вам может понадобиться хранить кое-какую дополнительную информа- цию (например, потенциальное применение данных, желаемая точность я), поэтому не торопитесь с ответом для некоторых множеств данных. 2.3.2. Большие целые. Напишите программу для работы с очень большими целыми числами, т. е. целыми числами, для которых недостаточен размер машинного слова. Более конкретно, вы могли бы попытаться вычислить большое число из ряда Фибо- наччи или значение факториала. L2.3.3. Железнодорожная станция. Разработайте и реализуйте на вычислительной машине функционирование небольшой сортировочной железнодорожной станции. По- езда будут прибывать в соответствии с некоторым расписанием. Вагоны прибываю- щих поездов должны быть перераспределены и сформированы в отбывающие поезда, уходящие в различные пункты назначения в соответствии с другим расписанием. Мо- гут прибывать также пустые вагоны, принадлежащие другим железным дорогам. По- следние нужно комплектовать и периодически возвращать владельцам. 2.3.4. Рассмотрите некоторые преимущества и недостатки использования связанных линейных списков в сравнении с последовательными линейными списками. Обратите особое внимание на вопросы объема памяти, добавления, удаления и доступа к эле- ментам списка. 2.3.5. Напишите две подпрограммы, которые будут (а) удалять и (б) добавлять эле- мент в хорошо упорядоченный массив CSIOO(N). Сравните их скорость и эффектив- ность с подпрограммами DELETE и INSERT для связанных списков. 2.3.6. Напишите подпрограммы, которые будут (а) добавлять элемент в начало связанного списка, (б) добавлять элемент в конец связанного списка и (в) распечаты- вать содержимое всех ячеек связанного списка. 2.3.7. Перестановки (стеки). Пусть целые 1, 2, 3, 4 прибывают в естественном по- рядке на вход стека. Рассмотрев все возможные последовательности операций зане- сения в стек и выборки из стека, определите, какие из 24 возможных перестановок можно получить на выходе. Например, перестановку 2314 можно получить, применив такую последовательность действий: занести 1, занести 2, выбрать 2, занести 3, вы- брать 3, выбрать 1, занести 4, выбрать 4. 2.3.8. Перестановки (деки). Дек (очередь с двумя входами) — это линейный список, для которого все операции внесения, удаления и доступа можно производить с любо- го конца списка. Измените упр. 2.3.7 для дека. 2.3.9. Моделирование (очереди). Напишите программу, моделирующую линию ожи- дания емкостью в 10 человек, если для обслуживания клиента и удаления его из оче- реди требуются 2 единицы времени. Вероятность появления одного нового клиента в 2.4. Понятия теории вероятностей и статистики 85 течение 1 единицы времени равна р, где 0<р<1. В течение единицы времени никогда не появляются два и более клиентов. Последите за переполнением очереди как за функцией от р. 2.3.10. Замкнутые связанные списки. На рис. 2.3.18 приведен пример замкнутого свя- занного списка. Можете ли вы придумать какое-либо применение для этой структуры данных. Попытайтесь реализовать одну из ваших идей. 2.3.11. Работа со связанными списками. Разработайте алгоритмы, выполняющие для списков с одной связью следующее: (а) Преобразование связанного списка в замкнутый связанный список (см. упр. 2.3.10). (б) Объединение двух списков, в каждом из которых ячейки INFO упорядочены лексикографически. (в) Преобразование связанного списка в последовательный список (обычный одномерный массив). 2.3.12. Упакованное десятичное представление. Разберитесь, что имеется в виду, ког- да говорят «упакованное десятичное представление целых чисел» (см, [77], стр. 37), Каковы преимущества и недостатки этого представления? *L2.3.13. Шах. Напишите программу, которая будет считывать шахматную позицию и определять, не находится ли один из королей под шахом. Можно затем попытаться определить, не является ли шах матом. . 2.3.14. Переполнение стека. Нужно попытаться разместить два стека в одном фикси- рованном блоке памяти, организованном как интервал последовательных адресов. Как следовало бы расположить стеки, чтобы минимизировать трудности, возникаю- щие в связи с переполнением, **L2.3.15. Кроссворды. Напишите программу составления кроссвордов. Предполо" жим, что исходными данными является конфигурация 6х6 (некоторое расположение пустых и заполненных квадратов) и список слов, состоящих из шести или менее букв. Результатом должно быть расположение этих слов, образующее общепринятый кросс- ворд, или сообщение о том, что такая конфигурация невозможна. *2.3.16. Рекурсивные деревья. Разработайте алгоритм построения единственного пути в рекурсивном дереве Т между произвольно заданными вершинами и и у, используя компактное линейное представление на рис. 2.3.17. Указание: Можно построить ал- горитм, просматривающий это представление справа налево один раз. 2.4. Элементарные 'понятия теории вероятностей и статистики Очень много важных задач содержат в той или иной степени не- определенность. Представляющие интерес величины заранее непред- сказуемы, а имеют случайный характер, который должен быть отра- жен в любой корректной модели. Модели такого типа называются ве- роятностными. В данном разделе мы будем рассматривать некоторые понятия из теории вероятностей и статистики. Ниже кратко описаны некоторые применения этого аппарата к разработке и анализу алгоритмов. 1. Анализ средней трудоемкости алгоритма. Предположим, что у нас есть алгоритм (алгоритм S), оптимизирующий (в некотором смысле) порядок выполнения заданий на вычислительной машине. К числу важнейших факторов, определяющих время работы алгорит- ма, относятся общее число (N) и типы заданий, ожидающих выполне- 86 Гл. 2. Некоторые основные приемы и. алгоритмы ния. Если все задания простого типа, то алгоритм 5 может построить расписание за время 0(N). Но если все задания очень сложные, то алгоритм S требует 0(N*) времени. Предположим, что между этими \ L 1—' ин—^ т Рис. 2.3.18. крайними случаями имеется 12 различных типов заданий и что паке- ты, как правило, содержат смесь из заданий различных типов. На- сколько хорош наш алгоритм? Чтобы ответить на этот вопрос, нам нужно знать, каково среднее, представительное множество заданий. Затем мы должны решить, насколько хорошо работает алгоритм в среднем. Отсюда следует необходимость точно определить, что такое «среднее». Возможно, что худший случай О(Л^) для операционной системы неприемлем; например, может оказаться, что вся система бу- дет бездействовать в ожидании, пока подпрограмма не составит рас- писание. Есля худший случай встречается редко и средняя трудоем- кость алгоритма равна О (^V372), то можно использовать алгоритм S в операционной системе. С другой стороны, если .средний режим 0(N*), мы, по-видимому, будем вынуждены применить какой-то другой быст- рый, грубый, эвристический алгоритм, не гарантирующий оптималь- ного расписания. На этом примере отчетливо виден ряд важнйх мо- ментов, связанных с анализом алгоритмов. 2. Моделирование. Одним из самых важных применений вычисли- тельной машины является ее использование в качестве средства про- ведения управляемых экспериментов на сложных реальных системах за короткое время и при относительно низких затратах. Для этого строят алгоритм, моделирующий реальную систему. Во многих отно- шениях это крайнее средство. К моделированию прибегают, как пра- вило, когда задачи безнадежно превышают наши аналитические воз- можности и сочетают в себе трудоемкость и неопределенность. В сущ- ности, все серьезные модели вероятностны. 3. Вычислительная статистика. Вычислительную машину часто используют для обработки и анализа статистической информации. Необходимо разрабатывать и анализировать алгоритмы, выполняющие статистические вычисления аккуратно и эффективно. 4. Алгоритмы принятия решений. Вычислительная машина ста- новится все более популярной в мире коммерции и государственного управления как помощник при решении важных вопросов. Все задачи 2.4. Понятия теории вероятностей и статистики 87 в этой области существенно включают процесс принятия решений в условиях неопределенности. Рассмотрим, например, следующую задачу. В текущий момент Правительство поддерживает ряд административных и обслуживаю- щих агентств. В условиях катастрофического уменьшения бюджета некоторое число агентств необходимо упразднить или сильно ограни- чить их в средствах. Имеется огромный объем данных, относящихся к прошлой, настоящей и будущей деятельности этих агентств. Как принять решение? Один из самых обещающих количественных мето- дов разрешения таких проблем известен как теория статистических решений Байеса. К сожалению, в этой теории совершенно отсутствуют хорошие вычислительные алгоритмы. В настоящее время ее полез- ность ограничивается относительно простыми задачами. 5. Генерация случайных чисел. Почти во всех предыдущих прило- жениях теории вероятностей и статистики требуется средство внесения в данные неопределенности. Хотелось бы, если возможно, делать это с помощью механизма, внутреннего по отношению к самой вычисли- тельной машине, избегая дорогостоящей и потребляющей много вре- мени внешней активности. Разработка и анализ хороших алгоритмов генерации случайных данных — это серьезная самостоятельная про- блема. , Мультипроцессорные системы Начнем с простой задачи. Имеется мультипроцессорная система с п-ятью идентичными процессорами. На этой системе нужно пропус- тить большую сложную программу. Программа требует трех из пяти процессоров и не может быть загружена, если число свободных процес- соров меньше трех. Какова вероятность того, что мы сможем загру- зить программу в тот момент, когда мы готовы работать с ней? Каждая вероятностная модель формулируется в терминах экспери- мента. Эксперимент — это любое точно определенное действие. В на- шем примере эксперимент состоит в том, чтобы определить, сколько в системе свободных процессоров. С каждым экспериментом мы можем связать множество исходов. Пометим наши пять процессоров целыми числами от 1 до 5. Один возможный исход эксперимента может быть тогда обозначен вектором с 5 компонентами (1,0, 1,0, 0), что означает состояние системы, когда процессоры 1 и 3 заняты, а процессоры 2, 4 и 5 свободны. Если система находится в этом состоянии, то про- грамма будет принята. Множество всех возможных исходов называет- ся пространством элементарных событий эксперимента. Используя 5-компонснтное представление, можно увидеть, что в нашем мульти- процессорном эксперименте имеется 2° элементов пространства эле- ментарных событий. Ниже все они явно перечислены: Гл. 2. Некоторые основные приемы а алгоритма 88 ^,=(0,0,0,0,0) •г,2=(0,1,0.1,0) s^ (1.0,1,1,0) •?2=(1,0,0.0,0) s,3= (0,1,0,0,1) •?24= (1,1. 0,0,1) .Гз=(0,1,0,0,0) я,4= (0,0,1,1.0) •?25=(1.1.0,1,0) ^=(0,0.1,0,0) Д15=(0,0,1,0,1) ;?2в=(1.1.1,0,0) s, "(0,0,0,1.0) .г,в=(0,0,0,1,1) S27= (0.1,1,1,1) Д.=(0,0,0,0.1) Я1т=(0,0.1,1,1) s^ (1,0.1,1.1) ^=(1.1,0,0,0) 5l8=(0,t,0,1,1) ^=(1.1.0,1,1) Д.= (1.0,1,0,0) Sw= (0.1,1,0,1) .?»= (1.1,1.0,1) ffa=(1,0,0.1.0) ffa)=(0,1,1,1.0) ^=(1,1.1.1,0) Sw<= (1,0,0,0,1) ^=(1.0,0,1,1) ^=(1.1.1.1.1) .?„= (0.1,1.0,0) ^=(1.0,1.0,1) Пусть S={si, Sa, Sy, . . .}—пространство элементарных событий эксперимента. Предположим на время, что S содержит конечное или бесконечное счетное число элементов. Событие — это любое подмно- жество пространства элементарных событий. Обычно событие словесно выражается в терминах эксперимента, а затем переводится на язык подмножества S. Рассмотрим, например, следующее событие: заняты по крайней мере четыре процессора. В терминах S это событие состоит из всех исходов, которые представляют состояния системы, когда ис- пользуются четыре или пять процессоров, т. е. ?={(0, 1, 1, 1, 1), (1, 0, 1, 1, 1), (1, 1, 0, 1, 1), (1, 1, 1, 0, 1), (1, 1, 1, 1,0), (1, 1, 1, 1, 1)}= ^l^T» S2Й^ S2S^ S30^ Ssi, 832}. Единичный акт эксперимента называется испытанием. Пусть Е — событие, определенное в пространстве S. Если исход испытания эксперимента принадлежит Е, то мы говорим, что событие Е произо- шло. При каждом испытании может иметь место только один исход s в S. Однако тем самым произойдет каждое событие, включающее s. События могут быть сформированы из других событий с помощью стандартных операций над множествами: объединения, пересечения и дополнения. Если EI = событие, состоящее в том, что заняты по крайней мере четыре процессора, и Еу, = событие, состоящее в том, что заняты самое большее четыре процессора, то ?3 = Ei П ?'2= событие, состоящее в том, что заняты в точности четыре процессора = == {(0, 1, 1, 1, 1), (1, 0, 1, 1, 1), (1, 1, 0, 1, 1), (1, 1, 1, 0, 1), (1, 1, 1, 1. 0)}= == 1^27' ^2Я' ^29> ^30i Sgi}. При чтении П читается как и, U как или и дополнение как не. Если Ei и ?3 — любые два непересекающихся события (т. е. ?i П Г\Е^=0), то они называются несовместными. Если Ei и ?z— несов- 2.4. Понятия теории вероятностей и статистики УУ местные события, то невозможно, чтобы при одном и том же испытании произошли оба события. В рассматриваемом примере, если ?i = процессор 1 занят и ?2 = процессор 1 свободен, то Ei П ?2=0. Проверьте это, явно перечислив все элементы ?i и Еу,- Теперь мы готовы начать обсуждение вероятности. Сначала попы- таемся сформулировать стандартное интуитивное понятие вероятности с помощью нашего нового словаря. Нас интересует вероятность того, что данное событие случится в результате эксперимента <§. Экспери- мент S повторяется N раз, причем N — большое число. Каждое испы- тание дает исход из S. Этот исход либо в ?, и в этом случае событие ? произошло, либо нет. Предположим, что событие ? произошло п раз в N испытаниях. В этом случае мы склонны определить вероятность события Е как ^(?)=^. Данное число можно интерпретировать как относительную частоту появления события ? при выполнении эксперимента <§\ в этом сущ- ность частотной интерпретации вероятности. Очень важно понять, что частотная интерпретация не является су- щественной частью теории вероятностей, хотя она и очень популярна и полезна на, практике. Теория вероятностей построена на формаль- ной аксиоматической базе, которую не следует отбрасывать как бес- полезную абстракцию чистой математики. Аксиоматическая теория определяет все правила, используемые при подсчете вероятности. Как мы увидим, эта теория обладает фундаментальными слабостями, и частотная интерпретация дает один из возможных способов справиться с этими слабостями. Пусть S — пространство элементарных событий эксперимента S- Пусть Р — связанная с S мера вероятности, которая ставит в соответ- ствие некоторым событиям ?sS действительное число P(?), называе- мое вероятностью события Е. Эти вероятности должны удовлетворять трем основным правилам (называемым аксиомами): I P(?)>0 для любого ?sS; II P(S)=1; III ^(?iU?2)=P(?i)+P(?,), если ?i и ?a несовместны, т. е. если ?in?a=0. Как только этим «некоторым» событиям приписываются вероятности, согласующиеся с перечисленными тремя аксиомами, становится воз- можным (в принципе) вычислять вероятность любого другого события, определенного на S, пользуясь приписанными вероятностями и тремя аксиомами. По-видимому, самый трудный аспект в построении вероятностных моделей — это установление вероятностей событий. Общая теория не 90 Гл. 2. Некоторые основные приемы и алгоритмы говорит нам, как для данной конкретной задачи решить, какие выбрать события и какие им приписать числа. Этот выбор целиком оставляется человеку, анализирующему задачу. Обычно вероятносуи устанавли- ваются на базе эксперимента и частотной интерпретации. Другой ши- роко распространенной' схемой является схема равновероЯЖВдго рас- пределения, которая описана в следующем' разделе. Очень важно по- нять, что этот выбор при моделировании может сильно повлиять (и влияет!) на полезность самой модели. Теория нейтральна; она будет давать предсказания независимо от выбора конкретных значений. Но, если выбор значений сделан недостаточно точно, предсказания станут неверными и не будут отражать поведение моделируемой задачи из «реального мира». Вернемся к нашей мультипроцессорной задаче. Предположим, что надежные экспериментальные данные показывают, что каждое из 32 со- стояний пространства 5 с равной вероятностью может быть фактиче- ским состоянием системы (исходом) в любом испытании. Поэтому перед испытанием у нас нет оснований предпочитать какое-либо однсГсостоя- ние другому. Отметим, что все 32 элемента в S взаимно исключают друг друга 1). Используя метод индукции и аксиомы II и III, легко показать покажите!), что P(S)^P(s,)+P(s,)+. . -+РМ+Р(5з2)=1 2). Так как каждое состояние равновероятно, то P(sO=P(s,)=. . .=Р (5з,) =1/32. Итак, основные значения вероятностей установлены. Теперь мы можем решить нашу мультипроцессорную задачу. Ка- кова вероятность того, что мы сможем загрузить нашу программу, когда она готова к выполнению? Интересующее нас событие — это Е = свободны три или более процессоров. В терминах элементов множества 5 ?={Si, Sa, ... , Sis, Sig}. Следовательно, P (Е) = Р (s, U s, U ... U s„) = =P(s,)+P(s,)+...+P(s„)-= 16 32 Jr .12 + • • • +: 32 ' 32 32 32 _1_ 2 • Таким образом, нам, по-видимому, удастся загрузить программу в половине попыток, учитывая, что мы пользуемся моделью с равными ^ Напомним, что я^ПЯв^О. О, 1, 1, 1)Г)(0, 1, 0, 1, 1)—в, a не (О, О, О, 1, 1). Это не характеристические векторы (см. приложение Б); не забывайте их интерпре- тацию. •^Заметьте, что S=SiU&iU. • -U^iLJSsa. 2.4. Понятия теории вероятностей и статистики 91 вероятностями и частотной интерпретацией конечного результата. Бели система работает в более тяжёлом режиме и состояниям s„, . . . ..., Sag соответствуют большие вероятности, чем состояниям Si, ... ,Sge, то теория предскажет меньшие шансы на успех. Очень заманчиво всегда подходить к решению вероятностных задач, используя основную процедуру, описанную в этом примере. Сформулируем ее: 1. Идентификация пространства элементарных событий S. В этой книге S будет часто содержать конечное число элементов. Пытайтесь выбирать S так, чтобы все его элементы были несов- местными и в совокупности исчерпывающими, т. е. чтобы ника- кие два события не могли произойти одновременно и чтобы при каждом испытании происшедшее событие входило в мно- жество S1). 2. Присваивание вероятностей. Присвойте вероятности элементам S. Это присваивание должно согласовываться с аксиомами I, II и III. Пространство S должно состоять из конечного числа не- совместных и в совокупности исчерпывающих элементов. По- этому вероятности должны быть присвоены элементам S таким образом, чтобы сумма всех присвоенных значений равнялась 1. (Почему сумма должна быть равна 1?) 3. Идентификация событий решения. Переведите искомое решение на язык событий из S. 4. Вычисление искомых вероятностей. Используя правила вычисле- ния (аксиомы 1,11 и III и другие правила из упражнений), под- считайте искомые вероятности. Хотя вывод большинства формул для подсчета вероятностей остав- ляется в качестве упражнений, есть одно настолько важное правило, что мы должны обсудить его очень подробно. Оно известно как формула условной вероятности. Пусть Е и F — два события, определенные в пространстве S, и пусть Р (Е) и Р (F) — вероятности, соответствующие этим событиям. Пусть P(E\F) обозначает вероятность события Е при условии, что произошло событие F. Как правило, P(E)^=P{E\F). Как только мы знаем, что событие F произошло, вычисление вероятно- сти Е зависит уже не от всего пространства S; теперь нам нужно рассматривать только те элементы S, которые обусловливают выпол- нение события F. Все это учитывается автоматически в формуле Р (Е | F) == - -р ' (имеет смысл, только когда P(F)^O). Проверим формулу условной вероятности на нашем мультипроцес- сорном примере. Предположим, что на пути в машинный зал для за- 1) Более формально, множество подмножеств Ai, . . . , An в S состоит из несов- местных и в совокупности исчерпывающих подмножеств, если А^[}А/=Й для всех i^l, и U A,=S. >==! 92 Гл. 2. Некоторые основные приема и алгоритма пуска программы мы встретили друга, который сказал нам, что он только что занял своей программой первый процессор и что програм- ма будет работать очень долго. Он ничего не сказал о состоянии ос- тальных четырех процессоров. Какова теперь вероятность того, что мы сможем загрузить свою программу? Пусть Е = событие, состоящее в том, что нам удается загрузка, т. е. что свободны три или более трех процессоров; F = событие, состоящее в том, что процессор 1 занят. Если событие F произошло, то мы знаем, что система должна нахо- диться В ОДНОМ ИЗ следующих 16 СОСТОЯНИЙ: Sa, S, — Sio> Sal — San, s^g — ?32. Каждое из этих 16 состояний по-прежнему равновероятно; иначе говоря, у нас нет оснований предпочесть какое-то одно состоя- ние всем остальным. Поэтому вероятность того, что предстоящее испы- тание будет иметь некоторый конкретный исход из этого множества, равна 1/16,' т. е. Р($г1Р)=^ для 1=2, 7—10, 21—26 и 28—32. В этом ограниченном пространстве исходы Sg, s^, s„, Sy и Sio означают появление события Е. Следовательно, по аксиоме III P(E\F)=P(s,\F)+P(s,\F}+P(s,\F)+P(s„\F)+P(s^F)=^. Чтобы воспользоваться формулой условной вероятности, рассмат- риваем полное пространство S. Тогда ?=={Si, Sa, ..., s„}; - = 'р2> s?——^О» ^I——^б» S!:S——S32^'^ Ef}F=={s^, s,, s„ s„ sin}; P{E[)F)=P(s,)+P(s,)+P(s,)+P(s,)+P(s^ (аксиома 111)=^; 32 16 +P(s„)+...+P(s^ (аксиома 111)=-; 32 P(E\F) Р(ЕГ[Р) P{F) j^ 32 _ 5 _16 "Тб' 32 А что, если появление события F никак не связано с ожидаемым появ- лением ?? Тогда P(E)=P(E\F). Но Р(^)=^-, поэтому P(E)=p-jьnF) , или P(EnF)-P(E)-P(F]. Если события Е и F таковы, что вероятность их совместного появления 2.4. Понятия теория вероятностей а статистика 93 равна^произведению вероятностей их раздельного появления, то гово- рят, что эти события независимы. Эта формула'легко обобщается на случай трех или более взаимно независимых событий, т. е. если мно- жества Ai, . . . , An таковы, что Р (A i П Aj)-=P (Л;) • Р (Л,) для любых i^j, то P(Aif)A,[}. . .ПЛ„)=Р(Л1)РИ2). . .Р{Ап). В большинстве задач имеется возможность определить одну или более действительных величин, которые задают информацию в более удобной форме, чем явное описание событий. Например, целочислен- ная функция Х = число свободных процессоров сообщает нам все, что мы хотим знать в нашем мультипроцессорном эксперименте. Искомая конечная вероятность может быть выражена как Р (Х^З) и равна вероятности того, что значение Х больше или рав- но 3. Обратите внимание на то, что Х в действительности является функцией, область определения которой есть пространство S, а об- ласть значений—множество {О, 1, 2, 3, 4, 5}, Любая такая функция из пространства (и определенной на нем вероятностной меры) задачи на множество действительных чисел называется случайной переменной. Фактически все серьезные вычисления вероятностей выполняются в терминах случайных переменных. Определение вероятностей на области значений случайной пере- менной называется распределением. В нашем мультипроцессорном примере, предполагая, что элементы S равновероятны, мы имеем Р(Х==0)=^, Р(Х=!)=Д, P(X=2)=|j, Р(Х=3)=^' ^(Х-4)=1. ^(Х=5)=^. Чтобы понять, как вычисляются эти значения, рассмотрим Р(Х=4)=.Р (имеются в точности четыре свободных процессора) ==P(s,USs[]s^s,Os,)= = Р (s,) + Р (из) + Р (sJ + Р (s,) + Р (s„) - ^1+1+14-1+^-=^ ~ 32 ' 32 ' 32 ' 32 ' 32 32 • 94 Гл. 2. Некоторые основные приемы и. алгоритмы Случайная переменная, область значений которой состоит из счет- ного числа возможных значений, называется дискретной. Если слу- чайная переменная Y должна принимать одно из значений г/i, г/а, . . . , то Р(У=у,)>0 при 1=1, 2, . . . ; Р(У=г/)==0 для всех остальных значений у. Дискретные распределения этого вида называются массовыми функциями вероятности. Так как переменная Y должна принимать в эксперименте одно из значений г/;, массовая функция должна удов- летворять отношению SP^=^.)=I. i Иначе говоря, с вероятностью 1 (т. е. уверенностью) переменная У должна равняться одному из допустимых значений (заметим, что Y не может равняться двум разным значениям одновременно). Легко проверить, что данная массовая функция вероятности случайной ве- личины удовлетворяет этому условию. Математическое ожидание, или среднее значение, или среднее, случайной переменной Y определяется как E[Y]=^y,P(Y=y,). Согласно частотной интерпретации вероятности, среднее есть сред- нее значение случайной величины, во время наблюдения за которой было проведено большое число испытаний. В нашем примере ?(X)=-(0)+1(1)+1^(2)+1^(3)+1(4)+-(5)=80=2.5. 32' "32" 32' 32 32' 32' 32' Отметим, что среднее не обязательно принадлежит области значений случайной переменной. Любая функция от случайной переменной С(У) также является случайной переменной (почему?), математическое ожидание которой задается формулой (1) Пусть опять переменная Х обозначает число свободных процессо- ров, Если случайная переменная G характеризует дефицит процессо- ров, т. е. равна числу процессоров, которых нам не хватает для того, чтобы запустить нашу программу, то { 3, если Х = О, J 2, если Х==1, Gw =} 1, если Х=2, [о, если Х=3. 1) ату формулу часто называют «законом стихийного статистика», так как она нередко вводится как определение (как сделали и мы) «стихийным» статистиком, за- бывающим, что эта формула может быть выведена, 2.4. Понятия теории вероятностей и статистики 95 Согласно равенству (1), получаем Е [G (X)] = 3 [Р (G == 3)] + 2 [Р (G = 2)] + 1 [Р (G == I)] + О [Р (G = 0)] == =3[Р(Х==0)]+2[Р(Х=1):1+1[Р(Х=2)]+0[Р(Х>3)]== •'U)\23 <32J ~32' \,32y ' " \32y 3Z Польза понятия математического ожидания увеличивается, когда фактическое значение, принимаемое случайной переменной, как пра- вило, мало отличается от среднего. Одной из мер этого отличия являет- ся так называемая дисперсия случайной переменной. Пусть Y — слу- чайная переменная со средним ^=?(V). Тогда дисперсия Y, обознача- емая как var [Y}, определяется следующим образом: var[y]=?[(y-^]=:S(y,-^0'==y.). (2) Здесь мы воспользовались формулой математического ожидания для функции от случайной переменной. Стандартное отклонение случай- ной переменной определяется как ст[У]=1ЛГаг"[У]. Для случайной переменной Х в нашем примере " 5' var [X]=(0-2.5)^) +(1-2.5)^|,) +(2-2.5)' + (3-2.5)- (|J)+ (4 -2.5)- (fi) +(5-2.5)- и (т[Х]=1.12. flV\ \32^ ' 1 '\ .32, + -40-! 25 -И"1-0' Сортировка методом прямого включения Этот раздел мы завершим анализом математического ожидания, или среднего, для трудоемкости одного простого алгоритма сорти- ровки. Сортировка методом прямого включения работает со списком не- упорядоченных положительных целых чисел (обычно называемых клю- чами), сортируя их в порядке возрастания. Это делается примерно так же, как большинство игроков упорядочивают сданные им карты, под- нимая каждый раз по одной карте. Покажем работу общей процедуры на примере следующего неотсортированного списка из восьми целых чисел: 27 412 71 81 59 14 273 87. Отсортированный список создается заново; вначале он пуст. На каж- дой итерации первое число неотсортированного списка удаляется из него и помещается на соответствующее ему место в отсортированном списке. Для этого отсортированный список просматривается, начиная с наименьшего числа, до тех пор, пока не находят соответствующее 96 Гл. 2. Некоторые основные приемы и алгоритмы место для нового числа, т. е. пока все отсортированные числа с мень- шими значениями не окажутся впереди него, а все числа с большими значениями — после него. Следующая последовательность списков показывает, как это делается: Итерация 0 Неотсортированный 412 71 81 59 14 273 87 Отсортированный 27 Итерация 1 Неотсортированный 412 71 81 59 14 273 87 Отсортированный 27 412 Итерация 2 Неотсортированный 71 81 59 14 273 87 Отсортированный 27 71 412 Итерация З Неотсортированный 81 59 14 273 87 Отсортированный 27 71 S/ 412 Итерация 4 Неотсортированный 59 14 273 87 Отсортированный 27 59 71 81 412 Итерация 5 Неотсортированный 14 273 87 Отсортированный 14 27 59 71 81 412 Итерация 6 Неотсортированный 273 87 Отсортированный 14 27 59 71 81 273 412 Итерация 7 Неотсортированный 87 Отсортированный 14 27 59 71 81 87 273 412 В следующем алгоритме заводится только один список, и переорга- низация чисел производится в старом списке. Algorithm SIS (Сортировка Прямым включением). Отсортировать на старом месте последовательность целых чисел 7(1), /(2), . . . , I{N) в порядке возрастания. Шаг 1. [Основная итерация! For J -е- 2 to N do through шаг 4 od; and STOP. Шаг 2. [Выбор следующего целого] Set K.-^-I(J}; and L^-J—l. Шаг 3. [Сравнение с отсортированными целыми] While K< 1 do set /(L+1) <-/(L); and L^r- -c-L—l od. Шаг 4. [Включение] Set I(L+\)^-K. Блок-схема алгоритма SIS приводится на рис. 2.4.1. Оценим теперь среднее число сравнений, необходимых для сорти- ровки случайных данных методом прямого включения. В качестве уп- ражнения мы оставляем определение максимального и минимального числа требуемых сравнений. Пусть N — число подлежащих сортировке ключей. Рассмотрим 1-й проход по циклу на шаге 1. В начале этого прохода первые i ключей неотсортированного списка ранее были правильно упорядочены, и теперь мы собираемся включить (1'+1)-й ключ в список из i отсорти- рованных ключей. Имеется f—1 «промежутков» между отсортирован- ными ключами и еще две позиции на концах списка, что в сумме дает 2.4. Понятия теории вероятностей и статистики 97 ( Начат ) J*-z К<-1У) 1 ' Lt-J-1 ^ г:; .\ /;•". : • Ю'Н^ ^^к<1(ц\^ f/sm_________ ^\L»1/^ [Да KL+1)<-1(Q }, г ,, Т^-IS-ft '-'' |——т——| ]————| Ы1 ^.' • L<-.L-1 I(.L+1)<-K l I J<-J+1 ——————————————————————————————^-<^^> \Hem (Окончание^ Рис. 2.4.1. Блок-схема алгоритма SIS. t'+l возможных позиций для следующего ключа. Предположим, что новый ключ с равной вероятностью 1/'(i'+l) может быть помещен в лю- бой из этих промежутков. Пусть X; — случайная переменная, равная числу сравнений, требуемых для помещения ключа t'+l в правильную 4 № 2658 98 Гл. 2. Некоторые основные приемы и алгоритмы позицию на этом проходе. Тогда РГУ 1 1 ( \ Л i О ( ' ^ 1_Ч ( ' Vl i ' , t ?[X,]=1 ^7TTJ+2l7TтJ+зl7TTJ+•••+7q-Г+-Г^T =^[l+2+3+...+(i-l)+i+t]= ' ('+1) (используем формулу Гаусса)'== t+1 i+l 1+-1 9 I >• Заметим, что, когда нужная позиция находится на дальнем конце, выполняется только i сравнений. Так как имеется N ключей, в цикле на шаге 1 выполняется N—1 итераций. Если случайная переменная Y обозначает обще? число сравнений при сортировке, то У=А',+Х,+...+Х^. Используя результат из упр. 2.4.11, получим ?[K]=?[XJ+?[XJ+...+?[X^_J= _4-— ^2^2, ^+ 3 1 • l^+f4+4)+•.•+f^±+^^ =4[1+2+...+(УУ-1)]+[^+|-. Л'-1 Л?-1 1 V • i V i ==^t+L^TT== f=i N 2 _^a "T Л/ 2 jW 4 ^--^F^-S:1 (см. упр. 2.4.10): f-1 -H^ где Н^'=^— называется N-м гармоническим числом1). i=i t Таким образом, среднее число сравнений, требуемых алгоритмом SIS для сортировки N ключей, приблизительно равно Л^/4, а средняя сложность равна О (N2). С помощью аналогичного анализа можно об- наружить, что среднее число перемещений /(L+1) -<- I (L) также OQV2). Алгоритм SIS не является очень хорошим алгоритмом сортировки, хотя, впрочем, он один из простейших и наиболее удобных для реали- зации. В разд. 5.1 будут изучены более сложные алгоритмы сортиров- ки со средней сложностью и сложностью в худшем случае 0(N log N). На примере сортировки методом прямого включения мы продемон- стрировали простой вероятностный анализ сложности. Далее в книге мы будем часто прибегать к подобному анализу. 1) Когда N->• оо, Hff приблизительно равно In ^+0,577+0(1/^). 2.4. Понятия теории вероятностей и статистики 99 Чтобы показать основное различие между вероятностным и стати- стическим подходом, вернемся к нашему анализу ожидаемой трудоем- кости алгоритма SIS. По заданному или предполагаемому распределе- нию сортируемых элементов мы вычислили ожидаемое число сравне- ний, выполняемых при сортировке N ключей. При этом мы восполь- зовались определениями и правилами вычисления из теории вероят- ностей. Таким образом, заданное распределение было использовано для предсказания поведения 'алгоритма.'ЭтбТтйп анализа характерен для большинства вероятностных моделей. Во многих отношениях статистические задачи «обратны» вероят- ностным задачам. Наблюдается поведение системы и делается попытка вывести заключения о лежащем в основе неизвестном распределении случайных величин, которые описывают функционирование системы. Определим случайную переменную Y, которая равна для любой слу- чайной последовательности N целых чисел числу сравнений, требуе- мых алгоритмом SIS для сортировки этой последовательности. Каждое применение алгоритма SIS к случайной последовательности целых чисел дает, таким образом, выборку Y. Хотя нам и не известно распре- деление У, мы можем взять несколько выборок, вычислить среднее У от этих полученных экспериментальным путем чисел и принять У как оценку математического ожидания У (т. е. использовать У для аппрок- симации Е [У]). Следовательно, для вывода заключений о случайной переменной используются полученные из наблюдений значения. Не представляется возможным дать общие рекомендации относи- тельно того, какая из форм анализа лучше. На практике они должны дополнять друг друга. В нашем примере мы сделали предположение о распределении и затем смогли вычислить Е [У] вероятностными методами. То есть мы предположили, что (1+1)-й ключ с равной ве- роятностью может оказаться помещенным в любую из позиций на кон- цах или внутри отсортированного списка из i элементов. Верно ли это предположение для «реальных» данных? С другой стороны, статистиче- ская оценка для Е [Y] может оказаться плохой из-за того, что на- блюдаемая выборка была в некотором смысле «непредставительной». Если нам сдали случайным образом четыре карты и все они оказались тузами, будем ли мы считать, что вся колода состоит только из тузов? Если провести оба анализа — сравнить статистическую оценку У с выведенным значением Е [У] — и значения окажутся близкими, будут основания считать, что мы кое-что знаем о средней трудоемкости ал- горитма. Если они сильно отличаются, возникает причина для бес- покойства. Продолжим обсуждение оценок и статистического анализа алго- ритмов в несколько более общих терминах. Нас интересует ожидаемая или средняя трудоемкость некоторого алгоритма А на множестве воз- можных исходных данных D. Множество D очень велико, и алгоритм А достаточно сложен. Рассмотрим обработку алгоритмом А некоторых случайным образом выбранных из D исходных данных как экспери- 4» 100 Гл, 2. Некоторые основные приемы и алгоритмы мент, который определяет случайную переменную Т, время работы алгоритма Л. Распределение Г неизвестно. Для наших целей не тре- буется обязательно статистически оценивать все распределение Т. Будет достаточно оценить значения некоторых свойств распределения, а именно математическое ожидание и дисперсию. Общая процедура оценки свойства 9 распределения следующая. Возьмем ряд наблюдений (Xi, Хз, . . . , Х„) за интересующей нас слу- чайной переменной X. Построим функцию F (Xi, Хз, . . . , XJ, об- ласть определения которой есть множество наблюдений, а область значений — множество возможных значений свойства 9. Такая функ- ция называется оценкой 9 и сама представляет собой случайную пере- менную (почему?). Как мы выбираем конкретную функцию в качестве оценки? По- скольку имеется много возможностей выбора, следует дать некоторый критерий, гарантирующий выбор хорошей оценки. Интуитивно самый очевидный критерий состоит в выборе для оценки такой функции F, собственное распределение 1) которой сильно концентрируется вокруг истинного значения 9. Рассмотрим три конкретные характеристики хороших оценок, которые отражают это интуитивное требование. Случайная переменная F является несмещенной оценкой 0, если Е [F]=Q. Существуют очень простые несмещенные оценки для матема- тического ожидания и дисперсии любой случайной переменной. Оценка п Х(Х„ .... Х„)=^Х. t'== 1 является несмещенной оценкой математического ожидания Е [X]. Это следует из EW-E\^X, = i'=i п ——ИВД] (см. упр. 2.4.11) =—n(?[X] (почему?) =Е[Х]. Так как^уаг [X] определяется через Е [X] (см. уравнение (2) и упр. 2.4.12), выбранная для var [X] оценка будет зависеть от того, знаем ли мы Е [X] или Е [X] должно быть оценено. Если значение Е [X] известно, то оценку G(Xi, .... X„)=^(X,-?[Xp естественно подсказывает определение var [X]. Легко установить, что 1) Напоминаем, что F — случайная переменная! 2.4. Понятия теории вероятностей и статистики 101 оценка G не смещена: [п -in E\G}=E ^Il(X,-?[X:H=^?[(X,--?[X^j= =4 Е (^ W] - 2E [X,] E [X] + (Е [X]D = i= i ==^-,^[X2]-n(?[X])^=var[X]. При этом используются результаты упр. 2.4.12. Если значение Е [X] неизвестно, как обычно и бывает, то оценка п ^(Xi, .... Х„)=^^(Х,-Х)^ (=1 является несмещенной оценкой для var [X]. Доказательство этого оставлено в качестве упражнения. Согласующаяся оценка G(Xi, .... Х„) свойства 9—это оценка, значение которой будет как угодно близко к 9 с вероятностью, при- ближающейся к 1, когда ге—>-оо. Более формально, G(Xi, . . . , Хд) является согласующейся оценкой для 9, если lim P{|G(Xi, ..., Х„)—9|<8}=1 для любого е > 0. П —> со Согласующаяся характеристика отражает наше интуитивное ожи- дание того, что, чем больше выборка, тем она более надежна. Это интуитивное предположение математически подтверждается одним из самых важных результатов в теории вероятностей. Теорема 2.4.1. (слабый закон больших чисел). Пусть Xi, ... , Х„— независимые случайные переменные и (a) ?[XJ=m, (б) var [Х,]=^2 для i=\, 2, п. Если Х(Х^, ..., Хп)=—^Х,., п ^/\" 1=1 то для любого е>0 lim P{ Х-те|<е}=1. Более сильная формулировка этой теоремы позволяет опустить условие (б) конечности дисперсии. Из закона больших чисел немедлен- но следует, что Х — согласующаяся оценка математического ожида- ния случайной переменной. Несмещенная оценка с минимальной дисперсией — это несмещенная оценка, дисперсия которой наименьшая среди всех несмещенных оце- нок или, возможно, среди всех несмещенных оценок определенного рода. Дисперсию часто можно рассматривать как меру точности оцен- 102 Гл. 2. Некоторые основные приемы и алгоритмы ки. Чем меньше дисперсия, тем больше шансы, что значение оценки будет близко к значению свойства, которое она оценивает. Таким образом, малая величина дисперсии является желательной характе- ристикой оценки. Пример. Время работы динамически выполняемого алгоритма изме- ряется с помощью двух системных часов. Показания первых часов 7\, вторые часы регистрируют время Тг. Те и другие часы неточны в связи с наличием шумов в системе. Но природа шума такова, что каждые часы с равной вероятностью дают отклонения в большую и меньшую сторону на одну и ту же величину. Поэтому Е [Ti]==E [Ts\==T = истинное время работы. Таким образом, и первые, и вторые часы несмещенные, но известно, что их точность различна, т. е. var [Ti]^var [TJ. Предположим, что var [Ti] • • • > Хп=Хп) и если Oi, . . . , а„ — про- извольные константы, покажите, что , Е [аЛ+аЛ+. . .+aA]=ai? [XJ+. . .+a„? [Х„}. 2.4.12. Если Х — произвольная дискретная случайная переменная, то покажите, что var [X]-E m-(? [X])2. 2.4.13. Покажите, что для любой случайной переменной Х и константы а var [aX}=a2\w [X]. Глава 7. Дополнительные замечания и ссылки Цель этой главы — привлечь внимание к материалу, дополняю- щему содержание этой книги. Она не должна служить исчерпываю- щей библиографией. Мы попытались найти хорошие, легко читаемые источники по вопросам, которые заинтересуют читателя. В этой главе две части. Первая — аннотированная библиография, упорядоченная по главам и разделам. Вторая — алфавитный список (по фамилиям авторов) работ, упомянутых в первой части. Где воз- можно, мы предпочитали цитировать учебники более или менее эле- ментарного уровня вместо трудных журнальных статей. Для обозна- чения уровня работы" использовались следующие сокращения: Е: элементарные, I: промежуточного уровня, А: трудные, VA: очень трудные. Дополнительным символом М помечены источники, требующие или использующие значительное количество математических выкладок. В качестве калибровки этой шкалы укажем, что данная книга харак- теризуется как IM. Глава 1. Полное построение алгоритма Не существует «официального» определения термина «полное по- строение алгоритма». Похоже, что большинство специалистов в об- ласти вычислительной математики находят приемлемым перечень, данный в конце разд. 1.1. Хорошим введением в математические машины и формальную теорию вычислений является книга [891. Более обширным и немного более трудным введением является [721. Хотя некоторые пуристы признают в качестве описания алго- ритма только полную программу в кодах, мы думаем, что полусло- весные пошаговые описания, использованные здесь (см. приложение А), и некоторое прозаическое обсуждение очень полезны (и часто необ- ходимы) для основательного понимания работы алгоритма. Многим людям трудно вникать непосредственно в программу, если даже она хорошо документирована. Естественно было бы полагать, что идея математической модели является наиболее фундаментальным понятием в прикладной мате- Гл. 7. Дополнительные замечания и ссылки 339 матике. Несмотря на это, мы не смогли найти хорошего элементарного обсуждения этой темы, ориентированного на применение вычисли- тельной техники. Считается, что первоначальная формулировка задачи коммивоя- жера принадлежит Мерриллу М. Флуду (Колумбийский университет, 1937 г.). Она возникла в связи с выбором маршрутов для школьных автобусов. К середине 50-х годов в литературе по исследованию опе- раций начали появляться журнальные статьи, посвященные этой задаче, и она широко изучается до сих пор. Хотя для задачи не из- вестны алгоритмы, полиномиальные в худшем случае, существует ряд впечатляющих эвристических и точных (но экспоненциальных в худшем случае) процедур ее решения. Ссылки на некоторые из них даны в разд. 4.4. В [63] описаны некоторые практические приложения задачи коммивояжера. Хорошее общее обсуждение реализации, отладки и документации дано в [99]. В качестве учебника по «стилю программирования» см. [541. Несмотря на то что для многих людей полиномиально-экспонен- циальный критерий сложности кажется вполне очевидным, до сере- дины 60-х годов он, по-видимому, не находил широкого применения. Первая явная его формулировка, которую мы нашли, содержится в [22]. Обозначения «0-большое» и «о-малое» стали популярными в ряде математических дисциплин. Подробное обсуждение можно найти в гл. 1 книги [56]. Глава 2. Некоторые основные приемы и алгоритмы 2.1. Структурное программирование сверху-вниз и правильность программ Предмет структурного программирования сверху-вниз нов и противоречив. Среди программистов он, кажется, быстро завоевывает признание, хотя пока далеко не всеобщее. Литература по структур- ному программированию растет экспоненциально. Для дальнейшего изучения мы бы рекомендовали [70]. Эта достаточно основательная книга содержит краткий исторический обзор предмета. Можно также посмотреть специальные выпуски двух популярных журналов [12], [17]. Более глубокое изложение материала содержится в [16]. 2.2. Сети Словарь терминов, связанных с сетями, все еще точно не определен. Для этих структур не выбрано даже единого общеупотребительного названия. Примерно в одной половине книг их называют сетями, а в другой — графами. Вершины часто называются точками или уз- лами; ребра часто называются линиями или дугами. Мы пытались 12* I , .'' 340 Гл. 7. Дополнительные замечания и ссылки пользоваться некоторой достаточно общеупотребительной термино- логией. Почти энциклопедическое изучение деревьев можно найти у Кнута 156]. Нетрудной, ориентированной на приложения книгой является 120J. Здесь можно найти хорошо изложенные основы применения сетей к теории переключателей и кодирования, анализу электрических схем и исследованию операций. Книга содержит также краткое об- суждение вопросов, связанных с применением теории сетей в химии. • При работе с сетями в теоретическом плане большую помощь может оказать книга [7J, которая содержит наиболее полную мате- матическую трактовку графов и сетей на современном уровне изло- жения этих вопросов. По-видимому, свое фундаментальное значение эта книга не утеряет и в ближайшем будущем. Алгоритмы обработки сетей очень интенсивно используются в области исследования операций. Литература в этой области обширна, мы укажем лишь на работы [34], [29J и [62]. Алгоритм CONNECT можно найти в [20]; там же рассматрива- ются другие матричные представления и ряд алгоритмов обработки сетей. Хорошая эвристика для проблемы изоморфизма описана в [14]. К сожалению, некоторые из высказанных в этой статье теоретических предположений, как было показано позднее, неверны. Впрочем, рассматриваемый в статье основной алгоритм остается одной из наи- более известных общих эвристик. Проблема изоморфизма была решена для некоторых специальных классов'^ет^^са,мьш. важным из них являются деревья; см. [13]. '"'""Для работы „с сетями было разработано много специальных языков программирования и пакетов программ. Приводим небольшую под- борку литературы по этим вопросам: [З], [10], [44], [55], [68]. Язык CLAMAR [68] замечателен тем, что он был полностью разработан двумя студентами. Использование большинства специальных языков ограничено и локализовано. 2.3. Некоторые структуры данных Большой и детальный перечень различных структур данных можно найти у Кнута [561. Среди других широко используемых книг можно назвать [8], [77] и [871. 2.4. Элементарные понятия из теории вероятностей и статистики Легко читаемым, ориентированным на практическое применение введением в теорию вероятностей является [811. В гл. 8 этой книги содержится прекрасное введение к теме надежности систем — теме, имеющей серьезное применение в вычислительной науке. Гл. 7, Дополнительные замечания и ссылки 341 Достаточно элементарную и легко понимаемую трактовку диск- ретных событий и случайных переменных можно найти в классической работе Феллера [26]. Очень элементарное, ориентированное на программистов (язык Basic) введение в дискретную вероятность содержится в [85]. Анализ^ ожидаемой трудоемкости алгоритмов, как правило, очень тдудец, анализ алгоритма SIS в этом разделе является исключением. Анализ ожидаемой трудоемкости алгоритма МАХ (см. разд. 1.2) можно найти в книге [56]. Алгоритм ETS (см. разд. 1.3) всегда выпол- няет одно и то же число операций для любого множества N городов. Алгоритм PRIM настолько бесхитростен, что едва ли стоит зани- маться анализом его ожидаемой трудоемкости. Это видно и по резуль- татам экспериментального анализа средней трудоемкости в разд. 5.2. Ниже приводится подборка ссылок, относящихся к приложениям, которые описаны в начале разд. 2.4. По теме «имитационное моделирование» смотрите [28]. Дополни- тельные ссылки даются для разд. 3.6 и 6.3. По вычислительной ста- тистике мы рекомендуем [30]. Генерация случайных чисел рассмот- рена в [57]. По Бейесовской теории принятия решений см. [98] и [18]. Достаточно полное введение в статистические методы можно найти в [73]. Книгой на элементарном уровне является [48]. Более фунда- ментальная трактовка содержится в [15]. Глава 3. Методы разработки алгоритма 3.1. Методы частных целей, подъема и отрабатывания назад В области общих методов решения задач работали психологи, математики и специалисты по вычислительной математике. Некоторые из наиболее известных источников — следующие. Психологом на- писана книга [96], математиком — [78, 79], специалистом по вычис- лительной математике— [76]. Большинство работ специалистов по вычислительной математике в области методов решения задач можно найти под рубрикой «ис- кусственный интеллект». Исчерпывающими обзорами являются [25] и [71]. Значительная часть этой литературы связана с играми на ЭВМ. Полное рассмотрение задачи о джипе можно найти в [35]. Ричард Беллман и другие развили метод отрабатывания назад в нечто, лежащее между искусством"?} 'науко"й,"известноё' как динами- ческое^рограммцрование. Хорошо написанные вводные обзоры можно "найтй"в Т45] и [52]. '"" ' 3.2. Эвристики Каждый год многие студенты «заново открывают» алгоритм GTS2. Гораздо более действенный (и более сложный) эвристический метод 342 Гл. 7. Дополнительные замечания и ссылки для задачи коммивояжера дан в [64]. Быстрые, простые (но не осо- бенно мощные) эвристические методы для очень больших задач рас- смотрены в [94]. Наглядное рассмотрение с большим количеством интересных примеров эвристических алгоритмов для составления расписаний и упаковки можно найти в [41]. Анализ ряда простых, но эффективных эвристических алгоритмов содержится в [50]. 3.3. Программирование с отходом Этот метод «заново открывался» много раз. Например, см. [39]. Хорошее общее описание процедуры отхода можно найти в [60]. В по- следней статье также содержится полезный полуэкспериментальный анализ средней трудоемкости, применимый к любому алгоритму с отходом. 3.4. Метод ветвей и границ Алгоритм этого раздела основан на статье [65], которая во многом способствовала популяризации процедуры ветвей и границ. Более содержательное рассмотрение см. в [38]. Как показывает последняя работа, процедуры ветвей и границ очень полезны для решения задач оптимизации, известных как задачи целочисленного линВйного'программирования. В этих задачах требуется найти множест- во целых чисел, которые максимизируют или минимизируют линейную форму при линейных ограничениях. Многие важные задачи, включая задачу коммивояжера, можно сформулировать как задачи целочис- ленного линейного программирования. Обзор работ по задаче коммивояжера до 1968 г. можно найти в [б]. Заслуживающими внимания вкладами в литературу по задаче коммивояжера являются работы [5] и [46]. Впечатляют результаты вычислительных экспериментов с этими двумя алгоритмами. Заметим, что в работе [46] используются остовные деревья минимального веса. Один из наиболее эффективных с точки зрения скорости и каче- ства решения эвристических алгоритмов для задачи коммивояжера можно найти в работе [64]. 3.5. Рекурсия Прекрасное описание рекурсии дано в книге [2]. Рекуррентные соотношения часто возникают в приложениях, и для нахождения решений таких уравнений в замкнутой форме су- ществует много методов. Хорошее вводное изложение этого материала можно найти в [66]. В книге [76] обсуждаются методы поиска в ширину и глубину. Гл. 7. Дополнительные замечания и ссылки 343 Рекурсивный поиск в глубину недавно был использован как основа для ряда эффективных сетевых алгоритмов. Одной из наиболее ранних и основополагающей является статья [88]. 3.6. Моделирование Большие усилия сделаны для развития хороших методов и языков моделирования. Эти усилия полностью оправданы важностью имита- ционных моделей для практических задач. В дополнение к книге [28] мы рекомендуем [40]. Оба труда содержат главы по специальным языкам моделирования. В книге [28] приведена обширная библио- графия, к которой следует обратиться каждому, кто серьезно интере- суется этой темой. Глава 4. Полный пример 4.1. Алгоритм построения остовного дерева минимального веса Алгоритм, приведенный в этом разделе, впервые сформулирован в работе [80]. Существует ряд уловок, которыми можно воспользо- ваться для ускорения этого основного алгоритма, но после этих из- менений он все же остается алгоритмом сложности 0(М2). Мы пред- почли пренебречь этими уловками и избежать ненужных усложнений. Хорошее вводное обсуждение интерполяции, экстраполяции и приближения данных по методу наименьших квадратов можно найти в книгах [43] и [33]. 4.2. Проверка программ По .проверке программ, хорошая литература отсутствует. Не- трудно понять, почему дело обстоит так. Опубликованные описания процедур проверки обычно отражают подходы и эмпирические пра- ви-ла, используемые отдельными группами в «реальном мире». В не- которой степени материал этого раздела отражает наши собственные идеи и опыт. По-видимому, пройдет еще некоторое время, прежде чем какой-то конкретный набор процедур проверки станет широко принятым. Легко читаемое, довольно полное описание проверок на правиль- ность можно найти в книге [92]. В [99] также содержатся полезные советы. Некоторые заботятся о строгих доказательствах правиль- ности программы, но пока что это направление исследований остается довольно бесплодным. (См. несколько ссылок в [99].) Два простых описания проверки эффективности содержатся в ис- следованиях [58] и [49]. Программы, строящие профили других про- грамм, обычно велики и сложны. Однако сильный студент может разработать и запрограммировать неплохую программу вычисления профилей '(см. [27]). 344 Гл. 7. Дополнительные замечания и ссылки 4.3. Документация и обслуживание Вопросы документирования программ и их обслуживания осве- щаются в работах [54], 199], [92], а также [42] и [74]. Глава 5. Алгоритмы вычислительной математики 5.1. Сортировка Вероятно, алгоритмы сортировки являются наиболее широко изученными алгоритмами во всей машинной математике. Большая часть из того, что известно в этой области, исчерпывающе отражена в третьем томе труда Кнута [591. Прекрасной обзорной статьей является [69]. Другие книги в порядке возрастания трудности: [77], [75], [I]. 5.2. Поиск Исчерпывающее обсуждение машинного поиска можно найти у Кнута [59]. Более элементарный подход содержится в книге [75]. В обоих этих источниках обсуждается важный метод, называемый хэшированием, которого мы не касались. При хэшировании ключи отыскиваются путем вычисления функции отТамого ключа. Значение этой функции задает точное или приблизительное расположение ис- комой" записи'.' " ^ Задачи ^вероятностного поиска требуют для своего решения изощ- ренных математических средств — пример, приведенный в данном разделе, представляет собой редкое исключение. Описание более сложных задач можно найти в работе [18]. Ссылки на оригинальные работы Хафмана и Циммермана можно найти у Кнута J56]. 5.3. Арифметические и логические выражения Дальнейшее обсуждение арифметических выражений можно найти в работах [56], [75] и [95]. 5.4. Управление страничной памятью Есть несколько хороших источников информации по алгоритмам управления страничной памятью, в том числе t4], [19], [II]. Мы смогли только слегка коснуться темы алгоритмов, применя- емых в математическом обеспечении ЭВМ (разд. 5.3 и 5.4). Компиля- торы и операционные системы конструируются с использованием широкого разнообразия таких алгоритмов. К некоторым из ранее цитированных источников можно обратиться за дополнительными примерами. В их число входят все три тома Кнута [56], [57], [59], а также [47], [8], [77], [75], [11] и [95]. 5.5. Параллелизм Описание машины Иллиак IV приведено в работе [84]. Ссылки на несколько интересных статей о параллельных вычислениях можно Гл. 7. Дополнительные замечания и ссылки 345 найти в книге [91]. Оказывается, М. Солин так и не опубликовал свой параллельный алгоритм нахождения остовного дерева минимального веса. Мы обнаружили краткое обсуждение в книге [24]. Алгоритм PARSORT взят из статьи [53]. Этот алгоритм обсуж- дается также в [24]. Глава 6. Математические алгоритмы 6.1. Игры и комбинаторные головоломки Литература по играм обширна и разнообразна, и мы не сможем осветить ее в достаточной мере. Однако мы предоставим список, кото- рого заинтересованному читателю хватит на годы. Элементарное, полуисторическое введение в магические квадраты можно найти в книге Гарднера [36]. В этой книге цитируется ряд более серьезных источников. Регулярную колонку Гарднера «Математические игры» в жур- нале Scientific American не пропускает ни один энтузиаст игр. Он также опубликовал или отредактировал более дюжины книг по ма- тематическим играм и головоломкам; например, см. [37]. Игра «нимбы», рассмотренная в этом разделе, была изобретена. Джеймсом Байнамом и описана Гарднером в его колонке в феврале 1974 г. Задача о тройной дуэли является классической. Гарднер [36] описывает ее возникновение. Несколько более общую и более серь- езную трактовку, чем приведена здесь, можно найти в книге [32]. Существует формальная ..математическая теория игр, которую мы не рассматривали', поскольку этот предмет заслуживает отдельного курса в большинстве университетов. Следующие книги служат вве- дением на нескольких различных уровнях: [97], [83], [93], [67]. Как и следовало ожидать, много усилий было направлено на анализ серьезных азартных игр. Книги [82] и [23] весьма основа- тельны, хотя и каждая в своем роде. Энтузиасты компьютерных игр должны обращаться к литературе по искусственному интеллекту, например к книгам [25], [76], а также к книге [86]. В книге [75] также имеется хорошая глава о машинно-ориентиро- ванных играх. 6.2. Кратчайшие пути Проблема отыскания кратчайших путей в сетях изучалась до осьмины. Из рассмотренных в этом тексте проблем особенно осно- вательно изучена сортировка. (Некоторые темы, как, например, поиск, слишком разнообразны, чтобы их можно было рассматривать как одну проблему.) Книга [62] содержит хорошее обсуждение, го- раздо более исчерпывающее, чем то, которое мы привели здесь. Алго- ритм Дейкстры впервые был сформулирован в работе 121]. Гл. 7. Дополнительные замечания и ссылки 6.3. Вероятностные алгоритмы Центральная предельная теорема (теорема 6.3.3) позволяет нам •-шпроксимировать ряд дискретных и непрерывных распределений стандартным нормальным распределением N (О, 1). Некоторые при- меры можно найти у Росса [81]. Эта аппроксимация часто позволяет значительно упростить вычисления. В книге Кнута [57] очень детально рассмотрены генераторы слу- чайных чисел. В ней обсуждается выбор параметров алгоритма LCM и дан широкий ассортимент статистических тестов для проверки «слу- чайности» последовательности случайных чисел. Многих читателей книги Кнута может также заинтересовать обсуждение вопроса, что такое случайная последовательность? (Этот материал несколько труден, но по крайней мере вы получите некоторое представление об усилиях, которые необходимо приложить для ответа на этот во- прос.) Книга Кнута [57], а также работа [47] могут быть использованы при дальнейшем изучении теории и примеров, относящихся к вероят- ностным алгоритмам. Две отличающихся точки зрения можно найти в статьях Гренандера и Нойтса в сборнике [611. Статистическая оценка производительности вычислительных си- стем привлекала до недавнего времени заметное внимание. Интере- сующиеся читатели могут обратиться к книгам [31], [47]. Для чтения этих книг необходимо иметь некоторое представление об организации вычислительных машин и операционных систем. Численная оценка сложности вычислений и NP-полные задачи Существует две важные темы, которых мы не смогли коснуться, так как их включение потребовало бы увеличения объема книги и некоторых сведений из дополнительного курса. Мы удовлетворимся простым их упоминанием и дадим несколько библиографических ссылок. Предмет численной или аналитической оценки вычислительной сложности относится к проектированию и анализу численных алго- ритм6вГ"Сюда относятся алгоритмы матричных операций, целочис- ленная арифметика и арифметика многочленов, решение алгебраиче- ских и дифференциальных уравнений, быстрые преобразования Фурье и т. д. Интересующийся читатель может обратиться к работам [57], [91], [1] и к статье Трауба в сборнике [611. Краткий и весьма легкий для чтения обзор содержится в [901. Было показано, что комбинаторные задачи, относящиеся к ши- рокому классу, включающему задачу о коммивояжере, и общие задачи планирования и упаковки (см. разд. 3.2) — все эквивалентны в том.., .смысле, что либо все они разрешимы, либо ни одна из них не разре- шима полиномиальными алгоритмами. Таким образом, если бы уда- лось показать, что хотя бы для одной из этих задач не может сущест- вовать алгоритма решения, имеющего в худшем случае полиномиаль- Гл. 7. Дополнительные замечания и ссылки 347 ную трудоемкость, то таких алгоритмов не должно существовать и для всех остальных задач этого класса. Наоборот, если можно найти хотя бы для одной из таких задач алгоритм, имеющий в худшем случае полиномиальную трудоемкость, то его можно было бы применить при построении полиномиальных алгоритмов для остальных задач. Задачи из этого класса 'называются Np-полньши. Наиболее элемен- тарной работой по этому вопросу, по-видимому, является [51]. Для более серьезного изучения можно порекомендовать [I]. 1. Aho, A. V., J. Е. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974(VAM). 2. Barren, D. W., Recursion Techniques in Programming, American Elsevier, New York, 1968(IM). 3. Basili, V. R„ C. K. Mesztenyi, and W. C. Reinboldt, "FGRAAL: Portran Extended Graph Algorithmic Language," Tech. Kept. 179, Computer Science Center, University of Maryland, 1972(.l); see also Tech. Rept. 225, 1973(1). 4. Belady, L. A., "A Study of Replacement Algorithms for a Virtual Storage Computer," IBM Syst. J., 5: 78-101 (1966)(l). 5.Bellmore, M., and J. C. Malone, "Pathology of Traveling Salesman SubtOur Elimination Algorithms," Oper. Res., 19: 278-307 (1971)(AM). 6. ———, and G. L. Nemhauser, "The Traveling Salesman Problem; A Survey," Oper. Res., 16: 538-558 (1968)(IM). 7. Berge, C., Graphs and Hypergraphs, North-Holland, Amsterdam, 1973(AM). 8. Berztis*s,A.T., Data Structures: Theory and Practice, Academic, New York, 1971(IM). S.Busacker, R. G., and T. L. Saaty, Finite Graphs and Networks, McGraw-Hill, New York, 1965(IM). 10. Chase, S. M., "GASP—Graph Algorithm Software Package," Q. Tech. Prog. Rept. (Oct.-Dec. 1969), Department of Computer Science, University of Illinois (I), H.Coffman, E. G., and P. J. Denning, Operating Systems Theory, Prentice-Hall, .Englewood Cliffs,' N.J., 1973(AM). 12.Compu(. Surv., 6: (1974)(E). 13.Corneil, D. G., "Graph Isomorphism," doctoral .thesis, Department of Computer Science, University of Toronto, Canada, 1968(AM); see also Tech. Rept. 18, Department of Computer Science, University of Toronto, 1970. 14.———, and С. С. Gotlieb, "An Efficient Algorithm for Graph Isomorphism," /. ACM, 17: 51-64 (1970)(AM). 15.Cox, D. R., and D, V. Hinkley, Theoretical Statistics, Chapman and Hall, London, 1974(AM). 16.Dahl, 0., E. Dijkstra, and C. A. R. Hoare, Structured Programming, Academic, New York, 1972(1). ^.Datamation, 19: (1973)(E). •le.DeGroot, M. H., Optimal Statistical Decisions, McGraw-Hill, New York, 1970(VAM). 19. Denning, P. J., "Virtual Memory," Comput. Surv., 2: 153-189 (1970)(l). ZO.Deo, N.. Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, N.J., 1974(!M). ,21.Dijkstra, E. W., "A Note on Two Problems in Connexion with Graphs," Numer. Math., 1: 269-271 (1959)(IM). 22-Edmonds, J., "Paths, Trees, and Flowers," Can. J. Math., 17: 449-467 (1965)(АМ). 23.Epstein, R. A., The Theory of Gambling and Statistical Logic, Academic, New York, 1967(AM). 24. Even, S., Algorithmic Combinatorics, Macmillan, New York, 1973(IM). • •L ^ -'^ f:. • . :i48 Гл. 7. Дополнительные замечания и ссылки 25. Feigenbaum, E. A., and J. Feldman, Computers and Thought, McGraw-Hill. New York, 1963(1). ' . . ^. > 26. Feller, W., An Introduction to Probability Theory and Its Applications, 2d ed., vol. 1, Wiley, New York, 1957 (IM). 2.7. Ferguson, L., "PROFILE, A CDC Fortrah Profiling Program," Tech. Rept. 75-6, Department of Applied Mathematics and Computer Science, University of Virginia; 1975(1). ZS.Fishman, G. S., Concepts and Methods т Discrete Event Digital Simulation, Wiley, . New York, 1973(1M)., , 29. Frank, H., and I. T. Frisch,' Communications, Transmission, and Transportation Networks, Addison-Wesley, Reading, Mass., 1971(AM). SO.Freiberger, W., and U. Grenander, A Short Course in Computational Probability and Statistics, Springer-Veriag, New York; 1971(VAM).. 31.Freiberger, W. (ed.), Statistical Computer Performance Evaluation, Academic, New York, 1972(A). 32-Freudenthal, H., Probability and Statistics, Elsevier, Amsterdam, 1965(IM). 33. Fruberg, C.E., Introduction to Numerical Analysis, 2d ed., Addison-Wesley, Reading, Mass., 1969(AM). 34.Fulkerson, D. R., "Flow Networks and Combinatorial Operations Research," Am. Math. Mon., 73: 115-138 (1966)(llvr). 35.Qale, D., "The Jeep Once More or Jeeper by the Dozen," Am. Math. Mon., 77: 493-501 (1970)(IM). 36. Gardner, M., The 2nd Scientific-American Book of Mathematical Puzzles and Diversions, Simon and Schuster, New York, 1961(EM). 37.———, The Unexpected Hanging and Other Mathematical Diversions, Simon and Schuster, New York, 1969(EM). 36.Garfinkel. R. S., and G. L. Nemhauser, Integer Programming, Wiley, New York, 1972(AM). 39. Golomb, S. W„ and L. D. Baumert, "Backtrack Programming," /. ACM, 12:516-524 (1965)(l). 40.Gordon, G., System Simulation. Prentice-Hall, Englewood Cliffs, N.J., 1969(1). 41. Graham, R. L., "Bounds on Multiprocessing Anomalies and Related Packing Algorithms," in Proc. Spring Joint Comput. Con/., 205-217 (1972)(1M), 42.Gunderman, R. E., "A Glimpse into Program Maintenance," Datamation, 19:99-101 (1973)(E). 43.Hamming, R. W., Introduction to Applied Numerical Analysis, McQraw-Hill, New York, 1971(IM). 44. Hart, R., "HINT: A Graph Processing Language," Res. Rept., Computer Institute for Social Science Research, Michigan State University, 1969(1). 45. Hastings, N. A. J., Dynamic Programming,' Crane, Russak, New York, 1973(IM). 46. Held, M., and R. M. Karp,-"The Traveling Salesman Problem and Minimum i Spanning Trees, Part II," Math. Prog., 1: 6-25 (1971)(AM). 47. Hellerman, H., and T. F. Conroy Computer System Performance, McQraw-Hill, New York, 1975(AM). Гл. 7. Дополнительные замечания и ссылки 340 48. Huntsberger, D. V„ and P. Billingsley, Elements of Statistical Inference, 3d ed., Allyn and Bacon, Boston, Mass., 1973(EM). 49. Ingalls, D. H. H., "FETE: A Fortran Execution Time Estimator," Tech. Rept. ) STAN-CS-71-204, Stanford University; Stanford, Calif., 1971(E). 50. Johnson, D., "Approximation Algorithms for Combinatorial Problems," J. Comput. Syst. Sci., 9: 256-278 (1974)(AM). 51. Karp, R. M., "On the Computational Complexity of Combinatorial Problems," Networks, 5: 45-68 (1975)(AM). 52. Kaufmann, A., Graphs, Dynamic Programming and Finite Games, Academic, New York, 1967(IM). 53. Kautz, W. H., K. N. Levitt, and A. Waksman, "Cellula' Interconnection Arrays," IEEE Trans. Comput., C-17: 443-451 (1968)(IM). 54. Kernighan, B. W., and P. J. Plauger, The Elements of Programming Style, McGraw-Hill, New York, 1970(E). . 55. King, C. A., "A Graph-Theoretic Programming Language," in R. C. Read (ed.), /P^ Graph Theory and Computing, Academic, New York, 1972, 63-74(1). ^ 56. Knuth, D. E., Fundamental Algorithms, The Art of Computer Programming, vol. 1, ^ Addison-Wesley, Reading, Mass., 1969a(AM). 1 57. ———, Seminumerical Algorithms, The Art of Computer Programming, vol. 2, Addison-Wesley, Reading, Mass., 1969b(AM). 58.———, "An Empirical Study of Fortran Programs," Software Pract. Exper., 1: 105-133 (1971)(E). 59.———i Sorting and Searching, The Art of Computer Programming, vol. 3, Addison-Wesley, Reading, Mass., 1973(AM). 60. ———, "Estimating the Efficiency of Backtrack Programs," Math. Comput., 29: 121-136.(1975)(IM). 61. LaSalle, J. P., The Influence of Computing on Mathematical Research and Education: Proc. Symp. Appl. Math., vol. 20, American Mathematical Society, Providence, R.I., 1974(AM). , 62. Lawler, E„ Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1975(AM), 63. Lenstra, J. K., and A. H. G. Kan Rinnooy, "Some Simple Applications of the Traveling Salesman Problem," Publication BW 38/74, Mathematisch Centrum,- Amsterdam, 1974(AM). 64. Lin, S., and B. W. Kernighan, "An Effective Heuristic Algorithm for the Traveling Salesman Problem," Oper. Res., 21; 498-516 (1973)(l). 65. Little, J. D. C„ K. G. Murty, D. W. Sweeney, and C. Karel, "An Algorithm for the Traveling Salesman Problem," Oper. Res., 11: 979-989 (1963)(IM). 66. Liu, C, L., Introduction to Combinatorial Mathematics, McGraw-Hill, New York, 1968(IM). 67. Luce, R. D., and H. Raiffa, Games and Decisions, Wiley, New York, 1957(AM). 68. Martin, C., and D. S. Richards, "CLAMAR: A Combinatorial Language," Tech. Rept. 75-5, Department of Applied Mathematics and Computer Science, University of Virginia, 1975(1). 69.'Martin, W. A„ "Sorting," Comput. Surv., 3: 148-174 (1971)(l). Гл. 7. Дополнительные замечания и ссылки 70. McGowan, С. L., and J. R. Kelly, Top-Down Structured Programming Techniques, Petrocelli/Charter, New York, 1975(E). 71. Meltzer, В., and D. Michie, Machine Intelligence 7, Wiley, New York, 1972(AM). 72. Minsky, M., Computation: Finite and Infinite Machines, Prentice-Hall, Englewood Cliffs, N.J., 1967(IM). 73. Mood, A. M., and F. A. Grayblll; Introduction to the Theory of Statistics, McGraw-Hill, New York, 1963(IM). 74. Mooney, J. W., "Organized Program Maintenance," Datamation, 21: 63-64 (1975) (Е). 75. Nievergelt, J., J. C. Farrar, and E. M. Reingold, Computer Approaches to Mathemati- cal Problems, Prentice-Hall, Englewood Cliffs, N.J., 1974(IM). 76. Nilsson, N. J., Artificial Intelligence, McGraw-Hill, New York, 1971(IM). 77. Page, E. S., and L. B. Wilson, Information Representation and Manipulation in a Computer, Cambridge, London, 1973(IM). 78. Polya, G„ How to Solve It, Doubleday, Garden City, N.Y., 1957(EM). 79. ———, Mathematical Discovery, vols. 1 and 2, Wiley, New York, 1962(EM). 80. Prim, R. C., "Shortest Connection Networks and Some Generalizations," Bell Syst. Tech. J., 36: 1389-1401 (1957)(IM). 61. Boss, S. M., Introduction to Probability Models, Academic, New. York, 1972(IM). 82. Scarne, J., Scame's Complete Guide to Gambling, Simon and Schuster, New York, 1961(E). 63. Singleton, R. R., and W. F. Tyndall, Games and Programs: Mathematics for Modeling, Freeman, San Francisco, 1974(IM). 84. Slotnick, D. L., "The Fastest Computer," Sci. Am., 224: 76-88 (1971)(E). 65. Snell, J. L., Introduction to Probability Theory with Computing, Prentice-Hall, En- glewood Cliffs, N.J., 1975(EM), 86. Spencer, D. D., Game Playing with Computers, Spartan, New York, 1968(E). 87. Stone, H., Introduction to Computer Organization and Data Structures, McGraw-Hill, New York, 1972(1). 88. Tarjan, R., "Depth-First Search and Linear Graph Algorithms," SIAMI, CompMt.,1: 146-160 (1972)(IM). 89. Trakhtenbrot, B. A., Algorithms and Automatic Computing Machines, Heath, Boston, Mass., 1963(1M). 90. Traub, J. F., "Numerical Mathematics and Computer Science," Comm. ACM, 15: 537-541 (1972)(IM). 91. ——— (ed.), Complexity of Sequential and Parallel Numerical Algorithms, Academic, New York, 1973(IM to AM). 9Z. Van Tassel, D., Program Style, Design, Efficiency, Debugging, and Testing, Prentice-Hall, Englewood Cliffs, N.J., 1974(E). 93. Von Neumann, J., and 0, Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princetdn, N.J., 1944(AM). 94. Webb, M. H. J., "Some Methods of Producing Approximate Solutions to Traveling Salesman Problems with Hundreds or Thousands of Cities," Oper. Res. Q., 22.: -' 49-66 (1971)(E). 95. Wegner, P., Programming Languages, Information Structures, and Machine Гл. 7. Дополнительные замечания и ссылки 351 Organization, McGraw-Hill, New York, 1968(1). 96. Wickelgren, W. A., How to Solve Problems: Elements of a Theory of Problems and Problem Solving. Freeman, San Francisco, 1974(EM). 97. Williams, J. D„ The Compleat Strategyst, McGraw-Hill, New York, 1966(EM). 98. Winkler, R. L., Introduction to Bayesian Inference and Decision, Holt, Rinehart and Winston, New York, 1972(IM). 99 Yohe, J. M., "An Overview of Programming Practices," Comput. S.urv,, 6; 221-245 (1974)(E). ИМЕЕТСЯ РУССКИЙ ПЕРЕВОД К СЛЕДУЮЩИМ РАБОТАМ: 1. Ахо А., Хлопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.— M.: Мир, 1979. Y2. Баррон Д. Рекурсивные методы в программировании.—M.: Мир, 1974. / 8. Берзтисс А. Структуры данных.— M.: Статистика, 1974. у' 9. Басакер Р., Саати Т. Конечные графы и сети.— M.: Наука^ 1974. 15. Кокс Д., Хинкли Д. Теоретическая статистика.—M.: Мир, 1978. V16. Дал У., Дейкстра Э., Хоор К. Структурное программирование.— M.: Мир, 1975. 25. Феигенбаум Э. Вычислительные машины и мышление.— M.: Мир, 1967. 26. Феллер В. Введение в теорию вероятностей и ее приложения.— M.: Мир, 1967. 36. Гарднер M. Математические головоломки и развлечения.—M.: Мир, 1971. 37. Гарднер M. Математические досуги.— M.: Мир, 1972. "^б. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы.— M.: Мир, 1976. '.57. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алго- ритмы.— M.: Мир, 1977. V'59. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск.— M.: Мир, 1978. 67. ЛьюсР., Райфа X. Игры и решения.—M.: ИЛ, 1961. "72. Минский M. Вычисления и автоматы.—M.: Мир, 1971. 75. Нивергельт Ю., Феррар Дж., Рейнголд Э. Машинный подход к решению мате- матических задач.— M.: Мир, 1977. 76. Нильсон H. Искусственный интеллект. Методы поиска решений.— M.: Мир, 1973. 78. Пойа Дж. Как решать задачу. Пособие для учителей.—M.: Учпедгиз, 1961. 79. Пойа Дж. Математическое открытие. Решение задач: основные понятия, изуче- ние и преподавание.— M.: Наука, 1970. \93. Фон Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение.— M.: Наука, 1970. Работа [87] — Трахтенброт Б. А. «Алгоритмы и вычислительные автоматы» — была выпущена издательством «Советское радио» в 1974 г. Приложение А. Соглашения, принятые для описания алгоритмов В этом приложении содержится объяснение соглашений, которые применялись при изложении алгоритмов в этой книге. Мы говорим «соглашения», а не «правила», потому что они не подразумеваются зафиксированными раз и навсегда; наоборот, подразумевается, что эти соглашения достаточно гибкие для того, чтобы изложить любой алгоритм в виде, удобном для чтения и понимания. Далее следует пример (из разд. 1.2) формы, в которой были опи- саны алгоритмы. Algorithm MAX. Даны N действительных чисел в одномерном массиве /?(!), R{2), . . ., R(N}; найти такие М и J, что M=^R(J)= max R(K). В случае, когда два или более элементов R имеют кк<л' наибольшее значение, выбирается наименьшее значение J. Шаг 0. [Инициализация] Set М-(- R(\); and J-f-\. Шаг 1. W=1?J If N---1 then STOP fi. Шаг 2. [Проверка каждого числа] For К. -<— 2 to N do шаг 3 od; and' STOP. Шаг 3. [Сравнение] If M0 od. Шаг f+1. [ 1 Операторы. Шаг f+2. [ 1 Операторы. Шаг f+3. [ 1 Операторы. Шаг f+4. [ ] Операторы. Порядок выполнения цикла 2 следующий: выполняются шаги г'+1, f+2 и f+3, затем проводится проверка, положительно ли J: J>0; если ./^0, то следующим выполняется шаг f+4; если J>0, то выполняются опять шаги f+1, f+2 и f+3 и J еще раз сравнивается с нулем и т. д. Предполагается, что где-то в пределах шагов f+1, f+2 или f+3 значение J меняется; в противном случае существует возможность бесконечного цикла. 3. Шаг i. [ 1 While PTR>0 do PTR ^- LEFT (PTR) od. 4. Шаг i. [ ] While J>0 do through шаг f+2 od. Шаг f+1. [ 1 Операторы. Шаг f+2. [ ] Операторы. Шаг f+3. [ 1 Операторы. Выполнение цикла while-do отличается от выполнения цикла do-while только тем, что в одной форме проверка осуществляется перед первым выполнением шага (шагов), предписанного оператором do, а не после. Использование od, как в форме 3, служит для опре- деления конца действия do; его применение идентично применению fi. 5. Шаг i. [ ] For / •<- 1 to N do шаг f+1 od. Цель формы 5 — допустить выполнение типичного DO- или FOR- цикла с приращением, равным 1, вместо^ тй.го,^ чтобы инициализиро- ватъ__индексную переменную / и увеличивать ее внутри цикла" do- while или while-do. 356_______________Приложение А. Соглашения для описания алгоритмов Операторы goto. Хотя принципы структурного программирования исключают потребность в операторах goto', иногда встречаются си- туации, когда goto кажется подходящим и естественным средством. В таких случаях алгоритмы бывают обычно очень короткими, и при- менение операторов goto не мешает пониманию логики алгоритма. Поэтому мы умеренно используем операторы goto. Приложение Б. Множества и некоторые основные алгоритмы на множествах Множества являются наиболее общей из всех математических структур и появляются почти в каждой математической модели. Часто задачи моделируются в терминах множеств, а алгоритмы реше- ния формулируются в терминах основных операций на этих множе- ствах. Реализация любого алгоритма может включать различные способы представления множеств и их обработки. Это приложение не является «введением в теорию множеств». Скорее оно предполагает знание основ теории множеств и операций над ними. В какой-то мере мы хотели установить обозначения, ис- пользуемые в книге, но основная цель приложения — ознакомить читателя с некоторыми вопросами, возникающими при использова- нии множеств для реализации алгоритмов. Б.1. Обозначения 1. Множества обозначаются латинскими заглавными буквами, а элементы множеств изображаются строчными буквами; например, U={r, s, t, и, v, w}. 2. и ^ U v — элемент множества U. v^rU v — не является элементом множества U. V^U V—подмножество U, т. е. каждый элемент V является также элементом U. V<=.U V—собственное подмножество U, т. е. существует эле- мент U, который не является элементом V. 3. V=0 V— пустое множество, т. е. в V нет элементов. 4. |V| Кардинальность V^ т. е. для конечных множеств число элементов -в. V. 5. U (J V Объединение множеств U и V, т. е. множество, состоящее из всех элементов U и всех элементов V. U П V Пересечение множеств U и V, т. е. множество, со- стоящее из всех элементов, являющихся одновре- менно элементами и U, и V. V—U Разность V и U, т. е. множество, состоящее из тех элементов V, которые не являются элементами U. V^:U,V Если V—подмножество U, тогда V обозначает дополнение V в U, т. е. V=U—V. 6. Если y={yi, Ua, • • •> Уп} — Конечное множество действительных 358 Приложение Б. Множества и алгоритмы на множествах чисел, то п п '^v^^v^+v.,Jr...+v^ и ГIy;=t'lг•'2•••У,•, означают соответственно сумму и произведение всех элементов V. 7. Г^П Наименьшее ^ие^ое^чиало, большее или равное у,. |_ v; J Наибольшее целое число, меньшее или "'равное Vi. 8. [У |=оо V—бесконечное множество, т. е. оно содержит бесконечное счетное число элементов. | V | < оо V — конечное множество. 9. Если I, k—положительные целые числа, то i\=ix (i—1)х. . .X Х2Х1 читается «f-факториал» (см. разд. 4.5). ()) читается «число сочетаний из i по /» и означает число способов выбора / разных объектов из i разных объектов. 10. Гармонический ряд — это бесконечный ряд рациональных чисел 1+^+T+T+•••+^+••- ^=144+---+^f:T t=i называется N-и частной суммой гармонического ряда. Б.2. Применение множеств и операции на множествах Как узнать, является ли данный элемент и элементом множества У? Глядя на У и проверяя, находится ли и там, не правда ли? Про- блема, однако, состоит в следующем: как может ЭВМ «смотреть» на V и проверять наличие иГ Это задача представления множества в ма- шине. Здесь будет дан один очень простой ответ. Возможны и другие ответы. Особенно простое представление возможно, если мы предпола- гаем, что все рассматриваемые множества являются подмножествами некоторого конечного универсального множества U. Пусть U содер- жит п различТЯых^элёментов, помеченных как 1,2, . . ., п (каждый элемент помечен определенным целым числом). Мы можем предста- вить любое подмножество V множества U цепочкой, или последова- тельностью, нулей и единиц. Если t-я позиция, или бит, этой цепочки есть 1, тогда элемент под номером i и обозначаемый у, находится в V, если же там 0, то v^V; например, если в U шесть элементов, то V= (0,0,1,0,1,1) Приложение Б- Множества и алгоритмы на множествах 359 представляет множество V, состоящее из элементов Уз, У„ и ^ и 0= (0,0,0,0,0,0) представляет пустое множество (всегда обозначаемое е), не содер- жащее ни одного элемента, в то время как [/==(1,1,1,1,1,1). Любая такая последовательность, представляюща'я~"мнЬжествсГ V, известна как характеристический вектор V (по отношению к U). Если U содержит п элементов, сколько имеется различных под- множеств [/? Заметим, что если \U\ меньше, чем число битов в слове вашей ЭВМ, то можно представить любое VsU одним словом памяти. Как тогда мы проверяем справедливость принадлежности v ^ У? В представлении характеристическим вектором мы смотрим, какая целочисленная метка была поставлена в соответствие v. Предположим, что это i. Тогда мы проверяем i-й бит в последовательности, представ- ляющей У. Если там стоит 0, то и^У, в противном случае v ^ У. Операция объединения множеств легко реализуется с помощью характеристических векторов. Все, что надо сделать, .чтобы получить _Лц^В, это «сложить» характеристический вектор, представляющий Л, с вектором, представляющим В. Мы проделываем это «сложение» покомпонентно при условии, что «сумма» двух единиц есть единица. Такое модифицированное сложение называется операцией двоичного ИЛИ и обозначается символом V- Основные правила этой'ойерацйи сведеньТ в четыре формулы: 1V1=1 1VO=1 OVl=l ovo==o Для примера пусть \V\=7; рассмотрим два характеристических вектора Л=(1,0,1,0,1,1,0) В== (1,1,0,0,1,0,0) Тогда Лий=(1,1,1,0,1,1,0) На многих ЭВМ эта реализация операции объединения может быть выполнена одной операцией, если \U\-S^ размера основного машинного слова. В противном случае нам может понадобиться \U\ операций. Мы можем также определить операцию двоичного Я Л и восполь- зоваться ею, чтобы сформулировать алгоритм для представления Л П.В характеристическим вектором из представлений для Лий. Аналогично операция .NOT. (не) может быть определена для представления дрполления~множества. Каковы другие операции на множествах, которые никогда не 360 Приложение Б. Множества и алгоритмы на множествах рассматриваются в математических курсах, но которые следует де- тально рассматривать для машинной реализации? Задумайтесь над этим вопросом, прежде чем читать дальше. По поводу операции исключения элемента и из множества V, обозначаемой V—{и}, можно сказать следующее: она требует одного шага, если использовать представление характеристическими век- торами. Далее, существует проблема отыскания элемента v. Какое из нашего текущего набора множеств содержит v (если какое-нибудь содержит)? Это пример задачи поиска. Более общие задачи поиска требуют отыскания всех элементов, обладающих некоторыми свой- ствами. Часто бывает, что рассматриваемые элементы множеств все яв- ляются действительными ^или целыми числами и могут быть упорядо- чены естественным образом, т. е. с использованием отношения между действительными числами «равно» и «больше, чем». Другие множе- ства элементов также могут быть упорядочены некоторым естествен- ным или хорошо определенным способом. Можете ли вы придумать несколько примеров? ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Анкер мана функция 147 Алгоритм (algorithm) 14 —, анализ 27, 193 — генерации случайных чисел (random number generation) — — — - LCM 330 — — — — MS 329 _ _ _ _ NRN 333 — — - — PNRN 335 — Дейкстры 312 — для тура коня 43—44 — извлечения несмещенной выборки (unbiased sample selection) 321 — — — — SELECT 324 — — — — SS 322 — — — — TRYAGAIN 321 — исчерпывающий (exhaustive) 20, 25 — отыскания остовного дерева мини- мального веса 184, 343 — параллельной сортировки (prallel sort) 292 — поиска в глубину (depth-first search) 150—151 — — в ширину (breadth-first search) 158 — полиномиальный 23 —, полное построение (complete deve- lopment) 13 — построения магических квадратов 298 — , правильность (correctness) 21 — Прима 185 — , разработка (design) 19—20 — , реализация (implementation) 22 — , сложность (complexity) 23 — сортировки (sorting) 96 — с отходами (backtracking) 129 — управления страничной памятью (paging algorithms) 268, 344 — — — — FIFO 269 — — — — LFU 279 — — — — LRU 269, 273 — эвристический (heuristic) 63, 113 — экспоненциальный 23, 25 — А 184 — BFS 158 — BSEARCH 242 — CONNECT 56 — DELETE 69 — DEMS 301 — DFS 150—151 —- ETS 20, 25 — GTS 113 — GTS2 114 — HEAP 234 — HEAPSORT 234 — INSERT 70 — ITP 263 — МАХ 15 — ODDMS 298 — PARSORT 292 — POSTFIX 260 — PRIM 185, 210 — QUICKSORT 226 — SIS 96 — SOLLIN 287 — WELLFORMED 79 Амдаля эффект 285 Анализ сложности (complexity analysis) 193 — — алгоритма _ _ _ _ BSEARCH 245 _ __ _ _ BTSI 249 — — — — DFS 154 — — — — DIJKSTRA 318 — — — — ETS 25 — — — — HEAP 234 _ — _ _ PARSORT 295 — — _ — PRIM 194, 209 — — — — QUICKSORT 225, 229 — — — — SIS 98 — — — — SOLLIN 289 — трудоемкости алгоритма (performance analysis) 85, 341 Арифметическое выражение 256 Блок-схема (flow-chart) 31 362 Предметный ук азател ь — алгоритма ветвей и границ 136 — — для задачи о пшенице, мышах и кошках 172 — — — тура коня 43 — — CONNECT 57 — — DELETE 71 — — INSERT 74 — — ITP 264 —_ _ PRIM 186, 190 — — SIS 97 — — — DIJKSTRA 314 — — — PARSORT 293 — — — POSTFIX 261 _ — _ QUICKSORT 211 _ _ _ SOLLIN 288 — — — SS 323 Документация программы (documentati- on) 28, 217, 344 Дуга (arc) 50 Вектор смежности (adjacency vector) 54 Вероятностная модель (probabilistic пю:1е1) 85 Вероятность события (probability of an event) 89 Ветвление (branching) 131 Вершина (vertex) 49 — изолированная (isolated) 50 — разделяющая (cut-vertex) 51 Взвешенная сеть (weighted network) 50, 182 Виртуальная память 266 Внешняя документация (external docu- mentation) 217 Выборка (sample) 99, 321 Выражение отношения 257 Высота дерева (height) 59 Вычисление границ (bounding) 133 Ганта схема 118 Генератор случайных чисел (random num- bers generator) 326, 346 Глубина рекурсии 146 Головоломка «8» 127 Граф (graph) 19 Данные входные и выходные (input, out- put) 220 Дважды рекурсивная функция 147 Дейкстры алгоритм 312 Дек (deque) 84 Дерево (tree) 45, 57, 82, 340 — корневое (rooted tree) 59 — — двоичное (binary) 59 — остовное (spanning tree) 61, 181 — рекурсивное (recursive tree) 82 — решений (decision tree) 237 Диаграмма сортировки 293 Динамическое программирование (dy- namic programming) 341 Дискретная случайная переменная 94 Дискретные события (discrete events) 167 Дисперсия (variance) 95 Доказательство правильности алгоритма (proof of correctness) — — — DFS 154 Задание (job) 118 Задача коммивояжера (traveling sales- man problem) 16, 132, 342 — об изоморфизме сетей 63 — — упаковке (packing) 120 — — — рюкзака 124 — о велосипедном замке 125 — — джипе 109, 341 — — количестве разбиений целого чис- ла (partitions) 147 — — пшенице, мышах и кошках 170 — — Ханойской башне 112 — статистическая 99 Закон больших чисел 101 Замкнутый маршрут (closed walk) 51 Игра «нимбы» (nimbi) 302, 345 Идентификатор 149 Изоморфизм 61 Имитационные алгоритмы 164 Инвариант сети (network invariant) 62 Интегральная функция распределения (cumulative distribution function; 333 Инфиксная форма выражений (infix form) 259 Инцидентность 49 Испытание (trial) 88 Итерация 31 Код сети (coding of a network) 63 Комментарий (comment) 28, 218 Компонента сети (component of a network) 51 Контекстно-свободные правила (con- text-free rules) 256 Корень дерева (root of a tree) 59 Латинские квадраты (latin squares) 308 Лес (forest) 57 Линейное программирование 342 Линейный связанный список (linear lin- ked list) 68 Логическое выражение 257 Предметный указатель 363 Магические квадраты (magic squares) 112, 297, 345 Маршрут (walk) 51 Массив (array) 66 Математическое ожидание (expected value) 94 Матрица инцидентности (incidence mat- rix) 53 — смежности (adjacency matrix) 53 — стоимостей (cost matrix) 19 Метод ветвей и границ (branch and bo- und) 131, 342 — линейный конгруэнтный 330 — отрабатывания назад (working ba- ckward) 108, 341 — планирования событий (event sche- duling) 167 — подъема (hill climbing) 107, 114, 341 — поиска в глубину (depth-first search) 150 — — в ширину (breadth-first search) 154 — середины квадрата (middle-square method) 106, 341 — сортировки 344 — — «быстрый» (quicksort) 226 — — «пирамидой» (heapsort) 230 — — простыми включениями (straight insertion sort) 97 — — «пузырьками» (bubble sort) 240 Минского гипотеза 295 Моделирование (simulation) 163, 341 — очереди (simulation of a queue) 165 Модель (model) 17 — сетевая (network model) 19 Мост (bridge) 51 Мультипроцессорная система 87, 118 Мультиребра (multiedges) 49 Независимые случайные переменные (in- dependent random variables) 104 Неориентированное ребро (undirected edge) 49 Непрерывная случайная переменная (continuous random variable) 326 Несмещенная оценка (unbiased estima- tor) 100 Нормальное распределение (normal dis- tribution) 327 Обслуживание программы (maintenance) 220, 344 Объединяющая вершина (collecting ver- tex) 31 Ориентированная сеть (directed network) 50 Остовная подсеть (spanning subnetwork) 51 Открытый маршрут (open walk) 51 Отладка программы (debugging) 197 Оценка (estimator) 100 — несмещенная (unbiased) 100 — согласующаяся (consistent) 101 Очередь (queue) 80 Параллельные машины (parallel machi- nes) 284, 345 Пирамида (heap) 229 Поиск (search) 344 — двоичный (binary) 242 — кратчайшего пути (shortest path) 309, 345 Полиномиальный алгоритм 23 Полная сеть (complete network) 65 Порядок функции (order of a finction) 24 Постановка задачи (statement of the prob- lem) 16 Постфиксная форма выражений (post- fix form) 259 Правильность алгоритма (correctness of an algorithm) 187 Предикатная вершина (predicate vertex) 31 Представление задачи (problem repre- sentation) 18 — сети 53 Префиксная форма выражений (prefix form) 259 Приведение (reduction) 133 Приоритет операций (priority) 263 Проверка программы (testing) 26, 197 Программирование сверху-вниз (top- down) 22, 31, 339 — с отходом назад (backtrack program- ming) 125, 342 — структурное (structured) 9, 31, 339 Программная документация (program documentation) 217 Пролог программы 218 Пространство элементарных событий (sample space) 87 Профиль исполнения программы (exe- cution profile) 29, 203 Процедура (procedure) 14 — Хаффмана и Циммермана 252 Процессор (processor) 118 Псевдослучайные числа (pseudorandom numbers) 329 Путь (path) 51 Разбиение целого числа (partition) 147 Развертывание циклов (loop unrolling) 202 364 Предметный указатель Разделяющая вершина (cut-vertex) 51 Распределение вероятности (distributi- on) 93 Реализация (implementation) — алгоритма Дейкстры 314 — — для тура коня 44 — — BFS 160 — — BSEARCH 243 — — BTSI 248 — — DELETE 72 — — DFS 155 — - FIFO 271 — — HEAP 235 — — HEAPSORT 235 — — INSERT 75 — — LFU 279 — — LRU 273 — _ PRIM 191 — очереди 82 — рекурсии на Фортране 148 — — — Алголе 149 Ребро (edge) 49 Рекурсия (recursion) 145, 342 Сеть (network) 16, 47, 340 — взвешенная (weighted network) 50 — двудольная (bipartite) 65 — — полная (complete) 65 — несвязная (disconnected) 51 — связная (connected) 51 Система с дискретными событиями 167 Слияние вершин (fusion) 56 Сложность (complexity) 23 Событие (event) 88, 165 Соллина алгоритм 287 Сортировка (sorting) 96, 223, 344 Список связанный (linked list) 67—68 — смежности (adjacency list) 72 Стандартное отклонение (standard de- viation) 95 Статистическая задача 99 Стек (stack) 78 Стековая память (pushdown store) 78 Степень вершины (degree of a vertex) 50 Стоимость тура (cost of a tour) 20 Страница памяти (page) 267 Страничный отказ (missing page fault) 267 Структура данных (data structure) 65 — древовидная (tree structure) 45 — управления программы (control stru- cture) 31, 45 Структурная блок-схема (structured flow-chart) 31 Структурное программирование (stru- ctured programming) 9, 31 Тестовые данные (test data) 199 Тройная дуэль 305, 345 Тур (tour) 19 — коня 36 Узел (node) 50 Указатель в списке (связь) (pointer, link) 68 Управление страничной памятью (paging) 268, 344 Функциональная вершина (function ver- tex) 31 Хаффмана и Циммермана процедура 252 Центральная предельная теорема 328, 332 Цепочка обращений (reference string) 269 Цикл (cycle) 51 Частотная интерпретация вероятности 89 Числа Фибоначчи 145 ЭВМ Иллиак IV 291, 345 Эвристика 113, 341 Эвристический алгоритм (heuristic al- gorithm) 63, 113 Экспоненциальное распределение 334 Экспоненциальный алгоритм 23, 25 Экстраполяция 215 Эффективность реализации алгоритма (implementation efficiency) 200 Язык параллельного программирования 290 — — — IVTRAN 291 NP-полные задачи 347 ОГЛАВЛЕНИЕ От редактора перевода . . ........................ 5 Предисловие .... ........................... 7 Глава!. Полное построение алгоритма ................... 14 1.1. Введение .... ........................ 14 1.2. Алгоритмы .... ........................ 14 1.3. Основные этапы полного построения алгоритма ......... 16 Глава 2. Некоторые основные приемы и алгоритмы ............ 30 2.1. Структурное программирование сверху-вниз и правильность программ 30 2.2. Сети .... .......................... 47 2.3. Некоторые структуры данных . . ................ 66 2.4. Элементарные понятия теории вероятностей и статистики ..... 85 Глава 3. Методы разработки алгоритмов ................. 106 3.1. Методы частных целей, подъема и отрабатывания назад ...... 106 3.2. Эвристики .... ........................ 113 3.3. Программирование с отходом назад . . .............. 125 3.4. Метод ветвей и границ . .................... 131 3.5. Рекурсия .... ........................ 145 3.6. Моделирование .... ..................... 163 Глава 4. Полный пример . . ....................... 181 4.1. Построение алгоритма для отыскания остовного дерева минимального веса .... ..................•.•••••• 181 4.2. Проверка программ ... ................•••• 197 4.3. Документация и обслуживание . . ................ 216 Глава 5. Алгоритмы машинной математики ................ 222 5.1. Сортировка .... ..............••••••••• 223 5.2. Поиск .... ................•••••••••• 241 5.3. Арифметические и логические выражения . ........... -'оо 5.4. Страничная организация памяти . . ...........•••• 266 5.5. Параллелизм .... ...........•••••••••••• —З 366 ________________________________________Оглавление Глава 6. Математические алгоритмы . .................. 297 6.1. Игры и комбинаторные головоломки . ............. 297 6.2. Кратчайшие пути ... ..................... 309 6.3. Вероятностные алгоритмы ... ................. 320 Глава 7. Дополнительные замечания и ссылки ............... 338 Приложение А. Соглашения, принятые для описания алгоритмов ...... 352 Приложение Б. Множества и некоторые основные алгоритмы на множествах . 357 Предметный указатель ......................... 361 С. Гудман, С. Хидетниеми ВВЕДЕНИЕ В РАЗРАБОТКУ И АНАЛИЗ АЛГОРИТМОВ Научный редактор К. Г. Катаев Мл. научный редактор Л. С. Суркова Художник А. В. Шипов Художественный редактор В. И. Шаповалов Технический редактор Л. П. Бирюкова Корректор М. А, Смирнов ИБ Л'« 2089 Сдано в набор 5.03.81. Подписано к печати 17.07.81. Формат 60х90'/,,. Бумага типографская № 1. Гарнитура литературная. Печать высокая. Объем 11,5 бум. л. Усл. печ. л. 23. Усл. кр. отт. 23, Уч.-изд. л. 23,61. Изд. № 1/0941. Тираж 37 500 экз. Заказ № 2658. Цена 2 руб. ИЗДАТЕЛЬСТВО «МИР» Москва, 1-й Рижский пер., 2 Ордена Октябрьской Революции и ордена Трудового Красного Знамени Первая Образцовая типография имени А. А. Жданова Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли. Москва, М-54, Валовая, 28 INTRODUCTION TO THE DESIGN AND ANALYSIS OF ALGORITHMS S. E. GOODMAN S. T. HEDETNIEMI University of Virginia McGraw-Hill Book Company New York — St. Louis — San Francisco — Auckland — Bogota — Dusseldorf — Johannesburg — London — Madrid — Mexico — Montreal—New Delhi — Panama — Paris—Sao Paulo—Singapore- Sydney — Tokyo — Toronto 1977 С.ГУДМАН С.ХИДЕТНИЕМИ ВВЕ4ЖИЕ В BWbCW и/wni/B' 'АЛГОРИТМОВ Перевод с английского Ю. Б. Котова Л. В. Сухаревой Л. В. Ухова под редакцией В. В. Мартынюка ИЗДАТЕЛЬСТВО «МИР» МОСКВА 1981