Минимальный проверяющий тест
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Министерство образования и науки Российской Федерации
Государственное образовательное учреждение
высшего профессионального образования
САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМЕНИ Н.Г. ЧЕРНЫШЕВСКОГО
Кафедра теоретических основ компьютерной безопасности и криптографии
КУРСОВАЯ РАБОТА
Минимальный проверяющий тест
Студента 3 курса
Кияйкина Александра Евгеньевича
Саратов 2012
Содержание
Введение
. Основные понятия и определения
. Теорема
. Алгоритм построения минимального проверяющего теста
Заключение
Список используемых источников
Приложение
Введение
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 году. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно ее приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались для построения схем электрических цепей и молекулярных схем. В настоящее время данная теория служит естественным аппаратом в некоторых главах чистой математики, а также находит многочисленные применения в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задачах о потоках в сети нефтепроводов и многих других.
В данной работе будет рассмотрено понятие проверяющего теста для некоторой системы. Будет приведен критерий минимальности проверяющего теста и его доказательство. Необходимые термины будут описаны в соответствующем разделе.
Особое место в работе занимает алгоритм построения минимального проверяющего теста. Для этого написана программа, реализующая данный алгоритм, а также будет рассмотрен пример его применения.
1. Основные понятия и определения
Под ориентированным графом (или, для краткости, орграфом) понимается пара
,
где -конечное непустое множество (вершины орграфа), а -отношение на множестве .
Параназывают дугой орграфа с началоми концом.
Отношение называют отношением смежности, а соответствующую ему двоичную булеву матрицу - матрицей смежности орграфа .
Пусть - некоторый орграф. Маршрутом в этом орграфе называется последовательность дуг
,
в которой для всех . Говорят, что маршрут проходит через вершины . Вершина называется его начальной вершиной, а - конечной.
Циклический маршрут в орграфе - это маршрут, в котором начальная и конечная вершины совпадают.
Маршрут, в котором никакая дуга не встречается более одного раза, называется путем.
Путь, каждая вершина которого принадлежит не более чем двум его дугам, является простым.
Простой циклический путь называют контуром, а простой путь, не являющийся контуром, - бесконтурным путем или (ориентированной) цепью.
Длиной маршрута называется количество составляющие его дуг.
Говорят, что вершина достижима из вершины , если в орграфе существует путь изв. Расстояниеот до - это длина кратчайшего пути из вершины в вершину . Отношение достижимости обозначают .
Матрица
является матрицей отношения достижимости в орграфе , имеющем матрицу смежности . Матрица называется матрицей достижимости орграфа .
Симметричная часть отношения достижимости называется отношением взаимной достижимости. Классы отношения взаимной достижимости называют сильными компонентами (или слоями) орграфа.
Орграф, по определению, является сильно связным, если отношение универсально на нем, т. е. если каждая его вершина достижима из любой другой.
Пусть даны орграфи отношение эквивалентности на множестве его вершин .
Факторграфом орграфа по эквивалентности называется орграф , вершинами которого являются классы эквивалентности . При этом из вершины проводится дуга в, если существует вершина из класса и из класса , такие, что .
Вершина орграфа, не достижимая из других его вершин, называется источником, а вершина, из которой не достижима никакая другая вершина - стоком.
Пусть орграф является функциональной моделью некоторой системы , допускающей одиночный отказ. Для обнаружения отказа производится проверка элементов системы, имеющая для каждого элемента два исхода: 0, если реакция элемента допустима, 1 в противном случае. Предположим, что система такова, что реакция 1, отмеченная у некоторого элемента, наследуется всеми достижимыми из него (в смысле орграфа ) элементами. Под проверяющим тестом понимается некоторая совокупность проверок элементов системы, позволяющая выяснить, имеется ли в системе отказ (без его локализации).
. Теорема
Проверяющий тест для системы минимален тогда и только тогда, когда он состоит из проверок элементов, которые соответствуют вершинам орграфа , взятым по одной из каждого стока факторграфа .
Доказательство
Пусть тест не содержит проверки ни одного представителя стокафакторграфа . Тогда отказ любого элемента, представленного вершиной, входящей в класс , не распознается данным тестом, и, значит, тест не является проверяющим. Таким образом, любой проверяющий тест содержит проверки представителей всех ст?/p>