Решение задач на тему: Задачи, NР-трудные в сильном смысле. Обслуживание требований без задержек

Введение

Большинство задач, интересных с практической точки зрения, имеют полиномиальные (работающие за полиномиальное время) алгоритмы решения. То есть время работы алгоритма на входе длины n составляет не более О(nк) для некоторой константы к (не зависящей от длины входа). Разумеется, не каждая задача имеет алгоритм решения, удовлетворяющий этому свойству. Некоторые задачи вообще не могут быть решены никаким алгоритмом. Классический пример такой задачи - "проблема остановки" (выяснить останавливается ли данная программа на данном входе). Кроме того, бывают задачи, для которых существует решающий их алгоритм, но любой такой алгоритм работает "долго" - время его работы не есть О(nк) ни для какого фиксированного числа к.

Если мы хотим провести пусть грубую, но формальную границу между "практическими" алгоритмами и алгоритмами, представляющими лишь теоретический интерес, то класс алгоритмов, работающих за полиномиальное время, является разумным первым приближением. Мы рассмотрим, руководствуясь [1], класс задач, называемых NР-полными. Для этих задач не найдены полиномиальные алгоритмы, однако и не доказано, что таких алгоритмов не существует. Изучение NР-полных задач связано с так называемым вопросом "Р = NР". Этот вопрос был поставлен в 1971 году и является сейчас одной из наиболее сложных проблем теории вычислений.

Зачем программисту знать о NР-полных задачах? Если для некоторой задачи удается доказать ее NР-полноту, есть основания считать ее практически неразрешимой. В этом случае лучше потратить время на построение приближенного алгоритма, чем продолжать искать быстрый алгоритм, решающий ее точно.

Оглавление

- Введение

- Задачи, NР-трудные в сильном смысле

- Обслуживание требований без задержек

- Алгоритм

- Последовательный анализ вариантов

- Псевдополиномиальное сведение задач и NР-трудные в сильном смысле задачи

- Использование NР-трудных задач Заключение

- Библиографический список

Заключение

Итак, какой же практический смысл имеет изучение теории сложности и классификация задач с точки зрения NР-полноты Ответ очевиден - зачастую гораздо разумнее и эффективнее найти доказательство того, что рассматриваемая задача принадлежит к классу NР-полных, и в соответствие с этим заняться поиском достаточно точных приближенных алгоритмов, нежели безрезультатно тратить время на отыскание полиномиальных алгоритмов ее решения. Ясно, что именно NР-полные задачи играют здесь центральную роль - дело в том, что полиномиальное время является, хоть и первым, но достаточно хорошим приближением понятия "практической разрешимости задачи".

Список литературы

1. Гэри М., Джонсон Д. "Вычислительные машины и труднорешаемые задачи" М.: Мир 1982-466 стр.

2. Иванова А.П. "Введение в прикладное программирование. Модели и вычислительные алгоритмы" М.: Физматлит 2002 г.

3. Перепелица В.А. "Асимптотически подход и решение некоторых экстремальных задач на графах. Проблемы кибернетики " М.: Наука, 1973 г.

4. А.В. Яковлев, А.А. Безбогов, В.В. Родин, В.Н.Шамкин, КРИПТОГРАФИЧЕСКАЯЗАЩИТА ИНФОРМАЦИИ

5. Еремеев А.В., Романова А.А., Сервах В.В., Чаухан С.С. Приближенное решение одной задачи управления поставками // Дискретн. анализ и исслед. операций. Серия 2. 2006. Т. 13, № 1. С. 27-39.