Лидеры рейтинга

ID: 226425

Konstantin Shvetski

Мастер-Эксперт

939

Россия, Северодвинск


ID: 259041

Алексеев Владимир Николаевич

Мастер-Эксперт

466

Россия, пос. Теплоозёрск, ЕАО


ID: 401284

Михаил Александров

Академик

392

Россия, Санкт-Петербург


ID: 137394

Megaloman

Мастер-Эксперт

328

Беларусь, Гомель


ID: 400669

epimkin

Профессионал

190


ID: 400484

solowey

Профессор

70


ID: 401888

puporev

Профессор

52

Россия, Пермский край


8.1.6

02.01.2021

JS: 2.2.2
CSS: 4.2.0
jQuery: 3.5.1


 

Консультации и решение задач по алгебре, геометрии, анализу, дискретной математике.

Администратор раздела: Коцюрбенко Алексей Владимирович (Старший модератор)


Коцюрбенко Алексей Владимирович
Статус: Старший модератор
Рейтинг: 2154
Konstantin Shvetski
Статус: Мастер-Эксперт
Рейтинг: 939
Михаил Александров
Статус: Академик
Рейтинг: 392
 

Перейти к консультации №:
 

Консультация онлайн # 199800
Раздел: • Математика
Автор вопроса: KoreanLamer (Посетитель)
Дата: 07.12.2020, 08:53
Поступило ответов: 1

Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Установить при помощи алгоритма Маркова, обладает ли данная схема кодирования свойством взаимной однозначности. Если обладает – обосновать при помощи построенного графа, если не обладает – предъявить неоднозначно декодируемое слово и раскодировать его в алфавите сообщений двумя способами

a1a2a3a4a5
b1b2b3b1b2b2b2b3b2b3b3b1b2b2b3

Последнее редактирование 16.12.2020, 16:23 Коцюрбенко Алексей Владимирович (Старший модератор)

Состояние: Консультация закрыта

Здравствуйте, KoreanLamer!

Рассмотрим все возможные разложения кодовых слов:





где в круглых скобках заключены префиксы и суффиксы, а в квадратных - кодовые слова (Λ обозначает пустой префикс, суффикс или кодовое слово). Тогда имеем набор префиксов Λ, b1, b2, b3, b2b2, b2b3, b3b1, b1b2b2 и набор суффиксов Λ, b2, b3, b2b3, b3b3. Построим множество S, содержащее все префиксы, являющиеся одновременно и суффиксами:

Для этого множества построим граф, вершины которого соответствуют элементам множества S, а каждое ребро связывает пару вершин, являющихся префиксом и суффиксом одного и того же кодового слова. В данном случае таких слов будет четыре: (Λ)b1b2(b2b3), (b2b3)Λ(b3), (b3)b1b2(Λ) и (b2)Λ(b2b3).

При этом в графе имеется ориентированный замкнутый цикл, содержащий вершину Λ, которому соответствует кодовая последовательность b1b2b2b3b3b1b2, декодируемая двумя способами: (b1b2)(b2b3b3)(b1b2) → a1a4a1 и (b1b2)(b2b3)(b3b1b2) → a5a2. Следовательно, данная схема кодирования не обладает свойством взаимной однозначности.


Консультировал: Коцюрбенко Алексей Владимирович (Старший модератор)
Дата отправки: 16.12.2020, 18:40

5
Здравствуйте, большое спасибо за помощь
-----
Дата оценки: 17.12.2020, 15:48

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 199800

Коцюрбенко Алексей Владимирович

Старший модератор

ID: 312929

1

= общий = |  12.12.2020, 06:51 |  цитировать |  профиль |  личное сообщение
KoreanLamer:

У Вас в условии задачи одно и тоже кодовое слово b1b2b2b3 повторяется дважды - для a4 и a5. Проверьте, всё ли правильно?

KoreanLamer

Посетитель

ID: 403724

2

= общий = |  12.12.2020, 14:02 |  цитировать |  профиль |  личное сообщение
Коцюрбенко Алексей Владимирович:

Да, ошибся в написании условия
a1| a2 |a3 |a4 |a5
b1b2| b3b1b2 |b2b2b3 |b2b3b3 |b1b2b2b|

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