Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Сложность вычислений



В качестве небольшого, но важного отступления отметим в данном разделе, что

алгоритмическая разрешимость еще не означает, что задача может быть реально решена.

Дело в том, что для нас на практике задача, решение которой требует тысячу лет или ресурсы, превышающие все вычислительные ресурсы планеты, тоже неразрешима.

И здесь вступает в силу «математика практической осуществимости»…Такого рода проблемами занимается теория сложности вычислений.

Рассмотрим для иллюстрации таблицу, в которой четыре столбца, соответствующие «абстрактному» объему исходных данных (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 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с)...