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

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

(СибАДИ)

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

Кафедра КИАС

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

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

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

Выполнила:

студентка группы ПИб-11И1

Вахрушева С.С.

Проверила: доцент

Палий И.А.

Омск-2012

Оглавление

Глава 1. Задания по графам 3

Глава 2. Логические исчисления 13

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

Описание программы: 17

Блок-схема подпрограммы1(функция maxim(a,b)) 19

Блок-схема подпрограммы2(функция f(x, y)) 19

Блок-схема основной части программы: 20

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

Примеры выполнения программы 23

Глава 1. Задания по графам

Вариант 2

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

																						Матрица 1
			1			2			3			4			5			6			7		8	9	10
1			−			−			5			−			9			−			4		1	−	−
2			4			−			−			−			2			−			2		3	−	−
3			1			−			−			−			−			9			−		−	1	−
4			−			5			−			−			−			−			6		−	10	−
5			2			−			3			7			−			−			4		−	10	4
6			−			6			5			−			−			−			7		−	1	3
7			−			−			10			9			−			−			−		1	−	9
8			−			5			−			−			5			−			−		−	−	−
9			1			−			−			8			7			−			−		−	−	−
10			9			1			8			3			9			5			−		−	−	−

Шаг 1: р = 1 d(3) = min(∞; 5) = 5 d(5) = min(∞; 9) = 9 d(7) = min(∞; 4) = 4 d(8) = min(∞; 1) = 1

Шаг 2: р = 8 d(2) = min(∞; 1 + 5) = 6 d(5) = min(9; 1 + 5) = 6

Шаг 3: р = 7 d(3) = min(5; 4 + 10) = 5 d(4) = min(∞; 4 + 9) = 13 d(10) = min(∞; 4 + 9) = 13

Шаг 4: р = 3 d(6) = min(∞; 5 + 9) = 14 d(9) = min(∞; 5 + 1) = 6

Шаг 5: р = 9 d(4) = min(13; 6 + 8) = 13 d(5) = min(6; 6 + 7) = 6

Шаг 6: р = 2 d(5) = min(6; 6 + 2) = 6

Шаг 7: р = 5 d(4) = min(13; 6 + 7) = 13 d(10) = min(13; 6 + 4) = 10

Шаг 8: р = 10 d(4) = min(13; 10 + 3) = 13 d(6) = min(14; 10 + 5) = 14

Шаг 9: р = 4 Нет дуг в неупорядоченные вершины. Минимальная временная метка d(6) = 14, поэтому след. шаг: р = 6

1

2

3

4

5

6

7

8

9

10

1

0^+

∞

∞

∞

∞

∞

∞

∞

∞

∞

р = 1

2

0^+

∞

5

∞

9

∞

4

1^+

∞

∞

р = 8

3

0^+

6

5

∞

6

∞

4^+

1^+

∞

∞

р = 7

4

0^+

6

5^+

13

6

∞

4^+

1^+

∞

13

р = 3

5

0^+

6

5^+

13

6

14

4^+

1^+

6^+

13

р = 9

6

0^+

6^+

5^+

13

6

14

4^+

1^+

6^+

13

р = 2

7

0^+

6^+

5^+

13

6^+

14

4^+

1^+

6^+

13

р = 5

8

0^+

6^+

5^+

13

6^+

14

4^+

1^+

6^+

10^+

р = 10

9

0^+

6^+

5^+

13^+

6^+

14

4^+

1^+

6^+

10^+

р = 4

10

0^+

6^+

5^+

13^+

6^+

14^+

4^+

1^+

6^+

10^+

р = 6

Д ерево:

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

																							Матрица 1
		1			2			3			4			5			6			7		8		9	10
1		−			−			5			−			9			−			4		1		−	−
2		4			−			−			−			2			−			-2		3		−	−
3		1			−			−			−			−			9			−		−		1	−
4		−			5			−			−			−			−			6		−		10	−
5		-2			−			3			7			−			−			4		−		10	4
6		−			6			5			−			−			−			7		−		-1	3
7		−			−			10			9			−			−			−		1		−	9
8		−			5			−			−			5			−			−		−		−	−
9		1			−			−			8			7			−			−		−		−	−
10		9			1			8			3			9			5			−		−		−	−

d^≤2(2) = min(∞; 1+5) = 6

d^≤2(3) = min(5; 9+3; 4+10) = 5

d^≤2(4) = min(∞; 9+7; 4+9) = 13

d^≤2(5) = min(9; 1+5) = 6

d^≤2(6) = min(∞; 5+9) = 14

d^≤2(7) = min(4; 9+4) = 4

d^≤2(8) = min(1; 4+1) = 1

d^≤2(9) = min(∞; 5+1; 9+10) = 6

d^≤2(10) = min(∞; 9+4; 4+9) = 13

d^≤3(2) = min(6; 13+5; 14+6; 13+1) = 6

d^≤3(3) = min(5; 6+3; 14+5; 13+8) = 5

d^≤3(4) = min(13; 6+7; 6+8; 13+3) = 13

d^≤3(5) = min(6; 6+2; 6+7; 13+9) = 6

d^≤3(6) = min(14; 13+5) = 14

d^≤3(7) = min(4; 6-2; 13+6; 6+4; 14+7) = 4

d^≤3(8) = min(1; 6+3) = 1

d^≤3(9) = min(6; 13+10; 6+10; 14-1) = 6

d^≤3(10) = min(13; 6+4; 14+3) = 10

d^≤4(2) = min(6; 10+1) = 6

d^≤4(3) = min(5; 10+8) = 5

d^≤4(4) = min(13; 10+3) = 13

d^≤4(5) = min(6; 10+9) = 6

d^≤4(6) = min(14; 10+5) = 14

	1	2	3	4	5	6	7	8	9	10
≤1	0	∞	5	∞	9	∞	4	1	∞	∞
≤2	0	6	5	13	6	14	4	1	6	13
≤3	0	6	5	13	6	14	4	1	6	10
≤4	0	6	5	13	6	14	4	1	6	10
	0	2	1	2	2	2	1	1	2	3

Д ерево:

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

Матрица 2

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

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

= min(7; 2+9) = 7

= min(∞; 2+8) = 10

= min(∞; 2+1) = 3

= min(∞; -3+8) = 5

= min(6; -3+1) = -2

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

= min(∞; -1+2) = 1

= min(6; -1+7) = 6

= min(1; -1+3) = 1

= min(∞; 1+2) = 3

= min(∞; 1+7) = 8

= min(5; 1+10) = 5

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

= min(8; 9+5) = 8

= min(1; 9-2) = 1

= min(2; 7-3) = 2

= min(10; 7+5) = 10

= min(3; 7-2) = 3

= min(1; 6-3) = 1

= min(1; 6-2) = 1

= min(3; 8-3) = 3

= min(5; 8+5) = 5

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

D₅

1

2

3

4

5

1

0

2

9

6

1

2

2

0

7

8

3

3

-3

-1

0

3

-2

4

1

-1

6

0

1

5

3

1

8

5

0

Деревья:

1 ) 5)

2 )

3 )

4 )

Задание 4. Метод ветвей и границ: Отыскать гамильтонов контур наименьшей длины, пользуясь алгоритмом ветвей и границ (матрица 3).

										Матрица 3
		1		2		3		4		5	6	7
1		∞		11		2		12		14	4	5
2		1		∞		1		11		12	6	4
3		9		7		∞		12		11	8	6
4		5		11		6		∞		2	10	2
5		4		9		7		7		∞	9	4
6		7		3		2		6		3	∞	5
7		9		10		6		10		12	7	∞

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

Приведенная матрица:

	1	2	3	4	5	6	7
1	∞	8	0^1	7	12	1	3
2	0^0	∞	0^0	7	11	4	3
3	3	0^0	∞	3	5	1	0^0
4	3	8	4	∞	0^1	7	0^0
5	0^0	4	3	0^1	∞	4	0^0
6	5	0^0	0^0	1	1	∞	3
7	3	3	0^0	1	6	0^1	∞

1

2

4

5

6

7

2

0³

∞

7

11

4

3

3

∞

0⁰

3

5

1

0⁰

4

3

8

∞

0¹

7

0⁰

5

0⁰

4

0¹

∞

4

0⁰

6

5

0¹

1

1

∞

3

7

3

3

1

6

0²

∞

	2	4	5	6	7
3	∞	3	5	1	0^0
4	8	∞	0^1	7	0^0
5	4	0^1	∞	4	0^0
6	0^4	1	1	∞	3
7	3	1	6	0^2	∞

	4	5	6	7
3	3	5	∞	0^3
4	∞	0^5	7	0^0
5	0^1	∞	4	0^0
7	1	6	0^5	∞

	4	6	7
3	3	∞	0
5	∞	4	0^0
7	1	0	∞
	1

	4	6	7
3	2	∞	0^2
5	∞	4	0^4
7	0^2	0^4	∞

4

6

3

2

∞

7

∞

0

Возвращаемся и запрещаем дугу (1,3) в приведенной матрице. Приводим на 1 первую строку.

	1	2	3	4	5	6	7
1	∞	7	∞	6	11	0^2	2
2	0^0	∞	0^0	7	11	4	3
3	3	0^0	∞	3	5	1	0^0
4	3	8	4	∞	0^1	7	0^0
5	0^0	4	3	0^1	∞	4	0^0
6	5	0^0	0^0	1	1	∞	3
7	3	3	0^0	1	6	0^0	∞

1

2

3

4

5

7

2

0⁰

∞

0⁰

7

11

3

3

3

0⁰

∞

3

5

0⁰

4

3

8

4

∞

0¹

0⁰

5

0⁰

4

3

0¹

∞

0⁰

6

∞

0⁰

0⁰

1

1

3

7

3

3

0¹

1

6

∞

	1	2	3	4	7
2	0^0	∞	0^0	7	3
3	3	0^0	∞	3	0^0
5	0^0	4	3	∞	0^0
6	∞	0^0	0^0	1	3
7	3	3	0^1	1	∞
				1

1

2

3

4

7

2

0⁰

∞

0⁰

6

3

3

3

0⁰

∞

2

0⁰

5

0⁰

4

3

∞

0⁰

6

∞

0⁰

0⁰

0⁰

3

7

3

3

0⁰

0⁰

∞

	2	3	4	7
3	0^3	∞	2	0^0
5	4	3	∞	0^0
6	∞	0^0	0^0	3
7	3	0^0	0^0	∞

	3	4	7
5	3	∞	0^6
6	∞	0^3	3
7	0^3	0^0	∞

3

4

6

∞

0³

7

0³

∞

П олучился контур:

7→3→2→1→6→4→5

6+7+1+4+6+2+4 = 30