МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к выполнению контрольной работы по дисциплине
«Дискретная математика»
для студентов заочной формы обучения
направления 27.03.04-Управление в технических системах
Севастополь
УДК 681.5
Методические указания к выполнению контрольной работы по дисциплине
«Дискретная математика» для студентов заочной формы обучения направления 27.03.04-Упарвление в технических системах/Сост. А.И.Грушун, Т.А.Грушун.-Севастополь:Изд-во СевНТУ, 2015.- 7с.
В методических указаниях к выполнению контрольной работы содержатся индивидуальные задания, а также рассматриваются примеры их решения.
Указания предназначены для студентов заочной формы обучения направления подготовки 27.03.04-Управление в технических системах.
Указания рассмотрены и утверждены на заседании кафедры информатики и управления в технических системах (протокол №5 от 9 января 2015 г.).
Рецензент: Кожаев Е.А. канд. техн. наук, доцент.
СОДЕРЖАНИЕ
1. | Цель указаний | |
2. | Методические рекомендации | |
3. | Задание на выполнение работы | |
Библиографический список |
1. ЦЕЛЬ УКАЗАНИЙ
Обучение студентов методам решения задач прикладной дискретной математики, являющейся необходимым математическим базисом образования бакалавра в области управления в технических системах.
2. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ
Методические указания содержат ряд задач Дискретной математики, которые позволяют закрепить приобретенные теоретические знания на конкретных примерах.
Индивидуальный вариант определяется конкретно в каждом задании. Также в каждом задании приводится пример решения типовой задачи.
Если решение типовой задачи вам непонятно, необходимо обратиться к соответствующему разделу теории и еще раз разобраться в теоретическом материале.
Если и после этого вы не можете решить задачу, необходимо обратиться за консультацией к ведущему преподавателю.
Теоретические сведения, необходимые для выполнения работы, приведены в [1, 2, 3, 4].
ЗАДАНИЕ НА ВЫПОЛНЕНИЕ РАБОТЫ
3.1 Представить число, заданное двумя последними цифрами номера Вашей зачетной книжки в 2, 8, 16 и 2-10 системах счисления, используя разложения на целые степени p, согласно формуле значимости.
Приведем пример для числа 146:
3.2 Перевести число с помощью алгоритмов умножения и деления из 10-ной системы счисления в 8-ную, 2-ную и 16-ную. Исходное десятичное число формируется следующим образом: целая часть соответствует последним трем цифрам номера вашей зачетной книжки, дробная – последним двум цифрам номера вашей зачетной книжки.
Например, переведем в 8-ную систему число 314.159.
Переводом числа из р-ной системы счисления в q-ную назовем построение числа в q-ной системе, представляющего ту же величину, что и исходное число р-ной системы. Для выполнения этой операции число р-ной системы разбивают на целую часть и дробную и каждую часть переводят отдельно.
Целую часть делим на q, получая остаток и целое частное. Остаток используется для формирования значения очередной цифры целой части q-ного числа, начиная с младшей. Результат деления (частное) снова делят на q, получая очередные остаток и частное. Процесс продолжается до тех пор, пока очередное частное не станет равным нулю. Все операции осуществляются в р-ной системе счисления. Переводим целую часть заданного числа:
Дробную часть числа переводим из р-ной в q-ную, умножая ее на основание q. Целая часть произведения используется для построения очередной цифры q-ного числа, начиная со старшей, с дробной частью проводим те же действия. Умножения дробной части проводим в исходной р-ной системе счисления. Преобразование дробной части заканчивается, когда достигается необходимая точность представления q-ного числа. Например, если в р-ной системе k разрядов дробной части, то в q-ной количество разрядов будет равно s, значение которого определяется по следующему неравенству: p-k £ q-s, т.е. s ³k*logq p.
Для нашего примера: 10 -3 £ 2 -s, s ³ 4.
Переводим дробную часть заданного числа:
3.3 Просуммировать само с собой двоичное число, полученное в задании 3.1.
Так же как для 10-ной системы, арифметика двоичной системы определяется двумя таблицами – сложения и умножения:
10 – означает, что разряд суммы равен 0, однако возникает единица переноса в следующий разряд. При сложении очередных (i-х) разрядов двоичных чисел A и B участвуют значения ai и bi и перенос pi-1 из предыдущего разряда. Формируются значения сi разряда суммы и перенос pi в следующий разряд.
Например:
Здесь А и В – восьмиразрядные двоичные слагаемые, С – восьмиразрядная двоичная сумма, Р – соответствующий двоичный вектор переносов между разрядами в процессе суммирования.
3.4Двоичное число, полученное в задании 3.2 контрольной работы, представить в форме с плавающей точкой.
Общая структура представления чисел с плавающей точкой имеет следующий вид: <знак порядка><порядок> <знак числа><мантисса>.
Примеры:
Двоичное число Форма плавающей точки
3.5 С помощью волнового алгоритма построить кратчайший путь для взвешенного графа, представленного на рисунке 1. Варианты весов дуг исследуемого графа представлены в таблице 1, номер варианта соответствует последней цифре номера зачетной книжки.
Рисунок 1 – Исследуемый граф
Таблица 1 - Варианты весов дуг исследуемого графа
Номер вари- анта | Вес дуги (х1,х2) | Вес дуги (х1,х3) | Вес дуги (х2,х3) | Вес дуги (х2,х4) | Вес дуги (х3,х4) | Вес дуги (х3,х5) | Вес дуги (х4,х5) | Вес дуги (х4,х6) | Вес дуги (х5,х6) |
Рассмотрим формулировку алгоритма построения кратчайшего пути для взвешенного графа.
- Начальная вершина хн (хн=х1) получает вес V н =0, ее номер вводится в массив М номеров вершин, изменивших вес. Остальные вершины хi получают вес V i =¥ и их номера не попадают в массив М.
- Если массив М пуст, то выполняется пункт 3, иначе выбирается с исключением из него очередная вершина хi и пересчитываются веса вершин, принадлежащих исходу G(хi) вершины хi:
" хj Î G(хi) (V j =min(V j, V i + lij)).
Если вес V j уменьшается, то номер j включается с приведением
подобных в М. Снова выполняется пункт 2. Вершины исхода G(хi) для вершины хi это вершины, в которые подходят дуги из вершины хi.
- Если вес V k =¥, то делается вывод, что пути из вершины хн к конечной вершине хk нет. Иначе выполняется процедура выделения дуг, то есть выделяются те дуги и вершины хj и хi, разность весов которых равна lij. После выделения дуг строятся кратчайшие пути, длины которых равны V k.
Рассмотрим пример. Задан взвешенный граф, представленный на рисунке 1. Веса дуг этого графа следующие: l12 =1, l13 =4, l23 =2, l24 =5, l34 =2, l35 =4, l45 =1, l46 =4, l56 =2.
1. V н = V 1 =0, М={1}, V 2 = V 3 = V 4 = V 5 = V 6 =¥.
2.
2.1. М¹0, i =1, M=0, G(х1)={ х2,х3 };
V 2 =min(¥, 0+1)=1, М={2};
V 3 =min(¥, 0+4)=4, М={2,3}.
2.2. М¹0, i =2, M={3}, G(х2)={ х3,х4 };
V 3 =min(4, 1+2)=3, М={3};
V 4 =min(¥, 1+5)=6, М={3,4}.
2.3. М¹0, i =3, M={4}, G(х3)={ х4,х5 };
V 4 =min(6, 3+2)=5, М={4};
V 5 =min(¥, 3+4)=7, М={4,5}.
2.4. М¹0, i =4, M={5}, G(х4)={ х5,х6 };
V 5 =min(7, 5+1)=6, М={5};
V 6 =min(¥, 5+4)=9, М={5,6}.
2.5. М¹0, i =5, M={6}, G(х5)={ х6 };
V 6 =min(9, 6+2)=8, М={6}.
2.6. М¹0, i =6, M=0, G(х6)=0.
2.7. М=0 и выполняется пункт 3.
- Для иллюстрации выполнения пункта 3 изобразим граф с весами вершин, полученными в результате решения (рисунок 2). Вершины входа G-1(хi) для вершины хi это вершины, из которых подходят дуги к вершине хi.
Рисунок 2 – Нахождение кратчайшего пути в графе
3.1. Начинаем с конечной вершины хk=х6: G-1(х6)= { х4,х5 };
(l46 =4)¹(V 6 - V 4 =3), поэтому дуга (х4,х6) не выделяется;
(l56 =2)=(V 6 - V 5 =2) и дуга (х5,х6) выделяется, одновременно выделяется вершина х5.
3.2. Для выделенной вершины х5: G-1(х5)= { х3,х4 };
(l35 =4)¹(V 5 - V 3 =3), дуга (х3,х5) не выделяется;
(l45 =1)=(V 5 - V 4 =1), выделяется дуга (х4,х5) и вершина х4.
3.3. Для выделенной вершины х4: G-1(х4)= { х2,х3 };
(l24 =5)¹(V 4 - V 2 =4), дуга (х2,х4) не выделяется;
(l34 =2)=(V 4 - V 3 =2), выделяется дуга (х3,х4) и вершина х3.
3.4. Для выделенной вершины х3: G-1(х3)= { х1,х2 };
(l13 =4)¹(V 3 - V 1 =3), дуга (х1,х3) не выделяется;
(l23 =2)=(V 3 - V 2 =2), выделяется дуга (х2,х3) и вершина х2.
3.5. Для выделенной вершины х2: G-1(х2)= { х1 };
(l12 =1)¹(V 2 - V 1 =1), выделяется дуга (х1,х3) не выделяется;
(l23 =2)=(V 3 - V 2 =2), выделяется дуга (х2,х1).
Построен кратчайший путь длиной 8:
(хн=х1,х2)(х2,х3)(х3,х4)(х4,х5)(х5,х6 = хk).