Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 84

Независимо от результатов дальнейших вычислений соответствующую ветвь графика развивать не следует. Одновременно с подсчетом оценок строим дерево, например, развивая ветвь с наименьшей нижней границей (рис. 9.9). Последовательность рассмотрения вершин указана номерами возле них на рисунке. В данном примере числа 42 н 40 в вершинах № 8 и 9 являются значениями соответствующих вариантов. В вер- 410 ных работ, положение которых в рассматриваемой вершине уже зафиксировано.

Для них время начала 1", допустимое, т. е. 4,")Ги. Остальные ресурсные работы выписываются в порядке убывания т,. Для каждой из них 1~ равно сумме времени начала и продолжительности записанной перед ней (выше нее) ресурсной работы. Заполнив таблицу, находим Т=гпах Ть Если для ресурсных работ, положение которых в рассматриваемой вершине не зафиксировано, оказалось 1и)ги, то найденное Т вЂ” минимальное время выполнения комплекса работ для множества вариантов, соответствующих этой вершине, причем минимум достигается при выполнении ресурсных работ в порядке, указанном таблицей.

Если жс окажется, что для какой-либо ресурсной работы, положение которой не зафиксировано, 1и(7и, то найденное время Т является нижней границей для этого подмножества вариантов. Действительно, Т получено без учета того, что работы нельзя начинать раисе их раннего срока начала. При фиксации положения одной ресурсной работы № 8 получаем табл. 9.3. Таблица 9,3 Рис.

9.9 шинах № 3, 4, 6, 7, 11, 12 ветвление производить не следует по двум причинам: так как их оценки (на рисунке записаны в кружках) — минимумы для соответствующих групп вариантов и так как каждая из них больше уже полученного времени 1=40. Любой одной из этих причин достаточно для прекращения ветвления. ГЛАВА ДЕСЯТАЯ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 10.1. НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ЛИНЕЙНОЙ АЛГЕБРЫ И МНОГОМЕРНОЙ ГЕОМЕТРИИ Множество )с" всех упорядоченных последовательностей и действительных чисел г(г„г„..., г,) является и-мерным линейным пространством.

Сами последовательности называются точками этого пространства или п-мерными векторами, а числа г„гы ..., г„составляющие последовательность г~)с",— координатами точки (вектора) г. В частности, множество )с всех действительных чисел является одномерным линейным пространством. Действия сложения, вычитания векторов и умножения 4!1 Н5зЕДМЕТНЫИ УКАЗАТЕЛЬ Автомат 295 — автономный 298 — аснвхраннмй 327 — нннцнальный 295 — комбинационный 331 — логический 331 — Мнлн 313 — Мура 81З вЂ” недетермннированный 321 сплава связный 298 — частичный !неполностью овреде.

левнмй! 304 Акснома 218 Анснаматнзнруемость 243 Алгебра 37 — булеза логвческнх функций 58 — — множеств 37, 64 — 7Кегалкнна 71 лагман 50 — регулярных событнй 317 Алгоритм 144, 201 Алфавнт 17, 148 йрвфметнка формальная 236 Ассоцнатнвность 39 Базнс линейного пространства 413 Блок-схема алгоритма 152 — мэшнны Тьюринга !63, 167 Вулеан 37 Вектор 16 — лнвейного пространства 411 Вершнна 83 — концевая 110 Ветвь 1Н Вывод 218 — в грамнатн~ге 263 Глубина формулы 54 Гомоморфизм 40 — автоматов 299 Грамматнка 265 — блочная 288 — контенстная 265 — контекстаа-свободна» 265, 269 — неоднозначная 274 — неукорачнзаюшая 268 — пряведенная 277 — регулярная 265 — тнва 0 265 Граф 88 — бззнсный 127 звездный 97 — нсключевня Нб 476 ГраФ неарнентнровавный 88 однородный 96 — орвентнраванный 88, 124 переходов 295 полный 96 связный 101 — цнклнческн связный 109 эйверов 106 Группа 45 Данные 147 Двойственность 64 Декомпознцня автоматов 343 Дерево 109 — вывода 271 — манснмэльное 118 — орневтнровзпное Н 1 — с корнем Н1 Детермнннзацпя 321 Днагавальпый метод 23 Днаметр графа 102 Днзъюнкцня 53 Днстрнбутнвность 39 Длкиа маршрута 99 — пути 124 Доказательства 210 Дополнение графа 97 — множества 10 отношеннн 31 Достижнмость 126, 298 Дуга 88 Еднннца полугруппы 43 решетки 48 Зада за лннсйпого ярограммпровенвя 422 — — — двойственная 428 — линейная оптнмнзацнв 422 — 7УР-полная 387 о выполцнмостн КНФ 380, 392 — — каынах 378, 394 — — коммивояжере !!9 — — покрытня 379, 396 — — различных прсдставнтелях 120 — перебора 376 — сетевого планнрования (РЕЕТ! 371 — транспортная 439 Замкнутость 37, 73 Изоморфвзм 40 — автоьгвтов 299 графов 85 Имплнкант 68 Имплпкацня 53 Интервал 69 Интерпретация 87, 239 Инцидентность 88 Источник 319 Исчисление 218 — ассоциативное 261 — выекавыванвй 219 — нредикатов 228 — — с равенством 235 Йтерзцнв 284, 317 Класс У(Р 383 — трудоемкости задач 381 — эквивалентности 34 Коммутативиость 39 Комнаэвцня автоматов 343 — алгоритмов !63 машин Тьюринга 163 — отображений 38, 43 — путей 125 функций 26 Конкатенация 284, 3!7 Конфигурация машины Тьюринга !57 Конъюнкция 58 Конус 416 Корень дерева 111 Лес 109 Линейная комбинация 4!3 — независимость 413 Линейное лодлрострвнство 4!2 пространство 411 Маршрут 99 Матрица ннцидентности 90 — отношения 30 — смежности 92 Машина Тьюрнвга 155 — — универсальная 169 — — недетермнинрованная 382 Метатеорема 219 Многогранник 417 Множество 9 — бесконечное 10 — вЫПуклое 416 — конечное 10 — коитннуальяое 23 перечислнмое 207 — разрешимое 207 — счетное 22 Модель 239 Моноид 43 Мощность множества 10.

2! Мультнграф 83, 248 Неотлнчнмость 300 Непротиворечивость 241 Нереэрешнмость алгоритмическая !77, 204 †2 Нормальная Форма бзкуса 269 — днэъюнктнвиая (ДЙФ) 62 — — — совершенная (СДНФ) 56 — — конъюнктнвная (КНФ) 63 Нумерация алгоритмов 202 — вершин 129 Область значений 19 — истинности 30 Область определения 19 Образ 19 Обрэаующвя 44 Объединение множеств 13, 317 — отношений 31 — влементов решетки 47 Оператор (операция яад функцнямп! 179 — — — — автоматный 297 — — — — наименьшего числа (Ы-оператор) 186, 186 — — — — примитивно.рекурсивный (ПР-оператор) !84 — (шаг алгоритма) 152, М7 Онерацпя 37 Окределнтель 4!5 Отношение 29 — бинарное 30 — обратное 32 порядка 35 рефлексявное 32 — симметричное 32 — транзнтнвное 32 — эквивалентности 33 Отображение 24 — автоматное 297 Отрицание 62 Отсечение 405 Паросочетанае 1!7, !22 Переменная несуп!сствевная 5! — свободная 83, 229 — связаннва ВЗ, 229 Перебор 381 Пересечение графов 97 — множеств 14 — элементов решетки 47 Подалгебра 37 Подграф 97 Подмножество 10 Подформула 54 Покрытие 69 Поле 37 Полянам Жегалкниа 72 Полнота формальной теорие 243 — Функциональная 70 Полугрупка 43 — свободная 44 Правило вывода 218 — подстановки 60, 221 Предикат 80 — примитивно.рекурсивный 183 Предметная область 80 Предстввимость событий 314 Преобразование 24 — аффиииае 4!8 Проблема остановки !76 — самопрнменнмостн 204 — соответствия (комбииаторная про блема Поста) 259, 376 — эквивалентности алгоритмов МЗ вЂ” — слов в полугруппе 44.

253 Программа бинарная 849 Продукция 254 Проекцвя !8 Произведение грабюв 104 — скалярное 4!8 Протяженность 103 Прямая сумма 98 Прямое пронэведенве автоматов 336 — — графов 104 — — множеств 17, Путь 124 477 ',~.; 4' Л' Часть графе 97 Штрих Шеффера 53 Эквввалеатность ЗЗ вЂ” автоматов 301 — алгоритмов ШЗ вЂ” грамматик 263 — формул 65, 85 Эллипсоид 419 Радяус (графа) 102 — протяженности !04 Разбиение 15 Разность множеств 15 Размерность яомбннаторной задачи 871 — 3 73 Разрешимость Формальной теории Э(4 Ранг вершины максимальный 126 — — мвнимельный 128 — линейного подпростраиства 413 — системы уравнений 414 Расстояние в графе !О! — — линейном просхраястее 414 Ребро 88 — кратное 89 Рекурсия двойная !91 кратная 191 одновременная 187 — првмитнвная !80 Решетка 47 разбиений 48 Самодвойствениость 64 Самоярнменимость 204,И2 Связность 10! Семаятика 214, 240 — Формальных языков 292 Сеть пз автоматов 334 — — языков 289 Снктаксяс И4, 240 Система комайд !49, 153, 34У вЂ” подстаиовок (полуснстема Туа) 260 — Поста каноническая 254 аормальиая 263 — Туэ 251 — уравнений 4!4 — формальная 216, 246-249 Слово 17, 263 Сложение по модулю 37, 63 Событие 314 — асинхронное 818 — определенное 316 — оегуляриое 317 Соотвежтвне 19 — взаимно однозначное 19 — канони ческое (для графов) 90 — сюръектнаиое 19 Функциоиэльяоа 19 Степень вершины 95 Стрелка Пирса 53 Суграф 97 СУпеРПозиция 27, 54, 179 Сходнмость алгоритме 149 Тезис Тьюрвнга 175 — Черча 194 Теорема Геделя о неполноте вторая 244 — — — — первая 244 — — — полнота исчисления преднкатов 243 — детерминнзацин 321 Кантора 23 — Кали 46 — Маркова — Посте 252 — о Функциональной полноте 78, 79 — Пелла — Аигера 307 — Райса 212 — йщрмальной таврия 2!9 — Холла 124 Теорема Черча 244 — Шеннона †Луизиа 345 Эйлера 108 Теория армальнал 2!8.