Авторефераты по всем темам >>
Авторефераты по разным специальностям
На правах рукописи
К р и в е н ц о в А л е к с а н д р С е р г е е в и ч Доверительная трудоемкость компьютерных алгоритмов:
разработка оценки и методика определения 05.13.11 Ч Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Москва 2012
Работа выполнена на кафедре Персональные компьютеры и сети в Федеральном бюджетном образовательном учреждении высшего профессионального образования Московский государственный университет приборостроения и информатики.
Научный консультант: доктор технических наук, профессор Ульянов Михаил Васильевич
Официальные оппоненты: Московский государственный университет имени М.В.Ломоносова, факультет вычислительной математики и кибернетики, кафедра Алгоритмические языки, доктор физико-математических наук, профессор Соловьев Сергей Юрьевич Рязанский государственный радиотехнический университет, кафедра Вычислительная и прикладная математика, доктор технических наук, профессор Белов Владимир Викторович
Ведущая организация: Нижегородский государственный технический университет имени Р.Е. Алексеева
Защита состоится л23 мая 2012 г. в 1430 на заседании диссертационного совета Д 212.119.03 в Московском государственном университете приборостроения и информатики по адресу: 107996, г. Москва, ул. Стромынка, д.20.
С диссертацией можно ознакомиться в библиотеке МГУПИ.
Автореферат разослан л23 апреля 2012 г.
Ученый секретарь Г В. Зеленко диссертационного совета к. т. н., доцент
Общая характеристика работы
Актуальность темы Алгоритмическое обеспечение, являющееся неотъемлемой частью программной системы, представляет собой совокупность алгоритмов, которые лежат в основе последующей программной или программно-аппаратной реализации. Эффективность использования ресурсов компьютера, хотя отчасти и определяется выбором среды, языка и тщательностью реализации, но в основном зависит от разработанных и/или выбранных алгоритмов. В связи с этим при разработке программного обеспечения возникает задача оценки качества алгоритма, а также выбора рациональных алгоритмов с учетом особенностей применения из множества существующих в данной предметной области. Критерий выбора, в основном, является комплексным и включает как общие, так и проблемно-зависимые оценки качества алгоритмов. К общим оценкам относятся оценки ресурсной эффективности алгоритмов, как правило, временная и емкостная сложность. Проблемнозависимые оценки связаны с особенностями задачи, например, в задаче сжатия изображения таковыми являются коэффициент сжатия, класс изображения, на который ориентирован алгоритм, метрики качества изображений и так далее.
В разное время вопросами анализа сложности алгоритмов, оценки качества программных средств и систем и их алгоритмического обеспечения занимались такие российские и зарубежные ученые, как: В. Липаев, А. А. Марков, Г. Е. Цейтлин, Г. С. Цейтин, Ю. И. Янов, Л. А. Левин, В. Е. Котов, В. А. Горбатов, А. И. Мальцев, М. Ю. Мошков, В. А. Носов, Б. Я. Фалевич, Д. Э. Кнут, А. Ахо, Дж. Хопкрофт, Дж. Ульман, М. Гэри, Д. Джонсон, Р. Грэхем, Д. Гасфилд, Р. Карп, Р. Тарьян, А. Кобхем, Т. Кормен, Р. Ривест, Г. Штейн, Ч. Лейзерсон и др.
Одним из основных компонент критерия оценки качества является временная эффективность или трудоемкость, в данном случае понимаемая как число базовых операций, заданных алгоритмом на конкретном входе.
Тип базовых операций определяется выбранной моделью вычислений. В настоящее время целым рядом ученых (Д.Э. Кнут, Д. Гасфилд, А. Ахо, Дж.
Хопкрофт, Дж. Ульман) разработаны различные методики анализа и оценки качества алгоритмов, позволяющие:
1. Получить теоретические функции трудоемкости алгоритма для лучшего и худшего случаев на множестве входов фиксированной длины. Аргументом функции является длина входа, а значением Ч число базовых операций в выбранной модели вычислений. Оценка в худшем случае не всегда реально применима, поскольку, как правило, значения трудоемкости, близкие к худшему случаю, имеют незначительную частотную встречаемость.
2. Оценить трудоемкость исследуемого алгоритма в среднем. В этом аспекте следует отметить труды следующих ученых: А. А. Марков, Н.М. Нагорный, Д. Э. Кнут, Дж. Макконелл. Минусом указанной методики является возможность ее применения лишь для узкого класса алгоритмов. Данный вид оценок также не позволяет прогнозировать число операций, заданных алгоритмом, для конкретного входа.
Следовательно, возникает необходимость в методике, которая должна предоставить исследователю инструмент для анализа трудоемкости и построения на этой основе реально применимого прогноза временной эффективности для конкретного входа. Таким образом, задача разработки методики прогноза числа базовых операций, которое не будет превышено для конкретного входа с заданной пользователем доверительной вероятностью, является актуальной.
Целью диссертационной работы является:
1. Разработка новой оценки качества алгоритмов - доверительной трудоемкости, позволяющей оценить трудоемкость алгоритма на конкретном входе с заданной доверительной вероятностью 2. Разработка методики определения доверительной трудоемкости исследуемого алгоритма из класса NPR на фиксированной длине входа.
Для достижения поставленной цели в диссертации необходимо решить следующие основные задачи:
1. Сформулировать критерий оценки временной эффективности алгоритма, позволяющий оценить трудоемкость на конкретном входе.
2. Разработать алгоритмическое обеспечение и программный комплекс для оценки трудоемкости алгоритма по разработанному критерию.
3. Провести исследование областей применимости разработанной методики по отношению к классу алгоритмов поиска подстроки в строке.
Методы исследования. В работе применены и использованы методы теории алгоритмов, математической статистики и теории вероятностей, методы вычислительной математики и функционального анализа. При разработке программного обеспечения применялись методы объектноориентированного программирования, с использованием сред разработки Borland Delphi 7, MatLab 6.5.
Научная новизна работы заключается в следующем:
Разработана новая оценка качества алгоритмов (доверительная трудоемкость), основанная на аппроксимации частотной встречаемости значений трудоемкости исследуемого алгоритма известной функцией плотности распределения.
Разработана методика построения прогноза о числе базовых операций, заданных исследуемым алгоритмом, которое не будет превышено с заданной пользователем доверительной вероятностью.
Практическая значимость.
Разработанные теоретические положения доведены до практических методик, алгоритмов и их программных реализаций.
Предложенная методика применена для оценки алгоритмов решения задачи поиска подстроки в строке, получены результаты, позволяющие априорно судить о качестве алгоритма по критерию доверительной трудоемкости.
Основные положения, выносимые на защиту.
1. Новая оценка качества алгоритмов - доверительная трудоемкость.
2. Методика аппроксимации наблюдаемого в эксперименте распределения частот значений трудоемкости исследуемого алгоритма как компонент общей методики оценки доверительной трудоемкости алгоритмов.
3. Алгоритм оценки качества алгоритмов по критерию доверительной трудоемкости.
Внедрение результатов работы. Разработано программное обеспечение Вычисление доверительной трудоемкости компьютерных алгоритмов, на которое получено свидетельство о регистрации программы для ЭВМ Роспатента № 2010611351 от 16.02.2010.
Результаты исследования используются в учебном процессе Московского государственного университета приборостроения и информатики и Научно-исследовательского университета Высшая школа экономики в рамках дисциплин Теория алгоритмов, Разработка эффективных алгоритмов, Методы разработки и анализа компьютерных алгоритмов.
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:
1. Межвузовская конференция Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ (г. Москва, 2007 г.) 2. 52-ой Всероссийской научной конференции МФТИ Современные проблемы фундаментальных и прикладных наук (г. Москва, 2009 г.);
3. XV Международной научно-технической конференции Информационные системы и технологии (г. Нижний Новгород, 2009 г.);
4. XI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. (г. Красноярск, 2010 г.) Публикации по теме диссертации. По теме диссертации опубликовано печатных работ. Из них 4 статьи, 1 из которых входит в перечень ВАК, тезисов докладов на международных и всероссийских научных конференциях и семинарах, 1 свидетельство о государственной регистрации программы для ЭВМ. В работах, опубликованных в соавторстве, автору принадлежит разработка математического, алгоритмического и программного обеспечения для оценки эффективности алгоритмов по критерию доверительной трудоемкости.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, списка литературы из 181 наименования и 2 приложений. Общий объем работы составляет 103 страницы, в том числе 90 страниц основного текста, включая 15 рисунков и 5 таблиц.
Основное содержание работы
Во введении обосновывается актуальность разработки методики оценки трудоемкости алгоритмов по критерию доверительной трудоемкости и формулируется цель исследования.
В первой главе даны формулировки основных понятий теории алгоритмов, используемых далее; проведен анализ литературных источников и описаны методы оценки эффективности и качества вычислительных алгоритмов. Рассмотрены существующие в настоящее время характеристики алгоритмов и методики оценки качества алгоритмов. Подробно рассмотрены основные компоненты комплексного критерия качества алгоритма:
1. Общие оценки качества, такие как оценки ресурсной эффективности алгоритмов Ч временной и емкостной сложности, а также эффективности алгоритма.
2. Проблемно зависимые оценки, которые актуальны для алгоритмов решения задач в узкоспециализированных областях, в которых общих оценок качества недостаточно для решения задачи рационального выбора алгоритма. Примерами таких оценок могут являться метрики качества изображений, точность, сходимость, устойчивость к ошибкам исходных данных, надежность и так далее. Детально рассмотрены оценки алгоритмов сжатия изображений, численных методов и поиска подстроки в строке.
Основное внимание уделено временным оценкам. Показано, что сравнение по временной эффективности двух алгоритмов на основе их функции трудоемкости вносит определенную ошибку в получаемые результаты. Основной причиной этой ошибки является различная частотная встречаемость элементарных операций, порождаемая разными алгоритмами и различие во временах выполнения элементарных операций на реальном процессоре.
Теоретические значения трудоемкости в худшем случае дают возможность сравнения алгоритмов по критерию максимума времени выполнения, что позволяет решить задачу о выборе рационального алгоритма в условиях жесткой ограниченности ресурсов, например, при определении максимальной нагрузки на сервер, определении ресурсов компьютера для поддержки приложений реального времени. В условиях неограниченности ресурсов сравнение алгоритмов может быть проведено по критерию трудоемкости в среднем. Однако для большинства алгоритмов возможно лишь ограничение данного вида оценок сверху, а для некоторых алгоритмов получение оценок такого рода в теории является достаточно сложной задачей. Следовательно, только оценка трудоемкости в худшем случае является универсальной, однако она зачастую не является приемлемой, поскольку значения трудоемкости, близкие к худшему случаю имеют, как правило, незначительную частотную встречаемость, из чего следует, что подобная оценка является сильно завышенной.
На основе проведенного в главе анализа сформулирована постановка задачи о необходимости введения новой количественной меры, позволяющей строить прогноз относительно числа базовых операций, заданных алгоритмом, с вероятностью, заданной исследователем.
Во второй главе введено понятие доверительной трудоемкости, понимаемое как число базовых операций, которое не будет превышено для конкретного входа с заданной пользователем доверительной вероятностью.
Предложено рассматривать значения трудоемкости алгоритма из класса NPR на входах фиксированной длины как дискретную ограниченную случайную величину, аппроксимируемую некоторым известным законом распределения.
Предлагаемое решение основано на классическом подходе математической статистики, и связано с построением доверительных интервалов оцениваемых величин с заданной доверительной вероятностью.
Разработана методика анализа алгоритма по критерию доверительной трудоемкости, которая состоит из следующих этапов:
1. Экспериментальное определение значений трудоемкости исследуемого алгоритма при фиксированной длине входа;
2. Аппроксимация полученных результатов функцией плотности некоторого известного закона распределения.
3. Подтверждение гипотезы о выборе закона распределения;
4. Определение доверительной трудоемкости при заданной исследователем доверительной вероятности.
Первый этап начинается с определения значения трудоемкости алгоритма в конкретном эксперименте. Под трудоемкостью алгоритма понимается число базовых операций, заданных алгоритмом. Проведя ряд таких экспериментов можно получить выборку значений трудоемкости исследуемого алгоритма для входов фиксированной длины. В настоящее время существует методика определения рационального объема выборки на основании выбранной исследователем надежности и относительной ошибки, изложенная в трудах М.В. Ульянова и В.Н. Петрушина. Например, в соответствии с данной методикой для алгоритма сортировки методом вставок, с наджностью 0,95 и относительной ошибкой 0,001 при длине входа в 100 элементов рассчитанное минимально необходимое число экспериментов составило 11191.
В зависимости от числа экспериментов, сегмент варьирования V разбивается на s полусегментов: [xi, xi xi ], i 1, s. В работе использованы рекомендации по выбору числа интервалов: log m s m, где Ч объем m выборки.
Для алгоритмов сортировки, в частности методом вставок, при s 75, длине входного массива в 100 элементов, проведены серии из 120 экспериментов, построена гистограмма наблюдаемого в эксперименте распределения частот, а также ее огибающая (рисунки 1-2). В данном случае произведено нормирование трудоемкости в сегмент [0;1] по формуле:
fi fmin fi norm, i 1,m, fmax fmin где f и f - теоретические значения трудоемкости для лучшего и m in m ax худшего случаев соответственно, Ч число экспериментов.
m Рис.1. Гистограмма частотной встречаемости значений трудоемкости алгоритма сортировки методом вставок при длине входного массива в 100 элементов и s 75.
Рис. 2. Огибающая гистограммы частотной встречаемости трудоемкости алгоритма сортировки методом вставок при длине входного массива в 100 элементов и s 75.
Этап 2. Объектом аппроксимации является частотная встречаемость значений трудоемкости исследуемого алгоритма, разбитая на интервалы, следовательно, аппроксимирующей будет являться интегрированная по интервалам выбираемая функция плотности. Описана методика выбора закона распределения для аппроксимации огибающей гистограммы наблюдаемого в эксперименте распределения частот. Показано, что в ряде случаев выбор бета-распределения является предпочтительным, поскольку его функция плотности имеет конечный носитель (0;1), а также может принимать унимодальный вид с произвольно смещенным центром.
Подзадачей на данном этапе является определение коэффициентов и бета-распределения, формулы расчета которых получены обращением известных формул для математического ожидания и дисперсии:
M, D, следовательно, ( )2 ( 1) 1 M M M (M 1)M, M 1.
D D Соответствующие поверхности приведены на рисунке 3.
Рис. 3. Зависимости (M, D) и (M, D) соответственно.
Для расчета численных значений и используется метод моментов, основанный на вычислении оценок M и D по данным выборки, однако, использование данного метода приводит к появлению погрешности, поскольку оценки параметров распределения, определяемые с его помощью, имеют интервальный характер.
Показано, что погрешность при использовании точечных значений выборочного среднего и выборочной исправленной дисперсии в качестве математического ожидания и дисперсии при определении доверительной трудоемкости не является значимой.
Для алгоритма сортировки методом вставок при длине входного массива n 100 и количестве испытаний k 12000 погрешность использования точечной оценки вместо интервальной составила 2%, 2%. Итоговая погрешность при определении доверительной трудоемкости с учетом погрешностей коэффициентов составила 1,84% с доверительными вероятностями 0,95 и 0,95.
M s Получены результаты аппроксимации для исследованного алгоритма сортировки. На рисунке 4 приведены графики относительных частот значений трудоемкости (синий график) и интегрированной по интервалам функции бета-распределения (зеленый график) с параметрами и, полученными методом моментов, для алгоритма сортировки методом вставок.
Рис. 4. График интегрированной функции плотности бета-распределения и график относительных частот значений трудоемкости алгоритма сортировки методом вставок.
Этап 3. Правомерность использования закона распределения случайной величины для аппроксимации гистограммы относительных частот трудомкости требует подтверждения средствами математической статистики. Выдвигаемая стандартно нулевая гипотеза ( H ) состоит в том, что выбранный закон не противоречит наблюдаемому в эксперименте распределению относительных частот трудомкости как случайной величины. В данном случае применяется наиболее распространнный критерий, инвариантный к виду закона распределения, Ч критерий согласия Пирсона. Для алгоритма сортировки методом вставок при описанных 2 2 ' ' условиях эксперимента 31,75, (,k) 91,25 при 0,05 и k 72, набл кр H следовательно, нет оснований отвергнуть гипотезу.
Заключительным этапом является определение доверительной трудоемкости f, то есть значения, которое не будет превышено с заданной пользователем доверительной вероятностью. Значение x определяется при помощи функции, обратной выбранному закону распределения, то есть функции, позволяющей однозначно сказать, в каком месте по оси абсцисс интегрируется площади под графиком функции плотности распределения.
В случае бета-распределения, если задана вероятность, то возможно 1 определение такого аргумента, что x B (,, ), где B (,, ) Ч x функция, обратная к интегрированной плотности бета-распределения.
Доверительная трудоемкость определяется преобразованием в реальный сегмент варьирования значения по формуле x fy x *( fmax fmin) fmin, где f и f Ч теоретические значения трудоемкости для лучшего и m in m ax худшего случаев соответственно.
Проанализированы результаты применения разработанной методики к алгоритмам сортировки. Для сортировки методом вставок сокращение по отношению к теоретическому сегменту варьирования составило 1,67 раза, а для сортировки поиском минимума - 8 раз (рисунок 5).
Рис. 5. Определение доверительной трудоемкости при 0,95 для алгоритма сортировки поиском минимума при n 50 с разбиением нормированного сегмента [0,1] на 75 полусегментов.
Таким образом, методика применима и ее ощутимый результат состоит в сокращении длины сегмента варьирования трудоемкости по сравнению с теоретическим сегментом. Методика также предоставляет пользователю математическую функцию, отражающую частотную встречаемость значений трудоемкости.
В третьей главе рассматривается задача поиска подстроки в строке, к алгоритмам решения которой применяется методика оценки алгоритма по критерию доверительной трудоемкости. Алгоритмы решения данной задачи описаны в трудах ряда ученых: А. Шеня, Д. Гасфилда, Т. Кормена, Р. Бойера, Дж. Мура, Д. Кнута, М. Крошмора, Г. Наварро, М. Рафинотта и многих других. Полученные результаты свидетельствуют о том, что описанная методика применима и дает существенный практический результат, который может быть использован как часть комплексного критерия оценки качества алгоритма.
Выбраны и подробно описаны алгоритмы Бойера-Мура, КнутаМорриса-Пратта, Грубой силы и Рабина-Карпа. Хорошие описания указанных алгоритмов и их модификаций приведены в трудах следующих авторов: Р. Бойера, Дж. Мура, С. Бааза, А. Гелдера, Т. Кормена, С.
ейзерсона, Р. Ривеста, Ц. Штейна, Ю. Манбера, С. Скиены и др.
Эксперименты по сравнению алгоритмов обработки строк представлены в книгах Дж. Дэвиса, С. Бушера, Р. Хорспула, Т. Лекрока, В. Смита и др.
Для каждого из алгоритмов при длине строки n 10000, длине искомой подстроки m 80 была проведена серия в 20000 экспериментов, в которых фиксировались значения функции трудоемкости. Такие параметры были выбраны как приближенно отражающие параметры поисковых систем, таких как Google, Yandex, Rambler. Описана методика проведения эксперимента, состоящая из определения исходного алфавита, размера строки и подстроки, объема выборки, правил генерации строки и подстроки, априорных свойств подстроки, а также коэффициентов нормирования. Приведены программные реализации алгоритма на языке Delphi с расстановкой счетчиков числа базовых операций в соответствии с выбранной моделью вычислений (пример на рисунке 6). Рассматривались модификации алгоритмов, решающих задачу поиска всех вхождений подстроки в строку.
Рис. 6. Листинг алгоритма Грубой силы с расставленными счетчиками числа базовых операций.
По результатам экспериментов были построены гистограммы относительных частот значений функции трудоемкости (с использованием разработанного программного обеспечения в среде MatLab), представленные на рисунках 7 - 10.
Рис. 7. Огибающая гистограммы наблюдаемого в эксперименте распределения частот алгоритма Бойера-Мура.
Отметим, что на асимметричность (левую или правую) гистограммы наблюдаемого распределения частот влияют коэффициенты нормирования.
Поскольку максимальное значение трудоемкости, полученное для худшего случая в теории, велико, по отношению к середине наиболее вероятного интервала трудоемкости, то выполнив преобразования в сегмент [0;1] по формуле нормирования, экспериментальные значения будут близки к нулю и попадут в начальные интервалы гистограммы.
Полученные экспериментальные данные показывают, что все гистограммы относительных частот значений трудоемкости имеют ярко выраженную левую асимметрию. В связи с этим целесообразным представляется принять за минимум и максимум аналогичные значения, полученные в эксперименте, с поправкой на некоторый коэффициент, позволяющий однозначно судить о том, что все экспериментальные значения экс экс лежат в интервале [ fmin / kmin; fmax *kmax]. В данном случае выбраны значения Ч k 1,2 k 1,,. Такое нормирование приводит к гистограммам, min max имеющим небольшое отклонение от симметричных.
Рис. 8. Огибающая гистограммы наблюдаемого в эксперименте распределения частот алгоритма Кнута-Морриса-Пратта.
Рис. 9. Огибающая гистограммы наблюдаемого в эксперименте распределения частот алгоритма Грубой силы.
Рис. 10. График интегрированной функции бета-распределения и огибающая гистограммы наблюдаемого в эксперименте распределения частот алгоритма РабинаКарпа.
Была выдвинута гипотеза об аппроксимации распределения относительных частот значений трудомкости функцией плотности бетараспределения. Для проверки гипотезы была произведена нормировка экспериментальных значений трудомкости в сегмент 0,1 с учетом коэффициентов k и k. Были определены границы полусегментов m in m ax разбиения сегмента 0,1 и рассчитаны эмпирические частоты в полусегментах. Также проводилась аппроксимация нормальным распределением, нормирование для которого не требуется.
По нормированным данным рассчитаны значения выборочной средней и выборочной исправленной дисперсии, на основе которых с помощью метода моментов были получены параметры и аппроксимирующего бета-распределения. Интегрированием полученной функции плотности по полусегментам были вычислены теоретические частоты. Корректная проверка гипотезы о бета-распределении была выполнена с использованием критерия Пирсона при уровне значимости 0,05. Во всех случаях наблюдаемое значение критерия Пирсона было значимо меньше, чем критическая точка, что позволяет принять гипотезу о бета-распределении. При определении параметров нормального распределения в качестве оценки использовалось выборочное среднее, в качестве оценки Ч выборочная исправленная дисперсия. Наблюдаемое значение по критерию Пирсона также во всех случаях было значительно меньше критического. Аппроксимации наблюдаемых в эксперименте распределений частот показаны на рисунках 11-14.
Рис. 11. График интегрированной функции бета-распределения и огибающая гистограммы наблюдаемого в эксперименте распределения частот алгоритма БойераМура.
Рис. 12. График интегрированной функции бета-распределения и огибающая гистограммы наблюдаемого в эксперименте распределения частот алгоритма КнутаМорриса-Пратта.
Рис. 13. График интегрированной функции бета-распределения и огибающая гистограммы наблюдаемого в эксперименте распределения частот алгоритма Грубой силы.
Рис. 14. График интегрированной функции бета-распределения и огибающая гистограммы наблюдаемого в эксперименте распределения частот алгоритма РабинаКарпа.
На основании полученных результатов был сделан следующий вывод:
решением задачи выбора рационального алгоритма по критерию временной эффективности при заданной размерности входных данных (длине строки n 10000, длине подстроки m 80) является алгоритм Бойера-Мура, который предпочтительнее, из четырех исследованных алгоритмов, по критерию доверительной трудоемкости при 0,95.
Отметим, что определение значения трудоемкости для худшего случая в теории является достаточно сложной задачей для ряда алгоритмов поиска подстроки в строке. В работе проведен анализ предельных случаев входных данных, которые могут привести к максимальному значению трудоемкости, на основе которого определено численное значение трудоемкости и рассчитано сокращение по отношению к теоретическому сегменту, поэтому в таблице приведены минимальные сокращения сегмента варьирования, и на практике они могут быть еще более значительными. Полученные экспериментальные результаты и расчеты доверительной трудоемкости приведены в таблице 1.
Табл. 1. Результаты сравнения алгоритмов.
Название Сокращение по 2 алгоритма Аппроксими- отношению к f набл кр поиска рующий закон теоретическому подстроки в распределения сегменту строке Бета- Бойера- распределение 78,64 91,25 71 3 2,3 раза Мура Бета- Кнута- распределение 19,77 91,25 157 4 1,3 раза МоррисаПратта Бета- Грубой распределение 18,56 91,25 181 6 37 раз силы Бета- распределение 16,34 91,25 263 5 24 раза Рабина(с учетом Карпа выбранной в алгоритме хешфункции) ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1. Проведен анализ основных подходов к оценке качества и выбору компьютерных алгоритмов. Введена новая характеристика качества алгоритмов Ч доверительная трудоемкость, и сформулирована задача о необходимости разработки методики ее получения.
2. Обоснован выбор вероятностного подхода к рассмотрению трудоемкости алгоритмов класса NPR (класса алгоритмов количественно параметрических по трудоемкости).
3. Разработана методика определения доверительной трудоемкости алгоритма при фиксированной длине входа, основанная на вычислении квантилей функции распределения вероятностей, аппроксимирующей частотное распределение значений трудомкости алгоритма.
4. Предложенная методика вычисления доверительной трудоемкости апробирована на модельных примерах. Для четырех алгоритмов поиска подстроки в строке при заданной длине входа решена задача рационального выбора алгоритма.
5. Разработано и реализовано в виде программного комплекса алгоритмическое обеспечение методики вычисления информационной чувствительности. Получено свидетельство Роспатента о регистрации программы.
6. Полученные результаты используются в учебном процессе Московского государственного университета приборостроения и информатики и Научно-исследовательского университета Высшая школа экономики в рамках дисциплин Теория алгоритмов, Разработка эффективных алгоритмов, Методы разработки и анализа компьютерных алгоритмов.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ В журналах, входящих в Перечень изданий, рекомендованных ВАК РФ.
1. Ульянов М.В., Петрушин В.Н., Кривенцов А.С.. Доверительная трудоемкость - новая оценка качества алгоритмов // Информационные технологии и вычислительные системы. 2009г. №2. С. 23Ц27.
В других изданиях.
2. Кривенцов А.С. Исследование трудоемкости алгоритма сортировки вставками на основе аппарата бета-распределения // Вестник молодых ученых МГУПИ. Информатика, №3, Москва, МГУПИ, 2008г. С. 38Ц43.
3. Кривенцов А.С. Построение функции трудоемкости алгоритма сортировки поиском минимума и ее анализ при помощи аппарата бетараспределения // Сборник научных трудов: Кафедре Экология и безопасность жизнедеятельности - 35 лет, Москва, МГУПИ, 2009г. С.
45Ц49.
4. Кривенцов А.С. Методика определения доверительной трудоемкости алгоритмов // Межвузовский сборник научных трудов Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ, Москва, МГУПИ, 2009г. С. 67Ц72.
5. Кривенцов А.С., Ульянов М.В. Методика определения доверительной трудоемкости алгоритмов // Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ: Материалы межвузовского сборника научных трудов №12, Москва, 2009, С. 66Ц69.
6. Кривенцов А.С. Доверительная трудоемкость // Современные проблемы фундаментальных и прикладных наук: Материалы 52-ой Всероссийской научной конференции МФТИ, Москва, 2009 г., С. 55 - 57;
7. Кривенцов А.С. Доверительная трудоемкость - новая оценка качества алгоритмов // Информационные системы и технологии: Материалы XV Международной научно-технической конференции, Нижний Новгород, 2009 г, С. 41Ц45;
8. Кривенцов А.С. Методика определения доверительной трудоемкости // Материалы XI Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям, г.
Красноярск, 2010 г., С. 88Ц92.
Патенты, свидетельства на программы для ЭВМ:
9. Ульянов М.В., Кривенцов А.С., Алексеенко А.С. Вычисление информационной чувствительности и доверительной трудоемкости компьютерных алгоритмов свидетельство об официальной регистрации программы для ЭВМ № 2010611351 // Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. Ч 16.02.2010.
Подписано к печати 20.04.2012 г. Формат 60х84. 1/16.
Объем 1,25 п.л. Тираж 100 экз. Заказ № 53.
Московский государственный университет приборостроения и информатики 107996, Москва, ул. Стромынка,
Авторефераты по всем темам >>
Авторефераты по разным специальностям