Категория
Информатика
Тип
реферат
Страницы
17 стр.
Дата
10.03.2014
Формат файла
.html — Html-документ
Архив
1004234.zip — 10.31 kb
  • trudnoreshaemye-zadachi-posledovatelnyj-analiz-variantov_1004234_1.html — 39.51 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Курсовая работа

по дисциплине «Алгоритмы с оценками»

На тему «
Труднорешаемые задачи. Последовательный анализ вариантов»

Содержание

Введение

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

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

2.Алгоритм

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

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

4.Использование NP-трудных задач

Заключение

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

Введение

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

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



Ваше мнение



CAPTCHA