В учебном пособии, «первые достаточно полно рассматриваются Основы теории элементарных алгоритмов (элементарных по Кальмару функций), изученных современной теорией алгоритмов и успешно используемых в математических исследованиях. Излагаются также способы получения границ оптимизации (в том числе и полиномиального вида) для алгоритмов установления разрешимости синтаксически; ограниченных уравнении Дискретного характера. Учебное пособие предназначено для студентов математических факультетов вузов и аспирантов. Оно будет также полезно и инженерным работникам, интересующимся математическими возможностями алгоритмов и программ!
Author(s): Косовский Н. К.
Publisher: Изд-во Ленингр. ун-та
Year: 1987
Language: Russian
Pages: 154
City: Ленинград
Титул ......Page 2
Аннотация ......Page 3
Предисловие ......Page 4
Введение ......Page 9
§ 1. Алгоритмы, вычислимые на ЭВМ, и элементарные алгоритмы ......Page 17
§ 2. Оценки функций посредством итераций экспонент ......Page 21
§ 3. Определение элементарных алгоритмов ......Page 25
§ 4. Определение классов функций, элементарных по Сколему и по Кальмару ......Page 27
§ 5. Использование логических связок, ограниченных кванторов и ограниченного перебора для построения функций классов С и К ......Page 32
§ 6. Замкнутость относительно контролируемой рекурсии класса функций, элементарных по Кальмару ......Page 34
§ 7. Элементарность по Кальмару каждого элементарного алгоритма ......Page 36
§ 8. Задание функций посредством одноместных операций суммирования и суженного суммирования ......Page 38
§ 9. Построение функций с ограниченным числом аргументов, не использующее-функций с большим числом аргументов ......Page 45
§ 1. Определение примитивно рекурсивных программ над натуральными числами ......Page 48
§ 2. Функции, вычислимые примитивно рекурсивными программами ......Page 53
§ 3. Программы, корректные в целом ......Page 58
§ 4. Исчисление равенств примитивно рекурсивных программ ......Page 61
§ 1. Примитивно рекурсивные программы, вычисляющие элементарные функции ......Page 64
§ 2. Представление элементарных функций некоторым классом примитивно рекурсивных программ ......Page 70
§ 3. Классификация элементарных программ ......Page 71
§ 4. Класс примитивно рекурсивных программ с полиномиально ограниченными регистрами ......Page 74
Краткие комментарии ......Page 78
§ 1. Представление предикатов, вычислимых недетерминированно за ограниченное число шагов, синтаксически ограниченными уравнениями над битовыми строками ......Page 83
§ 2. Взанмопредставление недетерминированных вычислений логико-арифметическими уравнениями ......Page 89
§ 3. Иерархия диофантовых представлений примитивно рекурсивных предикатов ......Page 97
§ 4. Простые представления примитивно рекурсивных функций в иерархии Гжегорчика ......Page 102
§ 5. Разрешимость синтаксически ограниченных логико-арифметических уравнений (серия переборных задач с высокими полиномиальными границами оптимизации установления их разрешимости) ......Page 105
§ 6. Экспоненциальная сложность любой схемы, реализующей проверку разрешимости логико-арифметических уравнений ......Page 111
§ 7. Экспоненциальная сложность любой схемы, реализующей одну быстро вычислимую функцию ......Page 114
§ 1. Булевы функциональные уравнения ......Page 117
§ 2. Граница оптимизации числа шагов алгоритмов установления разрешимости булевых функциональных уравнений ......Page 122
§ 3. Иерархия всех булевых функциональных уравнений (примеры простых переборных задач с полиномиальными границами оптимизации времени их решения) ......Page 125
Комментарии ......Page 129
Приложение 1. Угадывающие машины Тьюринга ......Page 145
Приложение 2. Темы для самостоятельных размышлений ......Page 147
Указатель литературы ......Page 149
Оглавление ......Page 153
