Сравнительный анализ компьютерных алгоритмов на основе информационной чувствительности

• Автор: Алексеенко, Анна Станиславовна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 122 с. : ил.

ВВЕДЕНИЕ

ГЛАВА 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. Изменение значений количественной квантильной меры информационной чувствительности для алгоритмов поиска подстроки в строке при изменении длины строки и длины подстроки.
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Предложен метод определения значений квантильной меры информационной чувствительности компьютерных алгоритмов при фиксированной длине входа и заданной доверительной вероятности, основанный на вычислении квантилей функции распределения вероятностей, аппроксимирующей частотное распределение значений трудомкости алгоритма. Для решения задачи сравнительного анализа алгоритмов по информационной чувствительности предложена методика построения квантильной меры информационной чувствительности как функции длины входа. Практическая ценность результатов работы. Реализация результатов. Разработано программное обеспечение Вычисление информационной чувствительности и доверительной трудоемкости компьютерных алгоритмов, на которое получено свидетельство о регистрации программы для ЭВМ Роспатента . Результаты исследования используются в учебном процессе Московского государственного областного университета, Московского государственного индустриального университета в рамках дисциплины Теория алгоритмов, что подтверждено соответствующими актами о внедрении. Апробация работы. XV Международной научнотехнической конференции Информационные системы и технологии Нижний Новгород, г. IX Всероссийской научнотехнической конференции Повышение эффективности средств обработки информации на базе математического моделирования Тамбов, г. Всероссийской научной конференции МФТИ Современные проблемы фундаментальных и прикладных наук Москва, г. Публикации. Основные результаты по теме диссертации опубликованы в 4х работах, из них 1 в журнале, включенном в Перечень ВАК РФ. Результаты проведенных исследований подробно изложены в последующих четырех главах. В первой главе даны формулировки основных понятий теории алгоритмов, используемые далее, и проведен анализ основных методов оценки качества алгоритмов. Проанализированы основные подходы к решению задачи оценки качества алгоритмов и способы построения комплексных критериев Б. А. Трахтенброт, М. Мошков, В. А. Носов, Д. Э. Кнут, А. Лхо, Дж. Хопкрофт, Дж. Ульман, Р. Грэхем, Д. Гасфилд, Р. Карп, Р. Тарьян, и др Рассмотрены основные компоненты комплексного критерия качества алгоритма. Показано, чао в ряде проблемных областей возникает требование стабильности по времени программной реализации алгоритма, учт которого приводит к необходимости использования количественной меры информационной чувствительности компьютерных алгоритмов. Анализ существующей статистической количественной меры информационной чувствительности алгоритмов Ульянов М. В. показал, что она не позволяет указать интервал значений трудомкости при заданной вероятности. В аспекте исследования информационной чувствительности рассмотрена классификация алгоритмов по степени влияния особенностей входных данных на значения трудоемкости. Более детально рассмотрены алгоритмы класса МРЯ количественнопараметрические по трудоемкости. На основе проведенного в главе анализа сформулирована постановка задачи о необходимости введения новой количественной меры, обеспечивающей учт требования стабильности по времени для компьютерных алгоритмов класса , и позволяющей указать интервал значений трудомкости при заданной вероятности. Во второй главе обоснован выбор вероятностного подхода к описанию трудоемкости алгоритмов. Оп в рамках исследуемой проблемной области применения алгоритма в данной программной системе. В качестве модельного примера приведены экспериментальные данные, полученные в результате исследования алгоритма умножения чисел в столбик. В третьей главе введена квантильная количественная мера информационной чувствительности компьютерных алгоритмов. Показано, что существующая статистическая количественная мера информационной чувствительности не полностью удовлетворяет указанным требованиям. В четвертой главе проведен анализ применения методики вычисления информационной чувствительности для сравнения алгоритмов по кри терию стабильности по времени. Для иллюстрации разработанной методики была выбрана задача поиска подстроки в строке и три алгоритма, решающие эту задачу алгоритм РабинаКарпа, алгоритм КнутаМоррисаПрагга и алгоритм последовательного поиска.