Содержание к диссертации
Введение
Глава 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
Приложение
- Комплексные критерии качества алгоритмов
- Гистограмма относительных частот трудоёмкости для алгоритма умножения длинных целых чисел «в столбик»
- Квантильная количественная мера информационной чувствительности как функция доверительной вероятности и функция размерности
- Теоретическая функция трудоемкости алгоритма Кнута-Морриса-Пратта в случае однократного вхождения подстроки
Введение к работе
Актуальность исследования.
Современный этап развития программных средств, характеризуется сложностью решаемых задач и высокими требованиями к программным реализациям и алгоритмическому обеспечению программных средств и систем. В связи с этим при разработке программного обеспечения возникает задача оценки качества и выбора алгоритмов, рациональных в условиях данной проблемной области применения.
В разное время вопросами анализа сложности алгоритмов, оценки качества программных средств и систем и их алгоритмического обеспечения занимались такие российские и зарубежные ученые, как: A. А. Марков, Г. Е. Цейтлин, Г. С. Цейтин, Ю. И. Янов, Л. А. Левин, B. Е. Котов, В. А. Горбатов, А. И. Мальцев, М. Ю. Мошков, В. А. Носов, Б. Я. Фалевич, Д. Э. Кнут, А. Ахо, Дж. Хопкрофт, Дж. Ульман, М. Гэри, Д. Джонсон, Р. Грэхем, Д. Гасфилд, Р. Карп, Р. Тарьян, А. Кобхем, и др.
Результатом этих исследований являются способы построения комплексных критериев оценки качества алгоритмов, учитывающие их различные характеристики: временную сложность, емкостную сложность, точность и т. д.
В некоторых проблемных областях к программному обеспечению предъявляются специфические требования, связанные с их особенностями. Характерным примером могут служить системы реального времени, диалоговые системы с существенными временными ограничениями, в том числе поисковые системы. Программное обеспечение таких систем должно не только удовлетворять временным ограничениям, но и обладать стабильностью по времени — различные входы алгоритма при фиксированной длине входа не должны приводить к значительным изменениям времени выполнения. Этот показатель является важным, т. к. обеспечивает, наряду с исполнительной аппаратурой, устойчивое время отклика программной системы на различные входы фиксированной длины.
Учет требования стабильности по времени может быть осуществлен на основе понятия информационной чувствительности компьютерных алгоритмов, введенного в 2004 г. М.В.Ульяновым и В.А.Головешкиным. Однако предложенная авторами статистическая количественная мера информационной чувствительности алгоритмов не позволяет указать интервал значений трудоёмкости при заданной вероятности, и таким образом не может быть адаптирована к конкретным требованиям разработчиков алгоритмического обеспечения.
Таким образом, актуальной является разработка подхода к определению новой количественной меры информационной чувствительности компьютерных алгоритмов, отражающей величину интервала значений трудоемкости для различных входов фиксированной длины, в котором обеспечивается заданная вероятность (доверительный интервал трудоёмкости).
Основные задачи исследования.
Анализ основных подходов к оценке качества и выбору компьютерных алгоритмов.
Постановка задачи о вычислении количественной характеристики, позволяющей оценить стабильность по времени компьютерных алгоритмов.
Обоснование выбора вероятностного подхода к рассмотрению трудоемкости алгоритмов класса NPR (класса алгоритмов количественно параметрических по трудоемкости).
Разработка методики вычисления количественной характеристики информационной чувствительности при фиксированной длине входа.
Разработка методики вычисления количественной характеристики информационной чувствительности как функции длины входа.
6. Иллюстрация разработанных методик на модельных примерах и решение задачи рационального выбора алгоритмов на основе квантильной количественной меры информационной чувствительности.
Объект исследования. Компьютерные алгоритмы, принадлежащие классу количественно-параметрических по трудоемкости алгоритмов (класс NPR).
Предмет исследования. Количественная мера информационной чувствительности компьютерных алгоритмов.
Методы исследования. В работе используются методы теоретической информатики, теории алгоритмов, методы математической статистики.
Научная новизна.
Введена квантильная количественная мера информационной чувствительности компьютерных алгоритмов.
Предложен метод определения значений квантильной меры информационной чувствительности компьютерных алгоритмов при фиксированной длине входа и заданной доверительной вероятности, основанный на вычислении квантилей функции распределения вероятностей, аппроксимирующей частотное распределение значений трудоёмкости алгоритма.
Для решения задачи сравнительного анализа алгоритмов по информационной чувствительности предложена методика построения квантильной меры информационной чувствительности как функции длины входа.
Практическая ценность результатов работы.
Разработанный метод определения квантильной меры информационной чувствительности может использоваться при проектировании программного обеспечения для решения задачи выбора
7 алгоритмов по комплексному критерию оценки их качества с учетом требования стабильности по времени.
Реализация результатов. Разработано программное обеспечение «Вычисление информационной чувствительности и доверительной трудоемкости компьютерных алгоритмов», на которое получено свидетельство о регистрации программы для ЭВМ Роспатента № 2010611351.
Результаты исследования используются в учебном процессе - Московского государственного областного университета, Московского государственного индустриального университета в рамках дисциплины «Теория алгоритмов», что подтверждено соответствующими актами о внедрении.
Апробация работы. Основные результаты диссертации были представлены на 4-х научных конференциях и семинарах: XV Международной научно-технической конференции «Информационные системы и технологии» (Нижний Новгород, 2009 г.);
IX Всероссийской научно-технической конференции «Повышение эффективности средств обработки информации на базе математического моделирования» (Тамбов, 2009 г.);
52-ой Всероссийской научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук" (Москва, 2009 г.);
III школе-семинаре «Задачи системного анализа, управления и обработки информации» (Москва, 2009 г.).
Публикации. Основные результаты по теме диссертации опубликованы в 4-х работах, из них 1 — в журнале, включенном в Перечень ВАК РФ.
Результаты проведенных исследований подробно изложены в последующих четырех главах.
В первой главе даны формулировки основных понятий теории алгоритмов, используемые далее, и проведен анализ основных методов оценки качества алгоритмов.
Проанализированы основные подходы к решению задачи оценки качества алгоритмов и способы построения комплексных критериев (Б.А. Трахтенброт, М. Ю. Мошков, В. А. Носов, Д. Э. Кнут, А. Ахо, Дж. Хопкрофт, Дж. Ульман, Р. Грэхем, Д. Гасфилд, Р. Карп, Р. Тарьян, и др.). Рассмотрены основные компоненты комплексного критерия качества алгоритма.
Показано, что в ряде проблемных областей возникает требование стабильности по времени программной реализации алгоритма, учёт которого приводит к необходимости использования количественной меры информационной чувствительности компьютерных алгоритмов. Анализ существующей статистической количественной меры информационной чувствительности алгоритмов (Ульянов М.В.) показал, что она не позволяет указать интервал значений трудоёмкости при заданной вероятности.
В аспекте исследования информационной чувствительности рассмотрена классификация алгоритмов по степени влияния особенностей входных данных на значения трудоемкости. Более детально рассмотрены алгоритмы класса NPR (количественно-параметрические по трудоемкости).
На основе проведенного в главе анализа сформулирована постановка задачи о необходимости введения новой количественной меры, обеспечивающей учёт требования стабильности по времени для компьютерных алгоритмов класса NPR, и позволяющей указать интервал значений трудоёмкости при заданной вероятности.
Во второй главе обоснован выбор вероятностного подхода к описанию трудоемкости алгоритмов.
Предложено рассматривать значения трудоемкости алгоритма класса NPR на входах фиксированной длины FA как дискретную ограниченную случайную величину, для чего построена вероятностная модель на множестве входов фиксированной длины Dn: — QD — выборочное пространство входов фиксированной длины QD = Dn, при этом случайное событие со є Q.D состоит в том, что в качестве входных данных алгоритма предъявляется вход DjSDn, j = 1,М, где М — число различных допустимых входов алгоритма длины п; — PDQ — вероятностная мера на Q^, отражающая частотную встречаемость входов из Dn в рамках исследуемой проблемной области применения алгоритма в данной программной системе. PF{FA=fi) = YJPD{Dj\ DjiDjeD^f^Dj)-/,
В качестве модельного примера приведены экспериментальные данные, полученные в результате исследования алгоритма умножения чисел «в столбик».
В третьей главе введена квантильная количественная мера информационной чувствительности компьютерных алгоритмов.
Сформулированы требования, которыми должна обладать количественная мера информационной чувствительности: — быть эффективно вычислимой на основе экспериментальных данных, полученных в ходе исследования алгоритма; измеряться в единых единицах измерения в количественной шкале (шкала с естественным нулем, максимумом или минимумом); обладать универсальностью, т. е. независимостью от предметной области, в которой используется данный алгоритм, иначе говоря, не должна быть проблемно-специфичной; подчиняться единому для различных предметных областей принципу содержательной интерпретации; быть сопоставимой, т.е. давать возможность решения на её основе задачи сравнения и выбора рациональных алгоритмов; обеспечивать возможность идентификации интервала трудоёмкости по заданной вероятности.
Показано, что существующая статистическая количественная мера информационной чувствительности не полностью удовлетворяет указанным требованиям.
Предложен подход к рассмотрению информационной чувствительности Sj(y,n) как длины теоретического сегмента варьирования трудоемкости, в которой с заданной вероятностью у будут наблюдаться значения трудоемкости алгоритма на входах фиксированной длины п.
В четвертой главе проведен анализ применения методики вычисления информационной чувствительности для сравнения алгоритмов по критерию стабильности по времени.
Для иллюстрация разработанной методики была выбрана задача поиска подстроки в строке и три алгоритма, решающие эту задачу: алгоритм Рабина-Карпа, алгоритм Кнута-Морриса-Пратта и алгоритм последовательного поиска.
На основе проведенного анализа результатов был сделан вывод об эффективности использования введенной квантильной количественной меры информационной чувствительности как компоненты комплексного критерия оценки качества алгоритмов, позволяющей учесть требование стабильности по времени при комплексной оценке качества алгоритмов.
Комплексные критерии качества алгоритмов
На современном этапе развития программных систем, который характеризуется как сложностью решаемых задач, так и комплексом высоких требований к программным реализациям, особые требования предъявляются и к алгоритмическому обеспечению программных средств и систем. Высокое быстродействие и производительность современных компьютеров не снижают требований к алгоритмическому обеспечению. Некоторые требования, в том числе и временные, остаются актуальными, ввиду возрастающей размерности решаемых задач. Проблема полиномиальной разрешимости NP - полных и NP - трудных задач остается сегодня открытой [32], но возникающие на практике задачи из этих классов побуждают разработчиков искать для них эффективные приближенные алгоритмы.
Очень часто именно выбор или разработка эффективного алгоритма в решающей степени задают не только временные характеристики программ, но и принципиальную возможность решения поставленной задачи за реальное время. В качестве примера можно указать на ряд задач в области современной криптографии, задачи моделирования сложных систем, в том числе в компьютерной биологии [57] и т. д. Алгоритмически актуальной остается группа задач о назначениях, например, различные практические формулировки задачи упаковки.
В рамках разработки алгоритмического обеспечения современных программных систем актуальной является проблема выбора рационального алгоритма в рамках оценок его качества. Критерии оценки качества алгоритмов тесно связаны с оценкой качества программных реализаций, поскольку последние отражают требования технического задания и особенности проблемной области применения. Мы рассмотрим вначале более детально оценки программных реализаций, поскольку в этом случае мы переходим от абстрактной модели вычислений к ресурсам реального компьютера.
Компоненты функции ресурсной эффективности программной реализации алгоритма. Определим в терминах требуемых алгоритмом ресурсов компьютера следующие компоненты, значения которых возможно зависят от характеристик множества D исходных данных алгоритма или некоторых его элементов [63]:
— VcxeiP) — ресурс оперативной памяти в области кода, необходимый для размещения машинного кода, реализующего данный алгоритм. Этот ресурс соотносим с объемом ЕХЕ- файла, с учетом оверлейных структур и принципа организации управления программной системой. Как правило, для одной и той же задачи, короткие по объему реализующего программного кода алгоритмы имеют худшие временные оценки, чем более длинные («быстрые алгоритмы являются в большинстве случаев достаточно сложными» [8]). В основном для небольших программ объём области кода не зависит от D. В случае больших программных систем или комплексов модули управления вычислительным процессом, при определенных исходных данных, могут подгружать в оперативную память дополнительные фрагменты кода. Такой подход характерен для оверлейных структур или программных систем со структурой, адаптивной к входным данным. Аналогичная ситуация может быть следствием выбора различных алгоритмов, рациональных в зависимости от характеристик входа; Кат (Р) — ресурс дополнительной оперативной памяти в области данных, требуемый алгоритмом под временные ячейки, массивы и структуры. Ресурс памяти для входа и выхода алгоритма не учитывается в этой оценке, т. к. является неизменным для всех алгоритмов решения данной задачи. Обычно более быстрые алгоритмы решения некоторой задачи требуют большего объема дополнительной памяти [8, 13]. В качестве примера можно привести быстрый алгоритм сортировки методом индексов [32], требующий дополнительной памяти в объеме, равном значению максимального элемента исходного массива (алгоритм допускает только целочисленные входы). Этот дополнительный объем является «платой» за быстродействие — мы можем получить отсортированный массив за &{п) операций, где п — размерность входного массива; Vsl (D) — ресурс оперативной памяти в области стека, требуемый алгоритмом для организации вызова внутренних процедур и функций. Объем данного ресурса значительно зависит от того, в каком подходе, итерационном или рекурсивном, реализован данный алгоритм. Требуемый объем памяти в области стека может быть критичен при рекурсивной реализации по отношению к размерности решаемой задачи, если дерево рекурсии достаточно «глубоко». Если алгоритм реализуется в объектно-ориентированной среде программирования, то требования к ресурсу стека могут быть значительны за счет длинных цепочек вызовов методов, связанных с наследованием в объектах; ТА (D) — требуемый алгоритмом ресурс процессора является оценкой времени выполнения данного алгоритма на данном компьютере.
Эта оценка определяется функцией трудоемкости алгоритма в зависимости от характеристических особенностей множества исходных данных.
Переход от функции трудоемкости к временной оценке связан с определением средневзвешенного времени ton выполнения обобщенной базовой операции в языке реализации алгоритма на данном процессоре и компьютере. Средневзвешенное время ton может быть получено экспериментальным путем в среде реализации алгоритма. Получение точной функции времени выполнения, учитывающей все особенности архитектуры компьютера, представляет собой достаточно сложную задачу; для оценки сверху можно воспользоваться функцией трудоемкости для худшего случая при данной размерности — /л(п)- Д1 более правдоподобной оценки может быть использована функция трудоемкости в среднем— fA{n). Функции ресурсной эффективности алгоритма и его программной реализации. Одним из возможных подходов к построению ресурсных функций является стоимостной подход, при котором используются весовые коэффициенты. При применении его аддитивной формы, получим функцию ресурсной эффективности алгоритма для входа D в виде [65]
Гистограмма относительных частот трудоёмкости для алгоритма умножения длинных целых чисел «в столбик»
В качестве иллюстрирующего примера приведены экспериментальные данные, подтверждающие предложенный вероятностный подход. Модельным примером является алгоритм умножения длинных целых чисел, реализующий классический метод умножения «в столбик». Поскольку значения трудоемкости ограничены лучшим и худшим случаями при фиксированной длине входа, то предварительно был проведен теоретический анализ функции трудоемкости.
Алгоритм Mult реализует умножение длинных целых двоичных чисел, сводящееся к многократному сложению со сдвигом. Если очередная цифра второго числа равна единице, то первое число добавляется к результату с соответствующим сдвигом. Массивы А и В содержат исходные двоичные числа длиной п, результат умножения записывается в 2п ячейках массива С. Запись этого алгоритма в принятом алгоритмическом базисе имеет следующий вид (справа в строке указано число заданных базовых операций модели вычислений):
На вход данного алгоритма подаются массивы А и В из п элементов — соответствующая задача имеет тип Ln, а трудоемкость алгоритма зависит как от количества чисел в массиве, так и от количества единиц во втором массиве — алгоритм является количественно-параметрическим (класс NPR, подкласс NPRS) [1]. Значение т в строках, связанных с циклом For обозначает число проходов данного цикла, зависящее от особенностей входа. Очевидно, что в лучшем случае, когда массив В подаваемый на вход алгоритма полностью состоит из нулей, тело цикла For не выполняется (т = 0), и, используя трудоёмкости, указанные в строках записи алгоритма, мы получаем функцию трудоемкости этого алгоритма в лучшем случае:
Аналогично, в худшем случае, когда массив В полностью состоит из единиц, цикл просматривает все элементы массива А, и значение т изменяется от 1 до п — 1 в зависимости от цикла по і, что в сумме даёт трудоёмкость в худшем случае: / (п) = \5п + 2 + п + 2п + п{\ + Ъп) + {5 + Ъ + 2 + 2)п2 +2п = Экспериментальные данные. Экспериментальное исследование алгоритма с целью определения частотной встречаемости значений трудоёмкости W3 состоит в проведении ряда экспериментов с его программной реализацией при фиксированной длине входа. Для каждого эксперимента генерируется случайный допустимый алгоритмом вход и, с помощью специально расставленного счётчика, фиксируется число заданных алгоритмом базовых операций. В предположении о том, что для исследуемого алгоритма в теории получены функции трудоёмкости для лучшего и худшего случаев, теоретический размах варьирования /2 - fj разбивается на выбранное число полусегментов. Далее определяется частотная встречаемость значений трудоёмкости W3 для каждого из полученных полусегментов и строится экспериментальная гистограмма относительных частот.
В соответствии с формулами, соответствующими минимальному и максимальному значениям функции трудоемкости для алгоритма умножения длинных целых чисел «в столбик» при « = 100 минимум и максим равны соответственно: // =1502, f2 = 152102, и теоретический размах варьирования равен 150600.
При разбиении размаха варьирования на равные полусегменты в большинстве из них экспериментальные частоты оказались равны нулю при 20000 экспериментов. Это свидетельствует о том, что входы, приводящие к таким значениям трудоёмкости, имеют вероятности, близкие к нулю, и не были сгенерированы. В связи с этим на рисунке 5 показаны только ненулевые части гистограммы относительных частот трудоёмкости для алгоритма умножения длинных целых чисел «в столбик» при длине входа п = 100, полученные по результатам обработки 20000 экспериментов.
Квантильная количественная мера информационной чувствительности как функция доверительной вероятности и функция размерности
В целях практического применения и теоретического исследования алгоритма необходимо рассматривать S}(y) не только как функцию доверительной вероятности, но и как функцию размерности — S: (у, п). Для построения такой функции необходима методика, опирающаяся на экспериментальные данные и прогнозирование значений Sl (у, п). Такая методика расчета квантильной количественной меры информационной чувствительности SlQ(y,n) как функции доверительной вероятности у и длины входа алгоритма п включает в себя следующие этапы: — экспериментальное исследование алгоритма, построение гистограммы относительных частот трудоёмкости и подбор аппроксимирующей функции плотности распределения вероятностей; — определение актуального сегмента длин входов, сегмента длин для экспериментального исследования и шага изменения длины входа; — получение данных о трудоёмкости алгоритма для длин входов в сегменте экспериментального исследования; — идентификация параметров аппроксимирующей функции плотности методом моментов на основе данных выборки; — задание доверительной вероятности у и расчёт на основе полученных данных значений SlQ(y,n) на основе 1/2±у/2-квантилей аппроксимирующей функции плотности относительно медианы распределения в сегменте экспериментального исследования; — построение функции тренда количественной меры информационной чувствительности или функций тренда параметров аппроксимирующего распределения, и прогнозирование значений SlQ [у, п) для актуального сегмента длин входов.
Основной проблемой вероятностного подхода к описанию трудоёмкости алгоритма является сложность теоретического доказательства того факта, что значения трудоёмкости данного алгоритма имеют определённый закон распределения. В общем случае задача может быть поставлена как задача нахождения такого закона распределения, который обладал бы определённой гибкостью формы и давал приемлемую аппроксимацию наблюдаемой гистограммы относительных частот трудоемкости. Поскольку значения функции трудоёмкости при фиксированной длине входа ограничены, то необходимо рассматривать дискретные функции распределения, ограниченные на сегменте. С другой стороны, значительное число различных значений трудоёмкости позволяет перейти к рассмотрению непрерывных распределений, описываемых функциями плотности. В качестве аппроксимирующей функции была выбрана функция плотности бета-распределения, которая описывает непрерывную случайную величину, носителем которой является сегмент [0, l]. Функция плотности бета-распределения, являясь двухпараметрической, обладает достаточно большой гибкостью формы. Ещё одно важное свойство этого распределения — устойчивость, т. е. сумма случайных величин, подчиняющихся бета-распределению, также имеет бета-распределение.
Плотность распределения вероятностей для бета-распределения задаётся функцией: где Г(-) — гамма функция Эйлера, а а и /3 — параметры функции плотности. В предположении об аппроксимации частотной встречаемости значений трудоёмкости функцией плотности симметричного бета-распределения, квантильная количественная мера информационной чувствительности иллюстрируется рис. 7. Поскольку носителем бета-распределения является интервал (0;1), то введём в рассмотрение нормированную случайную величину Т, реализации которой tt получаются на основе значений fa путём следующего преобразования: где fv и fA — соответственно минимальное и максимальное значение трудоёмкости, определённое на основе теоретических функций трудоёмкости исследуемого алгоритма для лучшего и худшего случаев при данной длине входа, a ft — значение трудоёмкости в /-ом эксперименте для случайного допустимого входа: ft - fA(D,), i = l,m, при этом очевидно, что -є[0,і]. После нормировки экспериментальных данных возможно построение гистограммы относительных частот для случайной величины Т, Если параметры аппроксимирующего бета-распределения известны, то путём интегрирования функции плотности бета-распределения по полусегментам, полученным при построении экспериментальной гистограммы относительных частот для случайной величины Т, могут быть получены теоретические относительные частоты бета-распределения и проверена гипотеза о правомерности такой аппроксимации. Для решения задачи определения параметров аппроксимирующего бета-распределения целесообразно применить метод моментов [55], при этом оценкой математического ожидания является выборочная средняя t, а оценкой дисперсии — «исправленная» выборочная дисперсия s . Математическое ожидание и дисперсия случайной величины Ту имеющей бета-распределение с параметрами а и /3, соответственно равны [55]
Теоретическая функция трудоемкости алгоритма Кнута-Морриса-Пратта в случае однократного вхождения подстроки
Экспериментальное исследование алгоритмов с целью определения частотной встречаемости значений трудоёмкости w состояло в проведении серии экспериментов с их программными реализациями при фиксированной длине входа. Для каждого эксперимента генерировался случайный допустимый алгоритмом вход и, с помощью счётчика, фиксировалось число заданных алгоритмом базовых операций. На вход эксперимента подавался фрагмент текста, в который однократно входил искомый шаблон. В предположении о том, что для исследуемого алгоритма в теории получены функции трудоёмкости для лучшего и худшего случаев, теоретический размах варьирования был разбит на выбранное число интервалов. Далее была определена частотная встречаемость значений трудоёмкости w для каждого из полученных полусегментов и построена экспериментальная гистограмма относительных частот.
При разбиении теоретического размаха варьирования на интервалы в большинстве из них экспериментальные частоты оказались равны нулю при 20000 экспериментов. Это свидетельствует о том, что входы, приводящие к таким значениям трудоёмкости, имеют вероятности, близкие к нулю, и не были сгенерированы. В связи с этим на рисунках 11-13 показаны только ненулевые части гистограмм относительных частот трудоёмкости для алгоритмов Рабина-Карпа, Кнута-Морриса-Пратта и последовательного поиска при длине строки, в которой производится поиск, п = 10000, длине искомой подстроки т = 20, полученные по результатам обработки 20000 экспериментов.
При длине строки п = 10000, длине подстроки т = 20 был осуществлен сравнительный анализ алгоритмов поиска подстроки в строке по стабильности по времени с помощью вычисления количественной квантильной меры информационной чувствительности.
Для каждого из указанных алгоритмов поиска подстроки в строке в качестве основной была выдвинута гипотеза об аппроксимации гистограммы распределения относительных частот функцией плотности бета-распределения.
Для проверки гипотезы о бета-распределении значений трудоёмкости данных алгоритмов была произведена нормировка экспериментальных значений функции трудоёмкости в сегмент [ОД], для которой были вычислены теоретические границы трудоёмкости. На этой основе были рассчитаны нормированные значения трудоёмкости t{, определены границы полусегментов разбиения сегмента [ОД] и рассчитаны эмпирические частоты в полусегментах.
Количество интервалов, на которые разбивался сегмент варьирования значений трудоемкости определялось по формуле Стерджесса: N - число единиц совокупности. В нашем случае N = 20000 - число проведенных экспериментов с программной реализацией каждого из алгоритма. Таким образом, количество интервалов равно 33.
По нормированным данным рассчитаны значения выборочной средней t и выборочной исправленной дисперсии s , на основе которых методом моментов были получены параметры а и /3 аппроксимирующего бета-распределения.
Интегрированием полученной функции плотности по полусегментам были вычислены теоретические частоты. Проверка гипотезы о бета-распределении была выполнена с использованием критерия Пирсона при уровне значимости 0,05.
Наблюдаемое значение критерия х рассчитано по формуле (9), критическое значение — стандартной функцией MS Excel. В результате проверки гипотезы получены следующие результаты: для алгоритма Рабина-Карпа: набл = 27,22, для алгоритма Кнута-Морриса-Пратта: ЛГнабл = 31,23, для алгоритма последовательного поиска: Zna6n =35,74.
Во всех случаях наблюдаемое значение критерия Пирсона было значимо меньше, чем критическая точка набл х {а\к} что позволило принять гипотезу о бета-распределении
