Читать онлайн «Компьютерное моделирование логических процессов. Архитектура и язык решателя задач»

УДК 519. 6 ББК 22. 19 [бl [ол о в е ш к и н В. А. , Ул ь я н о в М. В. Теория рекурсии для проrрам мистов. М. : ФИЗМАТЛИТ, 2006. 296 с. ISBN 5 922I 0721 6. Книrа является учебным пособием по теории рекурсии в аспекте ее при менения в области проrраммирования. В ней рассматриваются основы теории рекурсии и ее использование в области разработки и анализа рекурсивных алrоритмов. Приводятся основные сведения о рекурсивных последовательно стях и функциях, даны примеры рекурсивных алrоритмов, разработанных на основе рекуррентных соотношений, метода декомпозиции и метода ди намическоrо проrраммирования, излаrаются методы разработки рекурсивных алrоритмов и их теоретическоrо анализа, в том числе элементы теории pe сурсной эффективности вычислительных алrоритмов. Детально изложены Me тоды анализа рекурсивных алrоритмов, проиллюстрированные целым рядом примеров. Приложение содержит тексты проrрамм, реализующих рекурсивные алrоритмы, рассмотренные в основном тексте книrи, и результаты экспери ментальных исследований. Учебное пособие ориентировано на специалистов в области информатики и анализа алrоритмов, разработчиков алrоритмическоrо обеспечения и предназначено для студентов, аспирантов и преподавателей вузов, специализирующихся в области математической информатики, теории рекурсии, разработки, анализа и исследования рекурсивных алrоритмов. А. rоловещкин, М. В. Ульянов, 2006 Scan. Введение в теорию рекурсии . 11  1. Основные понятия и определения . . . II  2. Рекурсивно заданные последовательности и функции. 23  3. Классификация рекурсивно заданных последовательностей и функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30  4. Методы исследования и решения рекуррентных соотношений . 36 Задачи и упражнения к rлаве I . . . . . . . . . . . . . . . . . . . . . . . . . . 50 r л а в а 2. Рекурсивные алrоритмы и особенности их nporpaMMHbIX реализаций. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51  1. Рекурсивные алrоритмы. . . . . . . . . . . . . . . . . . . . . . . . . . . . 51  2. Особенности nporpaMMHbIX реализаций рекурсивных алrоритмов 56  3. Механизм обслуживания рекурсивноrо вызова . . . . . . . . . . . . 59  4. Представление последовательности рекурсивных вызовов в виде дерева рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Задачи и упражнения к rлаве 2 . . . . . . . . . . . . . . . . . . . . . . . . 65 r л а в а 3. Методы разработки рекурсивных алrоритмов 67  1. Метод рекуррентных соотношений . . . . . 68 '2. Метод декомпозиции. . . . . . . . . . . . . . . . . 71 3. Метод динамическоrо проrраммирования 74 Задачи и упражнения к rлаве 3. . . . . . . . . . . . 79 [' л а в а 4. Элементы теории ресурсной эффективности вычисли тельных алrоритмов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82  1.