Информационная чувствительность компьютерных алгоритмов.

Description

Информационная чувствительность компьютерных алгоритмов. Петрушин В.Н., Ульянов М.В. М.: ФИЗМАТЛИТ, 2010. 224 с. ISBN 978-5-9221-1264-2 Оглавление Предисловие Введение Список литературы Глава 1. Алгоритмы: определения, требования, оценки §1.1. Понятие и определения алгоритма §1.2. Требования к алгоритмам и их свойства §1.3. Модели вычислений и алгоритмы §1.4. Оценки ресурсной эффективности алгоритмов §1.5. Комплексные критерии качества алгоритмов §1.6. Особенности разработки алгоритмического обеспечения в аспекте результатов теории алгоритмов Задачи и упражнения Список литературы Глава 2. Специальные классификации компьютерных алгоритмов §2.1. Классификация компьютерных алгоритмов по степени влияния особенностей входов на трудоёмкость § 2.2. Классификация компьютерных алгоритмов по требованиям к дополнительной памяти §2.3. Классы статических и потоковых алгоритмов Задачи и упражнения Список литературы Глава 3. Вероятностный подход к описанию трудоёмкости компьютерных алгоритмов §3.1. Особенности трудоёмкости алгоритмов в классе NPR §3.2. Трудоёмкость алгоритма на входах фиксированной длины как дискретная ограниченная случайная величина §3.3. Гистограммы относительных частот трудоёмкости §3.4. Трудоёмкость как случайная функция и её статистические точечные оценки § 3.5. Проблема теоретического распределения вероятностей для значений трудоёмкости алгоритма как дискретной ограниченной случайной величины Задачи и упражнения Список литературы Глава 4. Аппроксимация распределения значений трудоёмкости функциями плотности с ограниченной вариацией §4.1. Возможность использования случайных величин, имеющих плотности, для аппроксимации распределения значений трудоёмкости алгоритма §4.2. Функции плотности распределения вероятностей с ограниченной вариацией и их свойства §4.3. Бета-распределение как одно из универсальных распределений для случайных величин с носителем на сегменте §4.4. Методы восстановления параметров функций плотности на основе данных выборки §4.5. Подходы к решению задачи оценки границ генеральной совокупности по данным выборки §4.6. Критерии проверки гипотез о виде закона распределения и особенности их применения к случайным величинам с ограниченной вариацией §4.7. Подходы к построению гистограммы относительных частот Задачи и упражнения Список литературы Глава 5. Информационная чувствительность компьютерных алгоритмов и её количественные меры §5.1. Понятие информационной чувствительности алгоритмов §5.2. Количественная нормированная мера информационной чувствительности на основе статистических точечных оценок трудоёмкости §5.3. Количественная нормированная мера информационной чувствительности на основе квантилей аппроксимирующей функции плотности § 5.4. Классификация компьютерных алгоритмов по статистической мере информационной чувствительности §5.5. Доверительная трудоёмкость — новая оценка качества компьютерных алгоритмов, основанная на информационной чувствительности Задачи и упражнения Список литературы Глава 6. Размерностная чувствительность компьютерных алгоритмов §6.1. Понятие размерностной чувствительности компьютерных алгоритмов §6.2. Размерностная чувствительность алгоритмов в подклассах класса NPR §6.3. Классификация компьютерных алгоритмов по размерностной чувствительности Задачи и упражнения Список литературы Глава 7. Статистические исследования ресурсных характеристик алгоритмов §7.1. Цели и задачи статистического исследования компьютерных алгоритмов §7.2. Структура инструментальных средств для исследования ресурсных характеристик компьютерных алгоритмов §7.3. Особенности планирования экспериментального исследования ресурсных характеристик компьютерных алгоритмов Задачи и упражнения Список литературы Глава 8. Сравнительный анализ компьютерных алгоритмов с использованием информационной чувствительности §8.1. Выбор рационального алгоритма поиска по ключу на основе анализа информационной чувствительности § 8.2. Задача поиска подстроки в строке. Анализ информационной чувствительности алгоритма Рабина-Карпа Задачи и упражнения Список литературы