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


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

Предисловие
тематической лингвистики. По затронутым здесь проблемам на русском языке (кроме отдельных статей в научных журналах) опубликованы обзоры П. Фишера 1965 г.1) с обширной библиографией, А. Ахоу и Дж. Улмана2) и Л. А. Гусева и И. М. Смирновой3), а также курс лекций Б. А. Трахтенброта4). В указанном курсе лекций подытожены и систематически излагаются результаты об оценках сложности вычислений на машинах Тьюринга (полученные вплоть до конца 1966 г.) и аксиоматическая теория сложности алгоритмов и вычислений, но почти не затрагиваются вопросы классификации (аналитической) рекурсивных функций. К сожалению, этот курс издан небольшим тиражом и мало доступен широкому кругу читателей. Это побудило нас включить в сборник переводы нескольких статей, обладающих большими методическими достоинствами (см., например, статью Ф. Хенни на стр. 223), содержание которых частично перекрывается работами советских математиков Я. М. Барздиня, Б. А. Трахтенброта, Р. В. Фрейвалда и других, опубликованными в советской печати (см. «Алгебра и логика» за 1963— 1967 гг.).
Для понимания большинства статей достаточно знакомства с элементами теории алгоритмов, например, в объеме первых трех глав и § 12 книги А. И. Мальцева5), а читателю статей о распознавании языков полезно было бы прочесть обзор Н. Хом-ского6) и упомянутые выше обзоры по теории языков.
В. А. Козмидиади А. А. Мучник
1) Фишер П., Многоленточные и бесконечные автоматы, Кибернетический сборник (новая серия), вып. 5, «Мир», 1968, стр. 64—80.
2) Ахоу А., У л м а н Дж., Теория языков, Кибернетический сборник (новая серия), вып. 6, «Мир», 1969, стр. 145—183.
3) Гусев Л. А., С м и р н о в а И. М., Языки, грамматики и абстрактные автомтные модели, I, II, Автоматика и телемеханика, № 4, № 5 (1968).
4) Т р а х т е н б р о т Б. А., Сложность алгоритмов и вычислений, Новосибирск, 1967.
5) Мальцев А. И., Алгоритмы и рекурсивные функции, «Наука», М., 1965.
6) X о м с к и и Н., Формальные свойства грамматик, Кибернетический сборник (новая серия), вып. 2, «Мир», 1966, стр. 121—230.

 

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


Математика