Практическое занятие 12.

Рубежная аттестация №1.

Вариант 0

1. Граф G₁ задан графически.

1) Задать G₁: а) аналитически; б) с помощью матрицы смежности; в) с помощью списка дуг; г) с помощью структуры смежности.

2) Для графа G₁ записать аналитически и изобразить графически некоторый подграф и некоторую часть графа, которая не является подграфом графа G₁.

2. Для графов G₁ и G₂ найти (записать аналитически и изобразить графически) G₁∩G₂, G₁∪G₂, G₁⊕G₂, G₁+G₂, G₁×G₂, G₁[G₂].

3. Над графом G₁ выполнить следующие унарные операции: а) удалить ребро (2,3); б) добавить ребро (1,2); в) удалить вершину 3; г) добавить вершину 5; д) ввести вершину 6 в ребро (3,4); е) отождествить вершины 3 и 2; ж) расщепить вершину 2 по разбиению Vʹ={1, 4}, Vʹʹ={3}; з) найти .

4. Для графа G₁ найти матрицу маршрутов длины 3 и все маршруты длины 3.

5. Для графа G₁ найти все сильные компоненты.

6. Для графа G найти: а) матрицу расстояний; б) эксцентриситеты всех вершин; в) диаметр и радиус; г) периферийные и центральные вершины.

7. 1) Для графа G найти: а) один из остовов; б) матрицу фундаментальных циклов; в) матрицу фундаментальных разрезов.

2) Установить, является ли граф эйлеровым.

G₁ G₂ G

8. Даны целые числа a=3653 и b=3107. Найти:

а) наибольший общий делитель a и b;

b) линейное представление наибольшего общего делителя a и b;

с) наименьшее общее кратное a и b.

9. Для натурального числа n=22869 найти:

1) число τ(n) всех натуральных делителей;

2) сумму σ(n) всех натуральных делителей;

3) количество φ(n) натуральных чисел, меньших n и взаимно простых с n.

10. Вычислить, не переводя в десятичную систему счисления:

(23054₍₇₎+4326₍₇₎) – 25651₍₇₎: 56₍₇₎.

11. Выяснить, является ли кодирование со схемой взаимно однозначным. Если нет, то указать слово, декодируемое неоднозначно:

: , , , , , , .

12. Построить схему оптимального префиксного алфавитного кодирования по методу Хаффмена для распределения вероятностей Р=(0,26; 0,20; 0,17; 0,15; 0,07; 0,05; 0,04; 0,03; 0,02; 0,01) появления букв алфавита в сообщении при 4-ичном кодировании.

13. Дано распределение вероятностей Р=(0,29; 0,24; 0,14; 0,13; 0,09; 0,05; 0,02; 0,02; 0,01; 0,01) появления букв алфавита в сообщении. Построить схему алфавитного кодирования по алгоритму Фано.

14. Построить по методу Хэмминга код сообщения .

15. По каналу связи передавалось кодовое слово, построенное по методу Хэмминга для сообщения . Было получено кодовое слово . Восстановить слово .