URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Крылов А.Г. Проблемы математической логики. Сложность алгоритмов и классы вычислимых функций Сборник переводов
Id: 104513
 

Проблемы математической логики. Сложность алгоритмов и классы вычислимых функций Сборник переводов

1970. 432 с. Мягкая обложка. Букинист. Состояние: 4. .
Обращаем Ваше внимание, что книги с пометкой "Предварительный заказ!" невозможно купить сразу. Если такие книги содержатся в Вашем заказе, их цена и стоимость доставки не учитываются в общей стоимости заказа. В течение 1-3 дней по электронной почте или СМС мы уточним наличие этих книг или отсутствие возможности их приобретения и сообщим окончательную стоимость заказа.

 Аннотация

Сборник содержит работы по актуальным проблемам математической логики, еще не получившим достаточного освещения в отечественной литературе. Эти работы посвящены оценкам сложности алгоритмов и вычислений, классификациям рекурсивных функций и различным типам вычислительных устройств, связанных с такими классификациями. В частности, значительное место занимают исследования «ограниченных» машин Тьюринга и обобщений конечных автоматов. В ряде работ изучаются множества слов, распознаваемых обобщенными автоматами, причем обнаруживаются связи с грамматиками, введенными в работах Н. Хомского.

Книга рассчитана на лиц, интересующихся современными проблемами математической логики, теории алгоритмов, теории автоматов, математической лингвистики и теории вычислительных машин.


 СОДЕРЖАНИЕ

Предисловие........................ 5

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

А. Гжегорчик. Некоторые классы рекурсивных функций. Перевод

А. А. Мучника.....................9

Р. В. Р и ч и. Классы предсказуемо вычислимых функций. Перевод Н. Н. Ка-

териночкиной...................... 50

Д ж. П. Клив. Иерархия примитивно рекурсивных функций. Перевод

С. С. Марченкова....................94

П. Акст. Итерация примитивной рекурсии. Перевод А. Гагарина... 114 П. Акст. Итерация относительной примитивной рекурсии. Перевод

С. Каллибекова.....................118

Добавление редактора. О двух подходах к классификации рекурсивных

функций.......................123

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

X. Я м а д а. Вычисления в реальное время и рекурсивные функции, не вычислимые в реальное время. Перевод В. Е. Фельдмана.....139

М. Р а б и н. Вычисления в реальное время. Перевод В. Е. Фельдмана. 156

А. Розенберг. Языки, определимые в реальное время. Перевод М. Афанасьева и М. В. Ломковской.............168

Ф. К- X е н н и, Р. Е. С т и р н з. Моделирование многоленточной машины Тьюринга на двуленточной. Перевод Ю. А. Бухштаба......194

С. С. Р а б и, П. К. Фишер. Методы перевода и сложность вычислений.

Перевод А. А. Мучника..................213

Ф. К- X е н н и. Вычисления на одноленточной машине Тьюринга с записью на ленте. Перевод Ю. Я. Брейтбарта..........223

Ф. К. X е н н и. Вычисления на машинах Тьюринга со входом. Перевод А. Набибина......................249

П. С т р н а д. Распознавание на машине Тьюринга со входом. Перевод Ю. А. Бухштаба....................271

Дж. Хартманис. Сложность вычислений на одноленточных машинах Тьюринга. Перевод А. А. Мучника..............282

Р. Е. С т и р н з, Дж. Хартманис, П. М. Льюис П. Иерархии вычислений с ограниченной памятью. Перевод М. И. Кановича.... 301

П М. Льюис II, Р. Е. С т и р н з, Д ж. Хартманис. Границы памяти для разрешения контекстно-свободных и контекстных языков. Перевод М. И. Кановича.................320

Д ж. Хартманис. Об объеме памяти, необходимом для распознавания

бесконтекстных языков. Перевод М. В. Ломковской....... 339

Д. X. Янгер. Распознавание к анализ контекстно-свободных языков за время я3. Перевод В. Е. Фельдмана.............344

Т. К а с а м и. О времени машинного распознавания языков, порожденных

линейными грамматиками Перевод В. Е. Фельдмана.......363

Добавление к статье Касами. Распознавание металинейных языков по

методу Т. Касами....................369

М. Фишер, А. Розенберг. Решение задачи о пересечении начала координат в реальное время. Перевод В. Е. Фельдмана.....372

П. Фишер, А. Мейер, А. Розенберг. Счетчиковые машины и счет-чиковые языки. Перевод В. Е. Фельдмана...........380

М. Блюм. Машинно-независимая теория сложности рекурсивных функций. Перевод В. А. Козмидиади...............401

 
© URSS 2016.

Информация о Продавце