Міністерство освіти і науки Російської Федерації
Державна освітня установа
вищої професійної освіти
САРАТОВСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ
ІМЕНІ Н.Г. ЧЕРНИШЕВСЬКОГО
Кафедра теоретичних основ комп'ютерної безпеки і криптографії
Курсова робота
Мінімальний перевіряючий тест
Студента 3 курсу
Кіяйкіна Олександра Євгеновича
Саратов 2012
Зміст
Введення
. Основні поняття та визначення
. Теорема
. Алгоритм побудови мінімального перевіряючого тесту
Висновок
Список використаних джерел
Додаток
Введення
Перша робота з теорії графів, що належить відомому швейцарському математику Л. Ейлера, з'явилася в 1736 році. Спочатку теорія графів здавалася досить незначним розділом математики, так як вона мала справу в основному з математичними розвагами та головоломками. Однак подальший розвиток математики і особливо її додатків дало сильний поштовх розвитку теорії графів. Вже в XIX столітті графи використовувалися для побудови схем електричних ланцюгів і молекулярних схем. В даний час дана теорія служить природним апаратом у деяких розділах чистої математики, а також знаходить численні застосування в різноманітних практичних питаннях: при встановленні різного роду відповідностей, при вирішенні транспортних задач, задачах про потоках в мережі нафтопроводів та багатьох інших. p align="justify"> У даній роботі буде розглянуто поняття перевіряючого тесту для деякої системи. Буде наведено критерій мінімальності перевіряючого тесту і його доказ. Необхідні терміни будуть описані у відповідному розділі. p align="justify"> Особливе місце в роботі займає алгоритм побудови мінімального перевіряючого тесту. Для цього написана програма, що реалізує даний алгоритм, а також буде розглянуто приклад його застосування. br/>
1. Основні поняття та визначення
Під орієнтованим графом (або, для стислості, орграфом) розуміється пара
,
де-кінцеве непорожнє безліч (вершини орграфа), а-відношення на множині.
Параназивают дугою орграфа з началомі кінцем.
Ставлення називають ставленням суміжності, а відповідну йому двійкову бульову матрицю - матрицею суміжності орграфа.
Нехай - деякий орграф. Маршрутом в цьому орграфе називається послідовність дуг
,
в якій для всіх. Кажуть, що маршрут проходить через вершини. Вершина н...
