Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

Предисловие
Ряд работ посвящен другим вопросам сложности алгоритмов {).
С оценками сложности вычислений связан другой подход к классификации вычислимых функций. (Связь между аналитическим и «сложностным» подходами исследуется в статье Р. В. Ри-чи для «сложности», измеряемой длиной ленты машины Тьюринга, используемой при вычислении. В общей постановке этот вопрос рассмотрен в добавлении А. А. Мучника (стр. 123— 138), в котором также дается обзор работ по классификации рекурсивных функций.)
Первые оценки сложности вычислений для конкретных предикатов и функций были получены в конце 50-х и начале 60-х гг. в работах Г. С. Цейтина, М. О. Рабина и Б. А. Трахтенброта и его учеников. Однако здесь сразу же пришлось столкнуться с большими трудностями, связанными с получением «хороших» нижних оценок (т. е. оценок, близких к верхним) для памяти и особенно времени вычисления. (Этим вопросам посвящены статьи Ф. Хенни, Дж. Хартманиса, П. М. Льюиса и Р. Стирнза, П. Фишера.) Специальный, но важный класс предикатов, вычислимых «в реальное время», рассматривался М. Рабином и А. Розенбергом (см. их статьи и в данном сборнике).
Развитие математической лингвистики и языков программирования привело к изучению специальных классов рекурсивных предикатов (на множествах слов) — контекстных и бесконтекстных (или контекстно-свободных) языков. Верхние оценки для сложности распознавания таких языков приводятся в статьях Дж. Хартманиса, П. М. Льюиса, Дж. Хартманиса и Р. Стирнза, Д. Нигера, Т. Касами и в добавлении к последней.
Абстрактный аксиоматический подход к изучению сложности алгоритмов и вычислений предложен М. Блюмом, который установил замечательные результаты о существовании «бесконечно оптимизируемых» в смысле сложности классов рекурсивных предикатов. Точный смысл высказанного утверждения и полное доказательство можно найти в двух статьях М. Блюма, заключающих этот сборник.
Мы надеемся, что настоящий сборник представит интерес для многих математиков, логиков, кибернетиков и тех, кто специализируется в области современного программирования и ма-
') Брейбарт Ю. Я., Коз ми диад и В. А., О двух подклассах машин Тьюринга, сводимых к конечным автоматам, ДАН СССР, 187, № 1 (1969), 9—10; Остроухое Д. А., Об оценках сложности нормальных алгорифмов, ДАН СССР, 184, № б (1969), 1292—1293; Маранджян Г. Б., О некоторых свойствах асимптотически оптимальных рекурсивных функций, Изв. АН Арм. ССР, 4, вып. 1 (1969), 3—22; Маранджян Г. Б., Иерархия рекурсивных функций и асимптотическая аддитивность, ДАН Арм. ССР, 48, № 4 (1969), 193—197.

 

1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика