Библиотека "Кибернетического Сборника". Сложность вычислений и алгоритмов
Автор(ы): | ред. Козмидиади В. А., Маслов А. Н., Петри Н. В.
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 байт |
Язык: | РУС |
Рейтинг: | 168 |
Открыть: | Ссылка (RU) |