Класс NP и NP-полные задачи
NP-полнота задачи о выполнимости булевой формулы. Решение задачи за полиномиальное время на недетерминированной машине Тьюринга. Определение набора значений переменных. Трансформация задачи о клике в задачу о вершинном покрытии и о гамильтоновом цикле.
| Рубрика | Программирование, компьютеры и кибернетика |
| Предмет | Теория алгоритмов |
| Вид | презентация |
| Язык | русский |
| Прислал(а) | incognito |
| Дата добавления | 28.01.2015 |
| Размер файла | 76,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Подобные документы
Полные и стохастические неполные алгоритмы локального поиска для решения задачи булевой выполнимости. Модели преобразования операторов. Реализация решателя, применяющего модифицированный алгоритм gNovelty, расширенный на использование непрерывных форм.
курсовая работа [531,9 K], добавлен 27.09.2016Сущность и постановка транспортной задачи для n переменных, их виды, применение и пример решения в MS Excel. Управляющие структуры ветвления Maple языка (if предложение). Решение транспортной задачи в векторных координатах для двух и трёх матриц.
дипломная работа [109,3 K], добавлен 12.01.2011Решение задачи расчета структуры и объема товарооборота методом линейного программирования. Формулы ограничений, транспортная задача оптимизации доставки товаров. Решение задачи о назначениях на основе матрицы стоимостей в электронной таблице Excel.
контрольная работа [1023,6 K], добавлен 27.05.2013Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
реферат [157,5 K], добавлен 21.08.2008Задача о ранце как задача комбинаторной оптимизации. Задача о загрузке, рюкзаке, ранце. Постановка и NP-полнота задачи. Классификация методов решения задачи о рюкзаке. Динамическое программирование. Метод ветвей и границ. Сравнительный анализ методов.
курсовая работа [1,7 M], добавлен 18.01.2011Сущность симплекс-метода. Общая характеристика задачи о смесях. Разработка основных алгоритмов решения задачи. Решение задачи в среде визуального программирования Delphi. Проектирование интерфейса пользователя. Разработка форм ввода-вывода информации.
курсовая работа [476,6 K], добавлен 22.05.2012Решение задачи аппроксимации поверхности при помощи системы нечёткого вывода. Определение входных и выходных переменных, их термы; алгоритм Сугено. Подбор функций принадлежности, построение базы правил, необходимых для связи входных и выходных переменных.
курсовая работа [1,8 M], добавлен 31.05.2014Решение задачи на тему максимизации функций многих переменных. Описание метода дихотомии, его применение для решения нелинейных уравнений. Решение данной задачи с использованием метода покоординатного спуска. Составление алгоритмов, листинг программы.
курсовая работа [138,5 K], добавлен 01.10.2009Построения математической модели с целью получения максимальной прибыли предприятия, графическое решение задачи. Решение задачи с помощью надстройки SOLVER. Анализ изменений запасов ресурсов. Определение пределов изменения коэффициентов целевой функции.
курсовая работа [2,4 M], добавлен 17.12.2014Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015