Контрольная работа по дискретной математике

Задание 1.

1. Задать представленный граф: перечислением, матрицей смежности и инцидентности. (Рис. 1)
2. Определить следующие характеристики графа: число ребер (дуг), вершин, коэффициент связности, степени всех вершин, цикломатическое число. (Рис. 1)
3. Произвести реберную и вершинную раскраски графа с определением вершинного и реберного хроматического числа. (Рис. 1)
4. Определить метрические характеристики графа: диаметр, радиус, эксцентриситет каждой вершины, центральные вершины). (Рис. 1)

Задание 2.

Определение кратчайшего пути из одной вершины в другую (алгоритм Дейкстры). (Рис. 2)

Задание 3.

Написать программу для машины Тьюринга.

Замечания:

а) В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.

б) Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек – должно быть выписано столько палочек, какова величина числа; например: 2 ® | | , 5 ® | | | | | , 0 ® áпустое словоñ.

1.1 A={a,b,c}. Приписать слева к слову P символ b (P ® bP). 1.2 A={a,b,c}. Приписать справа к слову P символы bc (P ® Pbc). 1.3 A={a,b,c}. Заменить на a каждый второй символ в слове P. 1.4 A={a,b,c}. Оставить в слове P только первый символ (пустое слово не менять). 1.5 A={a,b,c}. Оставить в слове P только последний символ (пустое слово не менять). 1.6 A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе. 1.7 A={a,b,c}. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да, входит) или пустое слово (нет). 1.8 A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a. 1.9 A={a,b,0,1}. Определить, является ли слово P идентификатором (непустым словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет). 1.10 A={a,b,0,1}. Определить, является ли слово P записью числа в двоичной системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ: слово 1 (да) или слово 0. 1.11 A={0,1}. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть. 1.3 Задачи для самостоятельного решения 21 1.12 A={0,1}. Для непустого слова P определить, является ли оно записью степени двойки (1, 2, 4, 8, …) в двоичной системе счисления. Ответ: слово 1 (является) или слово 0. 1.13 A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0.