Методы и инструментальные средства программирования в булевых ограничениях

• Автор: Богданова, Вера Геннадьевна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Иркутск
• Количество страниц: 138 с. : ил.

Содержание
ВВЕДЕНИЕ
ГЛАВА 1. МЕТОДЫ И ПРОГРАММНЫЕ СРЕДСТВА РЕШЕНИЯ ЗАДАЧ УДОВЛЕТВОРЕНИЯ ОГРАНИЧЕНИЙ С КОНЕЧНЫМИ ОБЛАСТЯМИ ЗНАЧЕНИЙ ПЕРЕМЕННЫХ ОБЗОР

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

1.2. Классификация задач удовлетворения ограничений с конечными

ОБЛАСТЯМИ И АЛГОРИТМОВ ИХ РЕШЕНИЯ.

1.3. Оценка эффективности алгоритмов

1.4. Инструментальные средства автоматизации программирования в

БУЛЕВЫХ ОГРАНИЧЕНИЯХ

ГЛАВА 2. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ВЫПОЛНИМОСТИ БУЛЕВЫХ ОГРАНИЧЕНИЙ

2.1. Базовый алгоритм.зз

2.2. Усовершенствованный алгоритм.зз
2.3. Гибридный алгоритм.
2.4. Сравнительный анализ разработанных алгоритмов
ГЛАВА 3. АВТОМАТИЗАЦИЯ ПОСТРОЕНИЯ БУЛЕВЫХ МОДЕЛЕЙ ДИСКРЕТНЫХ ЗАДАЧ
3.1. Средства спецификации булевых ограничений в международном
ФОРМАТЕ I И ЕГО РАСШИРЕНИЯХ
3.2. Булевы модели некоторых дискретных задач.
3.3. Технология булева моделирования дискретных задач.
3.4. Высокоуровневые языковые средства задания булевых
ОГРАНИЧЕНИЙ в ИНСТРУМЕНТАЛЬНОМ КОМПЛЕКСЕ РЕБУС
ГЛАВА 4. ИНТЕГРИРОВАННАЯ ИНСТРУМЕНТАЛЬНАЯ ВИЗУАЛЬНАЯ СРЕДА РЕБУС ДЛЯ АВТОМАТИЗАЦИИ ПРОГРАММИРОВАНИЯ И РЕШЕНИЯ ЗАДАЧ В БУЛЕВЫХ ОГРАНИЧЕНИЯХ
4.1. Постановка задачи и основные функциональные требования к
ИНСТРУМЕНТАЛЬНОМУ КОМПЛЕКСУ РЕБУС.
4.2. Концептуальная модель, принципы организации и архитектура
ИНСТРУМЕНТАЛЬНОГО КОМПЛЕКСА РЕБУС.
4.3. Архитектура и функциональные возможности подсистем
ИНСТРУМЕНТАЛЬНОГО КОМПЛЕКСА РЕБУС.
4.4. Визуальный пользовательский интерфейс и основные аспекты
ПРОГРАММНОЙ РЕАЛИЗАЦИИ ИК РЕБУС.
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Основная цель диссертации состоит в исследовании существующих на данный момент достижений в области решения систем булевых ограничений; разработка специализированных алгоритмов и программ для решения булевых уравнений; создании принципиально новой интегрированной инструментальной среды, объединяющей решатели комбинаторных задач большой размерности в единую систему, позволяющую автоматизировать процесс построения булевой модели решаемой дискретной задачи, выбирать из базы знаний (исходя из свойств полученной модели и накопленной статистики решения задач) подходящий алгоритм решения, проводить вычислительный эксперимент, сохранять результаты расчетов в пользовательской базе данных, осуществлять тестирование алгоритмов с использованием эталонных тестовых задач и тестов из библиотеки БАТЫВ [], включать в базу знаний инструментальной среды новые модели и алгоритмы. Методы исследования. При решении поставленных задач использовались методы системного и прикладного программирования, характерные для разработки инструментальных программных комплексов; методы объектно-ориентированного проектирования и разработки баз знаний и данных; комбинаторные методы дискретной математики и искусственного интеллекта. Научная новизна. Разработаны и реализованы новые алгоритмы решения булевых уравнений, показавшие на некоторых тестовых задачах сравнительно высокую эффективность. Эти алгоритмы ориентированы как на произвольное представление левой части уравнения, так и на традиционное представление в дизъюнктивной или конъюнктивной нормальной форме (формат МАСБ). С использованием технологии баз знаний разработана архитектура, языковые средства, алгоритмическое, информационное и программное обеспечение инструментального комплекса (ИК) РЕБУС, обеспечивающего автоматизацию всех этапов программирования в булевых ограничениях. С помощью базовой технологии моделирования ИК РЕБУС получены булевы модели для решения ряда классических дискретных задач (задача об п-ферзях, раскраска графа, покрытие конечного множества системой его подмножеств, ход шахматного коня, задача о голубях и клетках), а так же булевы модели для решения двух практических задач (равномерная загрузка локомотивного депо железной дороги, оперативный план отправления локомотивных бригад). Практическая значимость. Применение разработанных в диссертации методов и инструментальных средств автоматизации программирования в булевых ограничениях позволяет сократить трудозатраты на разработку, отладку и исследование булевых моделей, повышает качество и сокращает сроки выполнения необходимых многовариантных расчетов. Решатели ИК РЕБУС зарегистрированы в Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ) и используются для проведения экспериментальных расчетов по плановым темам НИР в ИДСТУ СО РАН. Применение ИК РЕБУС в учебных целях в качестве программного инструмента решения задач дискретной математики позволяет обучить студентов основным навыкам булева моделирования, наглядно ознакомить их с существующими комбинаторными методами решения классических задач искусственного интеллекта. Реализация. Исследование, разработка и применение рассматриваемых в диссертации программных средств выполнялись в рамках плановых тем ИДСТУ СО РАН “Методы автоматизации исследования и разработки интеллектных систем” (№ гос. Методы и инструментальные средства организации распределенных вычислений в сети Интернет” (№ гос. Интегрированные информационно-вычислительные и коммуникационные ресурсы: интеллектные методы организации, автоматизации разработки и применения” (- гг. СО РАН “Методы, технологии и инструментальные средства создания вычислительной инфраструктуры в Internet” (- гг. РФФИ №0 ’’Численное решение больших разреженных систем булевых уравнений”, №0 “Разработка инструментальной среды для создания и поддержки функционирования распределенных пакетов знаний в сети Интернет” и №8 “Разработка и реализация распределенной вычислительной системы решения булевых уравнений большой размерности”, в процессе реализации программы президиума РАН № “Разработка фундаментальных основ создания научной распределенной информационно-вычислительной среды на основе технологий GRID” (проект №6 “Планирование и оптимизация схем решения задач в распределенной мультиагентной вычислительной среде ”). Результаты исследований используются в Иркутском государственном университете путей сообщения при проведении практических занятий по дисциплине «Теория дискретных устройств автоматики и телемеханики», а так же в Информационно-вычислительном центре Восточно-Сибирской железной дороги филиала ОАО РЖД для разработки системы поддержки принятия решений при решении задач составления плана ремонта электропоездов и оперативного плана отправления локомотивных бригад в условиях отсутствия жесткого расписания движения грузовых поездов.