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


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

ПРЕДИСЛОВИЕ
Теория алгоритмов возникла и оформилась в самостоятельную дисциплину в 30—40-х гг. нашего века. Примерно в это же время, а также в последующие годы были получены решения ряда классических алгоритмических проблем математической логики, алгебры и топологии. В дальнейшем наметилась связь теории алгоритмов с кибернетикой: проектированием вычислительных устройств, программированием, моделированием биологических объектов (хотя в довольно скромных пока масштабах), математической лингвистикой. Обнаружилось, что бывают алгоритмические проблемы («рекурсивно») разрешимые и неразрешимые. Последние даже различают по «степеням неразрешимости». Однако и теоретически и особенно практически важно уметь устанавливать, насколько «легко» разрешима та или иная проблема, какими средствами (типами алгоритмов, вычислительных устройств и т. п.) она разрешима, сколь сложными могут быть программы алгоритмов и соответствующие им вычисления.
В соответствии с этим стали изучаться ограниченные классы алгоритмов, реализуемых логическими сетями, контактными схемами, конечными и растущими автоматами. Много исследований, начиная с известных работ Дж. Риордана и К. Шеннона, было посвящено получению оценок сложности алгоритмов подобного рода, решающих ограниченные алгоритмические проблемы типа вычислений булевых функций, многочленов и т. д. Конечные автоматы и особенно их обобщения стали хорошим средством описания моделей реальных языков и языков программирования.
С другой стороны, изучение самих вычислимых функций привело к выделению некоторых довольно простых и вместе с тем достаточных для большинства приложений классов функций: примитивно рекурсивных, элементарных по Кальмару и т. д., а затем были предложены некоторые классификации рекурсивных функций в работах А. Гжегорчика, П. Акста, Дж. Клива, Р. В. Ричи. (Переводы этих работ вошли в предлагаемый читателю сборник, образуя в нем первый цикл, связанный с рекурсивными классификациями.)
Каждый алгоритм задается программой, согласно которой производятся операции над «текущей» информацией, находящейся в «памяти», а исходная информация определяется конкретной задачей, которую разрешает данный алгоритм. Указанные выше понятия уточняются при каждой формализации основного понятия — алгоритма. Последовательность операций при приме-

 

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


Математика