Библиотека "Кибернетического Сборника". Сложность вычислений и алгоритмов

Автор(ы):ред. Козмидиади В. А., Маслов А. Н., Петри Н. В.
29.03.2010
Год изд.:1974
Описание: Затрагиваемые в сборнике проблемы математической логики тесно связаны с теорией вычислительных машин. В книге рассматриваются модели вычислительных устройств, их классификация, классификация языков, оценки сложности вычислений и оценки сложности программ. Развивается связанный со сложностью программ подход А. Н. Колмогорова к обоснованию теории вероятностей и теории информации. В настоящее время эти вопросы начинают привлекать большое число исследователей. Книга рассчитана на читателей, интересующихся современными проблемами теории алгоритмов и автоматов, математической лингвистики, вычислительных машин и программирования. Она будет полезна студентам и аспирантам указанных специальностей.
Оглавление:
Библиотека "Кибернетического Сборника". Сложность вычислений и алгоритмов — обложка книги. Обложка книги.
Предисловие редакторов перевода [5]
I. КЛАССИФИКАЦИЯ РЕКУРСИВНЫХ ФУНКЦИЙ
  Г. Т. Херман. Эквивалентность различных иерархий элементарных функций. Перевод А. А. Мучника [7]
  Дж. П. Клив, Г. Э. Роуз. En-арифметика. Перевод А. Мучника [18]
  М. X. Лёб, С. С. Вайнер. Иерархии теоретико-числовых функций. Перевод Ю. Д. Стригина [33]
  С. С. Вайнер. Классификация ординально рекурсивных функций. Перевод Ю. Д. Стригина [65]
II. КЛАССИФИКАЦИЯ ЯЗЫКОВ
  Ш. Грейбах. Одна бесконечная иерархия контекстно-свободных языков. Перевод А. А. Мучника [85]
  Т. Касаи. Об одной иерархии между контекстно-свободными и контекстно-связными языками. Перевод Э. Д. Стойкого [107]
III. АКСИОМАТИЧЕСКОЕ ОПИСАНИЕ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ И АЛГОРИТМОВ
  М. Блюм. Об эффективных процедурах для ускоряющих алгоритмов. Перевод М. И. Каиовича [127]
  Дж. Хелм, П. Янг. Сопоставление сложности и эффективности программ, допускающих ускорение. Перевод М. И. Кановича [150]
  П. Янг. Ускорения посредством изменения порядка, в котором перечисляются множества. Перевод А. А. Мучника [160]
  А. Эренфойхт, Я. Мыцельский. Сокращение доказательств при добавлении новых аксиом. Перевод А. А. Мучника [172]
  Дополнение 1. Л. А. Левин. Сигнализирующие вычислимых функции [174]
  Дополнение 2. М. И. Канович. Теорема об ускорении в формальных системах [186]
IV. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ НА МАШИНАХ ТЬЮРИНГА
  Г.-Й. Штосе. k-ленточное моделирование k-головочпых машин Тьюринга. Перевод В. Е. Плиско [190]
  Г.-Й. Штосе. Двуленточное моделирование машин Тьюринга. Перевод В. Е. Плиско [199]
  М. С. Патерсон. Ограничения на ленту для ограниченных во времени машин Тьюринга. Перевод В. А. Козмидиади [213]
  Т. Камеда, Р. Волмар. Заметка о сложности языков по числу поворотов на лентах. Перевод В. П. Захарова [222]
  B. Л. Бёркхард, П. П. Варайя. Проблемы сложности языков, вычислимых в реальное время. Перевод В. Л. Матросова [235]
  Дж. Хонкрофт, Дж. Улман. Некоторые результаты о машинах Тьюринга с ограниченной лептой. Перевод В. Н. Захарова [252]
V. ДРУГИЕ МОДЕЛИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
  C. Кук. Характеристики магазинных автоматов в терминах вычислителей, ограниченных во времени. Перевод В. Н. Захарова [266]
  С. Коул. Детерминированные автоматы с магазинной памятью и вычисления в реальное время. Перевод Г. С. Плесневича [289]
  П. К. Фишер, А. П. Мейер, А. Л. Розенберг. Ограниченные во времени генераторы последовательностей. Перевод И. А. Рахматулина [322]
  X. Р. Стронг. Вычисление с ограниченной глубиной. Перевод О. В. Симонова [349]
VI. СЛОЖНОСТЬ И СЛУЧАЙНОСТЬ
  П. Мартни-Лёф. О понятии случайности. Перевод В. Е. Плиско [364]
  К. П. Шпорр. Единый подход к определению случайных последовательностей. Перевод В. Е. Плиско [370]
Формат: djvu
Размер:6156845 байт
Язык:РУС
Рейтинг: 42 Рейтинг
Открыть: Ссылка (RU)