Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА)
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
±последовательности (удовлетворяющего выражению (2.2)). Найденная маска помещается в переменную Mask.
В блоке 4 вызывается подпрограмма GetByMask, которой в качестве входных параметров передаются М и Mask. Данная подпрограмма отыскивает все векторы в М, отвечающие заданной маске, и сохраняет их в список List4.
В блоке 5 используется свойство Count переменной List4. Оно содержит количество векторов, которое содержит список. Если List4. Count = 0, т.е. не найдено ни одного вектора, то на этом нахождение текущей субпоследовательности завершается. Найденная субпоследовательность, которая содержится в List3, присоединяется к списку Lst2 (блок 8). В этом же блоке происходит освобождение памяти, занимаемой объектами List3 и List4.
Если же в результате выполнения блока 4 был найден хотя бы один вектор, то нахождение субпоследовательности продолжается в цикле. Подпрограмма SelectVector, вызываемая в блоке 6, позволяет выбрать наиболее подходящий из возможных векторов (из List4), и сохраняет его в переменной V, после чего V присоединяется к List3 (блок 7). В этом же блоке все неиспользованные векторы возвращаются в исходный список М. Далее выполняется следующая итерация цикла.
Далее рассмотрим алгоритм функционирования подпрограммы GetMask. Исходными данными для работы является List - это список, который передается в подпрограмму из вызвавшей программы, на его основе строится маска. Результат работы подпрограммы возвращается через переменную Result. Строковые переменные Subl и Sub2 используются для выделения и сравнения частей векторов. На i-м шаге внешнего цикла Subl содержит подстроку, состоящую из трех элементов последнего вектора из списка List, стоящих в позициях i-1, i, i+l Sub2 содержит те же три элемента j-гo вектора:
Subl = List [List. Count-ll [i-1] + List [List. Count-1] [i] + List [List. Count - l] [i+l];= List [j] [i-1] + List [j] [i] + List [j] [i+1],
где '+' обозначает конкатенацию строк.
Если в подпрограмму передан пустой список, это вызовет ошибку, для исключения такой ситуации выполняется проверка, если возникла ошибочная ситуация, подпрограмма посылает 'сообщение об ошибке' вызвавшей программе и завершает работу. Символ '*' в маске означает незафиксированный разряд, т.е. при проверке соответствия вектора маске (в подпрограмме GetByMask) такой разряд не сравнивается.
На рис.4.4 приведена блок-схема подпрограммы GetByMask, которая по заданной маске Mask, извлекает векторы из списка L1 и добавляет эти векторы в список L2, который и является результатом ее выполнения. Переменная j - это счетчик строк, a i - позиций (разрядов). При достижении j значения, соответствующего количеству строк в L1, подпрограмма завершается (блок 4). При достижении значения i>n (т.е. пройдена вся строка), текущий вектор заносится в список L2, происходит переход к следующему вектору и переустановка i. Соответствие вектора маске проверяется в блоке 6 поразрядно, при первом несоответствии происходит переход к следующему вектору и переустановка i (блоки 9 и 8 соответственно).
Подпрограмма SelectVector, блок-схема алгоритма которой приведена на рис.4.5, необходима для того, чтобы выбрать наиболее подходящий из всех векторов, которые могут быть присоединены к субпоследовательности на данном шаге. Переменные LI, L2 - списки, содержащие строящуюся субпоследовательность и векторы, которые могут быть присоединены к ней на данном шаге соответственно; переменная V содержит выбранный вектор после завершения работы подпрограммы. Переменная i - счетчик строк, j - содержит значение номера выбранного вектора в L2. Здесь также используется функция GetFreeColCount, которая подсчитывает количество символов '*' в аргументе.
4.2.3 Результаты работы основного алгоритма
Исходными данными для работы алгоритма являлась тестовая последовательность, которая в результате выполнения программы должна быть преобразована в несколько субпоследовательностей, в совокупности перекрывающие исходную. Исходные данные:
T = {11111111; 10100101; 01110000; 00111110; 01011100; 00000110; 00011001; 11100011; 11010010; 10001101; 11110000; 00001111; 00010000; 00001101; 11111010; 00101111}.
В результате работы алгоритма получены следующие субпоследовательности:
S1S2S3S411111010 10100101 01011100 00001111 01110000 00101111 0001000000010000 11111111 10001101 00000110 11010010 11111110 1000111010001110 00011001 11100011 11110000 11111111 11111010 1111011111110111 00111110 00001101 01111111 11101110 00111101 00001111
4.2.4 Правила настроек КА
Этот этап связан с отысканием правил функционирования клеточных автоматов генерирующей сети по известной субпоследовательности. Номера правил вычисляются для каждой ячейки СКА по ее диаграмме состояний.
Используем следующие настройки СКА для генерации вышеуказанных субпоследовательностей.
S1 - 4, 33, 128, 50, 146, 101, 17, 17
S2 - 9, 65, 34, 5, 144, 195, 101, 65
S3 - 9, 129, 193, 212, 152, 33, 135, 21
S4 - 2, 9, 193, 66, 168, 200, 160, 20
5. Программа моделирования ска на языке Delphi
5.1 Исходные требования к программе моделирования
Исходными данными для работы программы являются:
.Количество сегментов сети клеточных автоматов n.
2.Начальные значения каждой клетки.
.Количество шагов эволюции клеточного автомата k.
.Правило функционирования для каждой клетки, заданное в виде минимальной дизъюнктивной нормальной форм
Результатом работы программы должны быть значения каждого КА на каждом шаге эволюции в следующем виде:
Программа должна работать в среде Windows 98/Me/2000/XP и иметь визуализированный интерактивный интерфейс.
5.2 Алгоритм реализации программы
На рисунке 5.1 изображена блок-схема основного алг