Введение
Глава 1 . Анализ существующих подходов к оценке качества алгоритмов 12
1.1. Понятие и определения алгоритма 12
1.2. Требования к алгоритмам и их свойства 16
1.3. Модели вычислений 19
1.3.1.Основные компоненты модели вычислений 19
1.3.2.Модель вычислений для языка процедурного программирования. 21
1.3.3.Базовые операции механизма реализации 22
1.4. Оценки ресурсной эффективности алгоритмов 25
1.4.1.Классические методы оценки алгоритмов 25
1.4.2.Оценки в теории сложности вычислений 28
1.4.3.Терминология и обозначения в теории ресурсной эффективности 29
1.4.4.Ресурсная характеристика и ресурсная сложность алгоритма... 33
1.5. Комплексные критерии качества алгоритмов 34
1.6. Требование стабильности по времени 43
1.7. Классификация компьютерных алгоритмов по степени влияния особенностей входов на трудоемкость 45
1.8.Постановка задачи исследования 59
Глава 2. Вероятностный подход к описанию трудоемкости компьютерных алгоритмов 60
2.1. Особенности трудоемкости алгоритмов в классе NPR 60
2.2. Трудоемкость алгоритма на входах фиксированной длины как дискретная ограниченная случайная величина 64
2.3. Гистограмма относительных частот трудоёмкости для алгоритма умножения длинных целых чисел «в столбик» 66
2.4. Трудоемкость как случайная функция и её статистические точечные оценки 70
2.5. Выводы 74
Глава 3. Информационная чувствительность компьютерных алгоритмов и ее количественная мера 75
3.1. Вычисление количественной меры информационной чувствительности на основе квантилей аппроксимирующей функции плотности 75
3.2. Квантильная количественная мера информационной чувствительности как функция доверительной вероятности и функция размерности 78
3.3. Методика вычисления квантильной количественной меры информационной чувствительности для случая аппроксимации гистограммы относительных частот функцией плотности бета-распределения 79
3.4 Выводы 88
Глава 4. Сравнительный анализ алгоритмов поиска подстроки в строке на основе информационной чувствительности 90
4.1. Задача поиска подстроки в строке 90
4.2. Минимум и максимум теоретической функции трудоемкости алгоритма Рабина-Карпа в случае однократного вхождения подстроки. 93
4.3. Теоретическая функция трудоемкости алгоритма Кнута-Морриса-Пратта в случае однократного вхождения подстроки 96
4.4. Теоретическая функция трудоемкости алгоритма последовательного, поиска в случае однократного вхождения подстроки 98
4.5. Сравнение алгоритмов Рабина-Карпа, Кнута-Морриса-Пратта и последовательного поиска по критерию стабильности по времени на основе экспериментальных данных 100
4.5.1.Экспериментальное исследование алгоритма Рабина-Карпа... 101
4.5.2.Экспериментальное исследование алгоритма Кнута-Морриса-Пратта 101
4.5.3.Экспериментальное исследование алгоритма последовательного поиска 102
4.5.4. Сравнение алгоритмов Рабина-Карпа, Кнута-Морриса-Пратта и последовательного поиска по стабильности по времени 103
4.6. Изменение значений количественной квантильной меры информационной чувствительности для алгоритмов поиска подстроки в строке при изменении длины строки и длины подстроки 106
Заключение 109
Список использованных источников 111
Приложение
