Алгоритмы интеллектуальной обработки информации и структурного синтеза программ

• Автор: Пинжин, Алексей Евгеньевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Томск
• Количество страниц: 114 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

1. ФОРМАЛЬНАЯ ТЕОРИЯ.

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

1.2. Нерекурсивные и рекурсивные детерминированные Смодели.

1.3. Постановка задачи

Выводы к главе 1.

2. АЛГОРИТМЫ ПЛАНИРОВАНИЯ И СИНТЕЗА ПРОГРАММ.

2.1. Проблема эффективности и общие принципы построения машины вывода для

устойчивых баз знаний

2.2. Планирование и синтез в классе НДСмоделей

2.2.1. Правила вывода
2.2.2. Трансформация вариантной части
2.2.3. Компиляция НДСмодели.
2.2.4. Постановка задали и схемы алгоритмов вывода.
2.2.5. Извлечение программы из доказательства
2.3. Планирование и синтез в классе РДСмоделей
2.3.1. Формальная модель доказательства
2.3.2. Подготовка данных и алгоритм вывода на РДСмодели.
2.4. Программная реализация
Выводы к главе 2.
3. ОЦЕНКА ЭФФЕКТИВНОСТИ
3.1. Расчет вычислительных затрат на осуществление вывода в классе Смоделей.
3.2. Получение вида зависимости вычислительных затрат от объема спецификации РДС модели
3.3. Экспериментальные результаты
Выводы к главе 3.
4. ИНТЕРПРЕТАЦИЯ СМОДЕЛИ ДЛЯ РЯДА ЛОГИЧЕСКИХ ИСЧИСЛЕНИЙ.
4.1. Трансформация спецификаций языка Пролог в конструкции теории Смоделей
4.2. Упрощенный метод интерпретации для ряда логических исчислений.
4.3. Реализация методов преобразования и экспериментальные результаты
Выводы к главе 4.
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРНЫХ ИСТОЧНИКОВ


Следует также отметить, что большинство современных алгоритмов логического вывода ориентированы на «оперативную» обработку базы знаний, исходя из предположения, что содержимое базы знаний постоянно меняется. В то же время существует ряд предметных областей, где база знаний меняется достаточно редко, что позволяет получить дополнительный прирост производительности при осуществлении логического вывода и синтеза путем использования внешней памяти. Предлагаемый в работе подход специальной подготовки базы знаний предназначен для применения на устойчивых моделях и показывает значительный прирост скорости вывода по сравнению с существующими аналогами. Отметим, что возможность динамического внесения изменений в подготовленные структуры данных не исключается, однако не входит в рамки настоящего диссертационного исследования. Цель работы и задачи исследования. Формальное определение элементов модели исходных данных и формулировка задачи логического вывода и синтеза программ на базе теории структурных функциональных моделей. Определение общих принципов, требований и архитектуры машины вывода. Формулировка правил вывода и разработка структур данных компиляции исходной спецификации с целью снижения вычислительных затрат при выполнении задачи планирования. Разработка и программная реализация алгоритмов планирования и синтеза. Расчет вычислительных затрат и экспериментальная оценка скорости разработанного алгоритма с использованием тестовых выборок данных. Адаптация разработанной машины вывода для решения задач, выраженных в языках ряда логических исчислений: логики высказываний, логики первого порядка, дескриптивной логики. Предметом исследования являются вычислительные модели и алгоритмы логического вывода и синтеза программ. Методы исследований. В работе использованы элементы теории структурных функциональных моделей, теории множеств, логики высказываний, первого порядка и дескриптивной логики, методы структурного программирования. На базе теории структурных функциональных моделей разработаны алгоритмы логического вывода и синтеза программ, обладающие высокими показателями скорости вычислений за счет представления исходной спецификации в виде специальных структур данных и использования метода динамической развертки, позволяющего сократить пространство вывода при помощи организации стека подпрограмм и рекурсивного планирования на иерархии подсхем. На основании анализа элементов спецификации языка Пролог и сопоставления их с конструкциями теории структурных функциональных моделей введены новые формальные правила и ограничения трансформации задач вывода на логике первого порядка в задачи планирования на структурных функциональных моделях. Произведена адаптация разработанной машины вывода для ряда задач, выраженных в языках традиционных логических исчислений (логики высказываний, логики первого порядка и дескриптивной логики) и экспериментально подтверждена более высокая скорость вычислений по сравнению с существующими аналогами. Практическая ценность и реализация результатов работы. Предлагаемые структуры данных и алгоритмы планирования реализованы в виде прикладного программного пакета. Предлагаемый подход хорошо масштабируется и особенно эффективен при обработке баз знаний большого объема. Предложенные модели данных компиляции и алгоритмы вывода были внедрены в ООО «ФлексСофт» при разработке медицинской информационной системы для обработки экспертной базы знаний ЕхрепОос. Применение предлагаемых подходов позволило многократно повысить скорость поиска противопоказаний лекарственных препаратов и реализовать дополнительные возможности трассировки найденного решения. Результаты работы также были использованы в проекте построения единой информационной среды Томского политехнического университета для решения задачи определения прав доступа пользователей (сотрудников университета) к информации о студентах. Применение предложенной стратегии вывода позволило реализовать эффективный алгоритм вычисления путем обхода дерева решений. Предложенный подход логического вывода и синтеза программ используется в учебном курсе теории языков программирования и методов трансляции, который преподается студентам Томского политехнического университета.