Сложность вычислений и алгоритмов

Купить бумажную книгу и читать

Название: Сложность вычислений и алгоритмов. Библиотека «Кибернетического Сборника»

Автор: См оглавление - подробнее

Издательство: Мир

Год издания: 1974

Страниц: 390

Формат: DJVU+OCR

Размер: 6 МБ

Качество: Отличное, 600дпи, текстовой слой, цветная обложка

Затрагиваемые в сборнике проблемы математической логики тесно связаны с теорией вычислительных машин. В книге рассматриваются модели вычислительных устройств, их классификация, классификация языков, оценки сложности вычислений и оценки сложности программ. Развивается связанный со сложностью программ подход А. Н. Колмогорова к обоснованию теории вероятностей и теории информации. В настоящее время эти вопросы начинают привлекать большое число исследователей. Перевод ряда более ранних работ содержится в сборнике «Проблемы математической логики» («Мир», 1970). Книга рассчитана на читателей, интересующихся современными проблемами теории алгоритмов и автоматов, математической лингвистики, вычислительных машин и программирования. Она будет полезна студентам и аспирантам указанных специальностей.

СОДЕРЖАНИЕ

Предисловие редакторов перевода

КЛАССИФИКАЦИЯ РЕКУРСИВНЫХ ФУНКЦИЙ

Г. Т. Херман. Эквивалентность различных иерархий элементарных функций. Перевод А. А. Мучника

Дж. П. Клив, Г. Э. Роуз, En-арифметика. Перевод А . А . Мучника

М. X. Лёб, С. С. Вайнер. Иерархии теоретико-числовых функций. Перевод Ю. Д. Стригина

С. С. Вайнер. Классификация ординально рекурсивных функций. Перевод Ю. Д. Стригина

КЛАССИФИКАЦИЯ ЯЗЫКОВ

Грейбах. Одна бесконечная иерархия контекстно-свободных языков. Перевод А. А. Мучника

Т. Касаи. Об одной иерархии между контекстно-свободными и контекстно-связными языками. Перевод Э. Д. Стойкого

АКСИОМАТИЧЕСКОЕ ОПИСАНИЕ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ И АЛГОРИТМОВ

М. Блюм. Об эффективных процедурах для ускоряющих алгоритмов. Перевод М. И. Кановича

Дж. Хелм, П. Янг. Сопоставление сложности и эффективности программ, допускающих ускорение. Перевод М. И1. Кановича

П. Янг. Ускорения посредством изменения порядка, в котором перечисляются множества. Перевод А. А. Мучника

А. Эренфойхт, Я. Мыцельский. Сокращение доказательств при добавлении новых аксиом. Перевод А. А. Мучника

Дополнение 1. Л. А. Левин. Сигнализирующие вычислимых функций

Дополнение 2. М. И. Канович. Теорема об ускорении в формальных системах

СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ НА МАШИНАХ ТЬЮРИНГА

Г.-Й. Штосе, /с-ленточное моделирование /с-головочпых машин Тьюринга. Перевод В. Е. Плиско

Г.-Й. Штосе. Двуленточное моделирование машин Тьюринга. Перевод В. Е. Плиско

М. С. Патерсон. Ограничения на ленту для ограниченных во времени машин Тьюринга. Перевод В. А. Козмидиади

Т. Камеда, Р. Волмар. Заметка о сложности языков по числу поворотов на лентах. Перевод В. П. Захарова

В. Л. Бёркхард, П. П. Варайя. Проблемы сложности языков, вычислимых в реальное время. Перевод В. Л. Матросова

Дж. Хопкрофт, Дж. Улман. Некоторые результаты о машинах Тьюринга с ограниченной лептой. Перевод В. Н. Захарова

ДРУГИЕ МОДЕЛИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

С. Кук. Характеристики магазинных автоматов в терминах вычислителей, ограниченных во времени. Перевод В. Н. Захарова

С. Коул. Детерминированные автоматы с магазинной памятью и вычисления в реальное время. Перевод Г. С. Плесневича

П. К. Фишер, А. П. Мейер, А. Л. Розенберг. Ограниченные во времени генераторы последовательностей. Перевод П. А. Рахматулина

X. Р. Строиг. Вычисление с ограниченной глубиной. Перевод О. В. Симонова

СЛОЖНОСТЬ И СЛУЧАЙНОСТЬ

П. Мартиш-Лёф. О понятии случайности. Перевод В. Е. Плиско К. П. Шпорр. Единый подход к определению случайных последовательностей. Перевод В. Е. Плиско