Диссертация (1150569)
Текст из файла
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ МОРСКОЙ ТЕХНИЧЕСКИЙУНИВЕРСИТЕТНа правах рукописиПетуховаНина ДмитриевнаРАЗРАБОТКА И ОЦЕНКА ЧИСЛА ШАГОВ РАБОТЫ АЛГОРИТМОВРЕШЕНИЯ ЗАДАЧ ЛОГИКО-ПРЕДМЕТНОГО РАСПОЗНАВАНИЯ ОБРАЗОВ СИСПОЛЬЗОВАНИЕМ ТАКТИК ОБРАТНОГО МЕТОДА МАСЛОВА05.13.17 – Теоретические основы информатикидиссертация на соискание ученой степеникандидата физико-математических наукНаучный руководитель – докторфизико-математическихнаук,доцент, КОСОВСКАЯ ТатьянаМатвеевнаСанкт-Петербург20162ОглавлениеВВЕДЕНИЕ ...................................................................................................................... 4Степень достоверности и апробация результатов ................................................
8Публикации результатов ......................................................................................... 9Положения, выносимые на защиту ........................................................................ 9Структура и объем диссертации ........................................................................... 10Содержание работы ................................................................................................ 10ГЛАВА 1. ОБЗОР СОВРЕМЕННОГО СОСТОЯНИЯ ПРЕДМЕТНОЙ ОБЛАСТИ......................................................................................................................................... 231.1.
Постановка задач Искусственного Интеллекта при логико-предметномподходе........................................................................................................................ 231.2. Обратный метод С.Ю. Маслова для решения задач логико-предметногораспознавания образов ..............................................................................................
27Общая схема обратного метода ............................................................................ 281.3. Алгоритмы Муравья ........................................................................................... 361.4. Параллельные вычисления ................................................................................ 381.5. Совместное применение идей муравьиных алгоритмов и параллельныхвычислений ................................................................................................................. 401.6.
Понятие неполной выводимости предикатных формул ................................. 41ГЛАВА 2. АДАПТАЦИЯ ОБРАТНОГО МЕТОДА МАСЛОВА РЕШЕНИЯЗАДАЧ ЛОГИКО-ПРЕДМЕТНОГО РАСПОЗНАВАНИЯ ОБРАЗОВ .................... 422.1. Формулировка обратного метода для решения задач логико-предметногораспознавания образов .............................................................................................. 422.2. Алгоритм IMA (InverseMethodAlgorithm), использующий тактику обратногометода ..........................................................................................................................
47Алгоритм IMA (Inverse Method Algorithm).......................................................... 502.3. Оценка числа шагов работы алгоритма IMA ................................................... 53ГЛАВА 3. АЛГОРИТМ, ОСНОВАННЫЙ НА ПРИМЕНЕНИИ ОБРАТНОГОМЕТОДА, МУРАВЬИНЫХ ТАКТИК И ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ..... 583.1. Применение идей муравьиных алгоритмов и параллельных вычислений длярешения задач логико-предметного распознавания образов ................................ 58Алгоритм IAPTA .................................................................................................... 593.2. Оценка числа шагов работы алгоритма IAPTA ...............................................
63ГЛАВА 4. ВЫДЕЛЕНИЕ МАКСИМАЛЬНОЙ ОБЩЕЙ ПРЕДИКАТНОЙПОДФОРМУЛЫ С ПОМОЩЬЮ ОБРАТНОГО МЕТОДА МАСЛОВА ................ 694.1. Использование обратного метода для решения задачи выделениямаксимальной общей подформулы .......................................................................... 694.2.
Алгоритм PHIAPTA (PartialHatchabilityInverseAntParallelTacticAlgorithm)выделения максимальной общей подформулы ...................................................... 6934.3. Оценка числа шагов работы алгоритма PHIAPTA. ......................................... 74ЗАКЛЮЧЕНИЕ .............................................................................................................
78ЛИТЕРАТУРА ............................................................................................................... 80ПРИЛОЖЕНИЕ А. Пример решения задачи с помощью алгоритма IMA.............. 89ПРИЛОЖЕНИЕ B. Пример решения задачи с помощью алгоритма IAPTA ........ 100ПРИЛОЖЕНИЕ C. Пример решения задачи выделения наибольшей общейподформулы с помощью алгоритма PHIAPTA. ....................................................... 1114ВВЕДЕНИЕАктуальность темы исследования.Во многих задачах искусственногоинтеллекта исследуемый объект характеризуется не только своими глобальнымипризнаками, задающими его свойства как единого целого, но и свойствами егочастей и отношений между ними.
При распознавании контурного изображенияобъект может быть представлен как множество его вершин и вида соединенийэтих вершин[19], [72], [76], [78], [83], [93]. В задачах диагностики объект задаѐтсянабором своих составляющих, а также зависимостями между этими элементами,позволяющими объекту функционировать[1],[10], [11], [12], [31], [32], [63].Такой подход ещѐ в 70-ые годы XX века был сформулирован в литературе(см., например,[29], [60], [64], [70], [94]). Однако практического применения онпочти не получил в силу высокой вычислительной сложности возникающих приэтом задач, которые являются NP-трудными [2], [17], [90].При изучении алгоритмов одно из ключевых мест занимает анализ времениих работы[36], [50], [71],[89],[92].
Первым шагом является нахождениеасимптотических оценок: верхней и нижней границ работы алгоритмов [15], [23],[43], [44].В настоящее время для множества задач найдены только такие алгоритмы,которые перебирают экспоненциально зависящее от длины записи исходныхданных количество вариантов. Такие задачи, как правило, являются NP-трудными[24]. Ясно, что при больших размерах решаемых задач применение алгоритмов сэкспоненциальной оценкой иррационально, хотя для задач небольшого объемаэкспоненциальные решения могут оказаться лучше полиномиальных (например,при n≥100 экспоненциальная оценка 1.1n лучше, чем 10n3)[73].В данной работе построены и доказаны оценки числа шагов алгоритмоврешения задач логико-предметного распознавания образов, использующихтактики обратного метода, который был предложен в середине 60ых годовсоветским логиком С.Ю.
Масловым (1932 – 1983).5Обратный метод С.Ю. Маслова не является менее эффективным методомавтоматического доказательства теорем, чем, например, метод резолюций [26],[33], [35],[52]. При практическом применении, как показано в диссертации, онявляется даже более эффективным, но не получил широкого распространения впрограммировании. Одной из причин этого является сложность реализацииобратного метода в оригинальном изложении С.Ю. Маслова[34].В диссертации предложена конкретизация обратного метода для частногослучая формул исчисления предикатов, к которым сводится доказательствонекоторых задач искусственного интеллекта.
А также разработаны алгоритмырешения задач логико-предметного распознавания образов, использующиетактики обратного метода Маслова, и доказаны оценки числа их шагов.Эффективностьэтихалгоритмовпроиллюстрировананапримерах.Представленные алгоритмы пригодны для программной реализации.Степень разработанности темы исследования. Термин «обратный метод»впервые введен С.Ю. Масловым в 1964 году в работе [55].
В этой работе авторомбыл разработан метод установления выводимости для формул классическогоисчисления предикатов без равенства и функциональных символов.Интерес к обратному методу установления выводимости появился в связи ссерией работ С.Ю. Маслова и группы математической логики ЛОМИ АН СССР:[25], [52], [53], [54], [56], [57] и [58].В 1973 году Н. Нильсон написал книгу, посвященную методам поискарешений в пространстве состояний[60]. В 1976 году Р.
Дуда и П. Харт изложили исистематизировалиметодыраспознаванияобразовидалианализпространственных сцен по их плоскому изображению [28]. В 1981 году Г.Е.Минц, назвав обратный метод «резолютивными исчислениями», применил его кнеклассическим пропозициональным логическим исчислениям. В 1982 году М.Гэри и Д. Джонсон написали книгу, посвященную вопросам сложности решениязадач [24].В работе [59] обратный метод, хоть и названный «резолютивнымиисчислениями» впервые применяется к неклассическим пропозициональнымлогическимисчислениям.В[18]обратныйметодрассматриваетсядля6классической логики без равенства на основе обратного исчисления свободныхпеременных. В 1989 году выходит работа В. Лифшица в которой представленыосновные идеи обратного метода в форме, подчеркивающей его связь с методомрезолюций [99].
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
