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

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

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

В 1992 году, в работе [105] приводится описание обратныхисчислений свободных переменных для неклассических предикатных логик.Метод свободных переменных для классической логики с равенством, а также рядкритериев избыточности были введены в работе [85].

Реализация обратногометода для предикатной интуиционистской логики описана в работе [104].В 2001году Дягтерев А.Н. и Воронков А.А. подвели некоторое обобщение в книге [86].В период с 2000 по 2001 год В.В. Бурлуцким был написан ряд работ,посвященных логическому выводу в модальных системах и реализации обратногометода для модальных логик КТ и S5 [3], [4], [5], [6], [7], [8], [9]. В 2004 году В.П.Оревков применил обратный метод и доказал разрешимость нового хорновскогофрагмента исчисления предикатов [62]. В ряде работ Д.С. Ларионова [45], [46],[47], [48], [49], [98] была разработана конкретизация обратного метода дляавтоэпистемической логики, которая применялась при построении экспертныхсистем.Г.Е.

Минц в 2010 году доказал разрешимость класса Е, используяобратный метод [100]. Кроме того, в 2010 году была предложена реализацияобратного метода с применением оператора получения благоприятного набора[79]. А в 2015 году В.А. Филипповским была предложена и реализована системаавтоматического поиска доказательств теорем, основанная на обратном методе, атакже проведено сравнение обратного метода и метода резолюций[77].Цельюдиссертационнойиразработкаалгоритмоврешенияработызадачявляетсянаучноелогико-предметногообоснованиераспознаванияобразов на основе обратного метода Маслова, а также доказательствоасимптотических оценок числа шагов работы этих алгоритмов.

Для выполненияпоставленной цели необходимо было решить следующие задачи:1. Провести исследование обратного метода, муравьиных алгоритмов,параллельных вычислений и задачи нахождения наибольшей общейподформулы.72. Сформулировать конкретизацию обратного метода для решения задачлогико-предметногораспознаванияобразов,допускающихформулировку средствами языка исчисления предикатов.3.

На основе сформулированного метода разработать алгоритм решениязадач логико-предметного распознавания образов.4. Модифицировать этот алгоритм, используя тактики муравьиныхалгоритмов и параллельных вычислений.5. Использовать последний алгоритм для решения задачи нахождениянаибольшей общей подформулы.6. Получить асимптотические оценки всех построенных алгоритмов.Целиизадачидиссертационнойработысоответствуютобластиисследований паспорта специальности 05.13.17 – «Теоретические основыинформатики»: пунктам 2 (Исследование информационных структур, разработкаи анализ моделей информационных процессов и структур), 5 (Разработка иисследованиемоделейиалгоритмованализаданных,обнаружениязакономерностей в данных и их извлечениях разработка и исследование методов иалгоритмов анализа текста, устной речи и изображений) и 7(Разработка методовраспознавания образов, фильтрации, распознавания и синтеза изображений,решающих правил.

Моделирование формирования эмпирического знания).Объектами исследования диссертационной работы являются формулыисчисления предикатов, к которым сводятся многие задачи искусственногоинтеллекта, и обратный метод Маслова. Предметом исследования являютсяразработкаиреализацияалгоритмоврешениязадачклассификацииИскусственного Интеллекта.Методологияработыосновананаметодахматематическогомоделирования, анализа и синтеза теоретического и практического материала.Для решения задач, поставленных в работе, использовались методы следующиетеоретические методы: построения математических моделей сложных систем,теории сложности алгоритмов, теории распознавания образов. В практическойчасти работы применялись методы построения и анализа алгоритмов.Научная новизна данной работы заключается в следующем.8Сформулирована конкретизация обратного метода для решения1.задачлогико-предметногораспознаванияобразов,допускающихформулировку средствами языка исчисления предикатов.Разработан алгоритм IMA решения задач логико-предметного2.распознавания образов, основанный на обратном методе.

На основе этогоалгоритма построен алгоритм IAPTA, использующий тактики муравьиныхалгоритмовипараллельныхвычислений.СформулированалгоритмPHIAPTA для решения задачи нахождения наибольшей общей подформулы.Получены асимптотические оценки всех построенных алгоритмов.Теоретическаяи практическая значимостьработы.Полученныерезультаты исследования применимы при разработке систем распознаванияобразов, объекты исследования в которых характеризуются свойствами своихэлементов и отношениями между ними, вследствие чего они допускаютформализацию на языке исчисления предикатов. Разработанные алгоритмыотличаются легкостью практической реализации.Степень достоверности и апробация результатовРезультаты диссертационной работы были представлены и обсуждались нанаучных конференциях: СПИСОК-2012, Санкт-Петербург, Россия, 25-27 апреля2012; XV Международная научная конференция «Information theories andapplications» (ITA 2012), Варна, Болгария, 18 июня-6 июля 2012; СПИСОК-2013,Санкт-Петербург, Россия, 23-26 апреля 2013; XVI Международная научнаяконференция «Information theories and applications» (ITA 2013), Варна, Болгария,29 июня-11 июля 2012, СПОСОК-2016, Санкт-Петербург, Россия, 26-29 апреля2016.Основные результаты диссертации были получены в рамках выполненияисследований при финансовой поддержке РФФИ (проект 14-08-01276).9Публикации результатовПо теме диссертации опубликовано 7 работ, из них 3 статьи врецензируемых научных журналах из перечня российских рецензируемыхжурналов, в которых должны быть опубликованы основные научные результатыдиссертаций на соискание учѐных степеней доктора и кандидата наук[41], [68],[65], 2 статьи в зарубежных научных журналах на английском языке [96], [97] итезисы 2 докладов [66],[67].

В статьях [41], [68] диссертанту принадлежитпостроение алгоритмов решения задач логико-предметного распознаванияобразов,основанныхасимптотическихнаоценокобратномэтихметодеалгоритмов.ВМасловастатьеи[65]нахождениедиссертантомпредложено применение построенных ранее алгоритмов для решения задачинахождения наибольшей общей с точностью до имѐн аргументов подформулыдвух элементарных конъюнкций атомарных формул.Личный вклад автора. Результаты, представленные в диссертационнойработе,полученысоискателемлибосамостоятельно,либоприегонепосредственном участии.Положения, выносимые на защиту1. Построен алгоритм IMA поиска вывода формул, к доказательствукоторых сводятся многие задачи Искусственного Интеллекта, основанный натактиках обратного метода Маслова.

Получены асимптотические оценки числашагов работы этого алгоритма.2. Построен алгоритм IAPTA поиска вывода формул, к доказательствукоторых сводятся многие задачи Искусственного Интеллекта, основанный натактиках обратного метода Маслова, а также тактиках муравьиных алгоритмов сиспользованием идей параллельных вычислений. Получены асимптотическиеоценки числа шагов работы этого алгоритма.103.

Построен алгоритм PHIAPTA поиска наибольшей общей подформулы,основанный на алгоритме IAPTA. Получены асимптотические оценки числашагов работы этого алгоритма.Структура и объем диссертацииРабота состоит из введения, четырех глав, разбитых на разделы подразделы,заключения, списка литературы и трех приложений. Общий объем рукописисоставляет 157 страниц текста, включая88 страниц непосредственно текстадиссертациии69страницприложений.Текстсодержит21рисунок.Библиографический список включает105 наименований.Содержание работыВовведенииобосновываетсяактуальностьтемыисследования,формулируется цель работы, дается обзор литературы по изучаемой проблеме,приводится краткое содержание работы по главам.В первой главе приведен обзор современного состояния предметнойобласти по рассматриваемой в диссертации теме.

В разделе 1.1 рассматриваетсяпостановка задач Искусственного Интеллекта при логико-предметном подходе. Вразделе 1.2 приведена формулировка обратного метода С.Ю. Маслова длярешения задач логико-предметного распознавания образов. В разделах 1.3-1.6даны обзоры тем алгоритмов муравья, параллельных вычислений и неполнойвыводимости предикатных формул соответственно.Во второй главе обратный метод Маслова адаптирован для решения задачлогико-предметного распознавания образов, построен алгоритм IMA решениятаких задач на основе обратного метода, получены асимптотические оценки этогоалгоритма.В разделе 2.1 разработано применение обратного метода для доказательствавыводимости формул вида  x1,..., xn  & Di a1,..., ak , x1,..., xn i  1 .(1)11Эта формула является частным случаем формул, для которых разработан S a1,..., ak обратный метод Маслова.

В (1) дизъюнкты Di a1,..., ak , x1,..., xn имеют видDi    S a1,..., ak  Pk x1,..., xn  ,iгде– обозначение длядизъюнкции отрицаний атомарных формул, входящих всписок постоянныхатомарных формул S a1,..., ak , а Pk – предикатный символ.iОпределение 1. Любой список Г формул вида Di a1,..., ak , с1,..., сnявляетсяF-набором для формул вида (1), если формулы в этом списке неповторяются.Определение 2. Пусть1,...,l –список констант из спискаa1,..., ak .1,..., l – список переменных и констант из списка a1,..., ak .

Рассмотримсистему равенств:1  1   l l(2)Пусть u1,..., u p – список без повторений всех переменных, входящих вравенства системы (2). Систему (2) будем называть системой уравнений впеременных u1,..., u p .Решением системы уравнений (2) будем называть всякийнабор значенийконстант 1,...,  p из спискаa1,..., akтакой, что в результатеодновременной замены всех переменных u1,..., u p на константы1,...,  pсоответственно левые и правые части каждого равенства системы совпадут.Система уравнений (2) не имеет решений, если в списке1,...,  pестьповторения, или если в системе уравнений (2) приходится сравниватьразные константы.12Определение 3. F-набор называется пустым □, если все формулы,входящие в него, не имеют переменных и тавтологичны.Определение 4.F-набор называется тупиковым, если в него входит хотябы одна формула, не имеющая переменных и являющаяся ложной или неявляющаяся ни тавтологией, ни противоречием.В разделе 2.2 сформулирован алгоритм IMA (InverseMethodAlgorithm),использующий тактику обратного метода.Алгоритм IMA (inverse method algorithm)1.

Строим δ-членный F-набор, формулы в котором не повторяются. То естьв формуле (1) удаляем все знаки конъюнкций и составляем список элементарныхдизъюнкций вида  S a1,..., ak  Pk  x1,..., xn  .ii2. Присваиваем значения переменным следующим образом:2.1. Отменяем все пометки об удалениях предикатных формул из(если они были).S  2.2. Берем формулу  S a1,..., ak  Pk t1,..., tm из рассматриваемого Fiнабора, содержащую m-местный предикатный символ такой, что набор t1 ,...,t mсодержит хотя бы одну переменную.2.3.

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

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