Курсовая работа / курсак.doc
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ХЕРСОНСКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
КАФЕДРА ТЕХНИЧЕСКОЙ КИБЕРНЕТИКИ
Практические задачи дискретной математики
Курсовая работа
по дисциплине «Основы дискретной математики»
Вариант № 37
Выполнил
студент группы 2СУ2 ________________ Федин С.О.
Руководитель
доцент ________________ Рудакова А.В.
Херсон 2006
Форма № У-9.01
Херсонский национальный технический университет
(назва вузу)
Факультет кибернетики
Кафедра технической кибернетики
Спеціальність 091401 — Системы управления и автоматики
Дисципліна основы дискретной математики
Курс 2 Група 2СУ2 Семестр 3
ЗАВДАННЯ
на курсовий проект (роботу) студентові
Федина Сергея Олеговича
(прізвище, ім’я, по батькові)
1.Тема проекту (роботи) Практические задачи дискретной математики
2.Термін здачі студентом закінченого проекту (роботи) 25.12.06 г.
3.Вихідні дані до проекту (роботи) Вариант № 37
4.Зміст розрахунково-пояснювальної записки (перелік питань, що їх належить розробити):
1.Задачи теории графов
2.Синтез логических схем
5.Перелік графічного матеріалу (з точним означенням обов’язкових креслень):
_________________________________________________________________________________________________________________________________________________________________________________________________________________________________
Дата видачі завдання ________05.09.06_____________
КАЛЕНДАРНИЙ ПЛАН
| № | Назва етапів курсового проекту (роботи) | Термін виконання етапів проекту (роботи) | Примітки |
| 1 | Изучение литературы | 05.09.06 — 20.09.06 | |
| 2 | Формальное описание графа и определение числовых характеристик | 21.09.06 — 29.10.06 | |
| 3 | Решение задачи о раскраске | 30.10.06 — 12.11.06 | |
| 4 | Построение таблицы истинности функции алгебры логики и ее анализ | 13.11.06 — 26.11.06 | |
| 5 | Минимизация функции алгебры логики | 27.11.06 — 5.12.06 | |
| 6 | Синтез логической схемы методом каскадов | 6.12.06 — 9.12.06 | |
| 7 | Оформление курсовой работы | 10.12.06 — 25.12.06 | |
Студент ____________________________
(підпис)
Керівник проекту (роботи)_________________________________________
(підпис)
_____Рудакова Анна Владимировна____________________________________________________
(прізвище, ім’я, по батькові)
05.09.06 г.
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| Разраб. |
| Федин С.О. |
| Провер. |
| Рудакова А.В. |
| Реценз. |
| Н. Контр. |
| Утверд. |
| Практические задачи дискретной математики |
| Лит. |
| Листов |
Курсовая работа содержит 37 страниц, 9 рисунков, 26 таблиц.
В работе выполнены:
1) формализованное описание графа с помощью таблицы, фактор — множества, матриц инциденции, смежности вершин, циклов, разрезов и путей;
2) поиск его числовых характеристик, таких как, степени вершин, вершинная и реберная связность, цикломатическое число, вершинное и реберное числа независимости, числа вершинного и реберного покрытий, вершинное и реберное числа внешней устойчивости, радиус и диаметр графа;
3) решена задача о раскраске графа;
4) составление таблицы истинности функции алгебры логики и записаны её совершенные дизъюнктивная и конъюнктивная нормальные формы;
5) анализ функции на принадлежность к классам;
6) минимизация логической функции методом Квайна-МакКласски и с помощью карт Карно;
7) синтез логической схемы методом каскадов и реализация её в базисе и-или-не с использованием двухвходовых элементов.
НЕОРИЕНТИРОВАНЫЙ ГРАФ, ЧИСЛОВЫЕ ХАРАКТЕРИСТИКИ, ЗАДАЧИ О РАСКРАСКЕ, ФУНКЦИЯ АЛГЕБРЫ ЛОГИКИ, ТАБЛИЦА ИСТИННОСТИ, МИНИМИЗАЦИЯ, КАРТЫ КАРНО, МЕТОД КАСКАДОВ.
Содержание
Введение 6
1. Задачи теории графов 7
1.1. Формализованное задание графа 7
1.2. Числовые характеристики графа 10
1.2.1 Степени всех вершин графа 10
1.2.2 Вершинная и реберная связность графа 11
1.2.3 Цикломатическое число графа 11
1.2.4 Вершинное и реберное числа независимости 11
1.2.5 Числа вершинного и реберного покрытий графа 12
1.2.6 Вершинное и реберное число внешней устойчивости графа 12
1.2.7 Радиус и диаметр графа 12
1.3. Задача о раскраске 13
2.Синтез логических схем 16
2.1Таблица истинности функции алгебры логики 16
2.2Анализ функции алгебры логики на принадлежность к классам 17
2.3Минимизация функции алгебры логики 17
2.4Синтез схемы методом каскадов 19
2.4.1Минимизация с помощью карт Карно 20
2.4.2Минимизация методом Квайна - Мак-Класски 20
2.5Синтез схемы методом каскадов 23
Заключение 36
Список использованных источников 37
ВВЕДЕНИЕ
При взгляде на географическую карту сразу бросается в глаза сеть железных дорог, что является типичным графом. Рассмотрим такую ситуацию: почтальон должен развести письма в соседние села. Существует много различных маршрутов поездки. А выбрать из них наикратчайший поможет граф.
Но кроме этого графы используются в строительстве при планировании проведения работ; для решения логических проблем, связанных с перебором вариантов и во многих других вопросах.
Впервые основы теории графов появились в работе Л.Эйлера, где он описывал решения головоломок и математических развлекательных задач. Широкое же развитие теория графов получила лишь в 50-х годах ХХ века в связи со становлением кибернетики и развитием вычислительной техники.
После изготовления первого компьютера стало ясно, что при его производстве возможно использование только цифровых технологий ограничение сигналов связи единицей и нулём для большей надёжности и простоты архитектуры ПК. Благодаря своей бинарной природе, математическая логика получила широкое распространение в ВТ и информатике. Были созданы электронные эквиваленты логических функций, что позволило применять методы упрощения булевых выражений к упрощению электрической схемы. Кроме того, благодаря возможности нахождения исходной функции по таблице позволило сократить время поиска необходимой логической схемы.
В программировании логика незаменима как строгий язык и служит для описания сложных утверждений, значение которых может определить компьютер.
Целью курсовой работы является закрепление знаний по дисциплине «Основы дискретной математики», практическое овладение математическим аппаратом, характерным для современной теории анализа сложных систем (теории графов) и проектирования систем управления, приобретение навыков самостоятельного синтеза логических схем.
7
1 ЗАДАЧИ ТЕОРИИ ГРАФОВ
Геометрический граф в пространстве jn (Эвклидово пространство) — это множество V={vi} точек пространства jn и множество Е={ek} простых кривых удовлетворяющих следующим условиям.