Теория кодирования и графов

Теория кодирования:
- минимальное расстояние кода
- кодирование, декодирование с матрицей 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, применяя алгоритм Форда-Беллмана.