Функциональная эффективность нечетко специфицированных алгоритмов

Определено понятие нечетко специфицированного алгоритма. Рассмотрены особенности спецификации таких алгоритмов. Выделена одна из их эксплуатационных характеристик – функциональная эффективность. Показана значимость этой характеристики для задач практического программирования. Предложены ста...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2006
Автор:	Шинкаренко, В.И.
Формат:	Стаття
Мова:	Російська
Опубліковано:	Інститут програмних систем НАН України 2006
Теми:	Теоретичні та методологічні основи програмування
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/2332
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Функциональная эффективность нечетко специфицированных алгоритмов / В.И. Шинкаренко // Проблеми програмування. — 2006. — N 1. — С. 24-33. — Бібліогр.: 11 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860003697661050880
author	Шинкаренко, В.И.
author_facet	Шинкаренко, В.И.
citation_txt	Функциональная эффективность нечетко специфицированных алгоритмов / В.И. Шинкаренко // Проблеми програмування. — 2006. — N 1. — С. 24-33. — Бібліогр.: 11 назв. — рос.
collection	DSpace DC
description	Определено понятие нечетко специфицированного алгоритма. Рассмотрены особенности спецификации таких алгоритмов. Выделена одна из их эксплуатационных характеристик – функциональная эффективность. Показана значимость этой характеристики для задач практического программирования. Предложены статистические показатели оценки функциональной эффективности. Визначено поняття нечітко специфікованого алгоритму. Розглянуті особливості специфікації таких алгоритмів. Виділена одна з експлуатаційних характеристик алгоритмів – функціональна ефективність. Показана значимість цієї характеристики для задач практичного програмування. Запропоновані статистичні показники оцінки функціональної ефективності Concept definition of the fuzzy specified algorithms is proposed. The particularities of the specification such algorithms are considered. One of the field-performance datas of algorithm - functional efficiency are noticed to. Meaning of this feature for problems of the practical programming is shown. Statistical factors of the estimation of the functional efficiency are offered
first_indexed	2025-12-07T16:37:36Z
format	Article
fulltext	Теоретичні та методологічні основи програмування © В.И. Шинкаренко, 2006 24 ISSN 1727-4907. Проблеми програмування. 2006. № 1 УДК 004.421 В.И. Шинкаренко ФУНКЦИОНАЛЬНАЯ ЭФФЕКТИВНОСТЬ НЕЧЕТКО СПЕЦИФИЦИРОВАННЫХ АЛГОРИТМОВ Определено понятие нечетко специфицированного алгоритма. Рассмотрены особенности специфика- ции таких алгоритмов. Выделена одна из их эксплуатационных характеристик – функциональная эф- фективность. Показана значимость этой характеристики для задач практического программирования. Предложены статистические показатели оценки функциональной эффективности. Введение Одной из задач прикладной теории алгоритмов является построение эффектив- ных алгоритмов и их анализ [1, 2]. При этом под эффективностью алго- ритмов, в первую очередь, понимают вре- менную эффективность или, как чаще ее на- зывают, временную сложность. Ставится задача оценки того, насколько эффективен алгоритм с точки зрения возможного вре- мени его выполнения. Интересна и другая задача: на- сколько эффективен алгоритм с точки зре- ния его функциональных “обязанностей”. Начнем с того, что одним из основ- ных свойств алгоритмов является их функ- циональность. Это свойство заключается в том, что алгоритм реализует некоторую, в математическом понимании, функцию ),(xfy = (1) где YyXx ∈∈ , - элементы некоторых про- извольных множеств. Данное свойство является одним из фундаментальных свойств алгоритмов на- ряду с дискретностью, результативностью, доступностью, массовостью, точностью (в смысле точной последовательности шагов), однозначностью [1]. Исследователи не заостряют внима- ния на этом свойстве, по-видимому, считая его тривиальным. Хотя понятие функцио- нальной эквивалентности алгоритмов, как алгоритмов реализующих одинаковую функцию вида (1), является вполне устояв- шимся. В данной статье обращается внима- ние на это свойство ввиду его особенности применительно к нечетко специфицирован- ным алгоритмам. Эта особенность заключа- ется в том, что разработанный в соответствии с нечеткой спецификацией ал- горитм может в каких-то случаях и в какой- то степени удовлетворять или нет требова- ниям пользователя. Само понятие нечетко специфициро- ванного алгоритма в некоторой мере ало- гично. Применительно к алгоритму специ- фикация определяется как “точное, одно- значное, недвусмысленное описание” [3] алгоритма. Само определение подразуме- вает точность, четкость. Однако многие за- дачи из практики программирования, реализованные в алгоритмах и программах и принесшие значительную пользу, можно отнести именно к нечетко специфицирован- ным. Очевидно, что и понятие нечеткой спецификации алгоритма, и понятие функ- циональной эффективности требуют деталь- ных пояснений и определений. 1. Нечетко специфицированные алгоритмы Ввиду явного противоречия между точностью спецификаций и их нечеткостью понятие нечетко специфицированного алго- ритма требует уточнения и как можно более строго определения. Определение понятия нечетко специ- фицированного алгоритма дадим на основе анализа характерных примеров. Рассмотрим два класса алгоритмов: сжатия данных и кластеризации. При этом обратим внимание на те вопросы, которые будут нужны при последующем изложении: спецификация, разработка алгоритмов, особенности и оцен- ка результатов их выполнения. 1.1. Алгоритмы сжатия данных. Особенности спецификации. Неформально алгоритмы сжатия данных можно специфи- цировать следующим образом: Теоретичні та методологічні основи програмування 25 спецификация 1. Алгоритм должен выполнять кодирование данных с возмож- ностью последующего восстановления (де- кодирования), объем выходных данных должен быть как можно меньше. Нечеткость формулировки заключа- ется в требовании “как можно меньше”. Ес- ли бы ставилась задача минимизации объема закодированных данных, специфи- кация была бы четкой. Однако задача по- строения такого алгоритма является намного более сложной, чем первоначаль- ная, а для случая сжатия без потери инфор- мации, в общем случае, - неразрешимой. На основе этой нечеткой специфика- ции разработан целый ряд универсальных программ - архиваторов, таких, как RAR, ZIP и др. Эффективность конкретного выпол- нения программы (КВП) оценивается пока- зателем степенью сжатия данных. Как известно [4], степень сжатия дан- ных в значительной степени зависит от осо- бенностей данных. В первую очередь степень сжатия за- висит от вида данных: текстовые, графиче- ские, аудио, видео, смешанные и т.д. Далее от характеристик представления данных. Например, для растровой графики: разреше- ния, глубины цвета, цветовой модели и т.п. И наконец, от самих данных. Так, резуль- таты сжатия фотографии и одноцветного квадрата такого же размера будут сильно разниться. С учетом особенности данных и ус- ловий применения алгоритмов сжатия спе- цификация конкретизируется. Например, спецификация дополняется следующими требованиями: кодированию подлежат рас- тровые изображения, код должен быть ус- тойчив к ошибкам и т.п. В соответствии с конкретизированными спецификациями разрабатываются более специализирован- ные алгоритмы сжатия. Особенности алгоритмов. Алго- ритмы сжатия не могут не ориентироваться на структуру сжимаемых данных. Это сле- дует из того факта [4], что без потери ин- формации ни один алгоритм не обеспечит сжатия любого файла, т.е. любой алгоритм сжатия размеры одной части файлов умень- шит, а другой увеличит (либо в случае ко- пирования не изменит). Отметим три возможности учета структуры данных в алгоритмах сжатия: - специализация алгоритмов для типичных структур (форматов) данных; - адаптация алгоритмов к данным в процессе сжатия; - параметрическое управление сте- пенью сжатия. Остановимся на последнем. Практи- чески все алгоритмы сжатия имеют ряд па- раметров управления, значения которых в большей степени задаются в программах - архиваторах как константы и в силу слож- ной взаимосвязи их значений с результатом сжатия недоступны пользователю. Напри- мер, частью многих алгоритмов сжатия яв- ляется алгоритм LPC (линейно – предсказы- вающее кодирование) [4]. Значение R- битного участка кода предсказывается как линейная комбинация нескольких преды- дущих участков, и, если зависимости в ис- ходных данных близки к линейным, вы- полнение алгоритма приводит к появлению многих повторяющихся участков кода. Управляющими здесь являются такие пара- метры, как длина участка кода и коэффици- енты линейного прогноза. Особенности результатов выпол- нения алгоритмов. Как оценить, какая сте- пень сжатия информации является доста- точной? Рассмотрим пример. Одним из при- менений архиваторов является перенос дан- ных с одной ЭВМ на другую с использова- нием некоторого носителя информации. Допустим, необходимо перенести два файла, один объемом 1V и второй - 2V . По- средником является носитель информации объемом 0V . При этом 01 VV >> и 02 VV > . Для переноса воспользуемся архиватором, который позволяет сжать файлы до объе- мов сжV1 и сжV2 (рис. 1). В первом случае, несмотря на высо- кую степень сжатия (2-3 раза), результат яв- ляется неудовлетворительным, во втором же при низкой степени сжатия ( ≈ 1,1 раза) результат удовлетворительный. Таким образом, какие-то результаты выполнения алгоритма будут приемлемы для пользователя, а какие-то нет. Опреде- Теоретичні та методологічні основи програмування 26 литься с этим можно лишь после выполне- ния программы, реализующей алгоритм. Такая ситуация возникает как следст- вие нечеткости спецификации. Четкая спе- цификация, отвечающая свойствам ограни- ченности и обобщенности [5], предопреде- ляет необходимые для пользователя результаты. Сравнение алгоритмов. Практиче- ски алгоритмы сжатия сравниваются по их реализациям в программах-архиваторах. Пример такого сравнения из [4] (час- тично) на основе файлов набора CalgCC в табл. 1. Таблица 1. Сравнение архиваторов по сте- пени сжатия файлов Архиваторы Файлы ARJ PKZIP RAR 7-Zip Bib 3.08 3.16 3.39 3.62 Bookl 2.41 2.46 2.80 2.94 Book2 2.90 2.95 3.39 3.59 … … … … … Progp 4.32 4.37 4.57 4.73 Trans 4.65 4.79 5.23 5.56 Итого 3.47 3.55 3.80 4.10 Сравнивается степень сжатия отдель- ных файлов и средняя несколькими архива- торами (алгоритмами). При этом не опреде- лен порядок отбора, количество файлов (кстати, слишком небольшое), на которых выполняется сопоставление. Оценка может сильно измениться на другой выборке файлов. 1.2. Алгоритмы кластеризации. Со- гласно Б. Эверитту, “кластеры – это непре- рывные области (некоторого) пространства с относительно более высокой плотностью точек, отделенные от других таких же об- ластей областями с относительно низкой плотностью точек”[6]. Спецификация алгоритма кластери- зации: спецификация 2. Алгоритм должен выполнять анализ данных и выделение в них всех кластеров. Имеются в виду экспе- риментальные данные, данные, полученные из хранилищ, и т.п. Нечеткость спецификации заклю- чается в понятии “более и менее высокой плотности точек”. На рис. 2 приведены три примера кластеров. Если в некоторых частных случаях (рис. 2,а) кластеры четко обозначены, то в более общем случае (рис. 2,б, 2,в) границы кластеров размыты. На рис. 2б, 2,в фактом является наличие двух кластеров, но ни од- ну точку нельзя с уверенностью причислить к кластеру либо межкластерному простран- ству, так как плотность точек постоянно снижается при удалении от центра кластера. Можно с большой долей уверенности предположить, что построение универсаль- ного алгоритма кластеризации невозможно в силу значительного разнообразия исход- ных данных. Отметим лишь некоторые воз- можные их особенности: - области с “относительно низкой плотностью точек” не содержат точек - ну- левая плотность точек между кластерами (рис. 2,а); - границы классов четко (рис. 2,а) либо нечетко (рис. 2,б, 2,в) выражены; - кластеры образуют выпуклые об- ласти (рис 2,а, 2,б) либо области произ- вольной формы (рис. 2,в); - точки однородные либо нет (с не- которыми атрибутами, например цветом), в случае с разнородными точками возможны пересекающиеся кластеры; - иерархические кластеры - “кла- стеры в кластерах”; - данные произвольных про- странств с различной мерой близости. Универсальный алгоритм кластери- зации должен учитывать все возможные особенности данных, но лишь визуализация в двумерном пространстве заранее (до по- строения либо применения алгоритма) по- зволяет эти особенности определить. В общем случае N-мерного пространства эти 1V 0V сжV2 сжV1 2V Рис.1. Пример результатов сжатия двух файлов Теоретичні та методологічні основи програмування 27 особенности могут быть выявлены лишь в процессе самой кластеризации. Разработанные эвристические [7] и математически обоснованные [6] алгоритмы могут с разной степенью эффективности применяться к различным исходным дан- ным. Для выявления других причин и по- следствий нечеткости спецификаций рас- смотрим характерный алгоритм кластериза- ции - иерархический алгоритм [8]. Изначально все точки считаем цент- рами кластеров, т.е. имеем N кластеров по одной точке в каждом. Определяем мини- мальное расстояние между центрами кла- стеров. Такие два кластера объединяем в один, пересчитав координаты центра. По- вторяем данную процедуру объединения кластеров до получения единственного. В процессе объединения строим де- рево (рис. 3). Каждый i-й его уровень пред- ставляет собой N-i корень дерева, который в свою очередь определяет все точки кластера. Один из уровней иерархии и является результатом кластеризации. Какой именно? Для ответа на этот вопрос необходимо вве- сти некий критерий. В [16] указаны среднее квадратов расстояний между образами в кластере, среднее квадратов расстояний ме- жду образами, входящими в разные кла- стеры, показатели, основанные на понятии матрицы рассеивания, минимальная и мак- симальная дисперсии, сумма квадратов рас- стояний между точками и соответствующи- ми центрами кластеров. Выбор одного из них часто определя- ется практической целесообразностью в процессе оценки результатов кластериза- ции. Таким образом, причины нечетко- сти спецификации алгоритмов кластериза- ции заключаются в следующем: - заранее неизвестными особенно- стями данных, которые следует учесть в алгоритме; - нечетким понятием “большей и меньшей плотности” точек; - неоднозначностью показателей качества кластеров и результатов кластери- зации. При этом некоторые причины нечет- кости являются неустранимыми на этапе спецификации. Так как алгоритм нечетко специфи- цирован, то определить, удовлетворяют ли результаты выполнения алгоритма в каждом конкретном случае можно лишь в процессе валидации, т.е. на последней стадии це- а б в Рис.2. Кластеры в двумерном пространстве: а - точки равномерно распределены и четко разграничены; б, в – точки нормально распре- делены, границы кластеров размыты 51z 41z 42z 31z 32z 33z 41z 42z 43z 44z 51z 52z 53z 54z 55z Рис. 3. Иерархия точек в процессе кластеризации. Теоретичні та методологічні основи програмування 28 почки: спецификация → алгоритм → программа → КВП → валидация. Если результаты неудовлетвори- тельны, то следует возвращаться на не- сколько шагов назад в указанной цепочке, что повышает затраты на решение конкрет- ных задач. Какие меры применяются разработ- чиками алгоритмов для снижения затрат? В случае с кластеризацией применя- ются различные управляющие данные для оперативного на этапе программы и КВП управления результатами. Управляющие па- раметры для некоторых алгоритмов класте- ризации даны в табл. 2. 1.3. Общие особенности нечетко специфицированных алгоритмов. Анализ приведенных и других алгоритмов позволя- ет к закономерностям нечетко специфици- рованных алгоритмов отнести причины или источники нечеткости и средства устране- ния последствий нечеткости. Основные источники нечеткости: - заранее неизвестные особенности исходных данных; - множественность показателей ка- чества результатов; - неопределенный уровень требова- ний к результатам. Устранение последствий нечеткости заключается в уточнении спецификаций, адаптации алгоритмов к данным и управле- нии алгоритмами посредством управляю- щих данных. Уточнение спецификаций по отноше- нию к данным дает возможность разрабаты- вать новые более эффективные, но и более специализированные алгоритмы. Специализация алгоритмов, разра- ботка адаптивных алгоритмов связаны с по- явлением новых алгоритмов, вопрос функ- циональной эффективности которых реша- ется отдельно. Наибольший интерес с точки зрения функциональной эффективности представ- ляют алгоритмы с управлением. Приведенные примеры нечетко спе- цифицированных алгоритмов не являются какими-то исключительными. К нечетко специфицированным мож- но отнести следующие алгоритмы: рас- познавания текста, речи и др. (в том числе нейросети), принятия решений, многокрите- риальной оптимизации, агенто-ориентиро- ванной технологии и др. Как видим, нечеткие спецификации присущи многим, в основном эвристиче- ским алгоритмам, которые относят к об- ласти искусственного интеллекта. С учетом бурного развития и перспектив этого на- правления нечетко специфицированные ал- горитмы представляются как некоторая тенденция развития программирования. 1.4. Определение нечетко специфи- цированного алгоритма. Нечеткую специ- фикацию следует отличать от неполной. Свойство полноты [3] или ограни- ченности [5] не выполняется, если в специ- фикации упущено какое-то требование. При этом возникает неоднозначность, в резуль- Таблица 2. Управляющие параметры алгоритмов кластеризации Алгоритм кластеризации Управляющие параметры Простой пороговый алгоритм [16] Порог T Максиминного расстояния [16] Соотношение расстояний между вновь создаваемым и ра- нее выделенными кластерами K внутригрупповых средних [16] Количество кластеров ИСОМАД [16] 5 параметров (ориентировочное количество кластеров, показатель компактности кластеров и др.) Глобальный “Роден” [8] Уровень качества α и уровень отделимости β Локальный “Роден” [8] Уровень качества α , уровень отделимости β и радиус кластеризации r Теоретичні та методологічні основи програмування 29 x X Y x X Y x X Y Рис.4. Отображение множества X на множество Y: а) однозначное, б) множественное в) нечеткое тате которой алгоритмы, удовлетворяющие спецификации, могут не устраивать пользо- вателя. Нечеткая спецификация также допус- кает неоднозначность. Принципиальным яв- ляется то, что эту неоднозначность нельзя устранить на этапе спецификации. Резуль- таты выполнения алгоритма не всегда будут удовлетворять пользователя. Кардинальное отличие нечеткой спе- цификации от неполной в том, что нечет- кость неустранима. В случае четко специфицированных алгоритмов спецификацией задается одна или множество функций, необходимых пользователю для решения некоторой за- дачи и удовлетворяющих пользователя. Если функция одна, то можно утвер- ждать, что спецификация и алгоритм явля- ются разными формами задания функции вида (1). Возьмем, например, формализован- ную спецификацию алгоритма сортировки. Спецификация 3. Предусловие XZxxxxP iN ∈∈=≡ XX ,:],[ 21 K , (2) где X – некоторый вектор с компонентами из некоторого линейно упорядоченного множества Z относительно отношения по- рядка ∝ . Постусловие ),]1,1[(& &))()(( :],[: * 1 * 2 * 1 +∝−∈∀ =∀ =≡∈≡ ii iii N xxNi xnxnx xxxXYQ K ** XX (3) где ∑ =    ≠ = = N i i i xx xx xn 1 .если,0 если,1 )( Эта спецификация определяет одно- значное соответствие между элементами множества X и Y (рис. 4, а). Спецификация многих алгоритмов задает неоднозначное отображение множе- ства X в Y (рис. 4, б). Характерными пред- ставителями таких алгоритмов являются алгоритмы, реализующие методы прибли- женных вычислений. К примеру, специфи- кация алгоритма определения корня непрерывной функции одной переменной: спецификация 4. &))(( CpP ∈≡ ϕ )(&)0)()((&]),[( Rbabap ∈<⋅∈ εϕϕ , где C – пространство непрерывных функций. ).0)((& &]),[(&)(: 0 00 = ∈<−≡ p bappppQ ϕ ε (4) При этом (4) задает отображение эле- ментов множества X Xbapx ∈= },,),({ εϕ на элементы множества Y Ypy ∈= }{ . За- метим, что y может принимать разные зна- чения при фиксированном x, а значит, спецификация задает множество функций вида (1). На рис. 4,б каждому значению Xx ∈ соответствует множество элементов Y из Y (в общем случае не обязательно ог- раниченное и связное). Каждая функция может быть реализована одним или не- сколькими алгоритмами. Так, методы хорд и касательных, соответствующие (4), реали- зуют различные функции, значения которых никогда не совпадают (только в пределе, который алгоритмически недостижим). Од- нако в этом случае любая функция из за- данного множества и любой соответству- ющий ей алгоритм при КВП дают ре- зультаты, удовлетворяющие пользователя. Теоретичні та методологічні основи програмування 30 Следовательно, спецификация 4 яв- ляется и полной и четкой. Спецификации 1 и 2 также задают множественное отображение X в Y (рис. 4,в), но в отличие от предыдущего ни одно значение из Y нельзя отнести к приемле- мым. Можно говорить о степени принад- лежности каждого элемента Yy ∈ к удовлетворяющим пользователя результа- там, т.е. множество Y является нечетким. На рис.4. степень принадлежности y мно- жеству удовлетворяющих пользователю ре- зультатов условно задана оттенками серого цвета (черный – степень принадлежности равна 1, белый – 0). Определение 1. Спецификация алго- ритма является нечеткой, если она задает отображение из X в Y, при этом каждому элементу из X ставится в соответствие нечеткое множество из Y. 2. Функциональная эффективность алгоритмов Как отмечено выше, функция, реали- зуемая нечетко специфицированным алго- ритмом, способна в какой-то мере удовле- творить потребностям пользователя. Встает вопрос, насколько эффективно такая функ- ция им удовлетворяет? Требуется дать объективный ответ на вопросы типа: - насколько хорошо сжимает дан- ные конкретный алгоритм; - насколько хорошо выполняется кластеризация конкретным алгоритмом; - какой алгоритм предпочтительнее с точки зрения функциональной эффектив- ности. Определение 2. Под функциональной эффективностью будем понимать эксплуа- тационную характеристику алгоритма, которая отражает степень соответствия алгоритма потребностям пользователя. Любой четко специфицированный алгоритм реализует функцию, результаты которой всегда должны удовлетворять по- требностям пользователя. Можно считать, что такой алгоритм имеет максимальную функциональную эффективность. Задача оценки функциональной эф- фективности алгоритма, как, впрочем, и других эксплуатационных характеристик, возникает в двух случаях: - при разработке новых, более со- вершенных алгоритмов для оценки их эф- фективности; - при разработке прикладного про- граммного обеспечения с целью выбора бо- лее эффективного алгоритма из альтерна- тивных с учетом перспектив и особенно- стей применения разрабатываемого ПО. 3. Показатели функциональной эффективности алгоритмов Показатель или показатели функцио- нальной эффективности должны давать ко- личественную оценку качества результатов выполнения алгоритма. При этом оценка должна обобщен- ной. В рассмотренных выше примерах подход к оценке функциональной эффек- тивности различается. В алгоритмах сжатия функ- циональная эффективность оценивается по степени сжатия, т.е. показатель зависит от двух измерений: исходных и результирую- щих данных. В алгоритмах кластеризации имеем несколько показателей и все они основаны на измерении результирующих данных. По-видимому, в общем случае сле- дует опираться только на результирующие данные, так как измерения на исходных, как показывает второй пример, не всегда воз- можны. Будем считать, что на множестве Y задана функция ),(yφρ = (5) где +∈ Rρ - оценка качества полученных алгоритмом результатов. Например, для алгоритмов сжатия данных )y(φρ = - функция, определяющая размер сжатых данных для конкретных x - входных данных для сжатия. Лучшее качество результатов соот- ветствует экстремуму функции φ . Не нару- шая общности, будем говорить о минимуме функции. Функционально оптимальным, с по- казателем оптимальности ρ , будем считать алгоритм 0A , реализующий функцию )(0 xf : Теоретичні та методологічні основи програмування 31 ))((min))(( 0 xfxfXx i Ai ρρ ∀ =⊂∀ , (6) где iA - алгоритм, соответствующий той же спецификации (далее альтернативный), реа- лизующий функцию )(xf i . Можно говорить о функциональной эффективности алгоритма в сравнении с эталоном – абсолютной функциональной эффективности либо по отношению к дру- гому альтернативному алгоритму – относи- тельной функциональной эффективности. Абсолютная функциональная эффек- тивность при фиксированном x %100 ))(( ))(())(( 0 ⋅ − = xf xfxf xAFE ρ ρρ . (7) определяет, насколько алгоритм, реализую- щий функцию (1), далек от оптимального. Оставляя открытыми вопросы суще- ствования минимума, функции и алгоритма, удовлетворяющего (6), отметим серьезные практические сложности разработки опти- мального алгоритма и доказательства его оптимальности. Гораздо большую практическую цен- ность и имеет относительная функциональ- ная эффективность, определяющая, на- сколько один алгоритм превосходит другой. Относительная функциональная эф- фективность двух алгоритмов, реализую- щих функции )(1 xf и )(2 xf при фиксиро- ванном x .%100 )))(()),((max( ))(())(( 21 21 ⋅−= xfxf xfxf xOFE ρρ ρρ (8) Учитывая гораздо большую востре- бованность относительного подхода, под функциональной эффективностью, если специально не оговорено, будем иметь в ви- ду относительную функциональную эф- фективность. Для сравнения функциональной эф- фективности двух алгоритмов (аналогично временной эффективности [9]) необходимо определить, насколько в среднем один алго- ритм превосходит другой и насколько часто его превосходство. Аналогично [9] предлагаются два по- казателя функциональной эффективности алгоритмов: - степень превосходства одного (i-го) алгоритма над другим (j-м) на ограни- ченном множестве XX ⊆ есть ∑ ⊂ − = Xx ji ji ij xfxf xfxf N XSUP ))((),((max( ))(()((1 ρρ ρρ , (9) где N - общее количество слагаемых; - область превосходства )))(()((( 1 ∑ ⊂ −= Xx jiij xfxfsign N XREG ρρ .(10) Следует обосновать возможность суммирования по всем x произвольного множества X . Элементами множества X могут быть целые, вещественные числа либо ко- нечные структуры из них. При практиче- ском применении алгоритмов указанные числа ограничены некоторым интервалом. Более того, для эффективного моделирова- ния данных программными средствами ин- тервалы значений входных данных следует указывать в спецификации программ. Количество знаков в представлении модельных вещественных чисел в цифро- вых ЭВМ ограничено, поэтому и количест- во таких чисел ограничено некоторым ин- тервалом. Так как из множества целых и мо- дельных вещественных чисел, как и их ком- бинации, формируется конечное множество X , то и само множество X конечно. Применительно к нашему примеру с алгоритмами сжатия функциональная эф- фективность по показателю оптимальности "объем сжатых данных" определяется степе- нью превосходства i-го алгоритма над j-м ijSUP и областью превосходства ijREG на множестве X . Заметим, что степень сжатия данных не может считаться показателем функцио- нальной эффективности алгоритмов сжатия, так как, с одной стороны, это точечная оценка и не является обобщенной, с другой – не позволяет решать задачи выбора и оценки алгоритма. Алгоритм может быть применен к различным данным, в том числе и к данным разных типов. Так, алгоритмы кластериза- ции могут работать в любом метрическом пространстве. Возникает вопрос о функцио- нальной эффективности алгоритмов приме- нительно к данным различных типов. Теоретичні та методологічні основи програмування 32 В этом случае показатели функцио- нальной эффективности ijSUP и ijREG мо- гут определяться в каждом пространстве от- дельно: Kijij K ijij XREGXREG ;XSUPXSUP L L 1 1 (11) или для всех типов вместе: kij kij XXXREG XXXSUP LUU LUU 21 21 , (12) где kX - множества различных метриче- ских пространств. В (9)-(12) подразумевается, что управляющие данные являются частью ис- ходных данных, т.е. алгоритм реализует функцию ),~(xfy = (13) где Xuxx ∈= ),(~ . Интерес вызывает функциональная эффективность алгоритмов с оптимальным управлением. При этом оцениваются потен- циальные возможности алгоритмов или воз- можности адаптации к данным посредством управления. Потенциальная степень превосход- ства одного (i-го) алгоритма над другим (j-м) на ограниченном множестве XX ⊆ есть ∑ ⊂ − = Xx ji ji ij xlxl xlxl N XSUP ))(),(max( )()(1 , (14) где )))(((min)( xfxl i u i i ρ= . Область потенциального превосход- ства ∑ ⊂ −= Xx jiij xlxlsign N XREG ))()(( 1 . (15) 4. S-R- показатели функциональной эф- фективности алгоритмов Показатели функциональной эффек- тивности ijSUP и ijREG ввиду очень боль- ших вычислительных затрат и значитель- ных людских ресурсов необходимых для их определения практически не применимы. S-R-показатели являются их стати- стической оценкой. Для их определения сумма заменяется интегралом соответст- вующей ступенчатой функции, а для вычис- ления применяется численный метод Монте-Карло [10]. Математическое обоснование этих статистических оценок аналогично времен- ной эффективности алгоритмов [9]. Здесь приведем лишь результаты. S-оценку степени превосходства i-го алгоритма над j-м (9) определим как ,%100 ))((),((max( )(()((1 1 ∑ = ∗ − = = M m mjmi mjmi ij xfxf xfxf M XS ρρ ρρ (16) где Xxm ⊂ элементы случайным образом сформированной выборки; M – количество экспериментов. R-оценку области превосходства i-го алгоритма над j-м (10) определим как ∑ = ∗−= = M m mjmi ij xfxfsign M XR 1 .%100))(()((( 1 ρρ (17) Доверительный интервал S-оценки при коэффициенте доверия β : ,100)100/( 6 1 ,100)100/( 6 1 3 1 2 ,2 3 1 2 ,2 ∗−+ << ∗−− ∑ ∑ = = k ijkij ij k ijkij StS XS StS ζ ζ β β где β,2t - табличное значение распределения Стьюдента; ∑ +−= − = kM Mkm mjmi mjmi k xfxf xfxf M 1)1( ))((),((max( )(()(( 3 1 ρρ ρρ ζ . Аналогично определяются довери- тельные интервалы для R-показателя. Таким образом, для определения S- и R-показателей необходимо: - выполнить последовательность численных экспериментов. Случайным об- разом формируется M исходных данных. При этих исходных данных выполняются i- й и j-й алгоритмы. Определяются резуль- таты их выполнения: - согласно (16) вычисляется S- пока- затель и (18) его доверительные интервалы; - согласно (17) вычисляется R- по- (18) Теоретичні та методологічні основи програмування 33 казатель и, соответственно, доверительные интервалы. Выводы 1. Многие эвристические алгоритмы, в ос- новном связанные с направлением програм- мирования, определяемым как искусствен- ный интеллект, представляются как нечетко специфицированные. 2. Функциональная эффективность алго- ритмов является объективной эксплуа- тационной характеристикой нечетко специ- фицированных алгоритмов. 3. При выборе рациональных алгоритмов для разрабатываемых программных средств следует учитывать их эксплуатационные ха- рактеристики. При этом будут эффектив- ными S-R-показатели, определенные в об- ласти, соответствующей их спецификации. 4. S-R-показатели функциональности алго- ритмов позволяют оценить эффективность вновь разработанных алгоритмов по срав- нению с существующими аналогами и управлять процессами совершенствования алгоритмов. 5. Предложенные статистические методы определения S-R-показателей позволяют оценить их достоверность. 1. Цейтлин Г.Е. Введение в алгоритмику. - Киев: Сфера, 1998. – 310 с. 2. Успенский В.А., Семенов А.Л. Теория алгортмов: основные открытия и приложения. - М.: Наука, 1987. – 288 с. 3. Агафонов В.Н. Спецификация программ: поня- тийные средства и их организация. – Новосибирск: Наука. Сиб. отд-ние, 1990. – 224 с. 4. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Д. Ватолин, А. Ра- тушняк, М. Смирнов, В. Юкин. - М.: Диалог-МИФИ, 2002. – 384 с. 5. Лисков Б., Гатэг Дж. Использование абстракций и спецификаций при разработке программ. - М.: Мир, 1989. – 424 с. 6. Гвишиади А.Д., Агаян С.М., Богоутдинов Ш.Р. Математические методы геоинформатики. I. О новом подходе к кластеризации // Кибернетика и систем- ный анализ. - №2. – С. 104-122. 7. Ту Дж., Гонсалес Р. Принципы распознавания образов. - М.: Мир, 1978. – 411с. 8. Жамбю М. Иерархический кластер-анализ и соот- ветствия. - М.: Финансы и статистика, 1988. - 342с. 9. Шинкаренко В.И. Сравнительный анализ времен- ной эффективности функционально эквивалентных алгоритмов // Пробл. программирования. – 2001. - №3-4 – С. 31-39. 10. Соболь И.М. Численные методы Монте-Карло: М. Наука, 1973. – 311 с. 11. Касперски К. Техника оптимизации программ. Эффективное использование памяти. СПб. - БХВ- Петербург, 2003. – 464 с. Получено 26.09.05 Сведения об авторе Шинкаренко Виктор Иванович доцент кафедры Компьютерные информа- ционные технологии, канд. техн. наук Место работы автора Днепропетровский национальный универси- тет железнодорожного транспорта им. ака- демика В. Лазаряна Днепропетровск, ул. Акад. Лазаряна, 2, Тел.8-056-776-19-52 (раб) Тел. 8-0562-47-39-67 (дом) E-mail ccp@diit-70.diit.ua, shink@tk.diit.edu.ua
id	nasplib_isofts_kiev_ua-123456789-2332
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1727-4907
language	Russian
last_indexed	2025-12-07T16:37:36Z
publishDate	2006
publisher	Інститут програмних систем НАН України
record_format	dspace
spelling	Шинкаренко, В.И. 2008-09-17T14:56:38Z 2008-09-17T14:56:38Z 2006 Функциональная эффективность нечетко специфицированных алгоритмов / В.И. Шинкаренко // Проблеми програмування. — 2006. — N 1. — С. 24-33. — Бібліогр.: 11 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/2332 004.421 Определено понятие нечетко специфицированного алгоритма. Рассмотрены особенности спецификации таких алгоритмов. Выделена одна из их эксплуатационных характеристик – функциональная эффективность. Показана значимость этой характеристики для задач практического программирования. Предложены статистические показатели оценки функциональной эффективности. Визначено поняття нечітко специфікованого алгоритму. Розглянуті особливості специфікації таких алгоритмів. Виділена одна з експлуатаційних характеристик алгоритмів – функціональна ефективність. Показана значимість цієї характеристики для задач практичного програмування. Запропоновані статистичні показники оцінки функціональної ефективності Concept definition of the fuzzy specified algorithms is proposed. The particularities of the specification such algorithms are considered. One of the field-performance datas of algorithm - functional efficiency are noticed to. Meaning of this feature for problems of the practical programming is shown. Statistical factors of the estimation of the functional efficiency are offered ru Інститут програмних систем НАН України Теоретичні та методологічні основи програмування Функциональная эффективность нечетко специфицированных алгоритмов Функціональна ефективність нечітко специфікованих алгоритмів Functional efficiency of the fuzzy specified algorithms Article published earlier
spellingShingle	Функциональная эффективность нечетко специфицированных алгоритмов Шинкаренко, В.И. Теоретичні та методологічні основи програмування
title	Функциональная эффективность нечетко специфицированных алгоритмов
title_alt	Функціональна ефективність нечітко специфікованих алгоритмів Functional efficiency of the fuzzy specified algorithms
title_full	Функциональная эффективность нечетко специфицированных алгоритмов
title_fullStr	Функциональная эффективность нечетко специфицированных алгоритмов
title_full_unstemmed	Функциональная эффективность нечетко специфицированных алгоритмов
title_short	Функциональная эффективность нечетко специфицированных алгоритмов
title_sort	функциональная эффективность нечетко специфицированных алгоритмов
topic	Теоретичні та методологічні основи програмування
topic_facet	Теоретичні та методологічні основи програмування
url	https://nasplib.isofts.kiev.ua/handle/123456789/2332
work_keys_str_mv	AT šinkarenkovi funkcionalʹnaâéffektivnostʹnečetkospecificirovannyhalgoritmov AT šinkarenkovi funkcíonalʹnaefektivnístʹnečítkospecifíkovanihalgoritmív AT šinkarenkovi functionalefficiencyofthefuzzyspecifiedalgorithms

Функциональная эффективность нечетко специфицированных алгоритмов

Репозитарії

Схожі ресурси