logologo
(812)328-44-22

Стоимость: 320 руб

Купить

Эффективные по времени и памяти алгоритмические приближения чисел и функций

Автор:Яхонтов С. В., Косовский Н. К., Косовская Т.М.

Год издания:2012

Сведения об издании:СПб.: Изд-во С.-Петерб. ун-та, 2012. — 256 с. ISBN 978-5-288-05283-5

Вид издания:Учебное пособие

Количество страниц:256

Учебное пособие содержит подробное обсуждение алгоритмических вещественных и комплексных чисел и функций с ограниченной сложностью вычисления рационально-значных приближений. В качестве основной вычислительной модели для определения алгоритмических чисел и функций используется машина Тьюринга. В качестве классов вычислительной сложности, практически полезных для создания таких систем чисел и функций, берутся класс полиномиальных вычислений по времени и класс линейных вычислений по емкости. В пособии приведены алгоритмы упомянутой сложности для вещественных чисел и функций, часто используемых на практике. Для проверки теоретических построений реализована библиотека классов на языке программирования C#. Для следующих вычислительных моделей доказываются условия полиномиальной реализации на машине Тьюринга: паскалевидные функции, итеративные паскалевидные функции, рефал-5-функции, итеративные рефал-5-функции, нормальные алгорифмы, алгоритмы Маркова—Поста, именованные и рекурсивные алгоритмы Маркова—Поста. Данные вычислительные модели полезно использовать для доказательства полиномиальности вычислений алгоритмических чисел и функций.

Рассматриваются также алгоритмические числа и функции, квазилинейные по времени и линейные по памяти при вычислении на машине Шёнхаге.

Учебное пособие рассчитано на студентов, магистрантов и аспирантов, специализирующихся в области теоретической и практической информатики. Подробнее

Основные партнёры