Минимальный проверяющий тест

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ Н.Г. ЧЕРНЫШЕВСКОГО

Кафедра теоретических основ компьютерной безопасности и криптографии

КУРСОВАЯ РАБОТА

Минимальный проверяющий тест

Студента 3 курса

Кияйкина Александра Евгеньевича

Саратов 2012

Содержание

Введение

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

2. Теорема

3. Алгоритм построения минимального проверяющего теста

Заключение

Список используемых источников

Приложение

Введение

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 году. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно ее приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались для построения схем электрических цепей и молекулярных схем. В настоящее время данная теория служит естественным аппаратом в некоторых главах чистой математики, а также находит многочисленные применения в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задачах о потоках в сети нефтепроводов и многих других.

В данной работе будет рассмотрено понятие проверяющего теста для некоторой системы. Будет приведен критерий минимальности проверяющего теста и его доказательство. Необходимые термины будут описаны в соответствующем разделе.

Особое место в работе занимает алгоритм построения минимального проверяющего теста. Для этого написана программа, реализующая данный алгоритм, а также будет рассмотрен пример его применения.

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

Под ориентированным графом (или, для краткости, орграфом) понимается пара

,

где -конечное непустое множество (вершины орграфа), а -отношение на множестве .

Параназывают дугой орграфа с началоми концом.

Отношение называют отношением смежности, а соответствующую ему двоичную булеву матрицу - матрицей смежности орграфа .

Пусть - некоторый орграф. Маршрутом в этом орграфе называется последовательность дуг

,

в которой для всех . Говорят, что маршрут проходит через вершины . Вершина называется его начальной вершиной, а - конечной.

Циклический маршрут в орграфе - это маршрут, в котором начальная и конечная вершины совпадают.

Маршрут, в котором никакая дуга не встречается более одного раза, называется путем.

Путь, каждая вершина которого принадлежит не более чем двум его дугам, является простым.

Простой циклический путь называют контуром, а простой путь, не являющийся контуром, - бесконтурным путем или (ориентированной) цепью.

Длиной маршрута называется количество составляющие его дуг.

Говорят, что вершина достижима из вершины , если в орграфе существует путь изв. Расстояниеот до - это длина кратчайшего пути из вершины в вершину . Отношение достижимости обозначают .

Матрица

является матрицей отношения достижимости в орграфе , имеющем матрицу смежности . Матрица называется матрицей достижимости орграфа .

Симметричная часть отношения достижимости называется отношением взаимной достижимости. Классы отношения взаимной достижимости называют сильными компонентами (или слоями) орграфа.

Орграф, по определению, является сильно связным, если отношение универсально на нем, т. е. если каждая его вершина достижима из любой другой.

Пусть даны орграфи отношение эквивалентности на множестве его вершин .

Факторграфом орграфа по эквивалентности называется орграф , вершинами которого являются классы эквивалентности . При этом из вершины проводится дуга в, если существует вершина из класса и из класса , такие, что .

Вершина орграфа, не достижимая из других его вершин, называется источником, а вершина, из которой не достижима никакая другая вершина - стоком.

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

2. Теорема

Проверяющий тест для системы минимален тогда и только тогда, когда он состоит из проверок элементов, которые соответствуют вершинам орграфа , взятым по одной из каждого стока факторграфа .

Доказательство

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

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

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

3. Алгоритм построения минимального проверяющего теста

Опираясь на описанную выше теорему, можно предложить следующую схему построения минимального проверяющего теста.

По исходному графу построим факторграф .

Найдем все стоки данного факторграфа .

Все возможные минимальные проверяющие тесты данной системы будут состоять из проверок элементов, взятых по одному из каждого стока.

Рассмотрим данный алгоритм, реализованный на объектно-ориентированном языке программирования Java (см. приложение). Алгоритм реализует вышеописанную схему, входные параметры - количество вершин и матрица смежности графа. В результате его выполнения мы получаем все возможные варианты минимального проверяющего теста системы, представленной исходным графом.

Рассмотрим работу программы, выполняющую данный алгоритм. В качестве примера рассмотрим исходный граф, изображенный на рис. 1.

Рис. 1

Рис. 2

Его факторграф изображен на рис. 2. Стоками данного факторграфа являются: и , поэтому возможные минимальные проверяющие тесты будут состоять из проверок элементов или .

На вход программе подадим количество вершин исходного графа и его матрицу смежности. Содержимое input.txt:

6

0 1 0 0 1 1

0 0 0 0 0 0

1 0 1 1 0 0

0 0 1 0 1 0

0 0 0 0 0 1

0 0 0 0 1 1

В ходе своего выполнения, программа выведет в файл output.txtвсе возможные варианты минимального проверяющего теста:

{2, 5}

{2, 6}

Рассмотрим другой пример. Пусть дан граф, изображенный на рис. 3.

Рис. 3

Рис. 4

Факторграфом данного графа является граф, изображенный на рис. 4. Стоком факторграфа будет вершина . Минимальным проверяющим тестом будет состоять в проверке элемента .

Решим данный пример с помощью программы.

Входные данные (файл input.txt):

8

0 1 1 0 1 0 0 0

0 0 1 1 0 0 0 0

0 1 0 1 0 0 0 0

1 0 0 0 0 0 1 1

0 0 0 0 0 0 0 1

1 0 0 1 0 1 1 0

0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 1

После завершения работы, программа выведет в файлoutput.txt единственный минимальный проверяющий тест - {8}.

Таким образом, программа по исходной матрице смежности графа выводит всевозможные минимальные проверяющие тесты системы, представленной этим графом.

Заключение

В данной работе было рассмотрено такое понятие как проверяющий тест некоторой системы, приведен критерий минимальности такого проверяющего теста, а так же был рассмотрен и реализован алгоритм построения минимального проверяющего теста.

граф тест проверяющий теорема алгоритм

Список используемых источников

1. Богомолов А.М., Салий В.Н. Алгебраические основы дискретных систем. - М.: Наука. Физматлит, 1997. - 368 с.

2. Абросимов М.Б., Долгов А.А. Практические задания по графам, 2-е издание: Учеб.пособие. - Саратов: Изд-во «Научная книга», 2009. - 76 с.

Приложение

Класс ru.sgu.csit.tokbik.coursework.Matrix

importjava.io.File;

import java.io.FileNotFoundException;

import java.io.PrintWriter;

import java.util.*;

public class MainClass {

private static List<Integer>ans = new ArrayList<Integer>();

private static PrintWriter pw = null;

private static List<List<Integer>> stocks = new ArrayList<List<Integer>>();

public static void main(String[] args) {

Scanner scanner = null;

Map<Integer, List<Integer>>componentsReachability = new HashMap<Integer, List<Integer>>();

Map<List<Integer>, List<Integer>>reachabilityBySCC = new HashMap<List<Integer>, List<Integer>>();

boolean f;

try {

scanner = new Scanner(new File("input.txt"));

inttopCount = scanner.nextInt();

int[][] adjacencyMatrix = new int[topCount][topCount];

for (inti = 0; i<topCount; i++) {

for (int j = 0; j <topCount; j++) {

adjacencyMatrix[i][j] = scanner.nextInt();

}

}

int[][] reachabilityMatrix = Matrix.getReachabilityMatrix(adjacencyMatrix, topCount);

for (inti = 0; i<topCount; i++) {

componentsReachability.put(i + 1, new ArrayList<Integer>());

for (int j = 0; j <topCount; j++) {

if (reachabilityMatrix[i][j] == 1) {

componentsReachability.get(i + 1).add(j + 1);

}

}

}

for (inti = 0; i<componentsReachability.size(); i++) {

f = false;

List<Integer> key = componentsReachability.get(i + 1);

for (List<Integer> list : reachabilityBySCC.keySet()) {

if (list.equals(key)) {

f = true;

break;

}

}

if (f) {

reachabilityBySCC.get(key).add(i + 1);

} else {

List<Integer> list = new ArrayList<Integer>();

list.add(i + 1);

reachabilityBySCC.put(key, list);

}

}

for (Map.Entry<List<Integer>, List<Integer>> entry : reachabilityBySCC.entrySet()) {

if (entry.getKey().equals(entry.getValue())) {

stocks.add(entry.getKey());

}

}

pw = new PrintWriter(new File("output.txt"));

pw.println("Начальная матрица смежности :");

Matrix.printMatrix(adjacencyMatrix, topCount, pw);

pw.println("Матрицадостижимости :");

Matrix.printMatrix(reachabilityMatrix, topCount, pw);

if (stocks.size() == 1 &&stocks.get(0).size() == 1) {

pw.println("Минимальный проверяющий тест : ");

} else {

pw.println("Возможные варианты минимального проверяющего теста : ");

}

rec(0);

} catch (FileNotFoundException e) {

pw.println("File not found");

} finally {

scanner.close();

if (pw != null) {

pw.close();

}

}

}

private static void rec(int step) {

if (step == stocks.size()) {

StringBuildersb = new StringBuilder();

sb.append("{");

for (Integer integer : ans) {

sb.append(integer + ", ");

}

sb.delete(sb.lastIndexOf(","), sb.length());

sb.append("}");

pw.println(sb);

return;

}

for (Integer el : stocks.get(step)) {

ans.add(el);

rec(step + 1);

ans.remove(el);

}

}

}

Классru.sgu.csit.tokbik.coursework.MainClass

importjava.io.File;

import java.io.FileNotFoundException;

import java.io.PrintWriter;

import java.util.*;

public class MainClass {

private static List<Integer>ans = new ArrayList<Integer>();

private static PrintWriter pw = null;

private static List<List<Integer>> stocks = new ArrayList<List<Integer>>();

public static void main(String[] args) {

Scanner scanner = null;

Map<Integer, List<Integer>>componentsReachability = new HashMap<Integer, List<Integer>>();

Map<List<Integer>, List<Integer>>reachabilityBySCC = new HashMap<List<Integer>, List<Integer>>();

boolean f;

booleanisOne = true;

try {

scanner = new Scanner(new File("input.txt"));

inttopCount = scanner.nextInt();

int[][] adjacencyMatrix = new int[topCount][topCount];

for (inti = 0; i<topCount; i++) {

for (int j = 0; j <topCount; j++) {

adjacencyMatrix[i][j] = scanner.nextInt();

}

}

int[][] reachabilityMatrix = Matrix.getReachabilityMatrix(adjacencyMatrix, topCount);

for (inti = 0; i<topCount; i++) {

componentsReachability.put(i + 1, new ArrayList<Integer>());

for (int j = 0; j <topCount; j++) {

if (reachabilityMatrix[i][j] == 1) {

componentsReachability.get(i + 1).add(j + 1);

}

}

}

for (inti = 0; i<componentsReachability.size(); i++) {

f = false;

List<Integer> key = componentsReachability.get(i + 1);

for (List<Integer> list : reachabilityBySCC.keySet()) {

if (list.equals(key)) {

f = true;

break;

}

}

if (f) {

reachabilityBySCC.get(key).add(i + 1);

} else {

List<Integer> list = new ArrayList<Integer>();

list.add(i + 1);

reachabilityBySCC.put(key, list);

}

}

for (Map.Entry<List<Integer>, List<Integer>> entry : reachabilityBySCC.entrySet()) {

if (entry.getKey().equals(entry.getValue())) {

stocks.add(entry.getKey());

}

}

pw = new PrintWriter(new File("output.txt"));

pw.println("Начальная матрица смежности :");

Matrix.printMatrix(adjacencyMatrix, topCount, pw);

pw.println("Матрицадостижимости :");

Matrix.printMatrix(reachabilityMatrix, topCount, pw);

for (List<Integer> stock : stocks) {

if (stock.size() > 1) {

isOne = false;

break;

}

}

if (isOne) {

pw.println("Минимальный проверяющий тест : ");

} else {

pw.println("Возможные варианты минимального проверяющего теста : ");

}

rec(0);

} catch (FileNotFoundException e) {

pw.println("File not found");

} finally {

scanner.close();

if (pw != null) {

pw.close();

}

}

}

private static void rec(int step) {

if (step == stocks.size()) {

StringBuildersb = new StringBuilder();

sb.append("{");

for (Integer integer : ans) {

sb.append(integer + ", ");

}

sb.delete(sb.lastIndexOf(","), sb.length());

sb.append("}");

pw.println(sb);

return;

}

for (Integer el : stocks.get(step)) {

ans.add(el);

rec(step + 1);

ans.remove(el);

}

}

}

Размещено на Allbest.ru