Решение некоторых задач булевой алгебры, теории графов и теории кодирования
Различные формы задания булевых функций. Переход от одной формы задания к другой. Построение и упрощение формул, задаваемых различными схемами. Нахождение кратчайших маршрутов для взвешенных графов с помощью алгоритма Форда–Беллмана и алгоритма Дейкстры.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 18.10.2017 |
| Размер файла | 669,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
Санкт-Петербургский государственный морской технический университет
Кафедра математики
Курсовая работа
по дискретной математике
РЕШЕНИЕ НЕКОТОРЫХ ЗАДАЧ БУЛЕВОЙ АЛГЕБРЫ, ТЕОРИИ ГРАФОВ И ТЕОРИИ КОДИРОВАНИЯ
Выполнил:
Разживин Никита Сергеевич
Санкт-Петербург 2013
1. Алгебра логики
1.1 Перевод чисел из одной системы счисления в другую
Задание 1. Перевод числа из одной системы счисления в другую.
1.2 Различные формы задания булевых функций. Переход от одной формы задания к другой. Карта Карно
формула алгоритм булевой беллман
Задание 2. Построить таблицы значений для функций.
1.
Вычисления с помощью Wolfram Mathematica:
- следование
Размещено на http://www.allbest.ru/
! - отрицание
- штрих Шеффера
- сложение по модулю 2
Размещено на http://www.allbest.ru/
- умножение
Размещено на http://www.allbest.ru/
Таблица 1
|
x |
y |
f1 |
|
|
0 |
0 |
1 |
|
|
0 |
1 |
0 |
|
|
1 |
0 |
0 |
|
|
1 |
1 |
1 |
Таблица 2
|
x |
y |
z |
||
|
0 |
0 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
|
|
0 |
1 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
|
|
1 |
0 |
0 |
1 |
|
|
1 |
0 |
1 |
1 |
|
|
1 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
Задание 3.
Написать таблицу значений для функции h(x,y), являющейся суперпозицией двух функций, если , ,
Таблица 3
|
x |
y |
z |
|||
|
0 |
0 |
0 |
1 |
1 |
|
|
0 |
0 |
1 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
0 |
|
|
0 |
1 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
1 |
1 |
|
|
1 |
1 |
0 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
0 |
Таблица 4
|
x |
y |
xyz |
||||
|
0 |
0 |
000 |
1 |
000 |
0 |
|
|
0 |
1 |
010 |
1 |
101 |
0 |
|
|
1 |
0 |
101 |
1 |
010 |
0 |
|
|
1 |
1 |
111 |
1 |
111 |
0 |
4. Написать таблицу значений функции. Найти фиктивные переменные для данной функции. Преобразовать данную формулу в эквивалентную ей, но не содержащую фиктивных переменных.
Таблица 5
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
|
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
|
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
По
р
По
р
По
р
р
Таблица 6
|
0 |
0 |
1 |
|
|
0 |
1 |
0 |
|
|
1 |
0 |
0 |
|
|
1 |
1 |
1 |
1.4. Совершенные дизъюнктивные и конъюнктивные формы булевых функций. Двойственные функции.
5. Для функции записать карту Карно, СДНФ, СКНФ. Построить двойственную функцию.
Таблица 7. Карта Карно
|
00 |
01 |
11 |
10 |
||
|
00 |
|||||
|
01 |
1 |
||||
|
11 |
1 |
1 |
|||
|
10 |
1 |
1 |
Таблица 8
|
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
1 |
0 |
1 |
|
|
0 |
0 |
1 |
0 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
0 |
1 |
|
|
0 |
1 |
1 |
0 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
1 |
0 |
|
|
1 |
0 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
1 |
|
|
1 |
0 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
0 |
0 |
1 |
1 |
|
|
1 |
1 |
0 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
0 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
СДНФ
СКНФ
6. Проверить, являются ли равносильными формулы A и B двумя способами а) составлением таблиц значений; б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований
Таблица 9
|
x |
y |
z |
|||
|
0 |
0 |
0 |
1 |
1 |
|
|
0 |
0 |
1 |
1 |
1 |
|
|
0 |
1 |
0 |
1 |
1 |
|
|
0 |
1 |
1 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
0 |
|
|
1 |
0 |
1 |
0 |
1 |
|
|
1 |
1 |
0 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
1 |
б)
1.3 Построение и упрощение формул, задаваемых различными схемами
7. Построить формулы, задаваемые данными схемами. Упростить их. Построить схемы, соответствующие упрощенным формулам.
1)
2)
Рисунок 2
Рисунок 3
8. Представить функцию в виде дизъюнктивного разложения по переменным , коэффициенты разложения (функции двух переменных) представить соответствующими формулами над множеством связок |,
Таблица 10
|
0 |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
1 |
1 |
|
|
0 |
0 |
1 |
0 |
0 |
|
|
0 |
0 |
1 |
1 |
0 |
|
|
0 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
1 |
|
|
0 |
1 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
1 |
|
|
1 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
1 |
1 |
1 |
|
|
1 |
1 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
1 |
1 |
|
|
1 |
1 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
0 |
Рисунок 4
9. С помощью СДНФ установить, являются ли равносильными следующие ДНФ:
1.4 Минимизация булевых функций методом Квайна-Мак-Класки и матричным методом Карно
10. Минимизировать функцию методом Квайна-Мак-Класки и графическим методом Карно. Найти индекс простоты функции.
1. Метод Квайна-Мак-Класки.
Таблица 11
|
0 |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
1 |
1 |
|
|
0 |
0 |
1 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
1 |
|
|
0 |
1 |
0 |
0 |
1 |
|
|
0 |
1 |
0 |
1 |
0 |
|
|
0 |
1 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
0 |
|
|
1 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
1 |
1 |
1 |
|
|
1 |
1 |
0 |
0 |
1 |
|
|
1 |
1 |
0 |
1 |
0 |
|
|
1 |
1 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
1 |
Таблица 12
|
№ гр. |
Набор |
№ наб. |
№ склеивания |
Результат склеивания |
№ скл. набора |
Результат склеивания |
Импликанты |
|
|
0 |
0000 |
0 |
0.1 0.2 0.4 0.8 1.3 2.10 4.12 8.10 8.12 3.11 10.11 10.14 12.14 11.15 14.15 |
000- 00-0 0-00 -000 00-1 -010 0-00 10-0 1-00 -011 101- 1-10 11-0 1-11 111- |
0,2,1,3 0,2,8,10 0,4,8,12 4,12,8,12 8,10,12,14 8,12,10,14 10,11,14,15 10,14,13,15 |
00-- -0-0 --00 --00 1--0 1--0 1-1- 1-1- |
J1 J2 J3 J4 J5 |
|
|
1 |
0001 0010 0100 1000 |
1 2 4 8 |
||||||
|
2 |
0011 1010 1100 |
3 10 12 |
||||||
|
3 |
1011 1110 |
11 14 |
||||||
|
4 |
1111 |
15 |
Таблица 13
|
0000 |
0001 |
0010 |
0100 |
1000 |
0011 |
1010 |
1100 |
1011 |
1110 |
1111 |
||
|
I1 |
+ |
+ |
+ |
+ |
||||||||
|
I2 |
+ |
+ |
+ |
+ |
||||||||
|
I3 |
+ |
+ |
+ |
+ |
||||||||
|
I4 |
+ |
+ |
+ |
+ |
||||||||
|
I5 |
+ |
+ |
+ |
+ |
ТДНФ
МДНФ =
2. Метод Карно
1.5 Представление булевых функций полиномами Жегалкина
11. Представить функцию полиномом Жегалкина.
Таблица 13
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
|
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
|
|
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
|
|
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1.6 Проверка принадлежности булевых функций классам Поста. Полные системы булевых функций. Базисы
Задание 12. Проверить, принадлежат ли функции и к классам T0, T1, L, S, M.
1.
Таблица 14
|
0 |
0 |
0 |
0 |
1 |
0 |
|
|
0 |
0 |
1 |
1 |
0 |
1 |
|
|
0 |
1 |
0 |
1 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
1 |
1 |
0 |
0 |
|
|
1 |
1 |
0 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
1 |
1 |
1.
Таблица 15
|
0 |
0 |
0 |
1 |
1 |
1 |
|
|
0 |
0 |
1 |
1 |
1 |
1 |
|
|
0 |
1 |
0 |
0 |
1 |
0 |
|
|
0 |
1 |
1 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
0 |
1 |
0 |
|
|
1 |
1 |
0 |
0 |
0 |
1 |
|
|
1 |
1 |
1 |
0 |
0 |
1 |
13. Доопределить функции , так, чтобы
Таблица 16
|
1 |
||||||||
|
0 |
0 |
0 |
- |
1 |
0 |
- |
1 |
|
|
0 |
0 |
1 |
1 |
- |
- |
1 |
0 |
|
|
0 |
1 |
0 |
- |
- |
1 |
- |
1 |
|
|
0 |
1 |
1 |
- |
0 |
0 |
- |
0 |
|
|
1 |
0 |
0 |
0 |
- |
- |
1 |
1 |
|
|
1 |
0 |
1 |
- |
1 |
- |
0 |
0 |
|
|
1 |
1 |
0 |
0 |
- |
0 |
- |
1 |
|
|
1 |
1 |
1 |
- |
1 |
- |
1 |
0 |
Т к то
Т к то
14. Являются ли полными следующие системы булевых функций Какие из указанных систем образуют базис?
- является полной системой, образует базис
Таблица 17
|
S |
L |
M |
||||
|
+ |
- |
- |
+ |
- |
||
|
+ |
+ |
- |
- |
+ |
||
|
- |
- |
+ |
+ |
- |
- является полной системой, образует базис
Таблица 18
|
S |
L |
M |
||||
|
- |
+ |
- |
- |
- |
||
|
- |
- |
+ |
+ |
- |
- является полной системой, образует базис Шеффера
Таблица 19
|
S |
L |
M |
||||
|
- |
- |
- |
- |
- |
- является полной системой, образует базис
Таблица 20
|
S |
L |
M |
||||
|
- |
+ |
- |
- |
- |
||
|
+ |
- |
- |
+ |
- |
1.7 Представление булевых функций в базисе Шеффера и в базисе Вебба
15. Записать функцию в базисе «не и» и в базисе «не или».
Базис Шеффера:
Базис Вебба:
1.8 Производные булевой функции
16. Найти частные производные булевой функции по каждой переменной и их вес, если
.
=
Таблица 21
|
0 |
0 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
|
|
0 |
1 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
|
|
1 |
0 |
0 |
1 |
|
|
1 |
0 |
1 |
1 |
|
|
1 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
17. С помощью карт Карно найти минимальную ДНФ для частичной функции .
Таблица 22
|
0 |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
1 |
- |
|
|
0 |
0 |
1 |
0 |
- |
|
|
0 |
0 |
1 |
1 |
1 |
|
|
0 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
1 |
|
|
0 |
1 |
1 |
0 |
- |
|
|
0 |
1 |
1 |
1 |
1 |
|
|
1 |
0 |
0 |
0 |
- |
|
|
1 |
0 |
0 |
1 |
- |
|
|
1 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
1 |
1 |
0 |
|
|
1 |
1 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
1 |
0 |
|
|
1 |
1 |
1 |
0 |
- |
|
|
1 |
1 |
1 |
1 |
1 |
Таблица 23
|
00 |
01 |
11 |
10 |
||
|
00 |
1 |
1 |
1 |
1 |
|
|
01 |
0 |
1 |
1 |
1 |
|
|
11 |
0 |
1 |
1 |
0 |
|
|
10 |
0 |
0 |
1 |
1 |
2. Основы теории графов
18. Заданы графы G1 и G2. Найти Для графа найти матрицы смежности, инцидентности, достижимости, контрдостижимости, сильных компонент и все маршруты длины 2, исходящие из вершины 1.
Рисунок 5
,
Вершины обозначаем через а вершины -
Рисунок 6
Рисунок 7. ,
Таблица 24
|
1 |
2 |
3 |
4 |
||
|
1 |
1 |
1 |
0 |
1 |
|
|
2 |
1 |
1 |
1 |
0 |
|
|
3 |
0 |
1 |
1 |
1 |
|
|
4 |
1 |
0 |
1 |
1 |
Таблица 25
|
E1 |
E2 |
E3 |
E4 |
E5 |
E6 |
E7 |
E8 |
||
|
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
2 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
3 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
|
4 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
Рисунок 8
Матрица сильных компонентов
- цепи начиная с вершины 1
- цепи начиная с вершины 2
- цепи начиная с вершины 3
- цепи начиная с вершины 4
- циклы различные
Ребра в скобках { } либо содержаться в маршруте, либо нет компонент сильной связи всего Маршрут длины 2 из вершины 1 -
2.1 Эйлеровы и планарные графы
Задание 19. Найти матрицы фундаментальных циклов, фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли граф эйлеровым? Является ли изображенный граф планарным?
Рисунок 9
Матрица фундаментальных циклов:C=(C1|C2)
Матрица фундаментальных разрезов:
K=(K1|K2)
K2=E7Ч7
K1=
Данный граф является эйлеровым, т к степени вершин чётны
F=6
H=8
M=12
Рисунок 10
граф является планарным
2.2 Нахождение кратчайших маршрутов для взвешенных графов с помощью алгоритма Форда-Беллмана и алгоритма Дейкстры
Задание 20. Найти кратчайшие маршруты из вершины S в вершину F для взвешенных графов G1 и G2.
Рисунок 11
Таблица 26
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
||||||
|
1 |
0 |
3 |
1 |
3 |
0 |
0 |
0 |
0 |
||||||
|
2 |
0 |
2 |
3 |
3 |
3 |
3 |
||||||||
|
3 |
0 |
4 |
4 |
4 |
4 |
|||||||||
|
4 |
0 |
4 |
||||||||||||
|
5 |
0 |
3 |
3 |
3 |
3 |
|||||||||
|
6 |
0 |
1 |
||||||||||||
|
7 |
0 |
1 |
||||||||||||
|
8 |
0 |
1 |
5 |
|||||||||||
|
9 |
0 |
6 |
Ответ:
20.2
Таблица 27
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|||||||
|
1 |
0 |
3 |
4 |
3 |
0 |
0 |
0 |
0 |
0 |
||||||
|
2 |
0 |
-2 |
3 |
3 |
3 |
3 |
3 |
||||||||
|
3 |
0 |
2 |
4 |
4 |
4 |
4 |
4 |
||||||||
|
4 |
0 |
4 |
1 |
1 |
1 |
1 |
|||||||||
|
5 |
0 |
3 |
2 |
2 |
2 |
2 |
|||||||||
|
6 |
0 |
-1 |
4 |
3 |
3 |
3 |
|||||||||
|
7 |
0 |
1 |
5 |
3 |
3 |
||||||||||
|
8 |
0 |
4 |
|||||||||||||
|
9 |
0 |
Ответ:
3. Элементы теории кодирования
3.1 Построение плоского дерева по его коду
Задание 21. По вектору установить, является ли он кодом какого-нибудь плоского дерева. В случае положительного ответа построить плоское корневое дерево по его коду.
(000110011101)2=(413)10
Рисунок 12
3.2 Построение кодового дерева для заданной схемы алфавитного кодирования
22. Для схемы алфавитного кодирования
найти среднюю длину слова и построить кодовое дерево.
Рисунок 13
Рисунок 14. Построение дерева с помощью пакета Wolfram Mathematica
3.3 Построение оптимального кодового дерева Хаффмена и кодовой схемы для заданных алфавита сообщений и кодирующего алфавита
23. Задан алфавит сообщений и кодирующий двоичный код алфавит . Относительные частоты появления букв алфавита сообщений A определяются распределением вероятностей . Построить кодовое дерево Хаффмана и кодовую схему.
Таблица 28
|
a |
b |
c |
d |
|
|
0.50 |
0.25 |
0.15 |
0.10 |
Объединяем наименьшие вероятности до тех пор, пока не образуется единица. <c,d> P34=0.25
Таблица 29
|
a |
<c,d> |
b |
|
|
0.50 |
0.25 |
0.25 |
<<c,d>b> P342=0.50
Рисунок 15
Таблица 30
|
<<c,d>b> |
a |
|
|
0.50 |
0.50 |
<<<c,d>b>a> P3421=1
Рисунок 16
3.4 Декодирование кодовых слов, построенных методом Хэмминга и содержащих ошибки не более чем в одном разряде
24. По каналу связи передавалось кодовое слово, построенное по методу Хэмминга для сообщения . После передачи по каналу связи, искажающему слово не более чем в одном разряде, было получено слово . Восстановить исходное сообщение.
=> ошибка в 8 разряде
исходное сообщение.
Список использованной литературы
1. Яблонский С. В. Введение в дискретную математику, 1986 г. Издание «Наука», 384 с
2. Зыков А. А. Основы теории графов, 1987 г. Издание «Наука», 383 с
3. Новиков Ф. А. Дискретная математика для программистов, 2000 г. Издание «Питер», 301 с
4. Кузнецов О. П. Дискретная математика для инженера, 2009 г. Издание «Лань», 400 с.
Размещено на Allbest.ru
...Подобные документы
Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.
курсовая работа [109,1 K], добавлен 22.01.2016Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация [430,0 K], добавлен 19.11.2013Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа [2,4 M], добавлен 08.10.2014История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
курсовая работа [1,8 M], добавлен 18.01.2013Нахождение минимального пути от фиксированной до произвольной вершины графа с помощью алгоритма Дейкстры, рассмотрение основных принципов его работы. Описание блок-схемы алгоритма решения задачи. Проверка правильности работы разработанной программы.
курсовая работа [495,4 K], добавлен 19.09.2011Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа [228,5 K], добавлен 30.01.2012Основополагающие понятия теории графов и теории групп. Определение эквивалентности, порождаемой группой подстановок, и доказательство леммы Бернсайда о числе классов такой эквивалентности. Сущность перечня конфигурации, доказательство теоремы Пойа.
курсовая работа [682,9 K], добавлен 20.05.2013Метод Форда-Беллмана для нахождения расстояния от источника до всех вершин графа. Алгоритмы поиска расстояний и отыскания кратчайших путей в графах. Блочно-диагональный вид и матрица в исследовании системы булевых функций и самодвойственной функции.
курсовая работа [192,1 K], добавлен 10.10.2011Основные этапы развития булевой алгебры и применение минимальных форм булевых многочленов к решению задач, в частности, с помощью метода Куайна - Мак-Класки. Применение минимизирования логических форм при проектировании устройств цифровой электроники.
курсовая работа [58,6 K], добавлен 24.05.2009Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.
реферат [108,4 K], добавлен 01.12.2008Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
курсовая работа [278,1 K], добавлен 21.02.2009Понятие и содержание теории графов. Правила построения сетевых графиков и требования к ним. Сетевое планирование в условиях неопределенности. Теория принятия решений, используемые алгоритмы и основные принципы. Пример применения алгоритма Дейкстры.
курсовая работа [1,0 M], добавлен 26.09.2013Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011Булевы алгебры – решетки особого типа, применяемые при исследовании логики (как логики человеческого мышления, так и цифровой компьютерной логики), а также переключательных схем. Минимальные формы булевых многочленов. Теоремы абстрактной булевой алгебры.
курсовая работа [64,7 K], добавлен 12.05.2009Изучение основных вопросов теории графов и области ее применения на практике. Разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера. Результаты тестирований работы данного алгоритма.
курсовая работа [362,9 K], добавлен 24.11.2010Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа [272,5 K], добавлен 05.06.2014Основные понятия, связанные с графом. Решение задачи Эйлера о семи кёнигсбергских мостах. Необходимые и достаточные условия для эйлеровых и полуэйлеровых графов. Применение теории графов к решению задач по математике; степени вершин и подсчёт рёбер.
курсовая работа [713,8 K], добавлен 16.05.2016
