Дискретная математика
Операции над множествами. Понятия и определения отношений и функций. Характеристики графов, алгоритм Форда–Беллмана нахождения минимального пути. Минимальные остовные деревья нагруженных графов. Формулы логики булевых функций, преобразования формул.
| Рубрика | Математика |
| Вид | методичка |
| Язык | русский |
| Дата добавления | 28.06.2013 |
| Размер файла | 693,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
2. Привести пример отношения частичного порядка на множестве целых чисел..
3. Дана функция f(x) = x 2 +lnx, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 17
1. Задано бинарное отношение r = {<x, x>, <y, z>, <x, z>, <z, x>, <z, y>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения транзитивного и симметричного.
3. Дана функция f(x) = x +, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 18.
1. Задано бинарное отношение r = {<1, 1>, <1, a>, <a, 1>, <a, 4>, <4, a>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r--рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения рефлексивного и транзитивного.
3. Дана функция f(x) = x 2 + 2x, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 19
1. Задано бинарное отношение r = {<1, 1>, <2, 2>, <2, 3>, <3, 2>, <3, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x 2 - y2 = 0?
3. Дана функция f(x) = 2x +, отображающая множество положительных действительных чисел во множество всех действительных чисел. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 20
1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <3, 3>, <4, 4>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не рефлексивного, не симметричного и не транзитивного.
3. Дана функция f(x) = x3ex, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 21
1. Задано бинарное отношение r = {<1, 3>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение ? рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения частичного порядка на множестве треугольников на плоскости.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R R и не являющейся сюръективной, инъективной, биективной.
Вариант № 22
1. Задано бинарное отношение r = {<1, 2>, <2, 2>, <2, 1>, <2, 3>, <3, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение ? рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x = - y?
3. Дана функция f(x) = lnx +, отображающая множество положительных действительных чисел во множество всех действительных чисел. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 23
1. Задано бинарное отношение r = {<1, 1>, <2, 2>, <2, 1>, <2, 3>, <3, 2>, <3, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r--рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением частичного полрядка на множестве действительных чисел отношение xry, задаваемое неравенством x 2 - y2 0?
3. Дана функция f(x) = ex +, отображающая множество положительных действительных чисел на множество положительных действительных чисел. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 24
1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <3, 1>, <3, 2> <1, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, не рефлексивного и симметричного.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество неотрицательных действительных чисел, R [0, ) и являющейся сюръективной, но не инъективной.
Вариант № 25
1. Задано бинарное отношение r = {<1, 2>, <2, 1>, <2, 3>, <1, 3>, <3, 1>, <3, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение--r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое неравенством x y?
3. Дана функция f(x) = lnx + 2x, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 26
1. Задано бинарное отношение r = {<2, 2>, <2, 4>, <1, 4>, <4, 1>, <4, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, не рефлексивного и не симметричного.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R R и являющейся сюръективной и неинъективной.
Вариант № 27
1. Задано бинарное отношение r = {<1, 1>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством xy = 100?
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R R и не являющейся сюръективной, инъективной, биективной.
Вариант № 28
1. Задано бинарное отношение r = {<1, 1>, <2, 2>, <3, 3>, <3, 1>, <1, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, не рефлексивного и симметричного.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R R и являющейся сюръективной, но не инъективной.
Вариант № 29
1. Задано бинарное отношение r = {<1, 1>, <2, 2>, <4, 4>, <2, 1>, <2, 4>, <4, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения частичного порядка.
3. Дана функция f(x) = x 2, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 30
1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <2, 4>, <4, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения эквивалентности.
3. Дана функция f(x) = x 2 +, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
3. Раздел «Графы»
1. Описать граф, заданный матрицей смежности, используя как можно больше характеристик. Составить матрицу инцидентности и связности (сильной связности).
2. Пользуясь алгоритмом Форда-Беллмана, найти минимальный путь из x1 в x7 в ориентированном графе, заданном матрицей весов.
3. Пользуясь алгоритмом Краскала, найти минимальное остовное дерево для графа, заданного матрицей длин ребер.
Варианты заданий
1 .1. 0 1 1 0 1 1 2. 4 6 12 3. 12 6 20 14
1 0 0 1 0 0 13 7 12 2 4 6
1 0 0 0 1 0 5 3 6 2 10 12
0 1 0 0 1 0 10 9 20 4 10 6
1 0 1 1 0 1 8 14 6 12 6
1 0 0 0 1 0 11
2 .1. 0 0 0 0 0 1 2. 1 3 9 3. 1 4 5
0 0 1 1 1 0 10 4 1 2 1
0 0 0 0 0 0 2 1 2 1 1
1 0 0 0 0 1 7 6 4 1 3
1 0 1 0 0 0 5 5 1 1 3
1 0 1 0 0 0 8
3 .1. 0 1 0 1 0 0 2. 3 5 11 3. 6 3 10 7
1 0 0 1 0 0 12 6 6 1 2 3
0 0 0 0 1 1 3 2 3 1 5 6
1 1 0 0 1 1 9 8 10 2 5 3
0 0 1 1 0 0 7 7 3 6 3
0 0 1 1 0 0 10
4.1. 0 0 0 0 0 1 2. 5 4 2 2 9 3. 7 2 11 7
1 0 1 0 1 1 1 1 1 1 7 3 4
1 0 0 0 0 0 2 1 1 3 2 3 1 5
0 0 1 0 0 1 2 1 1 11 1 3
0 1 1 1 0 0 2 2 1 6 7 4 5 3
0 0 1 0 0 0 1 5 1 1
2 1 1 2
5 .1. 0 0 0 1 1 0 2. 4 3 1 3. 2 5 5
0 0 0 1 0 1 3 2 1 4 2 8 7
1 0 0 0 0 0 1 1 1 8 10 1
0 1 0 0 0 1 3 1 1 5 10 13
1 0 0 0 0 0 2 1 5 5 7 1 13
0 1 0 1 0 0 3 2 2
2 2
6.1. 0 0 1 0 1 0 2. 9 2 12 3. 1 5 4 5
0 0 1 1 1 1 1 1 2 4 1 2 6 1
1 1 0 0 1 0 2 1 1 2 5 2 1 7
0 1 0 0 0 1 1 1 1 4 6 1 4
1 1 1 0 0 0 1 2 2 5 1 7 4
0 1 0 1 0 0 1 8
2 1 1 2
7.1. 0 0 1 1 0 0 2. 3 4 9 3. 4 3 5 6
1 0 0 0 0 1 12 10 4 4 2 1
1 0 0 0 1 0 2 1 3 2 1 1
0 1 0 0 0 1 7 6 5 1 3
0 0 1 0 1 0 5 6 1 1 3
0 1 0 1 0 0 8
8 .1. 0 1 1 0 1 1 2. 2 5 8 9 3. 1 3 4 5
1 0 1 1 0 1 10 4 1 2 9 1
1 1 0 0 1 1 5 3 2 1 3 2 1 1
0 1 0 0 0 1 7 6 4 9 1 3
1 0 1 0 0 0 5 5 1 1 3
1 1 1 1 0 0 9
9 .1. 0 1 0 1 1 1 2. 2 5 14 3. 5 3 10 7
1 0 0 1 0 0 11 12 6 5 1 2 4
0 0 0 1 1 0 3 2 3 1 5 6
1 1 1 0 1 0 9 8 10 2 5 3
1 0 1 1 0 1 7 7 4 6 3
1 0 0 0 1 0 10
10.1 0 1 1 0 1 1 2. 5 4 2 3 9 3. 7 2 11 7
1 0 0 1 1 1 1 1 1 6 7 3 4
1 0 0 0 1 0 4 1 1 3 2 3 1 5
0 1 0 0 0 1 2 1 1 11 1 3
1 1 1 0 0 1 2 2 1 6 7 4 5 3
1 1 0 1 1 0 1 5 1 1
2 1 1 2
11.1. 0 0 1 0 1 0 2. 4 9 3 1 3. 1 4 5
0 0 0 1 0 1 3 2 1 4 1 8 7
1 0 0 0 1 0 1 1 10 1 8 10 1
0 1 0 0 0 1 3 1 1 4 10 13
1 0 1 0 0 0 2 1 5 5 7 1 13
0 1 0 1 0 0 3 1 2
2 2
12.1 0 0 1 0 1 0 2. 9 10 2 12 3. 1 5 4 6
0 0 0 1 0 1 1 1 2 4 1 2 6 3
1 1 0 0 1 1 2 1 1 2 5 2 1 7
0 0 0 0 0 0 1 1 1 15 4 6 1 4
1 1 1 0 0 0 1 2 2 6 3 7 4
0 1 0 1 0 0 1 8
2 1 1 2
13.1. 0 0 0 0 0 0 2. 5 6 15 3. 12 6 10 4
1 0 0 1 0 1 13 7 12 2 5 6
1 0 0 0 1 0 4 3 6 2 10 12
1 1 1 0 0 0 10 9 10 5 10 6
1 1 0 0 0 0 8 4 6 12 6
0 1 0 0 1 0 11
14.1. 0 0 1 1 0 0 2. 2 3 9 3. 3 2 4 5
1 0 0 0 0 1 12 10 4 3 2 1
1 0 0 0 1 0 2 1 2 2 1 1
0 1 0 0 0 1 7 6 4 1 3
0 0 1 0 1 0 5 5 1 1 3
0 1 0 1 0 0 8
15.1. 0 1 0 1 0 0 2. 2 5 10 3. 6 3 10 4
1 0 0 1 0 0 12 6 6 1 2 3
0 0 0 0 1 1 3 1 3 1 8 6
1 1 0 0 1 1 9 8 10 2 8 3
0 0 1 1 0 0 7 4 3 6 3
0 0 1 1 0 0 10
16.1. 0 0 0 0 1 1 2. 5 4 2 2 10 3. 4 2 10 6
0 0 1 1 0 0 2 1 2 1 4 3 4
0 1 0 0 1 0 2 1 1 3 2 3 1 5
0 1 0 0 0 1 2 1 1 10 1 3
1 0 1 0 0 0 2 2 1 6 6 4 5 3
1 0 0 1 0 0 1 5 1 1
2 1 1 2
17.1 0 0 1 0 1 0 2. 4 9 8 3 1 3. 2 3 5
0 0 0 1 0 1 3 2 1 4 2 8 7
1 0 0 0 1 0 1 1 1 8 10 1
0 1 0 0 0 1 3 1 1 3 10 12
1 0 1 0 0 0 2 1 5 5 7 1 12
0 1 0 1 0 0 3 2 2
2 2
18.1. 0 0 1 0 1 0 2. 9 10 2 12 3. 1 3 4 5
0 0 0 0 0 0 1 1 2 4 1 2 6 8
1 0 0 0 1 0 2 1 1 2 3 2 1 7
0 1 0 0 0 1 1 1 1 4 6 1 4
1 0 1 0 0 0 1 2 9 2 5 8 7 4
0 1 0 1 0 0 1 8
2 1 1 2
19.1. 0 1 1 0 1 1 2. 3 5 12 20 3. 1 6 5 14
1 0 0 1 0 0 13 8 1 3 4 6
1 0 0 1 1 1 5 3 6 3 10 12
0 1 1 0 1 1 10 9 5 4 10 6
1 0 1 1 0 1 8 14 6 12 6
1 0 1 1 1 0 11
20.1. 0 1 0 0 1 0 2. 1 5 7 9 3. 6 3 4 5
1 0 0 1 0 0 10 4 6 2 9 1
1 0 0 0 1 1 5 3 1 3 2 1 4
0 1 0 0 0 1 7 6 4 9 1 3
0 0 1 0 0 0 4 5 1 4 3
0 1 1 0 0 0 9
21.1. 0 1 0 1 1 1 2. 1 5 15 3. 5 3 6 7
1 0 0 1 0 0 11 12 6 5 1 2 4
0 0 0 1 1 0 3 2 3 1 5 6
1 1 1 0 1 0 9 8 6 2 5 3
1 0 1 1 0 1 7 7 4 6 3
1 0 0 0 1 0 10
22.1 0 0 1 0 1 0 2. 3 4 1 5 9 3. 7 2 11 3
0 0 0 0 0 0 1 2 1 6 7 3 4
0 1 0 0 1 1 4 2 1 3 2 3 1 5
0 1 0 0 0 1 2 3 1 11 1 3
1 1 1 0 0 0 2 2 1 6 3 4 5 3
0 0 0 1 1 0 1 5 1 1
2 1 1 2
23.1. 0 0 1 0 1 0 2. 4 9 3 1 3. 1 9 4 5
0 0 0 1 0 1 3 2 1 4 1 8 7
1 0 0 0 1 0 1 1 10 14 1 9 8 10 1
0 1 0 0 0 1 3 1 1 4 10 13
1 0 1 0 0 0 2 1 5 5 7 1 13
0 1 0 1 0 0 3 1 2
2 2
24.1 0 0 1 0 1 0 2. 8 10 3 12 3. 3 2 4 6
0 0 0 1 0 0 1 1 2 3 3 5 6 3
0 1 0 0 1 0 2 1 1 2 2 5 1 7
0 0 0 0 0 1 1 1 1 15 4 6 1 4
0 1 1 0 0 0 1 2 2 6 3 7 4
0 1 0 0 0 0 1 8
2 1 1 2
25.1. 0 0 1 0 0 1 2. 5 4 2 2 10 3. 1 2 8 5
0 0 1 1 1 1 2 1 2 1 1 3 4
1 1 0 0 0 0 2 1 1 3 2 3 1 5
0 1 0 0 0 1 12 2 1 1 8 1 3
0 1 0 0 0 1 2 2 1 6 5 4 5 3
1 1 0 1 1 0 1 5 1 1
2 1 1 2
26.1. 0 0 0 0 1 0 2. 4 9 8 3 2 3. 2 9 3 5
0 0 0 1 0 0 3 2 1 5 2 8 7
1 0 0 0 1 0 2 1 1 9 8 10 1
0 1 0 0 0 1 3 1 1 3 10 12
0 0 0 0 0 0 2 1 5 5 7 1 12
0 1 0 0 0 0 3 2 2
2 2
27.1. 0 0 1 0 1 0 2. 9 8 1 12 3. 1 3 7 2
0 0 1 1 1 1 1 2 2 4 1 5 6 8
1 1 0 0 1 0 2 1 1 2 3 5 1 7
0 1 0 0 0 1 1 1 1 7 6 1 4
1 1 1 0 0 0 1 2 9 2 2 8 7 4
0 1 0 1 0 0 1 8
2 1 1 2
28.1. 0 1 1 0 1 1 2. 3 5 12 20 3. 1 6 5 14
1 0 0 1 0 0 13 8 1 3 4 6
1 0 0 1 1 1 5 3 6 3 10 12
0 1 1 0 1 1 10 9 5 4 10 6
1 0 1 1 0 1 8 14 6 12 6
1 0 1 1 1 0 11
29.1. 0 1 0 0 1 0 2. 1 8 6 7 3. 2 3 4 5
1 0 0 1 0 0 10 4 2 6 9 1
1 0 0 0 1 1 5 3 1 3 6 1 4
0 1 0 0 0 1 7 6 4 9 1 3
0 0 1 0 0 0 4 5 1 4 3
0 1 1 0 0 0 9
30.1. 0 1 0 1 1 1 2. 2 4 13 3. 5 3 6 4
1 0 0 1 0 0 11 12 6 5 1 2 7
0 0 0 1 1 0 3 2 3 1 5 6
1 1 1 0 1 0 9 8 6 2 5 3
1 0 1 1 0 1 7 4 7 6 3
1 0 0 0 1 0 10
4. Раздел «Булевы функции»
Для данной формулы булевой функции
а) найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований;
б) найти СДНФ, СКНФ табличным способом (сравнить с СДНФ, СКНФ, полученными в пункте “а”);
в) указать минимальную ДНФ и соответствующую ей переключательную схему.
Варианты заданий
|
Функция |
Функция |
|
|
1. ((x V y) Й--Шz) V x&y&z 2.--Ш(x&(y Й(xVz))) 3. (x Й(z&(y x))) 4.--Ш(xy) Й (xVz) 5.--Ш(x Й y) V (y Й z) 6. (x&y) Й (Ш(x&z) x) 7. (y Йx) (x Й z) 8. (x&Шy) Й ((ШxVz) & y) 9. Ш(xy) Й (xVz) 10. Ш(x& y) Й ((xVz)Й y) 11.x Й(y Й (z Й--y&z)) 12. ((y& Шz) Й--(xVШz)) Й--y 13. Ш(x&(y Й--(x z))) 14. (x Й(x&(yV--Ш(x y)Vx))) 15. Ш(x Й z) V Ш(y z) |
16. Ш(xy) Й (xVz) 17. x&y Й (Шx&z Й (xVy)) 18. (y Йx) (Шx Й z) 19. (x&Шy Й z) Й (x z) 20. Ш(x&y Й z) Й (x Й y) 21. Шx Й(y Й (z x)) 22. y&Шz Й--(xVШz&y) 23. Ш(x&(y Й(z y))) 24. x Й(x&(yV--Ш(x z))) 25. Ш(x Й y)V Ш(y&(xz)) 26. Ш(x y) Й Ш(x z) 27. Ш(x Й--y) Й (x&z) 28. x Й(z Й(x V--y&z)) 29. x&(y Й(z y)) 30. Ш(x Й z) V (y z) |
Вопросы к экзамену по дисциплине «Дискретная математика»
1. Основные понятия теории множеств: множества, подмножества, пустое множество, универсальное множество, множество-степень.
2. Способы задания множеств.
3. Операции над множествами.
4. Геометрическое моделирование множеств. Диаграммы Эйлера - Венна.
5. Алгебра множеств. Основные тождества алгебры множеств.
6. Эквивалентность множеств. Свойство транзитивности. Мощность множества.
7. Мощность объединения конечных множеств.
8. Эквивалентность множества точек отрезков и интервалов. Теорема Бернштейна.
9. Счетные множества. Теоремы о счетных множествах.
10. Мощность множества точек отрезка [0, 1]. Теорема Кантора.
11. Множества мощности континуума. Теоремы о множествах мощности континуума.
12. Отношения. Основные понятия и определения. Бинарные отношения. Область определения, область значений и область задания бинарного отношения.
13. Операции над отношениями. Обратное отношение, Композиция отношений.
14. Свойства отношений. Рефлексивность, симметричность, транзитивность, эквивалентность.
15. Классы эквивалентности. Разбиение множеств.
16. Отношение частичного порядка.
17. Функция как бинарное отношение. Область определения и область значений функции. Равенство функций.
18. Сюръективные, инъективные, биективные функции.
19. Обратная функция. Композиция функций.
20. Способы задания функций.
21. Определение графа. Различные типы графов.
22. Матричные способы задания графов.
23. Изоморфизм графов.
24. Маршруты, циклы в неориентированном графе.
25. Пути, контуры в ориентированном графе.
26. Связность неориентированного графа. Матрица связности.
27. Связность ориентированного графа. Матрицы односторонней и сильной связности..
28. Экстремальные пути в нагруженных ориентированных графах.
29. Алгоритм Форда - Беллмана нахождения минимального пути.
30. Деревья. Остовные деревья.
31. Минимальное остовное дерево. Алгоритм Краскала.
32. Определение булевой функции. Операции над булевыми функциями.
33. Формулы логики булевых функций.
34. Равносильные преобразования формул булевых функций.
35. Двойственность. Принцип двойственности.
36. Булева алгебра (алгебра логики). Полные системы булевых функций.
37. Нормальные формы формул булевых функций.
38. Разложение булевой функции по переменным.
39. Алгоритм Квайна построения сокращенной ДНФ.
40. Алгоритм Квайна - Мак-Класки построения сокращенной ДНФ.
41. Алгоритм построения минимальной ДНФ с помощью таблицы покрытий.
42. Применение алгебры булевых функций к релейно-контактным схемам.
Список рекомендованной литературы
1. Акимов О.Е. Дискретная математика: логика, группы, графы. - М.: Лаборатория Базовых Знаний, 2001.
2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоиздат, 1988.
3. Липский В. Комбинаторика для программистов. - М.: Мир, 1988.
4. Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: Издательство МАИ, 1992.
5. Новиков Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2002.
6. Судоплатов С.В., Овчинникова В.В. Элементы дискретной математики. - М.: ИНФРА - М, Новосибирск: Изд-во НГТУ, 2002.
Краткие сведения о математиках
Арнольд Владимир Игоревич - математик, академик Российской Академии наук.
Беллман Ричард - американский математик.
Буль Джордж (1815 - 1864) - английский математик. Основатель математической логики.
Гильберт Давид (1862 - 1943) - немецкий математик. Его исследования оказали большое влияние на развитие многих разделов математики, особенно на развитие логических основ математики.
Дейкстра Эдсгер (1930 - 2002) - голландский ученый, виднейший специалист в области программирования, лауреат премии Тьюринга.
Декарт Рене (1596 - 1650) - французский математик и философ. Впервые ввел понятия переменной, функции, системы координат на плоскости.
Кантор Георг (1845 - 1918) - немецкий математик. Разработал теорию бесконечных множеств. Идеи Кантора оказали большое влияние на развитие математики.
Колмогоров Андрей Николаевич (1903 - 19 ) - советский математик, академике АН СССР. Основополагающее значение имеют работы в области теории вероятностей. Является автором фундаментальных работ по теории множеств, теории меры, конструктивной логике, топологии, механике, теории дифференциальных уравнений, функциональному анализу.
Фибоначчи (Леонардо Пизанский) (1180 - 1240) - итальянский математик. Основные работы - трактаты об арифметике, алгебре и геометрии, которые являются первыми произведениями, содержащими задачи на приложения алгебры и геометрии.
Эйлер Леонард (1707 - 1783) - математик, физик, механик, астроном. Родился в Швейцарии, с 1726 по 1741 г. и с 1776 по 1783 г. работал в России.
Размещено на allbest.ru
...Подобные документы
Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.
курсовая работа [109,1 K], добавлен 22.01.2016Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.
учебное пособие [702,6 K], добавлен 29.04.2009Потоки в сетях, структура и принципы формирования алгоритма Форда-Фалкерсона, особенности его реализации программным методом. Минимальные остовные деревья. Алгоритм Борувки: понятие и назначение, сферы и специфика практического использования, реализация.
курсовая работа [311,3 K], добавлен 15.06.2015Метод Форда-Беллмана для нахождения расстояния от источника до всех вершин графа. Алгоритмы поиска расстояний и отыскания кратчайших путей в графах. Блочно-диагональный вид и матрица в исследовании системы булевых функций и самодвойственной функции.
курсовая работа [192,1 K], добавлен 10.10.2011Свойства операций над множествами. Формулы алгебры высказываний. Функции алгебры логики. Существенные и фиктивные переменные. Проверка правильности рассуждений. Алгебра высказываний и релейно-контактные схемы. Способы задания графа. Матрицы для графов.
учебное пособие [1,5 M], добавлен 27.10.2013Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
курсовая работа [1,8 M], добавлен 18.01.2013Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация [430,0 K], добавлен 19.11.2013Вид графов, используемых в теории электрических цепей, химии, вычислительной технике и в информатике. Основные свойства деревьев. Неориентированный граф. Алгоритм построения минимального каркаса. Обоснование алгоритма. Граф с нагруженными ребрами.
реферат [131,8 K], добавлен 11.11.2008Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
курсовая работа [701,9 K], добавлен 27.04.2011Понятия теории графов. Понятия смежности, инцидентности и степени. Маршруты и пути. Матрицы смежности и инцедентности. Алгоритм поиска минимального пути в ненагруженном ориентированном орграфе на любом языке программирования, алгоритм фронта волны.
курсовая работа [466,3 K], добавлен 28.04.2011Изучение основных вопросов теории графов и области ее применения на практике. Разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера. Результаты тестирований работы данного алгоритма.
курсовая работа [362,9 K], добавлен 24.11.2010Булевы алгебры – решетки особого типа, применяемые при исследовании логики (как логики человеческого мышления, так и цифровой компьютерной логики), а также переключательных схем. Минимальные формы булевых многочленов. Теоремы абстрактной булевой алгебры.
курсовая работа [64,7 K], добавлен 12.05.2009Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.
реферат [106,0 K], добавлен 27.11.2008Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
курсовая работа [278,1 K], добавлен 21.02.2009Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.
учебное пособие [1,3 M], добавлен 20.08.2014Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007Графическая интерпретация множеств и операций над ними. Математическая логика, булева алгебра. Совершенная конъюнктивная нормальная форма. Равносильные формулы и их доказательство. Полнота системы булевых функций. Логика предикатов, теория графов.
лекция [253,7 K], добавлен 01.12.2009Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа [272,5 K], добавлен 05.06.2014
