Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000, страница 2

Он начинает готовиться воды, уже возвестили о приходе тепла. н нач Предисловие к построению костров: в прошедшую зиму было пять охот (охоты будем идентифицировать числами), в которых отличились девять воинов (воинов идентифицируем буквами). В первой охоте т ни ись воины а, Й, р; во второй — воины с, у, й, р; в третьей— е отливоины а, И, у', р; в четвертой — воины 6, е, д, р; в пятой — воины а, с, е, р. Вождь чертит на земле расположение воинов в цепочках. Один вариант взаимного расположения воинов сменяет другой — костры не строятся. Неужели он лишился мудрости? Воин р ему не мешает — через него должны пройти все пять цепочек.

Воинов 6 и д следует поставить рядом, ибо ани отличились только в одной охоте — четвертой. Воины а и 6, с н И, е и у, д и 6 соответственно не должны находиться в одной и цепочке, так как ни одна из этих пар, например а и д, не отличалась в одной и той же охоте. Все эти рассуждения не дают вождю ключа к построению костров. Он снова начинает перебирать варианты взаимного расположения воинов в цепочках. П еб еребирать ему придется долго — число таких вариантов составляет около двух миллионов: Пв;! = 3! х 4! х 4! х 4( х 4! = 1 = 1 990 656, где в; — число охотников, отличившихся в 1-й охоте.

Костры не строились. Вождь вошел в пещеру и в изнеможении опустился на шкуру. Шкура... а что, если тем воинам, из-за которых не строились цепочки, выдать по шкуре за та, чтобы они "за ылии а своих геройствах в некоторых охотах. Такая изаб вость" воинов упростит процесс построения ритуальных костров. Выход найден. Он останется вождем!.. Ч итатель, чтобы легче следить за дальнейшими рассуждениями вождя, давайте построим матрицу Я = (д; ], каждой строке которой взаимно однозначно соответствует охота столбцу— и если '-й а у- ванн отличился в 1-й охоте, то д; = 1, в противном случае дб = 0: о 6 с д е У П й Р 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 1 0 1 О 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 Х ним снова отя глава племени и сохранил за собой шкуру вождя , перед о а встала проблема: каким образом построить аитуальные костры, истратив при этом минимальное число шкур? Что должен сделать вождь? С ушествовал такой обычай или нет — автору неизвестно.

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

Решению задач реальной размерности с учетом ограниченности временных и емкостных ресурсов ЭВМ н посвящен настоящий учебник. Учебник имеет двойное название. С точки зрения математика (внутренней) это — "Фундаментальные основы дискретной математики", с точки зрения пользователя (внешней) это — "Информационная математика". Книга написана на базе учебника "Основы дискретной математики" (М,: Высшая школа, 1986, 312 с).

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

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

Самарскому, академикам МАИ, РАЕН Д.А. Поспелову, С.А. Редкозубову, В.Н. Решетникову, академикам МАИ, член-корреспондентам РАЕН О.С. Бартеневу и И.Г. Шрамкову. Учебник создан в соавторстве с доцентом М.В. Горбатовой (ею написаны з1.9, 1.10, 2.10, 5.11) и академиком МАИ, член-корреспондентом РАЕН А.В. Горбатовым (им написаны з2.2,4.10,5.?в 5.10). Автор оар1еагег Соцйаге Ноаеаее Орегаге Ьоцш Агцаге. А. Коменорс ВВЕДЕНИЕ Вы, читатель, являетесь уже студентом высшей школы (университета, академии или института), и пора вам узнать, что понятие ШКОЛА (ЯСН01 А) есть аббревиатура, составленная из шести слов, приведенных в эпиграфе и принадлежащих перу известного чешского гуманиста, просветителя Амоса Каменнуса (1592-1671).

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

Под временной слооккосягью понимается время работы алгоритма, под емкосгяяой слоокяостью — объем памяти, необходимый для решения задачи. Временная и емкостная сложности являются функциями от размерности задачи. В настоящее время в связи с широким использованием вычислительной техники в различных сферах человеческой деятельности все большее значение приобретают вычисления на дискретных структурах — комбинаторные вычисления. Исследованию алгоритмов на дискретных структурах посвящены многочисленные публикации [2, 9, 11, 17, 18, 22, 25, 28, 29, 40, 431. Анализ трудностей, имевших место при поиске эффективных алгоритмов решения задач дискретной математики, привел к формулировке центральной теоретико-методологической проблемы дискретной математики — решению вопроса о возможности исключения перебора вариантов при решении задач на дискретных структурах.

Была выдвинута гипотеза, что для широкого класса задач дискретной математики, имеющих практический интерес, не существует эффективного алгоритма их решения, трудоемкость которого была бы полиномиальной функцией от размерности задачи. Эти задачи образуют класс ФР-полных задач, трудоемкость решения которых оценивается экспоиенциальной функцией. Согласно этой гипотезе задачи реальной размерности (равной нескольким сотням) не могут быть эффективно решены даже на ЭВМ будущих поколений. Действительно, если представить себе ЭВМ, в Веедеиие кохо ой символы используемой системы счисления или логики мокоторо сим о делируются различными состояниями атомов, прич чем масса ЭВМ авна массе Земли, то на основании общих законов физики эта ВМ не сможет даже в течение всех геологических эпох переработать больше 10гз двоичных разрндов информации [25). При решении же ФР-полных задач реальной размерности объем перерабатываемой информации превышает величину 10тз.

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

К эвристическим относятся алгоритмы широкого класса, начиная от ГСН-алгорнтмов (ГСН вЂ” грубая сила и невежество) и кончая ахитрыми", "жадными" и другими эвристическими алгоритмами. Название алгоритма соответствует тому виду эвристики, который определяет процедуру борьбы с перебором. Оценить, налько удалено полученное с помощью эвристического алгоритма решение от минимального в смысле значений функционала к ачества решения, принципиально невозможно. От этого существенн го о недостатка свободны характеризационные алгоритмы, струк- а оснотура которых была предложена автором в 60-х годах [9]. На о ванин характеризации проводимых комбинаторных преобразований можно найти минимальное решение без поиска всех эквивалентных решений, исключая их перебор. Характеризационный алгоритм решения задачи состоит из процедуры эквивалентирования и фактического получения решения.