ИНФОРМАЦИОННАЯ ЧУВСТВИТЕЛЬНОСТЬ КОМПЬЮТЕРНЫХ АЛГОРИТМОВ И ЕЁ КОЛИЧЕСТВЕННЫЕ МЕРЫ д.т.н., профессор М.В. Ульянов Кафедра «Управление разработкой программного обеспечения» НИУ-ВШЭ «Прикладная математика и моделирование систем» МГУПечати

ТРЕБОВАНИЯ РАЗРАБОТЧИКОВ АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ ПРОГРАММ Ресурсная эффективность по трудоёмкости и дополнительной памяти Прогнозирование временных характеристик на реальном диапазоне длин входов Обеспечение стабильности по времени на различных входах фиксированной длины

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ А – алгоритм; D A – множество возможных конкретных проблем для задачи, решаемой с помощью алгоритма А (множество допустимых входов алгоритма); D – конкретный вход алгоритма; f A (D) – функция трудоёмкости для входа D;

ПРОГНОЗИРОВАНИЕ НА ОСНОВЕ ФУНКЦИИ ТРУДОЁМКОСТИ: НЕДОСТАТКИ СУЩЕСТВУЮЩИХ ПОДХОДОВ Прогнозирование по трудоёмкости в худшем случае (гарантированная оценка сверху) даёт почти всегда сильно завышенные результаты Прогнозирование по трудоёмкости в среднем не учитывает информацию о размахе варьирования. Качество прогноза во многом определяется влиянием различных входов фиксированной длины на трудоёмкость, информационной чувствительностью исследуемого алгоритма в рамках выбранной количественной оценки.

ПОСТАНОВКА ЗАДАЧИ И ПРЕДПОЛОЖЕНИЯ Задача: Введение и сравнительный анализ различных количественных оценок информационной чувствительности. Предположения: 1. Трудоёмкость алгоритма на входах фиксированной длины - дискретная ограниченная случайная величина. 2.Выбор распределения, аппроксимирующего функцию трудоёмкости производится на основе экспериментальных исследований.

ГИСТОГРАММА ОТНОСИТЕЛЬНЫХ ЧАСТОТ ДЛЯ АЛГОРИТМА УМНОЖЕНИЯ ДЛИННЫХ ЦЕЛЫХ ЧИСЕЛ В СТОЛБИК (N=100).

ГИСТОГРАММА ОТНОСИТЕЛЬНЫХ ЧАСТОТ ТРУДОЁМКОСТИ ДЛЯ АЛГОРИТМА СОРТИРОВКИ ВСТАВКАМИ ПРИ N=100, M=20000

ГИСТОГРАММА ОТНОСИТЕЛЬНЫХ ЧАСТОТ ЗНАЧЕНИЙ ФУНКЦИИ ТРУДОЕМКОСТИ ДЛЯ АЛГОРИТМА КНУТА-МОРРИСА-ПРАТТА, N=10000, M-20.

ПОНЯТИЕ ИНФОРМАЦИОННОЙ ЧУВСТВИТЕЛЬНОСТИ Впервые понятие информационной чувствительности алгоритма по трудоёмкости введено М. В. Ульяновым и В. А. Головешкиным. Понятие «информационная чувствительность» отражает тот факт, что алгоритм задаёт различное число базовых операций принятой модели вычислений на разных входах, имеющих фиксированную длину. Ключевым для содержательной интерпретации этого термина является выбор количественной оценки (меры), обладающей свойством сопоставимости, т. е. дающей возможность решения задач сравнения алгоритмов и их рационального выбора.

ОЦЕНКА ИНФОРМАЦИОННОЙ ЧУВСТВИТЕЛЬНОСТИ ПО ЭНТРОПИИ Для дискретной случайной величины Непрерывный аналог - дифференциальная энтропия Проблемы: не чувствительность к положению моды, максимум для ограниченной случайной величины – при равномерном распределении, влияние на энтропийную оценку числа сегментов гистограммы

СТАТИСТИЧЕСКАЯ ОЦЕНКА ИНФОРМАЦИОННОЙ УВСТВИТЕЛЬНОСТИ Нормированный (относительный) размах варьирования функции трудоемкости Коэффициент вариации - стандартное отклонение трудоемкости

СТАТИСТИЧЕСКАЯ ОЦЕНКА ИНФОРМАЦИОННОЙ УВСТВИТЕЛЬНОСТИ Статистическая количественная оценка информационной чувствительности алгоритма по трудоёмкости Её применение возможно в случае отсутствия знаний о законе распределения значений трудоёмкости или какой-либо его аппроксимации Недостаток - она не позволяет указать интервал значений трудоёмкости при заданной вероятности,

КВАНТИЛЬНАЯ ОЦЕНКА ИНФОРМАЦИОННОЙ УВСТВИТЕЛЬНОСТИ Основная идея состоит в определении длины сегмента нормированных значений трудоёмкости, по которому интеграл от функции плотности равен заданной вероятности (надёжности) Отметим, так же, что эта оценка не содержит информацию о положении гамма-квантиля закона распределения на нормированном сегменте.

КВАНТИЛЬНАЯ МЕРА ИНФОРМАЦИОННОЙ ЧУВСТВИТЕЛЬНОСТИ – ИНТЕРВАЛ, СИММЕТРИЧНЫЙ ОТНОСИТЕЛЬНО МЕДИАНЫ РАСПРЕДЕЛЕНИЯ.

НОРМИРОВАННАЯ ВЕЛИЧИНА Т ДЛЯ АЛГОРИТМА УМНОЖЕНИЯ (N=100)

ВЫБОР ФУНКЦИИ ПЛОТНОСТИ РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ гамма функция Эйлера параметры функции плотности бета- распределения

КОЛИЧЕСТВЕННАЯ МЕРА ИНФОРМАЦИОННОЙ ЧУВСТВИТЕЛЬНОСТИ количественная мера информационной чувствительности является функцией от длины входа и вероятности. - доверительная вероятность - функция, обратная интегралу плотности распределения - параметры бета-распределения

ЗАВИСИМОСТЬ ИНФОРМАЦИОННОЙ ЧУВСТВИТЕЛЬНОСТИ АЛГОРИТМА УМНОЖЕНИЯ ОТ ДЛИНЫ ВХОДА ПРИ γ =0.95

СИММЕТРИЧНАЯ ПО ПЛОТНОСТИ ВЕРОЯТНОСТЕЙ ОЦЕНКА ИНФОРМАЦИОННОЙ ЧУВСТВИТЕЛЬНОСТИ Квантильная мера для ассиметричных функций плотности не является симметричной происходит выбрасывание из сегмента, более вероятных величин в пользу менее вероятных

ИДЕЯ СИММЕТРИЧНОЙ ОЦЕНКИ

СИММЕТРИЧНАЯ ПО ПЛОТНОСТИ ВЕРОЯТНОСТЕЙ ОЦЕНКА ИНФОРМАЦИОННОЙ ЧУВСТВИТЕЛЬНОСТИ

МОДЕЛЬНЫЙ ПРИМЕР Результаты экспериментального исследования алгоритма Кнута-Морриса-Пратта для поиска подстроки в строке Методом моментов были определены параметры аппроксимирующего бета-распределения

МОДЕЛЬНЫЙ ПРИМЕР Результаты расчётов :

ЗАКЛЮЧЕНИЕ Введённая симметричная по плотности вероятностей количественная оценка информационной чувствительности может быть использована как более достоверная в случае асимметрии аппроксимирующей функции плотности при прогнозировании временной эффективности компьютерных алгоритмов, а также при решении задачи рационального выбора алгоритмов по критерию стабильности по времени, равно как и при решении других задач прикладной теории алгоритмов

ПУБЛИКАЦИИ ПО ТЕМЕ 1. Головешкин В.А., Ульянов М.В. Теория рекурсии для программистов. М.: Издательство «Наука ФИЗМАТЛИТ», 2006 г. 2. Ульянов М.В. Ресурсно-эффективные компьютерные алгоритмы. Разработка и анализ. М.: Издательство «Наука ФИЗМАТЛИТ», 2008 г. 3. Петрушин В.Н., Ульянов М.В. Планирование экспериментального исследования трудоёмкости алгоритмов на основе бета-распределения. Информационные технологии и вычислительные системы С. 81– Петрушин В.Н., Ульянов М.В. Информационная чувствительность компьютерных алгоритмов М.: Издательство «Наука ФИЗМАТЛИТ», 2010 г.