|
Эта публикация цитируется в 11 научных статьях (всего в 11 статьях)
Сложностные задачи теории вычислений
А. О. Слисенко
Аннотация:
В статье дан обзор современного состояния теории сложности
вычислений и ее приложений. Работа состоит из трех
глав. В первой главе изложены результаты, опирающиеся на методы общей теории вычислимости. В их числе – общие
свойства характеристик сложности, экспоненциальные и более
высокие нижние оценки для конкретных задач, классификации
задач по сводимости. Во второй главе рассмотрена
сложность конкретных задач, для которых удалось построить
алгоритмы с нетривиальными верхними оценками временной
сложности. Среди этих задач – идентификация подслов данного
слова, задачи на графах, геометрические задачи, решение
различных уравнений и др. Третья глава посвящена нетривиальным
нижним оценкам сложности конкретных задач при
решении их на “ограниченных” вычислительных моделях;
среди последних – машины Тьюринга, неветвящиеся программы
и другие.
Библ. 385 назв.
Поступила в редакцию: 03.03.1981
Образец цитирования:
А. О. Слисенко, “Сложностные задачи теории вычислений”, УМН, 36:6(222) (1981), 21–103; Russian Math. Surveys, 36:6 (1981), 23–125
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/rm3102 https://www.mathnet.ru/rus/rm/v36/i6/p21
|
Статистика просмотров: |
Страница аннотации: | 1490 | PDF русской версии: | 2161 | PDF английской версии: | 67 | Список литературы: | 72 | Первая страница: | 3 |
|