URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Косовский Н.К. Основы теории элементарных алгоритмов
Id: 31273
 
999 руб.

Основы теории элементарных алгоритмов

1987. 152 с. Мягкая обложка. Букинист. Состояние: 4. .

 Аннотация

В учебном пособии впервые достаточно полно рассматриваются основы теории элементарных алгоритмов (элементарных по Кальмару функций), изученных современной теорией алгоритмов к успешно используемых в математических исследованиях. Излагаются также способы получения границ оптимизации (в том числе и полиномиального вида) для алгоритмов установления разрешимости синтаксически ограниченных уравнений дискретного характера.

Учебное пособие предназначено для студентов математических факультетов вузов и аспирантов. Оно будет также полезно и инженерным работникам, интересующимся математическими возможностями алгоритмов и программ.


 ОГЛАВЛЕНИЕ

Предисловие,.........

Введение.............

РАЗДЕЛ I. ОСНОВНЫЕ СВОЙСТВА КЛАССА ЭЛЕМЕНТАРНЫХ

АЛГОРИТМОВ

Глава 1. Начальные сведения....... •

§ 1. Алгоритмы, вычислимые на ЭВМ, и элементарные алгоритмы............

§ 2. Оценки функций посредством итераций экспонент

§ 3. Определение элементарных алгоритмов.....

§ 4. Определение классов функций, элементарных по Сколему и по Кальмару..........

§ 5. Использование логических связок, ограниченных кванторов и ограниченного перебора для построения функций классов СиК............

§ 6. Замкнутость относительно контролируемой рекурсии класса функций, элементарных по Кальмару.....

§ 7. Элементарность по Кальмару каждого элементарного алгоритма............

§ 8. Задание функций посредством одноместных операций суммирования и суженного суммирования.....

§ 9. Построение функций с ограниченным числом аргументов, не использующее функций с большим числом аргументов

Г лава 2. Примитивно рекурсивные программы.....

§ 1. Определение примитивно рекурсивных программ над натуральными числами.........

§ 2. Функции, вычислимые примитивно рекурсивными программами............

§ 3. Программы, корректные в целом....

§ 4. Исчисление равенств примитивно рекурсивных программ

Глава 3. Установление элементарности простейших примитивно рекурсивных программ........

§ 1. Примитивно рекурсивные программы, вычисляющие элементарные функции..........

§ 2. Представление элементарных функций некоторым классом примитивно рекурсивных программ......

§ 3. Классификация элементарных поограмм.....

§ 4. Класс примитивно рекурсивных программ е полиномиально

ограниченными регистрами.......73

Краткий комментарии...........77

РАЗДЕЛ II ГРАНИЦЫ ОПТИМИЗАЦИИ УСТАНОВЛЕНИЯ РАЗРЕШИМОСТИ СИНТАКСИЧЕСКИ ОГРАНИЧЕННЫХ УРАВНЕНИИ НЕКОТОРЫХ СИГНАТУР

Глава 1. Границы оптимизации установления разрешимости синтаксически ограниченных логико-арифметических уравнений. 82

§ 1. Представление предикатов, вычислимых недетерминированно за ограниченное число шагов, синтаксически ограниченными уравнениями над битовыми строками.....---

§ 2. Взаимопредставление недетерминированных вычислений логико-арифметическими уравнениями.....88

§ 3. Иерархия диофантовых представлений примитивно рекурсивных предикатов.........96

§ 4. Простые представления примитивно рекурсивных функции

в иерархии Гжегорчика........101

§ 5. Разрешимость синтаксически ограниченных логико-арифметических уравнений (серия переборных задач с высокими полиномиальными границами оптимизации установления их разрешимости)..........104

§ 6. Экспоненциальная сложность любой схемы, реализующей

проверку разрешимости логико-арифметических уравнений. НО

§ 7. Экспоненциальная сложность любой схемы, реализующей

одну быстро вычислимую функцию......113

Глава 2. Границы оптимизации установления непротиворечивости описания контактных схем из функциональных элементов, реализующих логические связки......116

§ 1. Булевы функциональные уравнения.....---

§ 2. Граница оптимизации числа шагов алгоритмов установления

разрешимости булевых функциональных уравнений.. 121 § 3. Иерархия всех булевых функциональных уравнений (примеры простых переборных задач с полиномиальными границами оптимизации времени их решения).....124

Комментарии............128

Приложение 1. Угадывающие машины Тьюринга.....144

Приложение 2. Темы для самостоятельных размышлений...146 Указатель литературы...,...,,..148

 
© URSS 2016.

Информация о Продавце