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

Страницы:
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 

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

УДК 519.87

Локально-паралельний стековий алгоритм бінарного клітинного автомату / Бенаддія Абдельлатіф, О.П. Міхаль // Біоніка інтелекту: наук.-техн. журнал. — 2011. — № 3

(77). — С. 112-118.

Локально-паралельне подання інформації забезпечує підвищення эфективности работи програмного забезпе­чення. Додання принципів локально-паралельної оброб­ки до клітинних автоматів дозволяє суттєво підвищити розміри моделей. Запропоновано і продемонстровано на тестових прикладах локально-паралельний стековий ал­горитм бінарного клітинного автомату.

Іл. 2. Бібліогр.: 7 найм.

UDK 519.87

Local-parallel stack algorithm of the binary cellular au­tomaton. / Benaddia Abdellatif, O.Ph. Mikhal // Bionics of Intelligense: Sci. Mag. — 2011. — № 3 (77). —P. 112-118.

Local-parallel presentation of information provides raised efficiency of the work of software. Application of principle of local-parallel processing to cellular automaton allows greatly enlarge the sizes of models. Local-parallel stacked algorithm of the binary cellular automaton is offered and demonstrated on test examples.

Fig. 2. УДК 519.87

ММохамад Али, О.Ф. Михаль ХНУРЕ, г. Харьков, Украина, fuzzy16@pisem.net

intelligence   ЛОКАЛЬНО-ПАРАЛЛЕЛЬНАЯ СОРТИРОВКА ОГРАНИЧЕННЫХ

МАЛЫХ НАБОРОВ ДАННЫХ

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

ЛОКАЛЬНАЯ ПАРАЛЛЕЛЬНОСТЬ, СОРТИРОВКА ДАННЫХ

Введение

Сортировка данных — классическая задача теории алгоритмов, сочетающая в себе прозрач­ность общей концепции и простоту постановки с многовариантностью решений в зависимости от дополнительных условий, налагаемых в связи с конкретными особенностями обрабатываемой информации. Алгоритмы сортировки подробно изучены для вычислительных систем (ВС) после­довательного действия. Параллельные ВС до не­давнего времени были исключительно многопро­цессорными, дорогими и громоздкими, поэтому они разрабатывались преимущественно для спе­циальных применений, а задачи сортировки рас­сматривалась в них главным образом в контексте реализации общих принципов распараллеливания алгоритмов применительно к большим массивам данных. Ситуация изменилась в последние деся­тилетия с появлением многоядерных процессоров и широким распространением (массовым исполь­зованием) сетевых вычислительных структур [1]: приобрела актуальность обработка ограниченных малых наборов данных (ОМНД). Задача сортировки применительно к ОМНД [2, 3] эффективно реша­ется с использованием алгоритмов, реализующих принципы локальной-параллельной (ЛП) обработки информации [4, 5]. Область применения ОМНДзадачи принятия решений при детерминированном наборе вариантов. К задачам этого типа относится, в частности, значительная часть тематики искус­ственного интеллекта (ИИ). Так, одна из парадигм ИИ — исследование и воспроизведение структур и функций человеческого интеллекта. Человек же в каждый конкретный момент своей практической деятельности эффективно оперирует ограниченным малым числом понятий [6]. Эффективность (ско­рость принятия решений) зачастую определяется правильной последовательностью рассмотрения вариантов, а реализация эффективности сводится к сортировке ОМНД. ЛП алгоритмы обеспечивают повышение скорости обработки без задействова­ния дополнительных аппаратных ресурсов. Поэто­му они целесообразны как структурный элемент при реализации обработки ОМНД. Сказанным определяется актуальность и практическая цен­ность данного направления.

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

1. Гносеологический аспект

Рассматриваемый предмет имеет глубокие кор­ни в природе человеческого интеллекта. Эффек­тивная человеческая деятельность характеризует­ся, в частности:

— ограниченным (не слишком большим) коли­чеством одновременно выполняемых (отслеживае­мых) заданий (процессов, объектов, дел, работ);

— правильным определением приоритетности (важности, последовательности) выполнения за­даний.

Деятельность с избыточным числом выполняе­мых заданий, или с плохо организованной приори­тетностью, как правило, малоэффективна. Данные аспекты базируются на ограниченности ресурсов реализации человеческого интеллекта. Факт, из­вестный в психологии [6]: средний человек спо­собен эффективно взаимодействовать (удержи­вать в памяти, отслеживать изменения, мысленно оперировать) одновременно не более, чем с 5—7 объектами (предметами, понятиями, блоками ин­формации). Данная закономерность обусловлена ограниченным числом информационных каналов взаимодействия с объектами, а также ограничен­ными ресурсами параллельной обработки инфор­мации (мыслительной деятельности) по плани­рованию выполнения действий с надлежащей приоритетностью.

Данная особенность человеческого интеллек­та имеет отношение к компьютерной технике и информационным технологиям в следующем аспекте. Практика развития компьютерных си­стем (hardware и software, включая ИИ) такова, что явно или неявно мерилом прогресса в этой об­ласти является степень соответствия человеческо­му интеллекту. Данное положение соответствует, в частности, известному тесту Тюринга [7]. Ис­ходя из этого, при разработке ВС целесообразно изучать «прототип» (hardware человеческий мозг и software — человеческую психику) и следовать тенденциям, предначертанным в этой «уже раз­работанной» «эталонной» и «априорно совершен­ной» системе, являющейся «технической базой», на которой реализован человеческий интеллект. Известно, что «прототип» «аппаратно реализован» на естественных (живых) нейронных сетях (НС). Основной особенностью обработки информации на НС и ключевым преимуществом НС является параллельность. Параллельность реализуема в на­стоящее время преимущественно на многопроцес­сорных и многоядерных вычислительных структу­рах, а также в виде распределённых (локально- и глобально-сетевых) ВС. Аппаратная база искус­ственных НС развита в настоящее время в суще­ственно меньшей степени. Исходя из этого, на­ряду с развитием аппаратных искусственных НС, целесообразны исследования и разработки в обла­сти алгоритмов, поддерживающих параллельную обработку информации на имеющихся наиболее развитых на настоящий момент типах аппаратного обеспечения. Перспективны ЛП алгоритмы, кото­рыми распараллеливание обработки информации может быть реализовано на ВС последовательного действия (работающих в рамках концепции Фон-Неймана), то есть на компьютерах общего назначе­ния. Таким образом, с использованием принципа ЛП параллельные вычисления претерпевают неко­торое качественное изменение. Соответственно, требуют пересмотра в рамках концепции ЛП также и классические процедуры сортировки данных [8].

2. Основные определения

Будем рассматривать набор данных А как мно­жество, состоящее из элементов:

A: («1, a2, «3,..., a-1, a, a^,..., an_2, an_b a„). (1)

Каждое из данных, соответствующее a;-, є A, iє (1, 2,...., я), — объект произвольной природы: число, фрагмент текста, запись в БД, картинка, фрейм и др. При этом элементы множества A мо­гут быть самими объектами набора данных, либо указателями на них, позволяющими взаимно­однозначно соотносить ai, є A и соответствующий объект. В первом случае операции, производимые над объектами множества A, связаны с перемеще­нием самих объектов (данных) в памяти, во втором — объекты непосредственно не перемещаются, а операции над ними сводятся к работе с указателя­ми. С точки зрения рассматриваемых далее алго­ритмов ЛП сортировки данное различие не суще­ственно.

Термин «ограниченный» предполагает конеч­ное число n элементов, неизменное в процессе сортировки; термин «малый» — количество элементов,прикоторомнетребуетсяиспользование видов (типов) памяти, существенно замедляющих информационный обмен в процессе выполнения сортировки. Разумеется, интерпретация термина «малый» может быть уточнена с учётом конкретной архитектуры ВС.

Отношение порядка (наличие упорядоченности) на множестве A предполагает указание для неко­торых элементов ai, aj є A, i, j є (1, 2, 3,..., я), i ф j, одного из следующих соотношений: ai -< aj, ai у aj. Символы « - и « у » есть отношения следования: «предшествует» и «следует за». В частности они могут интерпретироваться как арифметические соотношения между числами — бинарные отноше­ния «меньше» (<) и «больше» (>). При этом интер­претацией арифметического соотношения a, = aj может быть «произвольное следование»: справед­ливо любое из отношений следования a, -< aj, или «і у aj.

Множество А является упорядоченным, если от­ношение порядка определено для любых ai, aj є A. Множество А является частично упорядоченным, если отношение порядка определено только для некоторых из пар ai, aj є A. Элементы, для которых отношения порядка не определены, являются не­соизмеримыми. Множество является неупорядочен­ным, если ни для одной пары элементов не опреде­лено отношение порядка.

Будем различать множество как совокупность элементов (1) и последовательность элементов множества как выборку некоторых элементов множества с учётом порядка их размещения. Для упорядоченной последовательности, включающей все элементы множества А (1), в арифметической интерпретации с учётом замечания о соотношении ai = aj справедливо одно из выражений:

a1 < a2 < a3 <...< aM < at < a+1 <...< an_2 < a„-1 < an; (2)

a1 > a2 > a3 >...> aiA > at > a+1 >...> an_2 > a„-1 > an. (3)

Последовательность является упорядоченной по возрастанию (2) (соответственно, по убыванию (3) ), если для любой пары её элементов справедливо ai < aj (соответственно, ai > aj), где i, j є (1, 2, 3,..., я), i < j. Если хотя бы для одной пары элементов усло­вие ai < aj (ai > aj) не выполняется, последователь­ность не является упорядоченной по возрастанию (убыванию), то есть является неупорядоченной по возрастанию (неупорядоченной по убыванию). Таким образом, последовательность, упорядоченная по возрастанию, является неупорядоченной по убы­ванию; последовательность, упорядоченная поубыванию, является неупорядоченной по возрас­танию. То есть упорядоченности по возрастанию и убыгванию взаимно-обратно являются неупоря-доченностями. Данные и подобные представления (упорядочение, разупорядочение или переупоря­дочение) продуктивны применительно к задачам сортировки ограниченных малых наборов элемен­тов. Множество может быть изначально разупо-рядоченным. Процесс упорядочения — переход от одной последовательности (расстановки) эле­ментов к другой. Может быть введена мера разупо-рядоченности множества как число перестановок соседних элементов, которое необходимо произ­вести чтобы прийти к упорядоченной последова­тельности элементов.

Страницы:
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 самых важных уроков библии

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

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

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

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