'

ИНФОРМАЦИОННАЯ ЧУВСТВИТЕЛЬНОСТЬ КОМПЬЮТЕРНЫХ АЛГОРИТМОВ И ЕЁ КОЛИЧЕСТВЕННЫЕ МЕРЫ

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

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


×

HTML:





Ссылка: