Курсовая работа: Алгоритмы поиска кратчайших покрытий булевых матриц

Написанная мной на ЭВМ программа «Нахождение кратчайшего покрытия булевых матриц» помогает вручную не искать покрытие заданной или генерируемой булевой матрицы до размера 99 х 99, а предоставить это компьютеру.

5.1 Описание программы

Средство программирования:

Интегрированная Среда Разработки BorlandC++ Builder 6.0.

Поддерживаемые операционные системы:

Windows 95/98/ME/NT/2000/XP.

Система для тестирования программы:

Pentium-4 ~2.3 Gh, 512 MbDDR, WindowsXPSP2.

5.2 Описание интерфейса

Pokrytie.exe – откомпилированная и отлаженная программа. При запуске отображается окно дополнительной информации:

При нажатии двойным щелчком на кнопку «Программа» в окне появляется основная форма — Меню программы (рис. 1).

Рис.1. Меню программы Рис.2. Задание вероятности единицы

Требуется ввести число строк и столбцов матрицы, а также выбрать тип создания требуемой матрицы: вручную или автоматически (с помощью компьютера). В первом случае возможны 2 способа создания пустого шаблона матрицы: все поля – либо нули, либо единицы (для реализации необходимо это просто отметить). Во втором же должна быть введена вероятность создания единицы в определенном месте матрицы (рис. 2).

По умолчанию все элементы матрицы – нули и программа допускает присутствие в матрице нулевых строк и столбцов. Если вы не ввели параметры матрицы до конца, то при нажатии кнопки «Сгенерировать» программа сообщит вам об этом:

При правильном вводе данных и нажатии кнопки генерации на экране появляется окно ввода матрицы:

При написании программы я применила графический способ ввода элементов матрицы: внутри прямоугольника, соответствующего размерам матрицы, чтобы изменить значение определенного элемента матрицы, необходимо нажать кнопку мыши при положении курсора внутри определенного квадрата, соответствующего этому элементу. Белый цвет соответствует нулю, а цвет выделяемого текста (по умолчанию – синий) соответствует единице. Для хранения данных в программе использованы динамические матрицы, что позволяет выделять память только по мере необходимости.

5.3 Результат работы программы

Рассмотрим несколько примеров, иллюстрирующих работу программы.

5.3.1 Пример 1. Пусть дана матрица С:

1 2 3 4 5 6

.

Построим для этой матрицы кратчайшие покрытия методами Патрика и Закревского (строчное и столбцовое).

Матрица C в программе:

Покрытие методом Патрика: