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

Еще статьи

Интегральные микросхемы
Современный этап научно-технического прогресса характеризуется повсеместным внедрением принципиально новой техники. Ускорение научно-технического прогресса в значительной степени зависит от успехов современной микроэлектроники, являющейся современной элементной базой электронных устройств автоматики, т ...