Informacionnaya chuvstvitel'nost' komp'yuternyx algoritmov

Информационная чувствительность компьютерных алгоритмов. Петрушин В.Н., Ульянов М.В. М.: ФИЗМАТЛИТ, 2010. 224 с. ISBN 978-5-9221-1264-2......Page 1
Оглавление......Page 3
Предисловие......Page 6
Введение......Page 8
Список литературы......Page 14
Глава 1. Алгоритмы: определения, требования, оценки......Page 15
§1.1. Понятие и определения алгоритма......Page 16
§1.2. Требования к алгоритмам и их свойства......Page 22
§1.3. Модели вычислений и алгоритмы......Page 26
§1.4. Оценки ресурсной эффективности алгоритмов......Page 31
§1.5. Комплексные критерии качества алгоритмов......Page 39
§1.6. Особенности разработки алгоритмического обеспечения в аспекте результатов теории алгоритмов......Page 45
Задачи и упражнения......Page 50
Список литературы......Page 51
Глава 2. Специальные классификации компьютерных алгоритмов......Page 54
§2.1. Классификация компьютерных алгоритмов по степени влияния особенностей входов на трудоёмкость......Page 54
§ 2.2. Классификация компьютерных алгоритмов по требованиям к дополнительной памяти......Page 63
§2.3. Классы статических и потоковых алгоритмов......Page 66
Задачи и упражнения......Page 72
Список литературы......Page 74
Глава 3. Вероятностный подход к описанию трудоёмкости компьютерных алгоритмов......Page 75
§3.1. Особенности трудоёмкости алгоритмов в классе NPR......Page 76
§3.2. Трудоёмкость алгоритма на входах фиксированной длины как дискретная ограниченная случайная величина......Page 79
§3.3. Гистограммы относительных частот трудоёмкости......Page 80
§3.4. Трудоёмкость как случайная функция и её статистические точечные оценки......Page 85
§ 3.5. Проблема теоретического распределения вероятностей для значений трудоёмкости алгоритма как дискретной ограниченной случайной величины......Page 91
Задачи и упражнения......Page 102
Список литературы......Page 103
Глава 4. Аппроксимация распределения значений трудоёмкости функциями плотности с ограниченной вариацией......Page 105
§4.1. Возможность использования случайных величин, имеющих плотности, для аппроксимации распределения значений трудоёмкости алгоритма......Page 105
§4.2. Функции плотности распределения вероятностей с ограниченной вариацией и их свойства......Page 108
§4.3. Бета-распределение как одно из универсальных распределений для случайных величин с носителем на сегменте......Page 116
§4.4. Методы восстановления параметров функций плотности на основе данных выборки......Page 122
§4.5. Подходы к решению задачи оценки границ генеральной совокупности по данным выборки......Page 125
§4.6. Критерии проверки гипотез о виде закона распределения и особенности их применения к случайным величинам с ограниченной вариацией......Page 128
§4.7. Подходы к построению гистограммы относительных частот......Page 133
Задачи и упражнения......Page 136
Список литературы......Page 136
Глава 5. Информационная чувствительность компьютерных алгоритмов и её количественные меры......Page 138
§5.1. Понятие информационной чувствительности алгоритмов......Page 138
§5.2. Количественная нормированная мера информационной чувствительности на основе статистических точечных оценок трудоёмкости......Page 140
§5.3. Количественная нормированная мера информационной чувствительности на основе квантилей аппроксимирующей функции плотности......Page 143
§ 5.4. Классификация компьютерных алгоритмов по статистической мере информационной чувствительности......Page 152
§5.5. Доверительная трудоёмкость — новая оценка качества компьютерных алгоритмов, основанная на информационной чувствительности......Page 157
Задачи и упражнения......Page 163
Список литературы......Page 165
Глава 6. Размерностная чувствительность компьютерных алгоритмов......Page 166
§6.1. Понятие размерностной чувствительности компьютерных алгоритмов......Page 166
§6.2. Размерностная чувствительность алгоритмов в подклассах класса NPR......Page 168
§6.3. Классификация компьютерных алгоритмов по размерностной чувствительности......Page 170
Задачи и упражнения......Page 172
Список литературы......Page 173
Глава 7. Статистические исследования ресурсных характеристик алгоритмов......Page 174
§7.1. Цели и задачи статистического исследования компьютерных алгоритмов......Page 174
§7.2. Структура инструментальных средств для исследования ресурсных характеристик компьютерных алгоритмов......Page 176
§7.3. Особенности планирования экспериментального исследования ресурсных характеристик компьютерных алгоритмов......Page 182
Задачи и упражнения......Page 195
Список литературы......Page 196
Глава 8. Сравнительный анализ компьютерных алгоритмов с использованием информационной чувствительности......Page 197
§8.1. Выбор рационального алгоритма поиска по ключу на основе анализа информационной чувствительности......Page 197
§ 8.2. Задача поиска подстроки в строке. Анализ информационной чувствительности алгоритма Рабина-Карпа......Page 213
Задачи и упражнения......Page 222
Список литературы......Page 223