Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
В качестве небольшого, но важного отступления отметим в данном разделе, что
алгоритмическая разрешимость еще не означает, что задача может быть реально решена.
Дело в том, что для нас на практике задача, решение которой требует тысячу лет или ресурсы, превышающие все вычислительные ресурсы планеты, тоже неразрешима.
И здесь вступает в силу «математика практической осуществимости»…Такого рода проблемами занимается теория сложности вычислений.
Рассмотрим для иллюстрации таблицу, в которой четыре столбца, соответствующие «абстрактному» объему исходных данных (n)
Три строки соответствуют различным «функциям сложности вычислений». В таблице приведены времена вычислений в зависимости от объема данных и сложности вычислений (F).
n F | ||||
n | 10-5 cек | 30*10-6 cек. | 30*10-6 cек. | 30*10-6 cек. |
n5 | 0.1 cек. | 24.3 cек. | 5.2 мин. | 13 мин. |
2n | 10-3 cек. | 17.9 мин. | 35.7 лет | 366 столетий |
Бросается в глаза быстрый рост сложности вычислений в последней строке.
Действительно, с точки зрения теории сложности вычислений, между последним и двумя первыми типами задач пропасть. Первые две задачи относятся к классу задач с полиномиальной сложностью. А последняя – к задачам с экспоненциальной сложностью. Такие задачи называются трудноразрешимыми. Класс этих задач формируется эмпирически и носит название класса NP - полных задач.
Есть какая-то аналогия между проблемами алгоритмической разрешимости и трудноразрешимости. Как из-за невозможности определить понятие алгоритма проблема алгоритмической разрешимости сводится к возможности построения конкретизации, так и трудноразрешимость устанавливается сведением исследуемой задачи к одной из «эталонных» NP - полныхзадач.
Дата публикования: 2014-11-03; Прочитано: 282 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!