Диссертация (1150569), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

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

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

Поскольку взаимодействиемежду процессорами требует времени, то нельзя утверждать, что если решениезадачи требует время T, то при использовании n процессоров (и тщательномраспределении операций по процессорам) время составит T/n. Как правило, эту40величину следует умножить на log2(n) [20]. При редком взаимодействии междупроцессорами эта величина может быть существенно меньше.1.5. Совместное применение идей муравьиных алгоритмов и параллельныхвычисленийИзвестно [87], что в муравьиных алгоритмах муравей – это программныйагент, который является членом большой колонии и используется для решениякакой-либо проблемы.

Он снабжается набором простых правил, которыепозволяют ему выбирать действие, которое он должен совершить. Муравейподдерживает список табу, т. е. список действий, которые он уже совершил илине может совершить вообще.Настоящий муравей во время перемещения по пути будет оставлять засобой феромон. В математической модели количеству феромона соответствуетчисловой параметр (приоритет), приписываемый атомарным формулам [87].

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

Тогда распределение ипересчет феромона будем считать назначением и изменением весов на ребрахграфа поиска вывода, которые согласно алгоритму, будут назначать приоритетвыбора действия.411.6. Понятие неполной выводимости предикатных формулДляуменьшениячислашаговрешениязадачлогико-предметногораспознавания образов были предложены специальные виды описаний классов(многоуровневые описания классов [95]).При построении многоуровневых описаний классов используется понятиемаксимальной общей с точностью до имѐн переменных подформулы двухэлементарных конъюнкций [40].

Выделение такой подформулы также являетсяNP-трудной задачей и имеет обширное практическое применение. Например,обработка изображений и сигналов [14], [21], [69], [80], [22].Понятие неполной выводимости предикатной формулы было введено в [42]для распознавания объектов с неполной информацией. При этом рассматриваетсязадача проверки того, что из истинности всех формул множестваистинностьS   следуетA x  или некоторой еѐ максимальной подформулы A~ y  на набореразличных констант из ω, где список переменных y является подсписком спискапеременных x .Для обозначения того, что проверяется не логическое следование~Ax   y ' A'  y ' , а проводится выделение максимальной общей с точностью доимѐн аргументовподформулы двух заданных элементарных конъюнкций A x  и~~~A y , с нахождением такой подформулы A'  y ' формулы A y , что имеет место~следствие Ax   y ' A'  y ' , а также общего унификатора λ формулто есть такой подстановки имѐн переменныхA x  и A~'  y ' ,y' термов вместо некоторых имѐн~переменных из списка x , что A'  y ' является подформулой A x  после примененияунификатора λ,используется выражение~Ax   p yA y .42ГЛАВА 2.

АДАПТАЦИЯ ОБРАТНОГО МЕТОДА МАСЛОВА РЕШЕНИЯЗАДАЧ ЛОГИКО-ПРЕДМЕТНОГО РАСПОЗНАВАНИЯ ОБРАЗОВОсновные результаты этой главы изложены в следующих публикацияхавтора [41], [66], [96].2.1. Формулировка обратного метода для решения задач логико-предметногораспознавания образовВ главе 1 показано, что многие задачи Искусственного Интеллекта,допускающие формализацию на языке исчисления предикатов,сводятся кдоказательству формулы видаконъюнкция,& S    x Ax  ,гдеA x – элементарнаяS   – множество постоянных атомарных формул.Это равносильнодоказательствуистинностиформулыx1,..., xn   & Di a1,..., ak , x1,..., xn  для i 1любых наборов значений констант a1,..., ak , где Di a1,..., ak , x1,..., xn  имеет вид S    Pki x .Обратный метод Маслова разработан для эффективизации процедурыпостроения вывода в исчислении предикатов.

В диссертации представленаформулировка обратного метода для доказательства выводимости формул видаx1,..., xn   & Di a1,..., ak , x1,..., xn  i 1(2.1.1)Эта формула является частным случаем формул, для которых разработанобратный метод Маслова, описанный выше [61].

Обратный метод ориентированна существенное сокращение перебора при доказательстве выводимости формулгораздо более общего вида, имеющих три, а не две перемены кванторов.В (2.1.1) дизъюнкты Di a1,..., ak , x1,..., xn  имеют вид43,Di a1,..., ak , x1,..., xn    S a1,..., ak   Pki x1,..., xn  S a1 ,...,ak  – обозначениеформул, входящих в S a1 ,...,ak  .где(2.1.2)для дизъюнкции отрицаний атомарныхВ [61] этот метод сформулирован для формул видаz1,..., zk x1,..., xn  y1,..., ym  & Di z1,..., zk , x1,..., xn , y1,..., ym  , (2.1.3) i 1частным случаем которых являются рассматриваемые в диссертации формулы. Вних отсутствуют переменные под внутренним квантором всеобщности, и,соответственно, операции, связанные с этими переменными, следует опустить.Кроме того, все значения переменных x1,..., xn должны быть различными.Так как в (2.1.1) ak – константы, а d m отсутствуют, то условия 1 – 3определения 1.2.6 выполняются для любого Di a1,..., ak , x1,..., xn  , и таким образомимеем следующее определение.Определение 2.1.1.

Любой список формул Г вида Di a1,..., ak , с1,..., сn является допустимым для формул вида (2.1.1).Определение 2.1.2. Любой список Г формул вида Di a1,..., ak , с1,..., сn являетсяF-набором для формул вида (2.1.1), если формулы в этом списке неповторяются.Определение 2.1.3. Пусть 1,...,  l – список констант из списка a1,..., ak .1,..., l – список переменных и констант из списка a1,..., ak .

Рассмотрим системуравенств:1  1   l l(2.1.4)44Пусть u1,..., u p – список без повторений всех переменных, входящих в равенствасистемы (2.1.4). Систему (2.1.4) будем называть системой уравнений впеременных u1,..., u p .Решением системы уравнений (5) будем называть всякийнабор значенийконстант 1,...,  p из списка a1,..., ak такой, что в результатеодновременной замены всех переменныхu1,..., u pна константы1,..., pсоответственно левые и правые части каждого равенства системы совпадут.Система уравнений (2.1.4) не имеет решений, если в списке 1,...,  p естьповторения, или если в системе уравнений (2.1.4) приходится сравнивать разныеконстанты.Процедура отождествления переменных с константамиПусть Г – список формул вида Di a1,..., ak , u1,..., u p ;S – система уравнений впеременных u1,..., u p ; σ – решение этой системы.

Характеристики

Список файлов диссертации