Автореферат (1150568), страница 3

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

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

Алгоритм заканчивает работу.Иначе, переходим к п. 3.3.3. Параллельно работают δ процессоров; i-й процессор i  1,...,  осуществляет присвоение значений переменным.103.1. Если в рабочей формуле данного процессора нет переменных, то вкачестве рабочей для этого процессора выбираем формулу из следующейэлементарной дизъюнкции, содержащую хоть одну переменную.3.2. Ищем среди формул в S(ω)формулу Pk  a j ,..., a j  , имеющуюi1niприоритет, равный 1, и потенциально контрарную формуле Pk t1,..., tn , сiiкоторой работает этот процессор.

Если нашли подходящую формулу, топереходим к п. 3.3. Если ее нет, то переходим к п. 4.3.3. Решаем систему уравнений вида tl  a jll  1,..., ni  , унифицирующуюсписок переменных и констант со списком констант. В случае, если эта системаимеет решение, то переходим к п. 3.4. Если система решений не имеет, топонизить приоритет этого действия до 0 и переходим к п.

3.2.3.4. Записываем результаты, полученные разными процессорами, ипроверяем их на непротиворечивость следующим образом. Если процессорыодновременно присваивают одним и тем же переменным разные значения, тотакие результаты считаются противоречивыми. Если результаты действий двухпроцессоров не противоречат друг другу, то присвоение полученных значенийпеременных осуществляется в формулах обоих процессоров.3.5. Заменяем в F-наборе каждого процессора вхождения переменных изсписка на их значения, полученные в п. 3.3 и 3.4, если успешно пройденапроверка на непротиворечивость.3.6.

Если для какого-либо процессора получился пустой F-набор, то алгоритмзаканчивает работу. Формула выводима и найден набор значений переменных,существование которых утверждалось в формуле.3.7. Если получился тупиковый F-набор, то переходим к п. 4.3.8. Если для всех процессоров приоритеты всех действий равны 0, тоформула не выводима. Алгоритм заканчивает работу.3.9.

Если в F-наборе какого-либо процессора существуют формулы, имеющиепеременные, которым еще не присвоено значение, то переходим к п. 3.1.4. Возвратная часть алгоритма.4.1. Отменяем последнее действие п. 3.5, если это возможно, и переходим к п.3.2.4.2. Если для какого-либо процессора отмена последнего действия п. 3.5невозможна, то алгоритм заканчивает работу.4.3. Если все процессоры закончили работу, но пустой F-набор не получен, тоалгоритм заканчивает работу.

Формула не выводима.В разделе 3.2 получены асимптотические оценки числа шагов работыалгоритма IAPTAТеорема 3. (Нижняя оценка числа шагов работы алгоритмаIAPTA.)Количествошаговдоказательствалогическогоследованиявида11S  x Ak  x  и нахождения значений переменных, для которых этоследование имеет место, при использовании алгоритма IAPTA, не менее 2δ(s + 2)+ 2 шагов.Теорема 4. (Верхняя оценка числа шагов работы алгоритмаIAPTA.)Количество шагов доказательства логического следования вида S  x Ak  x и нахождения значений переменных, для которых это следование имеет место,при использовании алгоритма IAPTA составляет  шагов.O l  max sk   k В четвертой главе рассматривается решение задачи выделениямаксимальной общей подформулы с использованием алгоритма IAPTA.В разделе 4.1 приведена постановка задачи выделения максимальной общейподформулы двух заданных элементарных конъюнкцийA x  и~A y  , сточностью до имѐн переменных, как доказательства логического следования 1~~~A x   yA y  с нахождением такой подформулы A y   формулы A  y  , что~имеет место следствие A x   y A y   ,а также общего унификатора λ формулA x  и~A y  , то есть такой подстановки имѐн переменных y  вместо~некоторых имѐн переменных из списка x , что A y  является подформулойA x  после применения унификатора λ.Если в алгоритме IAPTA заменить действие «присвоение значенийпеременным» на «отождествление переменных», этот алгоритм можномодифицировать до алгоритма PHIAPTA, и применить и для решения задачивыделения максимальной общей подформулы.В разделе 4.2 приведен алгоритм PHIAPTA выделения максимальной общейподформулы двух заданных элементарных конъюнкций с точностью до имѐнпеременных.АлгоритмPHIAPTA (Partial Hatchability Inverse Ant Parallel Tactic Algorithm)1.

Строим δ-членный F-набор, формулы в котором не повторяются. То естьпереписываем без конъюнкций все дизъюнкты вида A( x ) Pk y1 ,..., yn , приiii 1,..., . Создаем популяцию из δ процессоров.Каждой паре потенциально контрарных формул P y ,..., y , иPkx ,..., xn ,j 1jkiвходящихводинF-набор,назначаем1niприоритетихотождествления равным 1. Остальные приоритеты назначаем равными 0.1Косовская Т. М. Частичная выводимость предикатных формул как средство распознаванияобъектов с неполной информацией // Вестник СПбГУ.

Сер. 10. 2009. Вып. 1. С. 74-84.122. Копируем δ-членный F-набор δ−1 раз. Таким образом получаем ровно δодинаковых F-наборов. Назначаем i-му процессору ( i 1,..., ) свою начальнуюформулу Pk y1 ,..., yn– формулу, с которой данный процессор начинает свойiiитерационный цикл, и потенциально контрарную ей формулу видаиз A x  , имеющую приоритет, равный 1. Для каждогоPk x1 ,...,xnjjпроцессора назначаем переменную li 0 ( i 1,..., ), означающую длину фрагмента~формулы A x  в формуле A y   .Если какие-то два процессора начинают работу с формулой, начинающейся содного и того же предикатного символа, то назначаем для них разные формулы изA x  , потенциально контрарные данной.

Если для каких-то двух процессоров несуществует разных потенциально контрарных формул, берем для них одинаковыепотенциально контрарные формулы и переходим к п. 3.3.3. Параллельно работают δ процессоров; i-ый процессор ( i 1,..., )осуществляет отождествление переменных следующим образом.3.1. Если в рабочей формуле данного процессора нет переменных, которыееще не проходили процедуру отождествления, то в качестве рабочей для этогопроцессора выбираем формулу из следующей элементарной дизъюнкции,содержащую хоть одну «не отождествленную» переменную. , имеющую3.2. Ищем среди формул в A x  формулу P  x ,..., xki  j1jn jприоритет, равный 1, и потенциально контрарную формуле Pk t1 ,...,tn(изii~A y   ), с которой работает этот процессор.

Если нашли подходящую формулу,то переходим к п. 3.3. Если ее нет, то переходим к п. 4.3.3. Решаем систему уравнений вида tl  x j ( l 1,..., ni ), унифицирующуюlсписки переменных. В случае, если эта система имеет решение, то увеличиваемдлину текущего фрагмента li на единицу, запоминаем это число и текущееотождествление и переходим к п. 3.4. Если система решений не имеет, топонизить приоритет этого действия до 0 и переходим к п. 3.2.3.4. Записываем результаты, полученные разными процессорами, ипроверяем их на непротиворечивость.3.5.

Заменяем в F-наборе каждого процессора вхождения переменных изсписка на их значения, полученные в п. 3.3 и 3.4, если успешно пройденапроверка на непротиворечивость.~3.6. Если для какого-либо процессора все переменные из A y   получилиновое значение, и выведен пустой F-набор, то алгоритм заканчивает работу.~Формула A y   полностью содержится в формуле A x  ).133.7. Если в F-наборе какого-либо процессора отсутствуют формулы,имеющие переменные, которые еще проходили процедуру отождествления, топереходим к п.

4.3.8. Если для всех процессоров приоритеты всех действий равны 0, топереходим к п. 4.3.3.9. Если в F-наборе какого-либо процессора существуют формулы, имеющиепеременные, которые еще не проходили процедуру отождествления, топереходим к п. 3.1.4. Возвратная часть алгоритма.4.1. Отменяем последнее действие п. 3.5, если это возможно, уменьшаемсоответствующую величину li на 1, запоминаем это число и текущееотождествление и переходим к п.

3.2.4.2. Если для какого-либо процессора отмена последнего действия п. 3.5невозможна, то процессор заканчивает работу.4.3. Если все процессоры закончили работу, то наибольшее число из всех li~на всех шагах является размером наибольшей подформулы A y   в A x  . Исоответствующие этому li отождествления являются наибольшей подформулой~A y   в A x  .В разделе 4.3 получены оценки числа шагов работы алгоритма PHIAPTA.Теорема 5. (Нижняя оценка числа шагов работы алгоритма PHIAPTA)Количество шаговвыделения максимальной общей подформулы двух~элементарных конъюнкций A x  и A  y  , при использовании алгоритмаPHIAPTA, не менее 4δ + 2δs − 1 + l шагов.Теорема 6.

(Верхняя оценка числа шагов работы алгоритма PHIAPTA.)Количество шаговвыделения максимальной общей подформулы двух~элементарных конъюнкций A x  и A  y  , при использовании алгоритмаPHIAPTA, не превосходит O  l  max s   шагов.kk В приложениях А, В и С приведены модельные примеры примененияалгоритмов IMA, IAPTA и PHIAPTA соответственно для решения задач логикопредметного распознавания образов.В заключении приведены итоги выполненного исследования, которыезаключаются в следующем:1. Сформулирована и обоснована адаптация обратного метода Маслова длядоказательства выводимости формул вида x1,..., xn   & Di a1,..., ak , x1,..., xn  , к i 1доказательству выводимости которых сводятся многие задачи ИскусственногоИнтеллекта, объекты исследования в которых характеризуются свойствами своих14элементов и отношениями между этими элементами, а, следовательно,допускающие формализацию средствами языка исчисления предикатов.2.РазработаналгоритмIMAвыводимостиформулвидаx1,..., xn   & Di a1,..., ak , x1,..., xn  , основанный на разработанной адаптации i 1обратного метода.

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

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