Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» icon

Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики»


Скачать 36.27 Kb.
НазваниеРасчетно-графическая работа по дисциплине «Алгоритмы дискретной математики»
Размер36.27 Kb.
ТипДокументы

Расчетно-графическая работа по дисциплине
«Алгоритмы дискретной математики»


Часть 1. Алгоритмы оптимизации на сетях и графах.

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



Вариант

SA

SC

SD

AB

AF

AG

BC

BG

CT

DF

FG

GT

1

1

4

6

3

5

1

3

5

4

1

3

7

2

2

4

5

4

2

1

3

4

2

1

1

5

3

2

1

6

2

4

5

1

2

1

2

3

7

4

3

2

5

1

2

5

1

5

1

5

1

5

5

6

5

2

1

4

5

6

1

2

2

4

2

6

5

2

3

2

1

2

3

5

4

2

2

1

7

1

5

5

2

5

1

3

4

3

1

2

6

8

5

2

3

1

4

1

2

1

4

2

1

4

9

4

5

3

2

1

4

5

6

4

1

2

1

10

3

4

6

3

4

1

2

5

4

1

2

6

11

2

5

7

4

5

2

3

6

3

2

4

8

12

2

3

6

1

2

3

4

5

3

2

3

1

13

2

3

4

5

1

2

3

4

5

1

3

4

14

1

3

5

2

4

1

2

3

2

1

2

6

15

2

5

4

3

4

2

2

2

3

2

2

5

16

1

2

6

3

5

2

2

3

4

1

3

4

17

3

3

5

2

6

1

3

4

5

2

4

2

18

2

1

5

2

5

1

1

5

2

3

5

7

19

2

4

6

3

4

3

3

2

1

4

1

5

20

1

2

3

4

4

4

3

6

3

4

2

6


2. Постройте поток минимальной стоимости из вершины s в вершину t в графе, используя алгоритм поиска потока минимальной стоимости.



Вариант

SA

SB

AD

AC

CD

CE

BE

DT

ET

1

2, 3

3, 4

2, 2

2, 3

4, 3

3, 4

3, 4

2, 3

3, 4

2

3, 2

2, 1

1, 1

3, 1

2, 3

1, 2

2, 1

3, 4

4, 3

3

1, 2

3, 2

4, 2

3, 2

1, 2

4, 3

3, 2

4, 3

2, 3

4

3, 4

1, 1

2, 3

2, 3

3, 2

2, 3

3, 1

2, 1

3, 3

5

2, 3

3, 1

2, 1

3, 4

4, 3

1, 2

2, 1

2, 1

4, 2

6

3, 4

2, 1

3, 1

3, 1

2, 2

3, 2

1, 1

3, 2

3, 2

7

1, 2

1, 1

2, 2

3, 2

1, 2

1, 2

2, 3

3, 1

2, 2

8

4, 3

2, 2

2, 3

3, 4

1, 2

3, 4

3, 4

2, 1

2, 3

9

2, 3

1, 2

3, 4

2, 3

4, 3

1, 1

4, 3

1, 1

3, 2

10

1, 2

1, 2

4, 3

2, 2

3, 3

2, 2

2, 1

2, 2

3, 3

11

3, 2

3, 1

2, 1

2, 1

4, 2

1, 2

3, 4

2, 3

2, 3

12

4, 3

2, 1

3, 2

3, 4

3, 1

1, 2

4, 3

3, 4

1, 3

13

3, 3

2, 2

2, 3

4, 3

2, 2

2, 1

2, 1

2, 3

2, 3

14

4, 2

1, 2

2, 1

2, 1

2, 3

3, 2

2, 2

1, 2

3, 4

15

3, 3

1, 2

4, 1

2, 3

3, 4

2, 3

2, 3

2, 3

4, 3

16

2, 2

1, 1

3, 1

3, 4

2, 3

2, 1

3, 4

2, 2

2, 3

17

1, 2

1, 3

3, 2

1, 2

1, 2

3, 1

2, 3

2, 3

3, 4

18

2, 2

2, 2

3, 4

4, 3

3, 2

3, 2

1, 2

3, 4

4, 3

19

1, 2

2, 3

4, 1

1, 2

4, 3

2, 3

2, 4

2, 3

2, 3

20

1, 3

2, 2

4, 2

3, 2

3, 2

3, 4

2, 2

1, 2

3, 4


3. Найдите методом ветвей и границ оптимальное решение задачи коммивояжера на графе.



Часть 2. Теория кодирования.

1. C помощью процедуры Хаффмана построить код с минимальной избыточностью для заданных P и q. Определить среднюю длину кодового слова. Построить кодовое дерево.



Вариант

P

q

1

Р= (0,23; 0,22; 0,18; 0,17; 0,08; 0,04; 0,02; 0,02; 0,02; 0,02)

4

2

Р = (0,3; 0,3; 0,2; 0,04; 0,03; 0,03; 0,03; 0,03; 0,03; 0,01)

2

3

Р = (0,2; 0,2; 0,1; 0,1; 0,1; 0,1; 0,08; 0,06; 0,06)

3

4

Р= (0,24; 0,21; 0,20; 0,15; 0,08; 0,04; 0,02; 0,02; 0,02; 0,02)

4

5

Р= (0,4; 0,2; 0,1; 0,08; 0,06; 0,04; 0,04; 0,04; 0,04)

2

6

Р = (0,5; 0,2; 0,1; 0,09; 0,08; 0,03)

2

7

Р= (0,24; 0,21; 0,20; 0,15; 0,08; 0,04; 0,02; 0,02; 0,02; 0,02)

4

8

Р= (0,3; 0,2; 0,2; 0,1; 0,1; 0,05; 0,05)

2

9

Р = (0,21; 0,20; 0,17; 0,16;0,12; 0,08; 0,04; 0,02)

4

10

Р= (0,4; 0,3; 0,08; 0,06; 0,04; 0,04; 0,04; 0,04)

2

11

Р= (0,20; 0,15; 0,15; 0,13; 0,12; 0,11; 0,11; 0,03)

4

12

Р = (0,4; 0,2; 0,1; 0,1; 0,05; 0,05; 0,05; 0,05)

2

13

Р = (0,5; 0,1; 0,1; 0,1; 0,1; 0,1)

2

14

Р = (0,3; 0,2; 0,1; 0,1; 0,06; 0,06; 0,06; 0,06; 0,06)

2

15

Р = (0,4; 0,2; 0,1; 0,1; 0,1; 0,1)

3

16

Р = (0,2; 0,20; 0,17; 0,15;0,13; 0,08; 0,04; 0,03)

4

17

Р = (0,3; 0,3; 0,1; 0,1; 0,1; 0,1)

3

18

Р= (0,23; 0,22; 0,21; 0,14; 0,09; 0,03; 0,02; 0,02; 0,02; 0,02)

4

19

Р = (0,3; 0,2; 0,1; 0,1; 0,1; 0,1; 0,1)

4

20

Р = (0,4; 0,1; 0,1; 0,1; 0,1; 0,08; 0,06; 0,06)

3



2. а) Закодировать данное слово α кодом Хэмминга.

б) По каналу связи передавалось кодовое слово, построенное по методу Хэмминга для сообщения α. После передачи по каналу связи, искажающему слово не более чем в одном разряде, было получено слово β. Восстановить исходное сообщение.

в) Пользуясь кодом Хэмминга найти ошибку в сообщении γ.



Вариант

α

β

γ

1

101 0001 1101

10 1110

111 1011 0010 1100

2

100 0011 0100

10 1000

111 0010 0101 1001

3

110 1011 1001

01 0010

110 0110 1101 0001

4

010 0101 1100

11 1010

110 0001 1111 1100

5

100 0011 0011

01 1000

110 0110 0001 1001

6

100 1111 0001

00 0110

010 0011 1101 0101

7

110 0011 1101

11 1010

110 0110 1100 1110

8

100 0010 1010

10 0110

111 0011 0010 0110

9

001 0111 1101

01 1001

001 0110 1111 1110

10

111 0111 0101

11 1011

010 1000 0111 1100

11

001 0100 1011

00 0101

101 1011 0010 1001

12

111 1110 0000

11 1100

100 1011 1110 1000

13

010 1110 0101

00 1001

100 0101 0101 1111

14

011 0100 1100

11 1101

010 0111 0101 1011

15

111 1110 0110

10 1001

111 1110 0111 1000

16

101 1001 1100

11 0110

110 0111 1101 0111

17

110 1100 0100

01 1010

011 0111 0111 1010

18

011 0110 0001

11 0101

001 1011 1000 1100

19

010 1001 0101

01 1001

111 0111 0101 1011

20

011 1100 1010

11 1110

110 1000 1111 1100



Примечание:

V1 = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27… - все числа у которых первый разрядравен 1

V2 = 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27… - все числа, у которых второй разряд равен 1

V3 = 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28… - все числа, у которых третий разряд равен 1

V4 = 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28… - все числа, у которых четвертый разряд равен 1,

V5 = 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 … - все числа, у которых пятый разряд равен 1.


Часть 3. Теория автоматов.

1. По данной кодовой комбинации α построить дешифратор с входным алфавитом {x, y} и записать его диаграммой состояний и таблицей состояний.

2. Для данного конечного автомата, заданного таблично, со множеством внутренних состояний {1,2,3,4,5,6,7,8,9}, входным алфавитом {a, b} и выходным алфавитом {x, y}:

а) Выяснить, является ли автомат сильно связным.

б) Построить эквивалентный минимальный автомат.

в) Проверить работу исходного и минимального автоматов над словом «bbabaab».



Вариант

α




1

xxyxxyyx



2

yxyxxyxy



3

yxyyxxyx



4

xyxxxyxy



5

xxxyxxyx



6

yxyyyxxx



7

xyyxyyxy



8

yxyyyyxx



9

xyyyxyxy



10

yxyyyxxy



11

yyxyyxxx



12

xyyyxxyy



13

yyxxyyyx



14

xyxxyyxy



15

yyyxxxyy



16

xyxyyxyx



17

yxxyxyyy



18

xxxyyyxy



19

yxyyxxyx



20

xyyxxyyx





Законченная расчетно-графическая работа в виде пояснительной записки – в бумажном виде не позже 15-й недели семестра предъявляется руководителю. После проверки работы студенту назначается время защиты.

В случае обнаружения недочетов, неверно рассчитанных характеристик и параметров, а также в случае наличия в тексте пояснительной записки большого числа грамматических ошибок, работа возвращается на доработку.

Среднее время самостоятельной работы студента на выполнение расчетно-графических работ 20 часов.

Похожие:

Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» iconРасчетно-графическая работа по дисциплине «Алгоритмы дискретной математики»
Найти кратчайшие пути между вершинами графа, используя алгоритмы Дейкстры и Флойда
Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» iconЗадания на расчётно-графическую работу
Расчётно-графическая работа состоит из двух разделов. Задания расчётно-графической работы выполняются с помощью электронной таблицы...
Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» iconРасчетно-графическая работа по дисциплине «сопротивление материалов» по теме : «Расчет стержней на прочность»
Государственное образовательное учреждение высшего профессионального образования омский государственный технический университет
Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» iconРасчётно-графическая работа

Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» iconРасчетно-графическая работа

Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» iconРасчетно-графическая работа по дисциплине «Налогообложение физических лиц» для студентов заочной формы обучения курса ( семестр) специальности 080107 «Налоги и налогообложение»
Дисциплина «Налогообложение физических лиц» углубляет знания студентов в области
Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» iconРасчетно-графическая работа (транспортная логистика) Задача 1
Всего продукции на складе 900 контейнеров, грузоподъемность транспортного средства 300 контейнеров. За минимальное количество рейсов...
Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» iconКурсовая расчетно-графическая работа по гидрогазодинамике
Затем излагается ход расчета. При этом сначала должна быть записана общая формула, а затем значения всех величин, входящих в нее....
Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» iconМетодические указания к выполнению расчетно-графических заданий для студентов очной формы
В течение семестра по дисциплине «Бухгалтерский учет и анализ» студенты должны выполнить два расчетно-графических задания (ргз):...
Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» iconКафедра химии и процессов горения курсовая работа по дисциплине «Физико-химические основы развития и тушения пожаров» Тема: Расчет параметров выгорания жидкостей и газов Расчетно
...
Расчетно-графическая работа по дисциплине «Алгоритмы дискретной математики» iconРасчетно-графические работы по дисциплине: «Инженерная и компьютерная графика»

Вы можете разместить ссылку на наш сайт:
Документы


При копировании материала укажите ссылку ©ignorik.ru 2015

контакты
Документы