Описание минимальных наборов признаков в приближенных множествах

рівня знань, вмінь і навичок окремого суб’єкта навчання. А це є основою для створення в системі управління учбовим процесом “схем дій” по підвищенню його ефективності.

Формування інформаційного ресурсу в АСКЗН дозволяє створити ефективну систему управління учбовим процесом, інформаційне середовище якої в значній мірі буде формуватися автоматично в АСКЗН і незалежно від роботи управлінських структур ВЗО. Особливістю наведеного підходу до побудови систем управління учбовим процесом є те, що як “фабрика” інформації використовується автоматизована система контролю знань і навчання. Основні переваги — мінімізація часу на формування інформаційного ресурсу систем управління учбовим процесом, підвищення достовірності, повнота інформації, яка автоматично формується в процесі автоматизованого контролю знань і навчання. Використання наведеної моделі інформаційної взаємодії при створенні систем контролю знань і навчання як елементів управління учбовим процесом дозволить “запрограмувати” такі зміни в інтелектуальному апараті суб’єкта навчання, які забезпечать формування спеціаліста з необхідним рівнем знань, вмінь та навичок.

На основі наведеної моделі в Черкаському державному технологічному університеті розроблена і впроваджена у виробничу експлуатацію інструмен -тальна програмно-інформаційна система контролю знань та навчання ТЕСТ, яка використовується для організації та проведення учбового процесу з урахуванням сучасних засобів і методів автоматизованого навчання та контролю знань. Особливістю системи ТЕСТ у порівнянні з традиційними контролюючими та навчаючими програмами є комп-

лексна автоматизація таких основних і найбільш трудомістких функцій підготовки спеціалістів та управління учбовим процесом, як: навчання; контроль знань; організація документообігу; облік студентів, викладачів, дисциплін; ведення баз параметрів контролю; формування та використання різних методик контролю; ведення архіву оцінок тестування студентів [4].

В цілому результати виробничої експлуатації системи ТЕСТ свідчать про її ефективність і дозволяють підійти до рішення задач управління учбовим процесом на якісно новому рівні, через максимальну автоматизацію процесів навчання та контролю знань.

Література: 1. Каган В.М., Сичеников И.А. Основы оптимизации процесса обучения в высшей школе. М.: Педагогика, 1987. 147 с. 2. Тесля Ю.Н. Основы теории информационного взаимодействия.Киев, 1995. 49с. (Препр. НАН Украины. Ин-т кибернетики им.В.М. Глушкова; 95-4). 3. Тесля Ю.Н. Информационное взаимодействие в природе. Киев, 1996. 37с. (Препр. НАН Украины. Ин-т кибернетики им.В.М.Глушкова; 96-5).

4. Тесля Є.Ю., Тесля Ю.М., Мисник Л.Д., Придворна О. О. Інформаційна технологія автоматизованого навчання та контролю знань як елемент системи управління учбовим процесом // Вісник Вінницького політехнічного інституту. Вінниця, 1999. №3. С.92-97.

Надійшла до редколегії 17.12.2002

Рецензент: д-р техн. наук, проф. Златкін А.А.

Катаева Євгенія Юріївна, аспірант кафедри програмного забезпечення автоматизованих систем Черкаського державного технологічного університету. Наукові інтреси: автоматизовані інформаційні системи та технології управління вищими закладами освіти. Адреса: Україна, 257006, Черкаси, вул. Героїв Дніпра, 15, кв. 34, тел: роб. (0472)433-341; дом. (0472)768-550.

УДК 004.827:510.635

ОПИСАНИЕ МИНИМАЛЬНЫХ НАБОРОВ ПРИЗНАКОВ В ПРИБЛИЖЕННЫХ МНОЖЕСТВАХ

СИТНИКОВ Д.Э, ТИТОВА Е.В.

Предлагается описание признаков приближенных множеств с помощью конечных предикатов. Дается геометрическая интерпретация задачи минимизации количества определяющих признаков. Определяется максимальное количество несократимых признаков для описания приближенного множества и решается задача выделения признаков, разбивающих множество на классы эквивалентности.

1. Введение

Теория приближенных множеств основывается на том, что нам изначально известна информация об элементах универсума. Некоторые объекты универ -сума являются неразличимыми с точки зрения имеющихся знаний, т.е. информация, связанная с ними, одинакова. Множества таких объектов представляют собой так называемые гранулы знаний [1,2].

С каждой гранулой ассоциируется определенный набор признаков, которые могут быть описаны различными способами. Уменьшение количества признаков при сохранении гранул универсума является важной и достаточно сложной задачей.

Рассмотрим подходы к нахождению минимального количества признаков, которые сохраняют гранулы знаний, так называемого редакта (reduct) [3]. Признаки объектов опишем с помощью конечных предикатов.

2. Представление редакта в геометрической форме

Пусть универсум U состоит из n объектов. С каждым из них связаны m признаков, каждый из которых задан с помощью одноместного предиката следующим образом:

1, если aj обладает признаком i;

0, если aj не обладает признаком i.

Множества объектов, с которыми связаны одинаковые наборы признаков, являются гранулами (т.е. объекты неразличимы с точки зрения имеющейся информации). Каждой грануле, таким образом, можно поставить в соответствие двоичный кортеж

РИ, 2003, № 1

137

длины m. Задача нахождения редакта сводится к отысканию предикатов, которые могут быть удалены. Невозможность удаления предиката Pj означает, что при его удалении гранулы сливаются, т.е. объекты универсума, которые были различимы, становятся неразличимыми. Безусловно, может существовать несколько редактов для конкретно взятого множества.

В таком виде задача нахождения редакта может быть представлена в геометрической форме.

Обозначим через En множество всех наборов (ai, a2,...an) из 0 и 1. Его можно рассматривать как множество всех вершин единичного n-мерного куба. Каждой грануле ставится в соответствие вершина с определенным набором (a1, a2,...,an) (табл. 1).

Таблица 1

а1 а2 а3 а4 а3

P1 0 0 0 1 1

P2 1 0 0 1 0

P3 0 1 1 0 1

Номер гранулы 1 2 2 3 4

Рассмотрим, что происходит при удалении предиката Pj. Вершины куба, для которых Pj =1, т.е. гранулы с наборами (a1, a2,...,aj-1, 1, aj+1,...an) проектируются на гиперплоскость, задаваемую оставшимися предикатами. В данном примере (рис.1) редактами являются наборы предикатов P1P3 и P1P2. Предикат P1 не может быть удален, так как при его изъятии точки (1,1,0) и (1,0,1) проектируются на плоскость P2P3 и сливаются с точками (0,1,0) и (0,0,1) соответственно. Предикат P1 является ядром, т.е. входит во все редакты. Если же при удалении предиката все проекции точек остаются различными (как видно из рис. 1, при удалении P2 или P3), то гранульная структура универсума не нарушается.

Рис. 1

3. Определение количества предикатов, необходимых для описания гранул универсума

Найдем теперь максимальное количество несократимых признаков для универсума.

Теорема. Пусть универсум U состоит из к гранул. Тогда предикатов, которые не могут быть удалены, не более к-1 (т.е. для описания к гранул требуется не более к-1 предикатов).

Доказательство. Пусть универсум U состоит из n объектов, описанных m предикатами. Еранульная структура универсума содержит k гранул.

Каждой грануле поставим в соответствие свою конституэнту единицы — конъюнкцию предикатов от Р1 до Рт (если значение предиката Pj для данной гранулы равно 1, то Pj записывается в положительном знаке, иначе Pj записывается с отрицанием) (табл. 2).

Таблица 2

а1 а2 а3 а4 а3 аб

P1 0 0 1 1 1 1

P2 1 0 1 1 1 1

P3 0 1 0 0 1 1

Номер гранулы 1 2 3 3 4 4

Еранула 1: P1P2P3;

Еранула 2: P1P2P3;

Еранула 3: P1P2P3;

Еранула 4: P1P2P3 .

Рассмотрим, что значит невозможность удаления предиката Pj. Это означает, что существует две конъюнкции, отличные в знаке Pj (т.е. в одной из них Pj содержится в положительном знаке, в другой —в отрицательном, при полном совпадении знаков остальных предикатов).

В нашем примере конъюнкции гранул 3 и 4: P1P2P3 и P1P2P3 отличны в знаке P3, а также конъюнкции гранул 1 и 3 P1P2P3 и P1P2P3 отличны в знаке P1 (т.е. предикаты P3 и P1 не могут быть удалены).

Пусть теперь после удаления всех возможных предикатов у нас осталось р—1 (р—1<т) предикатов, ни один из которых не может быть удален без нарушения гранульной структуры универсума. Подсчитаем, какое минимальное количество гранул определяют эти предикаты. Каждой грануле ставится в соответствие конъюнкция из р—1 предикатов (с отрицаниями или без): P[P2...Pp_1.

Если все р—1 предикатов являются неудаляемыми, то для каждого из них существуют две конъюнкции, отличные в знаке этого предиката. Минимальное количество всех конъюнкций — р. Действительно, для предиката Pj1 должно существовать две конъюнкции, отличные в знаке Pj1. Для предиката Pj2 должна существовать конъюнкция, отличная в знаке Pj2 хотя бы с одной из двух, которые отличны в знаке Pj1 (количество конъюнкций 2+1=3) и т.д. Всего для р— 1 неудаляемых предикатов количество конъюнкций не менее р.

Таким образом, р—1 неудаляемых предикатов определяют не менее р гранул. Следовательно, для описания k гранул требуется не более k—1 предикатов.

Следствие (для квадратных матриц). Пусть U состоит из n объектов, описанных n предикатами.

138

РИ, 2003, № 1

Тогда, по крайней мере, один из предикатов может быть удален.

Доказательство: Максимальное количество гранул для n объектов — n (каждый объект является гранулой). Тогда по теореме для описания n гранул нам потребуется не более n—1 предикатов.

4. Нахождение признаков, разбивающих универсум U на классы эквивалентности

Нахождение групп предикатов, разбивающих универсум на классы эквивалентности, является очень полезной операцией при нахождении редакта, так как любой предикат, входящий в эквивалентность, может быть удален без нарушения гранул (т.е. с точки зрения логики конечных предикатов он может быть выражен через отрицание остальных предикатов, входящих в эквивалентность).

Для нахождения эквивалентностей используется алгоритм построения дерева.

Для начала введем два понятия: Р0 — предикат, значение которого для всех элементов универсума

U равно 0 (V aeU, P0(a) =0), и Ри — предикат, значение которого для всех элементов универсума U равно 1 (V aeU, PU(a) =1).

Пусть все элементы универсума U описаны с помощью m предикатов.

Проиллюстрируем построение дерева эквивалентностей. Первый шаг состоит в выборе предиката

Pki (ki = 1,m). Предикат Pjq представляет собой первый ярус дерева, состоящий из одной вершины.

На втором шаге алгоритма мы строим второй ярус дерева путем построения вершин, состоящих из цепочек вида Pk1 ,Pk2 (k2 = k1 + 1,m), причем, если Pk1 л Pk2 ф Po, то эта вершина отбрасывается. Если

Pk1 Л Pk2 = Po и Pk1 v Pk2 = PU , то предикаты Pk1, Pk2 разбивают универсум U на два класса эквивалентности, и мы фиксируем эту цепочку. Если Pk1 Л Pk2 = Po и Pq v Pk2 ф Pu , то для этой вершины мы строим предикат P^k2 вида Pk1k2 = Pk1 v Pk2 .

Третий шаг алгоритма состоит в построении третьего яруса дерева, состоящего из вершин вида

PkpPk2 ,Pk3 (k3 = k2 + 1,m). С этими вершинами мы поступаем аналогично: если Pk^2 ЛPk3 ф Po , то эта вершина отбрасывается. Если Pk1k2 Л Pk3 = P0 и Pk1k2 v Pk3 = P]j , то предикаты Pk1,Pk2 ,Pk3 разбивают универсум U на классы эквивалентности (в данном случае на три класса). Если Pk^2 Л Pk3 = Po и Pk1k2 v Pk3 ф Pu , то для этой вершины мы строим

предикат Pk1k2k3 вида Pk1k2k3 = Pk^2 v Pk3 и продолжаем построение дерева путем создания четвертого яруса и т.д.

Всего ярусов в дереве эквивалентностей не более m (максимальная длина цепочки из m предикатов).

В результате построения дерева на каком-то шаге могут быть отброшены все вершины, т.е. нам не удастся выделить предикаты, разбивающие универсум U на классы эквивалентности. Некоторые предикаты могут входить в несколько эквивалентностей.

Проиллюстрируем работу алгоритма на примере (табл 3).

Таблица 3

Предикаты № гранулы

1 2 3 4 5

P1 1 o o o o

P2 o 1 o o o

P3 1 1 o o o

P4 o o 1 o o

P5 o o o 1 o

P6 o o o 1 1

Построим дерево эквивалентностей для предиката Pi (рис.2).

В данном примере мы нашли цепочку из предикатов Р1,Р2,Р4,Рб, которые разбивают универсум U на четыре класса эквивалентности. Для предиката Р2 нам не удастся построить дерево эквивалентностей. Для предиката Р3 мы получим еще одну эквивалентность: Р3,Р4,Рб.

Оценим сложность алгоритма построения дерева.

рис.2

Операции конъюнкции и дизъюнкции, т.е. операции нахождения Р0, PU и P^k2 k (Р ^ m) являются поразрядными и с применением вычислительной техники выполняются очень быстро. Оценим теперь сложность дерева эквивалентностей.

На любом шаге построения дерева количество вершин < cm , где i — номер яруса дерева. Следова-

m .

тельно, общее количество вершин дерева L < £ cm .

При больших m это число достаточно велико (например, при m=10 количество вершин дерева

m.

L < ^C‘m = Ю43 ). Можно сделать вывод, что пред-i=1

ложенный алгоритм эффективен при небольшом

139

РИ, 2003, № 1

количестве предикатов, которые, однако, могут описывать достаточно большие множества. Например, для БД с большим количеством записей и небольшим количеством полей.

Следует отметить, что ядро (т.е. предикаты, входящие во все редакты) не входит ни в одну эквивалентность.

Интерес представляют є-эквивалентности, когда предикаты Pkl,Pk2...Pk (p< m) делят универсум U на классы эквивалентности не точно, а с некоторым приближением.

В этом случае предикаты Р0 и PU представляются в несколько другом виде — виде предикатов Р0(є) и Ри(є). Ро(е) — предикат, значения которого равны 0 для всех элементов множества UicU, причем

I M

max і—----^-,— ----и-

[ M

где є<1 — некоторая заданная величина; M(P^), M(Pkj) — мощности множеств, описываемых предикатами Pki и Pkj .

Например, пусть предикат Pki описывает 100 объектов (M(Pk) =100); предикат Pkj описывает 5 объектов (M(Pkj) =5). И пусть существует объект а, для которого P^ (a) л P^ (a) = 1. Задано є=0,3.Тогда

max{ї0о’5}<є , следовательно, Pkl л Pkj = P0(e). УДК 519.21

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ФИНАНСОВЫХ ПОТОКОВ, ВОЗНИКАЮЩИХ В ПРОЦЕССЕ ДЕЯТЕЛЬНОСТИ МНОГОУРОВНЕВЫХ БИЗНЕССТРУКТУР

МИНКО Е.П., СЛИПЧЕНКО Е.В._______________

Рассматриваются задачи управления финансовыми потоками фирмы, имеющей иерархическую структуру. Акцентируется внимание на наиболее актуальных проблемах управления оборотным капиталом и на его оптимальном распределении между бизнес-единицами.

Введение

Одной из главных проблем подавляющего большинства предприятий является улучшение их финансово-экономического состояния в условиях дефицита оборотных средств [1,2]. Это связано с высокими темпами внедрения инноваций, с осторожной кредитной политикой банков и обострением конкуренции. В таком случае весьма актуальной является задача разработки эффективных механизмов управления оборотными средствами в различных бизнес-структурах. В данной работе иссл еду-

140

PU(S) — предикат, значения которого равны 1 для всех элементов множества U1cU, причем M(U\Ui) <р M(U) .

Выводы

Дана графическая интерпретация задачи нахождения редакта в приближенных множествах. Сделана оценка количества предикатов, необходимых для описания гранул универсума. Предложен алгоритм нахождения групп предикатов, разбивающих универсум на классы эквивалентности.

Литература: 1. Pawlak Z Rough sets // International Journal of Computer and Information Sciences. 1982. № 11. P. 341-356. 2. Pawlak Z. Vaguenes and uncertainty: a Rough set perspective // Computational Intelligence. 1995. Vol. 11, № 2. P. 227-232. 3. PawlakZ. Rough set approach to knowledge-based decision support / / European Journal of Operational Research. 1997. № 99. Р. 420-432.

Поступила в редколлегию 01.11.2002

Рецензент: д-р техн. наук Сухаревский О.И.

Ситников Дмитрий Эдуардович, канд. техн. наук, доцент, зав. кафедрой информационно-документных систем ХГАК. Научные интересы: приближенные множества. Увлечения: иностранные языки. Адрес: Украина, 61000, Харьков, Бурсацкий спуск, 4, тел. 72779-81.

Титова Елена Витольдиевна, мл. науч. сотрудник НЦ Войск ПВО. Научные интересы: приближенные множества. Увлечения: иностранные языки. Адрес: Украина, 61000, Харьков, пл. Свободы, 6, тел. 40-41-41 (257).

ются фирмы с иерархической структурой, ориентированные на бизнес-процессы (БП).

1. Экономические основы исследования

Бизнес-процесс — это деятельность, приносящая фирме финансовые результаты [1]. Он включает в себя два процесса:

— основной, приносящий деньги (полный цикл производства товаров и услут);

— обеспечивающий; состоящий из

а) процесса жизнеобеспечения (содержание зданий, оборудования, бухгалтерия, охрана и т.п.);

б) процесса управления основным БП;

в) процесса управления развитием БП, обеспечивающего системы при изменении условий.

Основной бизнес-процесс (ОСБП) имеет иерархическую 5-уровневую структуру (рис.1).

Бизнес фирмы в целом разбивается на направления (например, по товарным группам); направления на конкретные бизнес-процессы (КБП) (например, полные циклы производства и продаж конкретного вида продукции). КБП разбиваются на типовые бизнес-процессы (ТБП) и ЭБП (элементарные БП).

Сначала рассмотрим так называемые бизнес-единицы (БЕ). Под ними понимается структура, уп-

РИ, 2003, № 1