ВВЕДЕНИЕ
ГЛАВА I.АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ К ОЦЕНКЕ КАЧЕСТВА АЛГОРИТМОВ
1.1. Понятие и определения алгоритма.
1.2. Требования к алгоритмам и их свойства.
1.3. Модели вычислений.
1.3.1 .Основные компоненты модели вычислений.
1.3.2.Модель вычислений для языка процедурного программирования.
1.3.3.Базовые операции механизма реализации
1.4. Оценки ресурсной эффективности алгоритмов.
1.4.1.Классические методы оценки алгоритмов
1.4.2.0ценки в теории сложности вычислений.
1.4.3.Терминология и обозначения в теории ресурсной эффективности
1.4.4.Ресурсная характеристика и ресурсная сложность алгоритма
1.5. Комплексные критерии качества алгоритмов
1.6. Требование стабильности по времени
1.7. Классификация компьютерных алгоритмов по степени влияния особенностей входов на трудоемкость
1.8.Постановка задачи исследования.
ГЛАВА 2.ВЕРОЯТНОСТЫЙ ПОДХОД К ОПИСАНИЮ ТРУДОЕМКОСТИ КОМПЬЮТЕРНЫХ АЛГОРИТМОВ.
2.1. Особенности трудоемкости алгоритмов в классе ЫРЯ
2.2. Трудоемкость алгоритма на входах фиксированной длины как дискретная ограниченная случайная величина.
2.3. Гистограмма относительных частот трудомкости для алгоритма умножения длинных целых чисел в столбик
2.4. Трудоемкость как случайная функция и ее статистические точечные оценки.
2.5. Выводы
ГЛАВА 3.ИНФОРМАЦИОННАЯ ЧУВСТВИТЕЛЬНОСТЬ КОМПЬЮТЕРНЫХ АЛГОРИТМОВ И ЕЕ КОЛИЧЕСТВЕННАЯ МЕРА
3.1. Вычисление количественной меры информационной чувствительности на основе квантилей аппроксимирующей функции плотности
3.2. Квантильная количественная мера информационной чувствительности как функция доверительной вероятности и функция размерности
3.3. Методика вычисления квантильной количественной меры информационной чувствительности для случая аппроксимации гистограммы относительных частот функцией плотности бета
распределения.
ЗАВыводы
ГЛАВА 4. СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПОИСКА ПОДСТРОКИ В СТРОКЕ НА ОСНОВЕ ИНФОРМАЦИОННОЙ ЧУВСТВИТЕЛЬНОСТИ
4.1. Задача поиска подстроки в строке.
4.2. Минимум и максимум теоретической функции трудоемкости алгоритма РабинаКарпа в случае однократного вхождения подстроки. .
4.3. Теоретическая функция трудоемкости алгоритма КнутаМоррисаПратта в случае однократного вхождения подстроки.
4.4. Теоретическая функция трудоемкости алгоритма последовательного, поиска в случае однократного вхождения подстроки.
4.5. Сравнение алгоритмов РабинаКарпа, КнутаМоррисаПратта и последовательного поиска по критерию стабильности по времени на основе экспериментальных данных.
4.5.1 .Экспериментальное исследование алгоритма РабинаКарпа 1 4.5.2.Эксперимен тальное исследование алгоритма КнутаМорриса
Пратта.
4.5.3.Экспериментальное исследование алгоритма последовательного
поиска.
4.5.4. Сравнение алгоритмов РабинаКарпа, КнутаМоррисаПратта и последовательног о поиска по стабильности по времени.
4.6. Изменение значений количественной квантильной меры информационной чувствительности для алгоритмов поиска подстроки в строке при изменении длины строки и длины подстроки.
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
- Київ+380960830922