22.12 Ш96 Шурыгин, Виктор Афанасьевич. Сложностный метод теории алгоритмов [Текст] / В.А. Шурыгин. - М. : ЛИБРОКОМ, 2009. - 194 с. - ISBN 978-5-397-00185-4 : 305.02 р. Рубрики: Математика Математическая логика Кл.слова (ненормированные): теория алгоритмов -- алгорифмические проблемы -- проблемы распознавания -- инвариантная сложность -- нормальные алгорифмы -- подобия нормальных алгорифмов Аннотация: Направление в теории алгоритмов, в котором размеры программ, задающих алгоритмы, используются как средство исследования алгоритмических проблем, было основано А.А.Марковым в начале 60-х годов XX в. Сложностный метод А.А.Маркова позволяет расширить область применимости теорий, исследующих или использующих неразрешимые алгоритмические проблемы. Примерно в это же время А.Н.Колмогоров для исследований оснований теории информации и теории вероятностей начал создавать теорию, основанную на использовании минимальных размеров кодов алгоритмов. Марковское и колмогоровское направления теории сложности алгоритмов различались определениями основных понятий и изначально имели разное предназначение, но в процессе их развития произошло их сближение, поэтому их можно рассматривать как начала общей теории, использующей специфические методы исследований. В предлагаемой книге даются изложение основ этой теории и некоторые ее приложения. Книга адресована, в первую очередь, математикам, чья специализация связана с теорией алгоритмов, но она может быть интересной и более широкому кругу читателей для ознакомления с одним из новых направлений в теории алгоритмов. Экземпляры всего: 1 ч.з. (1) Свободны: ч.з. (1) |