Успехи математических наук
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



УМН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Успехи математических наук, 1981, том 36, выпуск 6(222), страницы 21–103 (Mi rm3102)  

Эта публикация цитируется в 11 научных статьях (всего в 11 статьях)

Сложностные задачи теории вычислений

А. О. Слисенко
Список литературы:
Аннотация: В статье дан обзор современного состояния теории сложности вычислений и ее приложений. Работа состоит из трех глав. В первой главе изложены результаты, опирающиеся на методы общей теории вычислимости. В их числе – общие свойства характеристик сложности, экспоненциальные и более высокие нижние оценки для конкретных задач, классификации задач по сводимости. Во второй главе рассмотрена сложность конкретных задач, для которых удалось построить алгоритмы с нетривиальными верхними оценками временной сложности. Среди этих задач – идентификация подслов данного слова, задачи на графах, геометрические задачи, решение различных уравнений и др. Третья глава посвящена нетривиальным нижним оценкам сложности конкретных задач при решении их на “ограниченных” вычислительных моделях; среди последних – машины Тьюринга, неветвящиеся программы и другие.
Библ. 385 назв.
Поступила в редакцию: 03.03.1981
Англоязычная версия:
Russian Mathematical Surveys, 1981, Volume 36, Issue 6, Pages 23–125
DOI: https://doi.org/10.1070/RM1981v036n06ABEH003102
Реферативные базы данных:
Тип публикации: Статья
УДК: 518.1+519.9
Образец цитирования: А. О. Слисенко, “Сложностные задачи теории вычислений”, УМН, 36:6(222) (1981), 21–103; Russian Math. Surveys, 36:6 (1981), 23–125
Цитирование в формате AMSBIB
\RBibitem{Sli81}
\by А.~О.~Слисенко
\paper Сложностные задачи теории вычислений
\jour УМН
\yr 1981
\vol 36
\issue 6(222)
\pages 21--103
\mathnet{http://mi.mathnet.ru/rm3102}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=643069}
\zmath{https://zbmath.org/?q=an:0484.68034|0501.68013}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?1981RuMaS..36...23S}
\transl
\jour Russian Math. Surveys
\yr 1981
\vol 36
\issue 6
\pages 23--125
\crossref{https://doi.org/10.1070/RM1981v036n06ABEH003102}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=A1981QL14100002}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/rm3102
  • https://www.mathnet.ru/rus/rm/v36/i6/p21
  • Эта публикация цитируется в следующих 11 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Успехи математических наук Russian Mathematical Surveys
    Статистика просмотров:
    Страница аннотации:1490
    PDF русской версии:2161
    PDF английской версии:67
    Список литературы:72
    Первая страница:3
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024