Введение к работе
Актуальность темы
Алгоритмическое обеспечение, являющееся неотъемлемой частью программной системы, представляет собой совокупность алгоритмов, которые лежат в основе последующей программной или программно-аппаратной реализации. Эффективность использования ресурсов компьютера, хотя отчасти и определяется выбором среды, языка и тщательностью реализации, но в основном зависит от разработанных и/или выбранных алгоритмов. В связи с этим при разработке программного обеспечения возникает задача оценки качества алгоритма, а также выбора рациональных алгоритмов с учетом особенностей применения из множества существующих в данной предметной области. Критерий выбора, в основном, является комплексным и включает как общие, так и проблемно-зависимые оценки качества алгоритмов. К общим оценкам относятся оценки ресурсной эффективности алгоритмов, как правило, временная и емкостная сложность. Проблемно-зависимые оценки связаны с особенностями задачи, например, в задаче сжатия изображения таковыми являются коэффициент сжатия, класс изображения, на который ориентирован алгоритм, метрики качества изображений и так далее.
В разное время вопросами анализа сложности алгоритмов, оценки качества программных средств и систем и их алгоритмического обеспечения занимались такие российские и зарубежные ученые, как: В. Липаев,
A. А. Марков, Г. Е. Цейтлин, Г. С. Цейтин, Ю. И. Янов, Л. А. Левин,
B. Е. Котов, В. А. Горбатов, А. И. Мальцев, М. Ю. Мошков, В. А. Носов,
Б. Я. Фалевич, Д. Э. Кнут, А. Ахо, Дж. Хопкрофт, Дж. Ульман, М. Гэри,
Д. Джонсон, Р. Грэхем, Д. Гасфилд, Р. Карп, Р. Тарьян, А. Кобхем, Т. Кормен,
Р. Ривест, Г. Штейн, Ч. Лейзерсон и др.
Одним из основных компонент критерия оценки качества является временная эффективность или трудоемкость, в данном случае понимаемая как число базовых операций, заданных алгоритмом на конкретном входе. Тип базовых операций определяется выбранной моделью вычислений. В настоящее время целым рядом ученых (Д.Э. Кнут, Д. Гасфилд, А. Ахо, Дж. Хопкрофт, Дж. Ульман) разработаны различные методики анализа и оценки качества алгоритмов, позволяющие:
Получить теоретические функции трудоемкости алгоритма для лучшего и худшего случаев на множестве входов фиксированной длины. Аргументом функции является длина входа, а значением — число базовых операций в выбранной модели вычислений. Оценка в худшем случае не всегда реально применима, поскольку, как правило, значения трудоемкости, близкие к худшему случаю, имеют незначительную частотную встречаемость.
Оценить трудоемкость исследуемого алгоритма в «среднем». В этом аспекте следует отметить труды следующих ученых: А. А. Марков, Н.М. Нагорный, Д. Э. Кнут, Дж. Макконелл. Минусом указанной
методики является возможность ее применения лишь для узкого класса
алгоритмов. Данный вид оценок также не позволяет прогнозировать
число операций, заданных алгоритмом, для конкретного входа.
Следовательно, возникает необходимость в методике, которая должна
предоставить исследователю инструмент для анализа трудоемкости и
построения на этой основе реально применимого прогноза временной
эффективности для конкретного входа. Таким образом, задача разработки
методики прогноза числа базовых операций, которое не будет превышено
для конкретного входа с заданной пользователем доверительной
вероятностью, является актуальной.
Целью диссертационной работы является:
Разработка новой оценки качества алгоритмов - доверительной трудоемкости, позволяющей оценить трудоемкость алгоритма на конкретном входе с заданной доверительной вероятностью
Разработка методики определения доверительной трудоемкости исследуемого алгоритма из класса NPR на фиксированной длине входа.
Для достижения поставленной цели в диссертации необходимо решить следующие основные задачи:
Сформулировать критерий оценки временной эффективности алгоритма, позволяющий оценить трудоемкость на конкретном входе.
Разработать алгоритмическое обеспечение и программный комплекс для оценки трудоемкости алгоритма по разработанному критерию.
Провести исследование областей применимости разработанной методики по отношению к классу алгоритмов поиска подстроки в строке.
Методы исследования. В работе применены и использованы методы теории алгоритмов, математической статистики и теории вероятностей, методы вычислительной математики и функционального анализа. При разработке программного обеспечения применялись методы объектно-ориентированного программирования, с использованием сред разработки Borland Delphi 7, MatLab 6.5.
Научная новизна работы заключается в следующем:
Разработана новая оценка качества алгоритмов (доверительная трудоемкость), основанная на аппроксимации частотной встречаемости значений трудоемкости исследуемого алгоритма известной функцией плотности распределения.
Разработана методика построения прогноза о числе базовых операций, заданных исследуемым алгоритмом, которое не будет превышено с заданной пользователем доверительной вероятностью.
Практическая значимость.
Разработанные теоретические положения доведены до практических методик, алгоритмов и их программных реализаций. Предложенная методика применена для оценки алгоритмов решения задачи поиска подстроки в строке, получены результаты, позволяющие
априорно судить о качестве алгоритма по критерию доверительной трудоемкости.
Основные положения, выносимые на защиту.
Новая оценка качества алгоритмов - доверительная трудоемкость.
Методика аппроксимации наблюдаемого в эксперименте распределения частот значений трудоемкости исследуемого алгоритма как компонент общей методики оценки доверительной трудоемкости алгоритмов.
Алгоритм оценки качества алгоритмов по критерию доверительной трудоемкости.
Внедрение результатов работы. Разработано программное обеспечение «Вычисление доверительной трудоемкости компьютерных алгоритмов», на которое получено свидетельство о регистрации программы для ЭВМ Роспатента №2010611351 от 16.02.2010.
Результаты исследования используются в учебном процессе Московского государственного университета приборостроения и информатики и Научно-исследовательского университета «Высшая школа экономики» в рамках дисциплин «Теория алгоритмов», «Разработка эффективных алгоритмов», «Методы разработки и анализа компьютерных алгоритмов».
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:
Межвузовская конференция «Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ» (г. Москва, 2007 г.)
52-ой Всероссийской научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» (г. Москва, 2009 г.);
XV Международной научно-технической конференции «Информационные системы и технологии» (г. Нижний Новгород, 2009 г.);
XI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям, (г. Красноярск, 2010 г.)
Публикации по теме диссертации. По теме диссертации опубликовано 9 печатных работ. Из них 4 статьи, 1 из которых входит в перечень ВАК, 4 тезисов докладов на международных и всероссийских научных конференциях и семинарах, 1 свидетельство о государственной регистрации программы для ЭВМ. В работах, опубликованных в соавторстве, автору принадлежит разработка математического, алгоритмического и программного обеспечения для оценки эффективности алгоритмов по критерию доверительной трудоемкости.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, списка литературы из 181 наименования и 2 приложений. Общий объем работы составляет 103 страницы, в том числе 90 страниц основного текста, включая 15 рисунков и 5 таблиц.
