Категория
Информатика
Тип
курсовая работа
Страницы
12 стр.
Дата
31.05.2010
Формат файла
.doc — Microsoft Word
Архив
150801.zip — 280.71 kb
  • trudnoreshaemye-zadachi-posledovatelnyj-analiz-variantov_150801_1.doc — 387 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы


Курсовая работа
по дисциплине «Алгоритмы с оценками»
На тему «Труднорешаемые задачи. Последовательный анализ вариантов»СодержаниеВведение1. Задачи, NP-трудные в сильном смысле1.1. Обслуживание требований без задержек2.Алгоритм2.1 Последовательный анализ вариантов3. Псевдополиномиальное сведение задач и NP-трудные в сильном смысле задачи4.Использование NP-трудных задач
ЗаключениеБиблиографический списокВведение
Большинство задач, интересных с практической точки зрения, имеют полиномиальные (работающие за полиномиальное время) алгоритмы решения. То есть время работы алгоритма на входе длины n составляет не более O(nk) для некоторой константы k (не зависящей от длины входа). Разумеется, не каждая задача имеет алгоритм решения, удовлетворяющий этому свойству. Некоторые задачи вообще не могут быть решены никаким алгоритмом. Классический пример такой задачи — «проблема остановки» (выяснить останавливается ли данная программа на данном входе). Кроме того, бывают задачи, для которых существует решающий их алгоритм, но любой такой алгоритм работает «долго» — время его работы не есть O(nk) ни для какого фиксированного числа k.
Если мы хотим провести пусть грубую, но формальную границу между «практическими» алгоритмами и алгоритмами, представляющими лишь теоретический интерес, то класс алгоритмов, работающих за полиномиальное время, является разумным первым приближением. Мы рассмотрим, руководствуясь [1], класс задач, называемых NP-полными. Для этих задач не найдены полиномиальные алгоритмы, однако и не доказано, что таких алгоритмов не существует. Изучение NP-полных задач связано с так называемым вопросом «P = NP». Этот вопрос был поставлен в 1971 году и является сейчас одной из наиболее сложных проблем теории вычислений.
Зачем программисту знать



Ваше мнение



CAPTCHA