Теория кодирования и графов
Теория кодирования:
- минимальное расстояние кода
- кодирование, декодирование с матрицей G
- Код Хемминга (кодирование, декодирование)
Теория графов:
- матрица смежности
- матрица индидентности
- матрица достижимости
- матрица сильной связности
- Диаметр, радиус и центры графа
- минимальный путь из одной вершины в другую
- эйлеровость и квазиэйлеровость графа
Машина Тьюринга
Алгебра высказываний:
- таблица истинности
- СДНФ
- СКНФ
- Многочлен Жегалкина
Задание 9
Найти наименьшее расстояние Хемминга для кода, заданного матрицей G и определить количество позиций, в котором код позволяет обнаруживать, исправлять ошибки.
Задание 10
Дан шифр, матрица кода G и закодированное сообщение B. Найти сообщение А и прочитать его.
Используя матрицу кода G и шифр из первого задания закодировать слово а.
Задание Конт.
Построить таблицу истинности.
Упростить, применяя основные равносильности алгебры логики.
Построить СДНФ, СКНФ.
Представить в виде канонического многочлена Жегалкина.
Задание 11
Дан шифр; пришло сообщение с. Декодировать его, используя код Хемминга и расшифровать, используя шифр. Шифр задан в таблице.
Задание Конт.
Определить к какому классу относится код, заданный матрицей G
Декодировать сообщение С (был использован код Хемминга).
Задание 12
Построить матрицы смежности, инцедентности, достижимости, сильной связности графа G.
Задание 13
Найти диаметр, радиус и центры графа.
Задание 14
Найти минимальный путь из вершины 1 в вершину 6, применяя алгоритм Форда-Беллмана.
Задание 15
Определить, является ли граф эйлеровым, квазиэйлеровым.
Задание 16
Машина T1 складывает натуральные числа, записанные в унарной системе счисления, программа машины T1 задана таблицей.
Машина T2 удваивает натуральные числа, записанные в унарной системе счисления, программа машины T2 задана таблицей.
Выписать последовательно возникающие при работе этих таблиц конфигурации на исходном слове U. Машина T1, слово U = 111+1. Машина T2, слово U = 1111.
Задание Конт
Построить матрицы смежности, сильной связности.
Найти диаметр графа.
Найти минимальный путь из вершины 1 в вершину 6, применяя алгоритм Форда-Беллмана.