Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 77
Текст из файла (страница 77)
Так как машина с произвольным доступом к памяти полиномиальным образом интерпретируема на машине элементарных логических операций 7., для доказательства ее полиномиальной интерпретируемости на некоторой машине Тьюринга Р(7 достаточно доказать полиномиальную интерпретируемость машины Е на машине Р(7. Кроме того, этим будет доказана полиномиальная интерпретируемость произвольных машин Тьюринга Т на машине Р(7. Теорема 9.3. Е-машина полиномиальным образом интерпретируется на машине Тьюринга.
Для доказательства нужна определенная техника программирования машин Тьюринга, и мы его опускаем, эоп КЛАССЫ ТРУДОЕМКОСТИ КОМБИНАТОРНЫХ ЗАДАЧ Размерность комбинаторных задач. Вопрос о размерности комбинаторных задач рассмотрим на примере задачи РЕЕТ (задачи сетевого или календарного планирования), которая формулируется следующим образом. Комплекс работ описывается сетью — ориентированным графом с двумя отмеченными вершинами — полюсами (вообще говоря, количество полюсов в сети может быть любым, но для «классической» задачи РЕЙТ их два), Каждая вершина о сети )»' соответствует определенному событию в процессе выполнения работ из данного комплекса: первый полюс — началу процесса, второй его концу, каждой работе соответствуют события ее начала и конца, могут быть и другие события.
Естественно, из первого полюса до. 371 стижимы все вершины сети событий М, а второй полюс достижим из всех вершин. Пусть пь о,,, и„— вершины сети Ф, причем о, — начало процесса, а и, — его конец. Если а; — начало некоторой работы, ьу — ее конец, а ~н — продолжительность,то сроки событий и, н п~ связаны одним из соотношений: Т~= =Т<+1ч, если продолжительность работы строго задана, или Т;)Т,+1н, если работа не может продолжаться меньше, чем (и единиц времени, или Т, — не начало работы, а событие, состоящее в том, что последнюю можно начинать.
Если п~ — начало некоторой работы, а п~ — конец работы, которая обязательно должна быть окончена, чтобы первую можно было начать, то Т,)Ть В дальнейшем равенства Т~ — Т,+Ь~ заменим неравенствами Т~)Т~+1„и Т~)Т~— Может случиться, что следующую работу нельзя начинать сразу после конца предыдущей, например, после укладки бетона надо дать ему застыть. Тогда обозначим Гц— время ожидания, и связь между сроками событий принимает уже привычный вид Т~)Т;+(;,. К такому же виду можно привести связь между концом йредшествующей работы о; и началом следующей пь когда времени ожидания нет: надо только положить 1ц=О (к тому же виду приводятся некоторые другие условия выполнения комплекса работ, причем значения 1п могут даже оказаться отрицательными).
Итак, каждому неравенству Т;)Тг+Ь, соответствует ориентированное ребро (пь о,) сети Ж. Обычно еще задается срок начала процесса Ть и требуется найти сроки Т~ (1=2,..., и), удовлетворяющие всем неравенствам и минимальности срока конца процесса Т„. Мы описали общие условия массовой задачи. Каждый ее вариант задается параметрами: число событий а, списком ребер (аь и;) сети М н соответствующими длительностями (ц. Эти варианты имеют разную размерность, с ростом которой естественно ждать увеличения сложности задачи. Однако понятие размерности определяют по-разному, Проще всего считать размерностью число вершин и в сети У, но с увеличением количества дуг сложность задачи тоже возрастает, да н увеличение количества значащих цифр в параметрах 1ц нрнводит к росту числа элементарных логических операций при интерпретации действий с ними.
Необходим глобальный параметр размерности, который к тому же годился бы для любых массовых задач. Если «содержательный» смысл такой задачи известен, то любой зтз ее вариант можно описать одним словом: нужно алгоритмически определить порядок параметров и их идентификаторы, если без последних нельзя обойтись, выбрать способы описания параметров и их идентификаторов в виде подслов, состоящих из символов некоторого алфавита, добавить к последнему символы-разделители, наконец, записать значения всех параметров с необходимыми идентификаторами и разделителями в порядке, который был алгоритмически определен. С учетом информационных возможностей многосимвольного алфавита, длина полученного слова множится на логарифм числа символов в нем по основанию 2.
Произведение естественно называть информационной сложностью варианта массовой задачи, Как было указано в $9.1, его иногда называют размерностью варианта. Таким образом, размерность варианта массовой задачи зависит от способа его описания. Дать независимое определение затруднительно. Кроме того, метод описания конкретных вариантов следует считать существенной частью задачи: от него зависит трудоемкость решения, например, существуют описания, в которых явно указан ответ.
Как описать вариант задачи РЕКТ7 Сеть Ж можно задать любым способом, которым задаются графы (см. 5 4.1), но проще всего — квадратной матрицей смежности !!зп(!,' ~ т=ь Кроме того, нужно задать соответствующие длительности. Будем описывать их тоже квадратной матрицей !!1ц!!,"=~ 7-~ с элементами, принимающими числовые значения, Если ем=О, т. е, ориентированного ребра (оь о,) в сети й7 нет, то значение гц не играет роли, но для упрощения формул, которые понадобятся в дальнейшем, мы рассматриваем такую переменную, принимающую числовые значения.
Длительности Гп (1, 1'=1, 2, ..., а) будем считать целыми числами: их измеряют с точностью до некоторой единицы времени (чаще всего — рабочего дня). Порядок вершин сети Ф, определяющий матрицы !!ен!! и !!1п!(,— почти произвольный; важно только, что п~ — это начало процесса, а о„— его конец. Количество а вершин сети У можнб определить по числу остальных параметров; его следует задать лишь для возможности контроля. Как описать решение рассматриваемой задачи? Оно состоит из сроков событий Т,, Тм ..., Т„, Срок начала процесса Т, можно не указывать: он должен быть равен О, но опять же для упрощения формул будем считать, что реше.
373 ние задачи описывается последовательностью чисел Ть Т„,, Т„. Так как мы рассматриваем целые значения 1н, можно потребовать, чтобы сроки Т~ тоже были целыми числами: если какое-нибудь решение задачи РЕКТ существует, то существует и решение с целыми значениями сроков. Однако решения может и не быть. Когда в сети Ф есть ориентированный цикл Я (с,„..., о;,, с,,) с положительной 8 суммой длительностей ~ч~ 1, „,+1,н„,не существует сроков ь 2 Тм(й=1, „., з), удовлетворяющих всем неравенствам ТЫ~~ ТМ-ъ + 1юь — Мл(й = 2, 3, ..., З); т;, ~ т;, + ~...,. Действительно, складывая эти неравенства, получаем 5 5 А= 4 т,„> ~ Т,„+~,,„н„+~„ц, 2=1 ь=3 откуда следует +~;... <о, ь=г что противоречит положительности суммы длительностей, соответствующих ребрам цикла Л.
Кроме того, если даже существуют значения Ть Ть ..., Т,, удовлетворяющие неравенствам Тз)Т~+Гп при ем=1 (1, 1=1, 2, ..., и), но в сети Ж нет ориентированной цепи Т.(оь..., о ), соединяющей начало процесса с~ с его концом и, то и при условии Т~= =О значение Т„не имеет минимума. Отметим еще, что решение может быть не единственным: пусть сеть У состоит из трех вершин аь см оз и трех ориентированных ребер (оь са), (сь сз) и (о~, сз), которым соответствуют неравенства: Т~>Т~+3; Та)Т~+8; Тзъ Т,+2.
Тогда сроки Т~ и Тз определяются однозначно — Т,=О, Т,=й, но Та может иметь любое значение от 3 до 6 включительно. Обозначим уе двоичную переменную, которая будет равна 1, если решение рассматриваемого варианта задачи РЕКТ существует, и 0 в противном случае, Значение этой переменной должно быть указано в ответе для варианта.
Если уз=О, то переменные Ть Тм ..., Т» не имеют смысла. Им могут быть присвоены любые значения или даже не 374 присвоены никакие (во многих алгоритмах решения задачи РЕЕТ какие-то значения всем или по крайней мере некоторым переменным Т! присваиваются всегда). При уз=1 значения Т!, Т„, Т, должны удовлетворять условиям задачи. Как оппсать задачу РЕЕТ в целом? Ее условия являются предикатами, зависящими от введенных нами переменных: Рм (есп Гм, Т„Т?) = [еп = О! !/(Т~ )» Т, + Гм), (!,у=1,2, ..., а); Р, (Т,) = (Т, = 0); Р„(егв епп ..., е,„, е„, .„, е„„, 1т!, ...
1!,! гм " 1!ь Т ) =Р ((ам !4," !у ! (Те)! — !) = л п =Р,(Т,) й! й й Р!т(есь Гм, Ть Тт); 1=! у=.! Р„, и ((е;;, 1!Д"! !." ! Т„) =1гО!О, ... О„ЯЯ вЂ” зто условие минимальности продолжительности ҄— — Т! =Т выполнения всего комплекса работы; Ржек ((~с!' Г!')1=! ! — !) = Д Т!~ Т2' "' ..., Т„!=)? Р„((е„., Г!т)'!,", (Т!)",,) — зто условие существования допустимого календарного плана. Таким образом, Р„, Р,,„,„и Р„, и.— это не предикаты, у которых количество аргументов должно быть фиксировано, а системы предикатов. Их арность, т.е. количество аргументов, определяется целым параметром л, Его и считают семантической размерностью варианта массовой задачи РЕЕТ.
Система предикатов Р ((е„, !!!)";=!!=!, (Т;)!= (в=1, 2, ...) описывает саму массовую задачу. В общем случае имеются два параметра семантической размерности и!, пз (отличающейся от ранее введенной размерности — приведенной длины описания варианта задачи). Массовая задача — зто система предикатов Р7'"'((Х!)!!!!, (У!)!ч!!'). Совокупность переменных Х(Х„... ..., Хчвч!) является описанием варианта данной массовой задачи, у(уь ..., у,!!„,! ) — описание гипотетического ответа, и если Р,"'"' (Х, У) истинно, то У вЂ” в самом деле ответ, Количества ~р(п,) переменных Хь описывающих вариант, и ф(пз) переменных Уб описывающих ответ, — заданные функции семантических размерностей кч и пь В зависимости от них заданы также области значений каждой переменной и сами предикаты Р.„"" (Х, У).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
