АННОТАЦИЯ 3
ВВЕДЕНИЕ 7
1 Задача о нахождении кратчайшего покрытия булевой матрицы 10
1.1 Неформальная постановка задачи 10
1.2 Математическая модель и постановка задачи 11
2 Обзор подходов к решению задачи о покрытии булевой матрицы 13
2.1 Приближенные методы решения задачи 13
2.1.1 Жадный алгоритм 14
2.1.2 Минимаксный алгоритм 15
2.2 Точные методы нахождения кратчайшего покрытия 17
2.2.1 Метод Патрика 17
2.2.2 Методы линейного программирования 18
2.2.3 Методы, связанные с обходом деревьев поиска 19
2.2.3.1 Т-задача как модель для решения задач кратчайшего покрытия
булевой матрицы 23
2.2.3.2 Параметры метода сокращённого обхода дерева поиска для
нахождения кратчайшего покрытия булевой матрицы 24
2.2.3.3 Алгоритм сокращенного обхода дерева поиска 24
2.2.3.4 Пример решения задачи методом сокращённого обхода дерева
поиска 25
3 Программная реализация алгоритма для поиска кратчайшего покрытия булевой
матрицы 27
3.1 Реализация алгоритма «PriKraPok_М» для поиска кратчайшего покрытия
булевой матрицы 33
3.2 Реализация метода сокращенного обхода дерева поиска 43
3.3 Пример решения задачи разработанным алгоритмом 52
3.4 Разработка и программная реализация интерфейса для ввода булевой
матрицы 54
ЗАКЛЮЧЕНИЕ 59
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 61
ПРИЛОЖЕНИЕ А Программная реализация интерфейса ввода булевой матрицы 62
ПРИЛОЖЕНИЕ Б Генерация случайных булевых матриц 64
ПРИЛОЖЕНИЕ В Вспомогательные подпрограммы для измерения времени работы алгоритмов, вычисления средних значений и записи результатов в файл 66
Актуальность работы. Развитие схемотехники в микроэлектронике происходит стремительно и эффективно, однако с ростом сложности разрабатываемых устройств возрастает и уровень сложности задач проектирования, решаемых в данной области науки и техники. Решение многих задач проектирования, связанных с конструированием устройств, анализом, диагностикой, оптимизацией логических схем сталкиваются с необходимостью решения задач кратчайшего покрытия булевой матрицы, которые являются подходящей моделью для оптимальной реализации отдельных этапов рассматриваемых задач. Ряд характеристик проектируемых устройств, логических схем в интегральном исполнении зависит от эффективности решения задач, сводимых к задаче поиска кратчайших покрытий. Среди таких задач можно отметить минимизацию числа элементов схем (транзисторов), контролепригодность, ряд оптимизационных задач конструкторского проектирования.
Алгоритмы нахождения кратчайших покрытий практической сложности оказываются во многих случаях сложными и даже нереализуемыми в силу чисто вычислительных трудностей переборного характера, поэтому разработка алгоритмов, сокращающих перебор и позволяющих решать практические задачи представляется актуальным.
В сфере информационной безопасности к задаче поиска кратчайшего покрытия булевой матрицы сводится ряд задач оптимизации управления доступом, распределения памяти, анализа угроз и обеспечения безопасности информационных систем. Например, в контексте управления правами доступа, обнаружения угроз, мониторинга сетевого трафика и анализа уязвимостей. Анализ систем на предмет уязвимостей может быть смоделирован как задача покрытия множества. Например, определение минимального набора тестов или сканирований, которые необходимо выполнить для полного покрытия всех возможных уязвимых точек в системе.
Цель работы. Разработать алгоритм решения задачи о кратчайшем покрытии булевой матрицы методом сокращенного обхода дерева.
Задачи:
1. Сделать обзор подходов к решению задачи о покрытии булевой матрицы.
2. Выбрать наиболее приемлемый подход для разработки нового алгоритма.
3. Исследовать Т-задачу как модель для решения задач кратчайшего покрытия.
4. Реализовать приближенный алгоритм решения задачи о покрытии булевой матрицы.
5. Реализовать алгоритм сокращенного обхода дерева поиска для решения задачи кратчайшего покрытия булевой матрицы.
Научная новизна. Основная новизна данной работы заключается в применении метода сокращенного обхода дерева поиска, разработке его параметров для решения задачи поиска кратчайшего покрытия булевой матрицы и реализации соответствующего алгоритма, который обладает большей эффективностью и скоростью при нахождении точного решения рассматриваемой задачи.
Научно-практическое значение работы. Разработанный алгоритм может быть применен в различных областях при решении практических задач, сводимых к задаче о кратчайшем покрытии булевой матрицы. Применение данного алгоритма может повысить эффективность и точность решения таких задач как оптимизация логических схем, анализ данных, обработка изображений, размещение информации в памяти ограниченного объема и другие. Кроме того, разработанный алгоритм может найти свое применение в промышленности, в области автоматизации процессов, оптимизации производства и разработки новых технологий. Таким образом, результаты данной работы имеют практическую значимость и могут быть использованы в различных инженерных и научных областях.
В ходе выполнения магистерской дипломной работы был рассмотрен вопрос поиска кратчайшего покрытия булевой матрицы, который имеет широкое применение в различных областях, таких как комбинаторная оптимизация, теория графов, биоинформатика и другие. Целью работы было разработать и реализовать программное решение, основанное на методах точного и приближенного поиска, а также оценить их эффективность на различных булевых матрицах. Были изучены математические модели и постановка задачи поиска кратчайшего покрытия булевой матрицы. Был проведен обзор подходов к решению рассматриваемой задачи, рассмотрены минимаксный алгоритм, методы Патрика, линейного программирования и методы, связанные с обходом дерева поиска.
Был изучен метод сокращенного обхода дерева поиска и его применение для решения задачи покрытия. В работе описывается технология решения задачи поиска кратчайшего покрытия булевой матрицы методом сокращенного обхода дерева поиска. Предложены параметры метода сокращённого обхода дерева поиска для нахождения кратчайшего покрытия булевой матрицы, которые были продемонстрированы на примере. Пример показал, что алгоритм сокращенного обхода дерева поиска применим к нашей задаче.
Точный метод решения задачи поиска кратчайшего покрытия булевой матрицы, используемый в данной работе, применяет эвристические подходы и стратегии оптимизации для сокращения пространства поиска. Основная часть алгоритма представлена подпрограммой SOD, которая использует метод обхода дерева поиска с использованием функции нижней оценки. Алгоритм обхода основан на принципе выбора оптимальных ветвей дерева для дальнейшего исследования. Введенная нижняя оценка используется для принятия решения о дальнейшем рассмотрении текущего разбиения или пропуске некоторых ветвей дерева поиска. Это позволяет значительно сократить количество проверок. Точный метод, основанный на методе обхода дерева поиска с использованием эвристических подходов, показал более высокую точность решения задачи по сравнению с приближенным алгоритмом.
Дальнейшие исследования могут быть направлены на оптимизацию алгоритмов для улучшения их производительности, а также на разработку гибридных методов, объединяющих преимущества приближенных и точных подходов.
