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

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

Сибирская государственная автомобильно-дорожная академия

(СибАДИ)

Факультет ИСУ

Кафедра КИАС

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

по дисциплине «Дискретная математика»

на тему: «Алгоритмы дискретной математики»

Выполнила: студентка группы ПИб-11И1

Окунев С.A.

Проверила: доцент Палий И.А.

Омск 2012

Содержание

• Задание 1 Алгоритм Дейкстры
• Задание 2 Алгоритм Беллмана
• Задание 3 Алгоритм Флойда
• Задание 4 Метод ветвей и границ
• 2. Логические исчисления
• Задание 1
• Построение таблиц истинности
• Метод от противного
• Задание 2
• Задание 3
• 3. Задание по программированию
• Блок-схема программы
• Листинг программы

• Задание 1 Алгоритм Дейкстры
• Определить кратчайшие пути от вершины 1 до всех остальных вершин графа, используя алгоритм Дейкстры. Построить дерево кратчайших путей. Отрицательные длины в матрице заменить положительными (матрица 1).
• Матрица 1

	1	2	3	4	5	6	7	8	9	10
1	?	6	?	?	?	?	?	7	?	1
2	3	?	2	2	?	?	-1	?	?	10
3	5	3	?	?	?	2	?	?	3	?
4	?	7	7	?	?	?	-2	2	?	?
5	5	5	?	-2	?	2	?	?	?	?
6	7	5	?	?	?	?	3	?	?	?
7	?	?	?	?	3	?	?	5	2	3
8	?	?	?	?	?	2	?	?	10	9
9	?	5	?	?	10	?	7	3	?	7
10	?	?	?	7	3	6	1	?	8	?

Шаг 1: p = 1 d(1) = 0

Шаг 2: p = 10 d(2) = min(?; 0 + 6) = 6 d(8) = min(?; 0 + 7) = 7 d(10) = min(?; 0 + 1) = 1

Шаг 3: p = 7 d(4) = min(?; 1 + 7) = 8 d(5) = min(?; 1 + 3) = 4 d(6) = min(?; 1 + 6) = 7 d(7) = min(?; 1 + 1) = 2 d(9) = min(?; 1 + 8) = 9

Шаг 4: p = 5 d(5) = min(4; 2 + 3) = 4 d(8) = min(7; 2 + 5) = 7 d(9) = min(9; 2 + 2) = 4

Шаг 5: p = 9 d(2) = min(6; 5 + 4) = 6 d(4) = min(8; 4 + 2) = 6 d(4) = min(7; 4 + 2) = 6 d(9) = min(4; 4 + ?) = 4

Шаг 6: p = 2 d(2) = min(6; 4 + 5) = 6 d(8) = min(7; 4 + 3) = 7

Шаг 7: p = 4 d(3) = min(?; 6 + 2) = 8 d(4) = min(6; 6 + 2) = 6

Шаг 8: p = 6 d(3) = min(8; 6 + 7) = 8 d(8) = min(7; 6 + 2) = 7 d(6) = min(6; 6 + 2) = 6

Шаг 9: p = 8 d(8) = min(7; 6 + ?) = 7

Шаг 10: p = 3 d(3) = min(8; 7 + ?) = 8

1

2

3

4

5

6

7

8

9

10

P

1

0+

?

?

?

?

?

?

?

?

?

p=1

2

0+

6

?

?

?

?

?

7

?

1+

p=10

3

0+

6

?

8

4

7

2+

7

9

1+

p=7

4

0+

6

?

8

4+

7

2+

7

4

1+

p=5

5

0+

6

?

6

4+

6

2+

7

4+

1+

p=9

6

0+

6+

?

6

4+

6

2+

7

4+

1+

p=2

7

0+

6+

8

6+

4+

6

2+

7

4+

1+

p=4

8

0+

6+

8

6+

4+

6+

2+

7

4+

1+

p=6

9

0+

6+

8

6+

4+

6+

2+

7+

4+

1+

p=8

10

0+

6+

8+

6+

4+

6+

2+

7+

4+

1+

p=3

• Дерево:
• Задание 2 Алгоритм Беллмана
• Определить кратчайшие пути от вершины 1 до всех остальных вершин графа, пользуясь алгоритмом Беллмана. Построить дерево кратчайших путей (матрица 1).

• Матрица 1

	1	2	3	4	5	6	7	8	9	10
1	?	6	?	?	?	?	?	7	?	1
2	3	?	2	2	?	?	-1	?	?	10
3	5	3	?	?	?	2	?	?	3	?
4	?	7	7	?	?	?	-2	2	?	?
5	5	5	?	-2	?	2	?	?	?	?
6	7	5	?	?	?	?	3	?	?	?
7	?	?	?	?	3	?	?	5	2	3
8	?	?	?	?	?	2	?	?	10	9
9	?	5	?	?	10	?	7	3	?	7
10	?	?	?	7	3	6	1	?	8	?

• d^?2(3) = min(?; 6+2) = 8
• d^?2(4 = min(?; 6+2;1+7) = 8
• d^?2(5) = min(?; 1+3) = 4
• d^?2(6) = min(?; 7+2;1+6) = 7
• d^?2(7) = min(?; 6-1;1+1) = 2
• d^?2(9) = min(?; 7+2;1+8) = 9
• d^?2(10) = min(1; 6+1;1+9) = 1

• d^?3(2) = min(6;8+3;8+7;4+5;7+5;9+5) = 6
• d^?3(3) = min(8;8+7) = 8
• d^?3(4) = min(8;4-2) = 2
• d^?3(5) = min(4;2+3;9+10) = 4
• d^?3(6) = min(7;8+2;4+2) = 6
• d^?3(7) = min(2;8-2;7+3;9+2) = 2
• d^?3(8) = min(7; 8+2;2+5;9+3) = 7
• d^?3(9) = min(9;8+3;2+2) =4
• d^?3(10) = min(1;2+3;9+7) = 1
• d^?4(2) = min(6;2+7;6+5;4+5) = 6
• d^?4(3) = min(8;2+7) = 8
• d^?4(5) = min(4;4+10) = 4
• d^?4(7) = min(2;2-2;6+3;4+7) = 0
• d^?4(8) = min(7;2+2;4+3) = 7
• d^?4(10) = min(1;4+7) = 1
• d^?5(5) = min(4;0+3) = 3
• d^?5(6) = min(6;4+2) = 6
• d^?5(8) = min(4;0+5) = 5
• d^?5(9) = min(4;0+2) = 2
• d^?5(10) = min(1;0+3;4+9) = 1
• d^?6(2) = min(6;3+5;2+5) = 6
• d^?6(4) = min(2;3-2) = 1
• d^?6(5) = min(3;2+10) = 3
• d^?6(6) = min(6;3+2) = 6
• d^?6(7) = min(0;2+7) = 0
• d^?6(8) = min(4;2+3) = 4
• d^?6(10) = min(1;2+7) = 1

• d^?7(2) = min(6;3+5;2+5) = 6
• d^?7(3) = min(8;1+7) =8
• d^?7(7) = min(0;1-2;5+3) = -1
• d^?7(8) = min(4;1+2) = 3
• d^?8(5) = min(3;-1+3) = 2
• d^?8(6) = min(5;3+2) = 5
• d^?8(8) = min(3;-1+5) = 3
• d^?8(9) = min(2;-1+2;3+10) = 1
• d^?8(10) = min(1;-1+3;3+9) = 1
• d^?9(2) = min(6;2+5;1+5) = 6
• d^?9(4) = min(1;2-2) = 0
• d^?9(5) = min(2;1+10) = 2
• d^?9(6) = min(5;2+2) = 4
• d^?9(7) = min(-1;1+7) = -1
• d^?9(8) = min(3;1+3) = 3
• d^?9(10) = min(1;1+7) = 1
• d^?10(2) = min(6;0+7;5+4) = 6
• d^?10(3) = min(8;0+7) =7
• d^?10(7) = min(0;0-2;4+3) = -2
• d^?10(8) = min(3;0+2) = 2

	1	2	3	4	5	6	7	8	9	10
?1	0	6	?	?	?	?	?	7	?	1
?2	0	6	8	8	4	7	2	7	9	1
?3	0	6	8	2	4	6	2	7	4	1
?4	0	6	8	2	4	6	0	4	4	1
?5	0	6	8	2	3	6	0	4	2	1
?6	0	6	8	1	3	5	0	4	2	1
?7	0	6	8	1	3	5	-1	3	2	1
?8	0	6	8	1	2	5	-1	3	1	1
?9	0	6	8	0	2	4	-1	3	1	1
?10	0	6	7	0	2	4	-2	2	1	1


• Задание 3 Алгоритм Флойда
• Определить кратчайшие пути между всеми парами вершин графа, используя алгоритм Флойда. Построить деревья кратчайших путей (матрица 2).
• Матрица 2

	1	2	3	4	5
1	?	3	?	-1	8
2	?	?	9	6	?
3	8	?	?	1	?
4	?	?	1	?	2
5	7	-1	?	3	?

D0	1	2	3	4	5
1	0	9	?	-1	8
2	?	0	9	6	?
3	8	?	0	1	?
4	?	?	1	0	2
5	7	-1	?	9	0

D1	1	2	3	4	5
1	0	3	?	-1	8
2	8	0	9	6	?
3	8	11	0	1	16
4	?	?	1	0	2
5	7	-1	?	3	0

• = min(?; 8+3) = 11
• = min(1; 8-1) = 1
• = min(?; 8+8) = 16
• = min(-1; 7+3) = -1
• = min(3; 7-1) = 3

D2	1	2	3	4	5
1	0	3	12	-1	8
2	?	0	9	6	?
3	8	11	0	7	?
4	?	?	1	0	2
5	7	-1	16	3	0

• = min(?; 3+9) = 12
• = min(-1; 3+6) = -1
• = min(1; 11+6) = 1
• = min(?; 7+9) = 16
• = min(3; 7+6) = 3

D3	1	2	3	4	5
1	0	3	12	-1	8
2	17	0	9	6	?
3	8	11	0	7	?
4	9	12	1	0	2
5	7	-1	16	3	0

• = min(3; 12-11) = 3
• = min(-1; 12+7) = -1
• = min(?; 9+8) = 17
• = min(6; 9-1) = 6
• = min(?; 1+8) = 9
• = min(?; 1+11) = 12
• = min(7; 16+8) = 7
• = min(-1; 16+11) = -1
• = min(3; 16+7) = 3

D4	1	2	3	4	5
1	0	3	0	-1	1
2	15	0	7	6	8
3	8	11	0	7	9
4	9	12	1	0	2
5	7	-1	16	3	0

• = min(3; -1+12) = 3
• = min(12; -1+1) = 0
• = min(8; -1+2) = 1
• = min(17; 6+9) = 15
• = min(9; 6+1) = 7
• = min(?; 6+2) = 8
• = min(8; 7+9) = 8
• = min(11; 7+12) = 11
• = min(?; 7+2) = 9
• = min(7; 3+9) = 7
• = min(-1; 3+12) = -1
• = min(16; 3+1) = 4

D5	1	2	3	4	5
1	0	0	0	-1	1
2	15	10	7	6	8
3	8	8	0	7	9
4	9	1	1	0	2
5	7	-1	4	3	0

• = min(3; 1-1) = 0
• = min(0; 1+4) = 0
• = min(-1; 1+3) = -1
• = min(15; 8+7) = 15
• = min(7; 8+4) = 7
• = min(6; 8+3) = 6
• = min(8; 9+7) = 8
• = min(11; 9-1) = 8
• = min(7; 9+3) = 7
• = min(9; 2+7) = 9
• = min(12; 2-1) = 1
• = min(1; 2+4) = 1
• Деревья:
• 1) 5)
• 2)
• 3)
• 4)
• 
• Задание 4 Метод ветвей и границ
• Отыскать гамильтонов контур наименьшей длины, пользуясь алгоритмом ветвей и границ (матрица 3).
• Матрица 3

	1	2	3	4	5	6	7
1	?	14	7	15	8	15	10
2	2	?	9	2	15	5	12
3	12	1	?	13	10	4	4
4	13	6	1	?	15	15	12
5	8	14	12	2	?	3	5
6	6	11	4	11	5	?	4
7	3	12	10	3	15	7	?

	1	2	3	4	5	6	7
1	?	14	7	15	8	15	10	7
2	2	?	9	2	15	5	12	2
3	12	1	?	13	10	4	4	1
4	13	6	1	?	15	15	12	1
5	8	14	12	2	?	3	5	2
6	6	11	4	11	5	?	4	4
7	3	12	10	3	15	7	?	3

	1	2	3	4	5	6	7
1	?	7	0	8	1	8	3
2	0	?	7	0	8	3	5
3	11	0	?	12	9	3	3
4	12	5	0	?	14	14	11
5	6	12	10	0	?	1	3
6	2	7	0	7	1	?	0
7	0	9	7	0	12	4	?
1	1

	1	2	3	4	5	6	7
1	?	7	03	8	03	7	3
2	00	?	7	00	7	2	5
3	11	08	?	12	8	2	3
4	12	5	05	?	13	13	11
5	6	12	10	00	?	03	3
6	2	7	00	7	00	?	03
7	00	9	7	00	11	3	?

• Минимальная длина контуров, содержащая дугу при ветви (3,2) равна 22
• Минимальная длина контуров не содержащая дугу при ветви (3,2) равна 22+8=30

	1	3	4	5	6	7
1	?	00	8	00	7	3
2	02	?	00	7	2	5
4	12	012	?	13	13	11
5	6	10	00	?	02	3
6	2	00	7	00	?	03
7	00	7	00	11	3	?

• Минимальная длина контуров, которая содержит дугу при ветви (4,3) будет равна 22
• Минимальная длина контуров не содержащая дугу при ветви (4,3) равна 22+12=34

	1	4	5	6	7
1	?	8	03	7	3
2	02	?	7	2	5
5	6	01	?	02	3
6	2	7	00	?	03
7	00	00	11	3	?

• Минимальная длина контуров, которая содержит дугу при ветви (1,5) будет равна 22
• Минимальная длина контуров не содержащих дугу при ветви (1,5) равна 22+3=26

	1	4	6	7
2	02	?	2	5
5	?	00	02	3
6	2	7	?	05
7	00	00	3	?

• Минимальная длина контуров, которая содержит дугу при ветви (6,7) будет равна 22
• Минимальная длина контуров не содержащая дугу при ветви (6,7) равна 22+5=27

	1	4	6
2	02	?	2
5	?	00	02
7	00	00	?

• Минимальная длина контуров, которая содержит дугу при ветви (5,6) будет равна 22
• Минимальная длина контуров не содержащая дугу при ветви (5,6) равна 22+2=24

	1	4
2	0	?
7	?	0

• Минимальная длина контуров, которая содержит дугу при ветви (5,6) будет равна 22.

• 8 + 3 + 4 + 3 + 1 + 1 + 2 = 22
• 4>3>2>1>5>6>7



2. Логические исчисления

Вариант 7

Задание 1. Доказать или опровергнуть данные логические следствия, используя два метода: анализ таблицы истинности; от противного.

· ¦ ;

· ¦ .

Построение таблиц истинности:

1. ¦

A	B	C	D
0	0	0	0	1	1	0	0	1
0	0	0	1	1	0	0	1	0
0	0	1	0	1	0	1	0	0
0	0	1	1	1	1	1	1	1
0	1	0	0	0	1	0	1	0
0	1	0	1	0	0	0	1	0
0	1	1	0	0	0	1	1	1
0	1	1	1	0	1	1	1	1
1	0	0	0	0	1	1	0	0
1	0	0	1	0	0	1	1	1
1	0	1	0	0	0	1	0	0
1	0	1	1	0	1	1	1	1
1	1	0	0	1	1	1	1	1
1	1	0	1	1	0	1	1	1
1	1	1	0	1	0	1	1	1
1	1	1	1	1	1	1	1	1

Формула , является логическим следствием .

A	B	C
0	0	0	1	1	1	1	1	1	1	0	0	0
0	0	0	1	1	1	1	1	1	1	0	0	0
0	0	1	1	1	1	1	1	1	1	0	0	0
0	0	1	1	1	1	1	1	1	1	0	0	0
0	1	0	1	0	0	1	1	1	1	1	0	1
0	1	0	1	0	0	1	1	1	1	1	0	1
0	1	1	1	0	1	1	1	1	1	1	0	1
0	1	1	1	0	1	1	1	1	1	1	0	1
1	0	0	0	1	1	1	0	1	1	0	1	1
1	0	0	0	1	1	1	0	1	1	0	1	1
1	0	1	0	1	1	1	0	1	1	0	1	1
1	0	1	0	1	1	1	0	1	1	0	1	1
1	1	0	0	0	0	0	1	0	1	0	0	0
1	1	0	0	0	0	0	1	0	1	0	0	0
1	1	1	0	0	1	0	1	1	0	0	0	0
1	1	1	0	0	1	0	1	1	0	0	0	0

¦ .

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

Метод от противного:

1. ¦

Предположим, что = 0. Это значит, что =0, а =1 или =1, а =0.

Если =0 следовательно A=C=0.

Если В=1 и D=1, тогда =0, =0.

Если B=0 и D=1, тогда =0.

Если В=1 и D=0, тогда =0.

Если =0, тогда B=0 и D=0.

Предположим, что А=С=1, тогда А=В=0 и =0.

Теперь предположим, что А=1, С=0, тогда =0.

Теперь предположим, что А=0, С=1, тогда =0.

Исходя из этого можно сделать вывод, что формула =0, а =1 является логическим следствием .

2. ¦ .

Предположим, что =0, это значит что эти обе части равны 0.

Рассмотрим такой вариант, что В=0, а =1, тоесть тоже самое что А=0 и В=0, тогда из =1, =1, , тоесть С=0 либо С=1.

Если С=0, то из =1.

Если С=1, то из =1.

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

Задание 2 Ввести необходимые обозначения и записать каждое из высказываний как формулу исчисления предикатов. Обосновать справедливость (ложность) заключения при помощи диаграмм Эйлера-Венна

Некоторые писатели - женщины. Все женщины любят цветы. Следовательно, среди тех, кто любит цветы, есть писатели.

Решение:

А(х) = «х - женщина»

В(х) = «х любит цветы»

С(х) = «х - писатель»

Некоторые писатели женщины

( х) ( А(х) & С(х) ) 1

(х) ( А(х) В(х) ) 2

() ( В(х) & С(х) ) 3

( ( А(х) & С(х) ), (х) ( А(х) В(х) ) () ( В(х) & С(х) )

А - множество женщин

В - множество любителей цветов

С - множество писателей

а с

а в

в с

Задание 3

Пусть предметная область , «x < y». Рассмотреть все варианты одновременной квантификации переменных двухместного предиката . Определить истинность получаемых выражений.

Q(x,y) = x < y

1. (( Q(x,y) = Л. «Какой бы мы не взяли х, любой у будет больше х» = Ложь

2. Q(x,y) = «Найдется х, что для него найдется у, такой что у > х» = Истина.

3. ( Q(x,y) = «Для любого х, найдется у > х» = Истина.

4. Q(x,y) = «Найдется х, что любой у будет больше х» = Ложь.

5. Q(x,y) = «Для любого у, найдется х меньше у» = Истина.

6. ( Q(x,y) = «Найдется у, больший любого х» = Ложь.



3. Задание по программированию

дискретный математика граф алгоритм

Программирование алгоритма дискретной математики

Задание:

Общие положения. При выполнении задания необходимо

1. Подробно описать алгоритм.

2. Подробно описать программу, реализующую алгоритм: типы и структуры данных, блок-схему программы и т.п.

3. Привести листинг программы.

4. Привести результаты решения не мене трех тестовых примеров с различными исходными данными.

Индивидуальное задание(вариант 7):

Квадратная подматрица. Вводится матрица a(m,n) из 0 и 1. Найти в ней квадратную подматрицу из одних единиц максимального размера.



Блок-схема программы





Листинг программы

#include <stdlib>

#include <stdio>

#include "time.h"

#include "conio.h"

#include "iostream.h"

int TestRectangle(bool **array, int i_begin, int j_begin, int i_end, int j_end) {

for (int i = i_begin; i

курсовая работа "Алгоритмы дискретной математики" скачать



Подобные документы

• Алгоритмы на графах

  Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.
  
  презентация [36,1 K], добавлен 16.09.2013
  

• Метод Форда-Беллмана нахождения расстояния от источника до всех вершин графа

  Метод Форда-Беллмана для нахождения расстояния от источника до всех вершин графа. Алгоритмы поиска расстояний и отыскания кратчайших путей в графах. Блочно-диагональный вид и матрица в исследовании системы булевых функций и самодвойственной функции.
  
  курсовая работа [192,1 K], добавлен 10.10.2011
  

• Поиск кратчайшего пути между парами вершин в ориентированном и неориентированном графах путем использования алгоритма Флойда

  Способы решения задач дискретной математики. Расчет кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах с помощью использования алгоритма Флойда. Анализ задачи и методов ее решения. Разработка и характеристика программы.
  
  курсовая работа [951,4 K], добавлен 22.01.2014
  

• Построение эйлерова цикла. Алгоритм Форда и Уоршелла

  Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.
  
  реферат [108,4 K], добавлен 01.12.2008
  

• Теория графов. Описание графов. Алгоритм Прима-Краскала

  Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
  
  курсовая работа [625,4 K], добавлен 30.09.2014
  

• Алгоритмы на графах. Нахождение кратчайшего пути

  Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
  
  курсовая работа [2,4 M], добавлен 08.10.2014
  

• Графическое представление графа

  Алгоритм перехода к графическому представлению для неориентированного графа. Количество вершин неориентированного графа. Чтение из матрицы смежностей. Связи между вершинами в матрице. Задание координат вершин в зависимости от количества секторов.
  
  лабораторная работа [34,0 K], добавлен 29.04.2011
  

• Дискретная математика

  Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
  
  контрольная работа [463,0 K], добавлен 17.05.2015
  

• Графы. Основные понятия

  Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
  
  лабораторная работа [85,5 K], добавлен 09.01.2009
  

• Задачи и алгоритмы дискретной математики

  Потоки в сетях, структура и принципы формирования алгоритма Форда-Фалкерсона, особенности его реализации программным методом. Минимальные остовные деревья. Алгоритм Борувки: понятие и назначение, сферы и специфика практического использования, реализация.
  
  курсовая работа [311,3 K], добавлен 15.06.2015
  

• Теория графов

  Нахождение минимального пути от фиксированной до произвольной вершины графа с помощью алгоритма Дейкстры, рассмотрение основных принципов его работы. Описание блок-схемы алгоритма решения задачи. Проверка правильности работы разработанной программы.
  
  курсовая работа [495,4 K], добавлен 19.09.2011
  

• Метод Дейкстры нахождения кратчайшей цепи в связанном графе

  Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
  
  курсовая работа [228,5 K], добавлен 30.01.2012
  

• Алгоритм Дейкстры

  Изучение конкретного раздела дискретной математики. Решение 5-ти задач по изученной теме с методическим описанием. Методика составления и реализация в виде программы алгоритма по изученной теме. Порядок разработки программного интерфейса и руководства.
  
  курсовая работа [110,2 K], добавлен 27.04.2011
  

• Решение задач с применением теории графов

  Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
  
  курсовая работа [1,8 M], добавлен 18.01.2013
  

• Дискретная математика

  Общая характеристика распространенных проблем поиска величины максимального потока в сети при помощи алгоритма Форда-Фалкерсона. Знакомство с задачами по дискретной математике. Рассмотрение особенностей и этапов постройки дерева кратчайших расстояний.
  
  контрольная работа [740,3 K], добавлен 09.03.2015
  

• Графы

  Понятия и определения орграфа и неориентированного графа, методы решения. Неориентированные и ориентированные деревья. Подробное описание алгоритмов нахождения кратчайших путей в графе: мультиграф, псевдограф. Матрица достижимостей и контрдостижимостей.
  
  курсовая работа [251,0 K], добавлен 16.01.2012
  

• Изучение функций в курсе математики

  Решения задач дискретной математики: диаграммы Эйлера-Венна; высказывание в виде формулы логики высказываний и формулы логики предикатов; СДНФ и СКНФ булевой функции. При помощи алгоритма Вонга и метода резолюции выяснить является ли клауза теоремой.
  
  контрольная работа [133,5 K], добавлен 08.06.2010
  

• Теория графов

  Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
  
  курсовая работа [225,5 K], добавлен 14.05.2012
  

• Передаточная функция дискретной системы

  Определение связи между выходом и входом для непрерывных систем. Вычисление передаточной функции и основы структурного метода дискретной системы. Расчет передаточной функции дискретной системы с обратной связью. Передаточные функции цифровых алгоритмов.
  
  реферат [67,2 K], добавлен 19.08.2009
  

• Метрические характеристики графа

  Понятие "граф" и его матричное представление. Свойства матриц смежности и инцидентности. Свойства маршрутов, цепей и циклов. Задача нахождения центральных вершин графа, его метрические характеристики. Приложение теории графов в областях науки и техники.
  
  курсовая работа [271,1 K], добавлен 09.05.2015
  

Другие документы, подобные "Алгоритмы дискретной математики"

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам