TechShape.ru

Информационные технологии

Основные разделы

Корректирующие коды. Линейные групповые коды. Код Хэмминга

𝑝	𝑞	𝑟
И	И	И	И
И	И	Л	Л
И	Л	И	И
И	Л	Л	И
Л	И	И	Л
Л	И	Л	Л
Л	Л	И	И
Л	Л	Л	Л

В дизъюнктивной нормальной форме:

1б. Система множеств {x1, x2, …, xn} наз. разбиением множества А, если она удовлетворяет след. условиям:

) Любое множество X{x1, x2, …, xn} явл. помножеством мн-ва А.

) Любые два мн-ва Xi, Xj{x1, x2, …, xn}явл. непересекающимися.

) Объединение всех мн-в, входящих в разбиение, дает мн-во А.

Задано мн-во 𝐴 = {1, 2, 3, 4, 5, 6, 7}:

а) {{1, 2}, {3, 4, 5}, {6, 7}} - эта совокупность элементов составляет разбиение мн-ва А, т.к. удовлетворяет всем условиям, приведенным выше.

б) {{1, 5}, {3, 4, 5}, {2, 6, 7}} - эта совокупность элементов не явл. разбиением А, т.к. не удовлетворяет условию непересекаемости.

2а. Ориентированные пути графа (с указанием длины пути):

v1v2(1), v1v4(1), v1v2v3(2), v1v2v4(2), v1v2v3v4(3), v2v3(1), v2v4(1), v2v3v4(2),

v3v4(1), v5v1(1), v5v3(1), v5v3v4(2), v5v2(1), v5 v1v2(2), v5v1v4(2), v5

v1v2v3(3), v5 v1v2v4(3), v5 v1v2v3v4(4), v5 v2v3(2), v5 v2v4(2), v5v2v3v4(3).

Для заданного графа невозможно построить цикл

2б

Идея алгоритма Уоршелла состоит в расширении множества промежуточных вершин по следующему правилу: на каждом шаге в рассмотрение добавляется одна новая вершина, после чего достижимости вершин пересчитываются “через нее”. Если w - промежуточная вершина, то достижимость вершины v из вершины u через w пересчитывается по правилу: D[u;v] = D[u;v] ИЛИ (D[u;w] И D[w;v]). Таким образом, получаем матрицу достижимости:

Перейти на страницу: 1 2 3 4 5

Еще статьи

Понятие и типы микропроцессорных устройств
Замечательным свойством микропроцессорных устройств является их высокая гибкость, возможность быстрой перенастройки при необходимости даже значительных изменений алгоритмов управления. Перенастройка осуществляется программным путем без существенных производственных затрат. Создание микропроцессоров ...