Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 62

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

Строками двунаправленных стрелок над со­ответствующими нумерованными строками обо­значены ЛП операции обмена между сегментами. Каждая строка стрелок есть одна ЛП операция. Как показано, инвертирование последовательно­сти реализуется за n шагов. В примере (рис. 3) в нечётных шагах процесса осуществляется обмен между чётными и нечётными сегментами (чётный сегмент стоит слева от нечётного), а в чётных стро­ках — обмен между нечётными и чётными сегмен­тами (чётный сегмент стоит справа от нечётного).

ГТ     ГТ     ТТ ГТ

1) 76543210

ГТ      ГТ ГТ

2) 6 7 4 5 2 3 0 1

ГТ    гт    тт. гт

3) 6 4 7 2 5 0 3 1

гт    тт гт

4) 4 6 2 7 0 5  1 3

гт    гт    тт гт

5) 4 2 6 0 7  1  5 3

гт    тт гт

6) 2 4 0 6  1 7 3 5

гт    гт    гт гт

7) 2 0 4  1 6 3 7 5

гт    гт гт

8) 02143657 0   1   2   3   4   5   6 7

Рис. 3. ЛП сортировка последовательности из 8 элементов

В примере (рис. 3) ЛП сортировка начата со строки обменов «чётыш—нечётный». Возможен также другой порядок: начало сортировки со стро­ки «нечётный—чётный». При изменении порядка чередования обменов общее число шагов сорти­ровки не изменяется: полная ЛП пересортировка 4 элементов (1, 2, 3, 4) — (4, 3, 2, 1) реализуется за равное число шагов.

 

ГТ гт

ГТ

1)

1234

1234

 

гт

гт гт

2)

2   14 3

1324

 

ГТ гт

гт

3)

2413

3    14 2

 

гт

ГТ гт

4)

4231

3412

 

4321

4321

 

а

б

Рис. 4. ЛП сортировка последовательности из 4 элементов в двух вариантах: начиная с «чётный—нечётный» (а) и «нечётный—чётный» (б)

Результат сортировки также остаётся прежним, поскольку изменение касается только фаз сорти­ровки по чередованию чётностей.

Пример (рис. 4) соответствует графу на рис. 1 б. При этом ЛП алгоритм преобразования (1, 2, 3, 4)

— (4, 3, 2, 1) реализует пару цепочек (10, 11) типа (4), но с сокращённым числа промежуточных со­стояний:

(1, 2, 3, 4) — (2, 1, 4, 3) — (2, 4, 1, 3) —

— (4, 2, 3, 1) — (4, 3, 2, 1) (10) (1, 2, 3, 4) — (1, 3, 2, 4) — (3, 1, 4, 2) —

— (3, 4, 1, 2) — (4, 3, 2, 1). (11)

Выражение (10) соответствует рис. 4 а — ЛП со­ртировка начинается с сопоставления «чётный— нечётный»; выражение (11) — рис. 4 б начало сортировки с «нечётный—чётный». На графе рис. 1 б элементы (10) (кроме исходного и конечно­го) выделена жирным пунктиров, элементы (11)

— мелким пунктиром. Сопоставление рис. 4 а, б с графом рис. 1 б позволяет видеть, каким образом реализуется выигрыш в производительности ЛП сортировки по сравнению с традиционной после­довательной.

7. Обсуждение результатов

Граф (рис. 1 а) демонстрирует симметрию раз­личных вариантов сортировки. Различные виды последовательностей из 3 элементов расположены в вершинах 6-угольника. Каждая вершина соедине­на с двумя другими, потому что связь соответствует обмену местами в паре соседствующих элементов, а у последовательности из трёх элементов имеется ровно 2 варианта пар обмена. Изменение порядкаэлементов на обратный реализуется за 3 шага не только для (1, 2, 3) — (3, 2, 1), но и для любых пар последовательностей (вершин графа) с взаимно-инверсным расположением символов. Легко ви­деть, что на графе соответствующие парные верши­ны в 6-угольнике расположены диагонально.

Аналогично, граф (рис. 1 б) также демонстриру­ет симметрию. Каждая из вершин графа соедине­на с тремя другими, так как у последовательности из 4 элементов имеется три пары соседствующих элементов, что соответствует трём вариантам об­мена. Изменение порядка элементов на обратный реализуется за 6 шагов не только для (1, 2, 3, 4)

— (4, 3, 2, 1), но и для любых пар последователь­ностей (вершин графа) со взаимно-инверсным расположением символов. Это может быть не­посредственно прослежено на графе. Изображе­ние графа (рис. 1 б) укрупнено, имеет очертания ромба. Вершины графа, расположенные по левой верхней стороне ромба, в последовательности сле­ва направо (т.е. (1, 2, 3, 4), (2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1) ) взаимно-инверсны вершинам графа, расположенным по правой нижней стороне ромба, в последовательности справа налево (т.е. (4, 3, 2, 1),

(4, 3, 1, 2), (4, 1, 3, 2), (1, 4, 3, 2) ). Аналогично,

взаимно-инверсны вершины расположенные по правой верхней и левой нижней сторонам ромба.

Граф (рис. 1 б) — непланарный. При других его начертаниях (начиная, например, с изменения по­рядка расположения вершин второго слева столб­ца) другие его вершины будут «выведены» на сто­роны ромба. При этом в силу симметрии (каждая вершина соединена ровно с тремя другими) сохра­няется взаимно-инверсное расположение вершин. Между взаимно-инверсными вершинами непо­средственно и наглядно может быть прослежена на графе цепочки длиной ровно 6 шагов.

Описанная ситуация не является неожиданной, поскольку сводится к циклической замене симво­лов или может рассматриваться как перекодировка записи выражений (1, 2, 3) — (3, 2, 1) и (1, 2, 3, 4)

— (4, 3, 2, 1) и соответствующая замена символов в графах (рис. 1).

Таким образом, рассмотренное выше ЛП пре­образование (1, 2, 3, 4) — (4, 3, 2, 1), проиллюстри­рованное графом (рис. 1 б) является достаточно общим, справедливым для любых пар взаимно-инверсных вершин.

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

Работа ЛП процедуры сортировки (рис. 2) смо­делирована в варианте с 8 3-битовыми сегментами.

Заполнение сегментов выполнено наборами чисел (0, 1, 2, 3, ., 7) со случайной перестановкой от ге­нератора случайных чисел с равномерным законом распределения. Модель реализована на языке Py­thon и демонстрирует работоспособность алгорит­ма.

8. Перспективы использования

Сортировка данных — классическая задача, ис­черпывающе разработанная для ВС последова­тельного типа. С применением элементов парал­лельной обработки сортировка приобретает новые очертания. В случае ЛП целесообразна работа с ограниченными наборами данных. При этом ско­рость выполнения сортировки возрастает пропор­ционально числу конкатенированных сегментов, вследствие чего она может быть использована в приложениях с быстрым принятием оперативных решений. Применительно к ситуациям типа систем массового обслуживания, наряду с дисциплинами выборки заданий из очередей FIFO и FILO, полу­чает право на существование очередь с заданиями, последовательность (очерёдность, важность, акту­альность, срочность) выполнения которых изме­няется в процессе нахождения заданий в очереди. Одним из приложений для подобных систем явля­ется Интернет: распределённая система хранения информации с децентрализованным управлением и мультиагентной обработкой. Другая важная при­кладная область — интерфейс взаимодействия ВС с оператором, в частности, обучающие системы.

Выводы

Локально-параллельное представление инфор­мации обеспечивает повышенную эффективность работы программного обеспечения. Принципы локально-параллельной обработки применимы к задачам сортировки наборов данных. Процеду­ры сортировки рассмотрены на комбинаторном уровне для 3-, 4- и 8-элементных последователь­ностей. Разработано алгоритмическое обеспече­ние локально-параллельной сортировки. В ходе моделирования, проведенного на языке Python, выявлено, что локально-параллельный алгоритм максимально эффективен применительно к сорти­ровке малых (в пределах разрядности процессора) выборок.

Список литературы: 1. Мохамад, Али Перспективы реали­зации локально-параллельных вычислений на многоядер -ных процессорах [Текст] / Мохамад Али, О.Ф. Михаль // Радиоэлектронные и компьютерные системы. — 2008. — № 6 (33). — С. 234—237. 2. Мохамад, Али. Локально-параллельная сортировка данных с ограниченной разрядностью [Текст] / Мохамад Али. // Материалы международной научно-практической конференции студентов и аспирантов "Информационные технологии в экономике и образовании". М.: Российский универ­ситет кооперации, 2008. — С. 48—52. 3. Мохаммед, Али

Локально-параллельная сортировка со встречной чере­дующейся упорядоченностью данных [Текст] / Мохамед Али, О.Ф. Михаль // Материалы 13-го международного молодёжного форума "Радиоэлектроника и молодёжь в XXI веке". Ч.2. Харьков: ХНУРЭ, 2009. — С. 209. 4. Михаль, О.Ф. Локально-параллельные алгоритмы определения степени включения и степени равенства нечетких множеств [Текст] / О.Ф. Михаль // Проблемы бионики. Вып. 55. — 2001. — С. 80—90. 5. Михаль, О.Ф. Принципы организации систем нечеткого регулирова­ния на однородных локально-параллельных алгоритмах [Текст] / О.Ф. Михаль, О.Г. Руденко// Управляющие си­стемы и машины. — 2001. — № 3. — С. 3-10. 6. Милнер, П. Физиологическая психология [Текст] / П. Милнер М.: Мир, 1973. — 648 с. 7. Люггер, Дж.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем [Текст] / Дж.Ф. Люгер 4-е изд.: Пер. с англ. — М.: Изд. дом «Вильямс», 2005. — 864 с. 8. Кормен, Т. Алгоритмы: по­строение и анализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ри-вест М.: МЦНМО, 2001. — 960 с.

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

УДК 519.87

Локально-паралельне сортування обмежених малих наборів даних / Мохамад Алі, О.П. Міхаль // Біоніка інте­лекту: наук.-техн. журнал. — 2011. — № 3 (77). — С. 119-125.

Розглянуто локально-паралельне подання інформації стосовно задач сортування наборів даних. Процедури со­ртування проаналізовано на комбінаторному рівні для 3-, 4- и 8-елементних послідовностей. Подано алгоритмічне забеспечення локально-паралельного сортування. В ході моделюровання на мові Python виявлено, що локально-паралельний алгоритм максимально эфективний сто­совно до сортування виборок в межах разрядности про­цесора.

Іл. 4. Бібліогр.: 8 найм.

UDK 519.87

Local-parallel sorting of limited small sets of data / Moha­mad Ali, O.Ph. Mikhal // Bionics of Intelligense: Sci. Mag. — 2011. — № 3 (77). —P. 119-125.

Local-parallel presentation of information is considered referring to problem of the sorted data sets. The Procedures of the sorting is analysed on combinatorial level for 3-, 4- and 8-element sequences. Algorithmic provision of local-parallel sorting is presented. In the course of modeling in language Python is revealled that local-parallel algorithm is greatly ef­ficient with reference to sorting the samples within processor register size.

Fig. 4. Ref.: 8 items.информационные технологии и программно-технические комплексы

УДК 004.93

intelligence

Е. А. Гофман1, А. А. Олейник2, С. А. Субботин3

1 Запорожский национальный технический университет, г. Запорожье, Украина, gofmanjenek@rambler.ru; 2 Запорожский нацщональный технический университет, г. Запорожье, Украина, olejnikaa@gmail.com;

3 Запорожский национальный технический университет, г. Запорожье, Украина, subbotin@zntu.edu.ua ИНДУКЦИЯ ЛИНГВИСТИЧЕСКИХ ПРАВИЛ С ИСПОЛЬЗОВАНИЕМ

ДЕРЕВЬЕВ РЕШЕНИЙ

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

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

Введение

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

Поскольку базы правил в экспертных системах часто характеризуются большим объёмом, акту­альной является задача индукции правил, суть ко­торой заключается в том, что на основе начального набора правил необходимо сформировать новую базу правил меньшего объёма, которая в достаточ­ной мере представляла бы начальную базу правил и была бы менее избыточной.

Существуют различные методы индукции пра­вил [2], однако эти методы при обработке правил анализируют их качество по отдельности, не рас­сматривая и не учитывая качество всей базы в це­лом, что приводит к получению неоптимальных баз нечётких правил. Поэтому актуальной является разработка новых методов индукции правил, кото­рые учитывали бы качество всей базы знаний, а не только отдельных правил. Для решения данной за­дачи предлагается создавать деревья решений [3— 5], которые после их построения переводились бы в лингвистические правила. Выбор деревьев реше­ний обосновывается их возможностью выявлять ненаблюдаемые связи внутри рассматриваемых объектов, процессов и систем.

Целью данной работы является разработка мето­да индукции лингвистических правил с использова­нием математического аппарата деревьев решений.

Для достижения поставленной цели необходи­мо решить следующие задачи:

— обзор математического аппарата деревьев ре­шений;

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа