Задача о выполнимости
Булево выражение называется выполнимым, если существует хотя бы одна комбинация значений переменных, подстановка которых обращает его в единицу.
Пример. □
Выражение
выполнимо, так как при
это выражение обращается в единицу.
Выражение
не является выполнимым, поскольку на
всех наборах переменных оно равно нулю.
■
Задача о выполнимости состоит в том, чтобы установить, выполнимо ли некоторое булево выражение, представленное в конъюнктивной нормальной форме.
Справедливо следующее утверждение.
Теорема. Задача о выполнимости является NP – полной.
Задачу коммивояжера удается решить за время, экспоненциально зависящее от числа городов. Таким образом, задача коммивояжера принадлежит к числу NP – полных.
Определение того, имеет ли ориентированный или неориентированный граф гамильтонов цикл есть NP – полная задача.
Определение оптимального маршрута в задаче коммивояжера с симметричной матрицей стоимостей является NP – полной задачей.
Литература
1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа,
1986. – 311 с.
2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энерго-
атомиздат, 1987. – 496 с.
3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для
инженера. – М.: Энергоатомиздат, 1988. – 480 с.
4. Сигорский В.П. Математический аппарат инженера. – М.: Техника,
1975. – 768 с.
5. Шапорев С.Д. Дискретная математика. – СПб.: БХВ-Петербург, 2006.
- 400 с.
6. Хаханов В.И., Чумаченко С.В. Дискретная математика. Курс лекций и
практические занятия (электронная версия). ХНУРЭ, 2003.
7. Яблонский С.В. Введение в дискретную математику. – М.: Наука,
1979. – 272 с.
8. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной
математике. – М.: ФИЗМАТЛИТ, 2005. – 416 с.
Электронное пособие курс лекций
по дисциплине
«Дискретная математика».
Для студентов дневной и заочной форм обучения
направления подготовки 6.050102
«Компьютерная инженерия»
Составитель:
Александр Евгеньевич Богданов
Редактор А.Е. Богданов
Техн. редактор Л.А. Лыгина
Оригинал – макет Л.А. Лыгина
Підписано до друку ____________
Формат
.
Папір типограф. Гарнітура Times.
Друк офсетний. Ум. друк. арк.___. Обл.-вид.арк._____.
Тираж ___ прим. Вид. №_______. Замова №______. Ціна договірна.
Видавництво Технологічного інституту
СНУ ім. Володимира Даля(м. Сєвєродонецьк)
Адреса видавництва: 93400, м. Сєвєродонецьк, Луганської обл.,
пр. Радянський, 59-а, головний корпус
Телефон: 8(06452) 4-03-42
E-mail: sti@sti.lg.ua