Коды с обратной связью и задачи комбинаторного поиска тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Лебедев Алексей Владимирович

• Лебедев Алексей Владимирович
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Лебедев Алексей Владимирович

Введение

Глава 1. Задачи комбинаторного поиска - обзор известных

постановок задачи и результатов

1.1 Типы задач поиска

1.1.1 Задачи группового тестирования

1.1.2 Задача Реньи-Улама

1.1.3 Задачи с различной степенью адаптивности

1.1.4 Задачи с различными типами вопросов

1.1.5 Задачи с различными допустимыми видами ошибок

1.1.6 Задачи с различными пространствами поиска

1.1.7 Задачи с различными условиями выигрыша

1.1.8 Задачи поиска на графах

1.1.9 Задачи с движением

1.2 Задачи поиска с точки зрения кодирования

1.3 Заключение

Глава 2. Комбинаторный поиск движущегося элемента

2.1 Задача поиска движущегося элемента с минимальной

суммарной мощностью тестов

2.1.1 Постановка задачи и основные определения

2.1.2 Построение оптимальной стратегии поиска движущегося элемента

2.1.3 Доказательство асимптотической оптимальности построенной стратегии

2.2 Комбинаторный поиск быстрых объектов

2.2.1 Постановка задачи и основные определения

2.2.2 Адаптивный поиск быстрых объектов

2.2.3 Неадаптивный поиск быстрых объектов

2.3 Выводы

Глава 3. Кодирование в канале с мгновенной безошибочной

обратной связью

3.1 Исправление одной ошибки в каналах с обратной связью

3.1.1 Основные определения

3.1.2 Канал с одиночной обратной связью и произвольным графом ошибок

3.1.3 Двоичный симметричный канал с обратной связью

3.1.4 Двоичный асимметричный канал

3.1.5 Недвоичный случай для каналов с обратной связью

3.2 Исправление линейной доли ошибок в асимметричном канале с обратной связью

3.2.1 Основные определения

3.2.2 Коды с низкой скоростью и большим количеством ошибок

3.2.3 Списочно декодируемые коды для асимметричного канала

3.2.4 Двухшаговый алгоритм кодирования

3.3 Выводы

Заключение

Список литературы

Список рисунков

Список таблиц

Введение

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

Задачи поиска определяются следующим образом. Имеется множество объектов, среди которых ищется один или несколько специальных объектов. Поиск ведется с помощью вопросов, на которые отвечает оракул. Традиционно это вопросы с ответами ДА или НЕТ, но есть и варианты поставки задачи с более сложными вопросами. Оракул может отвечать безошибочно, а может и целенаправленно ошибаться, как в известной задаче (игре) Улама-Реньи. Важным является и то, как задаются вопросы: адаптивно, когда известны ответы на все предыдущие вопросы, или же без обучения, когда все вопросы задаются одновременно. Требуется построить алгроитм задания вопросов, который позволяет однозначно найти специальный объект за минимальное число вопросов.

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

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

Целью данной работы является разработка оптимальных алгоритмов поиска движущихся объектов и надежной передачи сообщений для различных моделей каналов с обратной связью.

Достижения данной цели включает в себя решение следующих задач:

1. Для задачи комбинаторного поиска движущегося объекта разработать оптимальный по количеству и суммарной мощности вопросов.

2. Для задачи кодирования в каналах с обратной связью разработать оптимальный метод кодирования при малом числе ошибок в прямом канале.

3. Сравнить оптимальные методы кодирования для двоичного и недвоичного каналов с мгновенной безошибочной обратной связью.

Основные положения, выносимые на защиту:

1. В задаче поиска движущегося элемента, который может перемещаться в любую из соседних вершин графа, для графа - отрезка длины п в явном виде построена асимптотически оптимальная стратегия с суммарной мощностью тестов п + 2\/п, при этом по количеству тестов стратегия также является асимптотически оптимальной.

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

3. Разработан рекурсивный алгоритм передачи сообщений по каналу с мгновенной безошибочной многократной обратной связью и одной ошибкой, передающий максимально возможное число сообщений. Доказано, что для двоичного канала с одной возможной ошибкой двух обратных связей достаточно для передачи такого же числа сообщений, как и при полной обратной связи.

4. Рассмотрены различные обобщения задачи кодирования в каналах с мгновенной безошибочной обратной связью и одной ошибкой на д-ичный случай, и построены оптимальные стратегии передачи сообщений для случая полной обратной связи.

5. Доказано, что для двоичного асимметричного канала с одной обратной связью доля исправляемых ошибок может достигать примерно 0,44 при асимптотически ненулевой скорости передачи информации, тогда как без обратной связи это верно только если доля ошибок меньше 0,25.

Научная новизна:

Все полученные результаты данной работы являются новыми. В частности

1. Найдена оптимальная стратегия с суммарной мощностью тестов п + 2у/п для задачи поиска с движущимся элементом на отрезке длины п.

2. Для задачи комбинаторного поиска движущегося элемента при произвольном числе перемещений построена неадаптивная стратегия с таким же количеством тестов как у оптимальной адаптивной стратегии.

3. Разработан алгоритм для кодирования в каналах с возможной ошибкой и мгновенной безошибочной обратной связью, который обеспечивает передачу максимально возможного числа сообщений.

4. Доказано, что в двоичном канале с мгновенной безошибочной обратной связью и одной ошибкой необходимо и достаточно использовать обратную связь дважды для передачи точно такого же числа сообщений, как и при неограниченном использовании обратной связи.

Научная и практическая значимость

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

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

Введение диссертации (часть автореферата) на тему «Коды с обратной связью и задачи комбинаторного поиска»

Апробация работы.

Основные результаты работы неоднократно докладывались на семинаре ИППИ РАН по теории кодирования под руководством Л. А. Бассалыго в 2019-2023 годах.

Также результаты были представлены на следующих международных конференциях:

1. Algebraic and Combinatorial Coding Theory (ACCT), IEEE, Bulgaria, 2020

2. IEEE International Symposium on Information Theory (ISIT), Melbourne, Victoria, Australia, 2021

3. International Workshop Sphere packings, coverings, and spherical codes (SPCSC), Bulgaria, 2023

4. IEEE International Symposium on Information Theory (ISIT), Taipei, Taiwan, 2023

Личный вклад.

Все основные результаты диссертации были получены автором лично или при непосредственном его участии.

Публикации.

Основные результаты по теме диссертации изложены в 5 печатных трудах, индексируемых базами WoS и Scopus, 3 из которых изданы в журналах, входящих в собственный перечень рекомендованных мфти, 2 — в трудах конференций.

Объем и структура работы.

Диссертация состоит из введения, трёх глав и заключения. Полный объём диссертации составляет 116 страниц с 6 рисунками и 6 таблицами. Список литературы содержит 123 наименования.

Глава 1. Задачи комбинаторного поиска - обзор известных постановок задачи и результатов

1.1 Типы задач поиска

Рассмотрим неформальную постановку задачи как игру двух лиц, см. [1; 2], где первый игрок загадывает один или несколько объектов из известного множества, а второй игрок хочет найти эти объекты. Для этого второй игрок задает вопросы (также оговоренного вида), на которые первый игрок дает ответы. В некоторых постановках задачи часть ответов может быть ложной. Второй игрок выигрывает, если он правильно находит объекты, загаданные первым игроком.

Имеется несколько факторов, которые определяют постановку задачи поиска. Первым таким фактором является пространство поиска как множество объектов, которые могли быть загаданы.

Другим фактором являются возможные типы вопросов и ответов. В классической, двоичной постановке задачи вопрос имеет форму «принадлежит ли загаданный элемент х к данному множеству Т?». Её обобщением является постановка с вопросами вида «к какому из множеств Т\,Т%,... ,Т8 принадлежит ж». Могут возникать дополнительные ограничения, например, на структуру множества Т. Задачи также различаются по степени адаптивности. Если перед каждым вопросом второй игрок знает ответы на все предыдущие вопросы, то это называется адаптивным поиском. Если же второй игрок задает все вопросы одновременно список вопросов, то это неадаптивный поиск. Возможны и промежуточные варианты, когда второй игрок задаёт вопросы так называемыми «пачками». Получив ответ на очередную пачку, он задает следующую пачку вопросов. Таким образом получается несколько неадаптивных этапов.

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

В завершении рассмотрим ограничения на количество вопросов, которое достаточно для второго игрока, чтобы гарантированно найти загаданный элемент. Это ограничение может объясняться максимально возможными затратами ресурсов второго игрока.

Рассмотрим различные сочетания указанных факторов и возникающие постановки задач.

1.1.1 Задачи группового тестирования

Первая формализация задачи группового тестирования была опубликована в 1943 году [3]. Мотивация данной постановки задачи возникла из того факта, что в тот период времени всех призывников тестировали на реакцию Вассермана. Так как тестирование каждой пробирки крови затратно, то появилась идея проверять группы призывников (отсюда принятый в англоязычной литературе термин group testing). Тогда в качестве ответа могло получиться, что заболевание есть (но тогда не было понятно, у кого именно из группы и надо было искать дальше), либо же заболевания не обнаруживалось, что означало, что его нет ни у кого из данной группы. До сих пор многие разновидности данных задач остаются открытыми.

Характерной особенностью задач группового тестирования является то, что чаще всего в них есть множество искомых объектов и в качестве решения необходимо указать один из них или же несколько.

Большой вклад в решение подобных задач внесли Ду и Хванг. Они систематизировали известные результаты по данной проблеме и подытожили их в монографии [4]. Также стоит упомянуть работу [5], в которой рассмотрена задача комбинаторного поиска при ненадежных тестах.

1.1.2 Задача Реньи-Улама

В некоторых работах, например в [6—10], задачи Реньи-Улама были известны как просто задачи Улама. Авторы даже не ссылались на работы Реньи [11; 12], так как, вероятно, просто не знали о них. Однако Реньи всё же раньше сформулировал задачу данного типа. Первоначально она выглядела следующим образом: два игрока (далее А и Б) играют в игру. Игрок А загадывает некий предмет, а игрок Б должен как можно быстрее его отгадать с помощью вопросов, на которые А будет отвечать либо да, либо нет. Можно также допускать, что некий процент ответов окажется ошибочными. Например, это может произойти из-за того, что А неправильно поймёт вопрос или не будет знать точного ответа. В таком виде эта задача была в статье [11].

В дальнейшем задача преобразовывалась и усложнялась, во многих работах игроки А и Б получили имена Алиса и Боб соответственно своим первым буквам. Улам же несколько позже популяризировал задачи данного типа, рассмотрев их в своей автобиографии [13]. В его формулировке некто загадывал целое число от 1 до 220. При помощи 20 вопросов, на которые можно получить бинарный ответ, необходимо было отгадать число. Показывалось, что, очевидно, деля возможные для ответа числа на максимально равные части, спрашивая каждый раз, в какой половине загаданное число, и таким образом сокращая количество вариантов вдвое, мы всегда успеем за 20 вопросов прийти к однозначному ответу. Однако в случае, если несколько раз ответ может оказаться ложным, задача сразу усложняется. Спрашивалось, сколько вопросов понадобится, если в ответе могут соврать один или два раза. У такой задачи есть тривиальная стратегия. Можно каждый вопрос повторять по пять раз, тогда, так как ложными могут оказаться не больше двух ответов, мы всегда будем знать правильный ответ на каждый вопрос. Однако такое решение требует весьма много вопросов. На самом же деле оказалось, что несколько возможных неправильных ответов не так уж сильно увеличивают число требуемых вопросов. Подробнее можно почитать в работах [14—17].

Стоит отметить, что также существует вариант названия "задачи Реньи-Берлекампа-Улама". Оно возникло из-за того, что Берлекамп занимался этой задачей раньше Улама (1964) и достиг огромных результатов в данной

области. Многие авторы впоследствии ссылались на результаты его статьи [18]. В частности, в ней ему удалось получить аналог оценки сферической упаковки Хэмминга [19], но для более обобщенной ситуации в случае адаптивной стратегии. На поставленный вопрос Улама для М = 220 и одной ошибки, мы можем получить результат - 25 вопросов. То есть это всего на 5 вопросов больше, чем в безошибочном случае. Именно такой ответ получил Пелч в своей работе [10], приведя точный алгоритм. Также он показал, что выигрыш за счёт адаптивности у стратегий возникает, начиная с М = 21. Для этого он привёл адаптивный алгоритм с 8 вопросами, тогда как лучший неадаптивный состоит из 9 вопросам, согласно работе [20].

Чуть позже был разрешен и случай двух ошибок. Пелч, Мундичи и Чижович для М = 220 получили ответ 29 в статье [21]. Затем в [6] был решен случай уже для произвольно большого числа элементов в пространстве поиска, но при этом их количество должно быть степенью двойки. Их результат для случая 2 ошибок обобщил Гузицкий в [14]. Была получена граница, которая почти везде достигалась, а в случаях отклонения разница была лишь на единицу.

Был рассмотрен и случай трёх ошибок. Стоит отметить, что он уже гораздо сложнее, и это максимальное значение ошибок, для которого задача Реньи-Улама была решена при произвольном количестве элементов М. Сначала в работах [9; 22] было показано, что при уже классическом М = 220 число требуемых вопросов равно 33. Затем Серено и Негро в [17] решили случай для числа элементов, являющимся степенью двойки. Аулетта почти смог описать произвольный случай в [23], однако некоторые исключения оказались трудноразрешимыми. Наконец, Деппе завершил доказательства всех вариаций в [24].

Случаи большего числа ошибок также рассматривались при дополнительных ограничениях, упрощающих задачу. Так, для конкретных видов значения М были получены точные результаты в работах [22; 25]. Позже Спенсеру удалось вывести асимптотическую оценку для общего случая в [26]. Так как вариаций было очень много, описать пошагово конкретную стратегию не представлялось возможным, а теоретические мощностные оценки не давали нужных результатов. Тогда было придумано воспользоваться следующим

рассуждением: если сделать несколько продуктивных шагов за первого игрока, то этого может хватить, чтобы оценка на оставшуюся часть вопросов оказалась хорошей. Это действительно сработало. Оказалось, достаточно хорошо задать количество вопросов, равное числу ошибок е, чтобы оставшуюся часть можно было ограничить теоретической оценкой, не используя подробное описание дальнейшей стратегии. Однако это работает лишь для достаточно больших значений числа элементов М и ошибок е.

В конце концов удалось с помощью экспериментального метода получить оценку, описанную Берлекампом [18]. Саркисян и Лоулер вывели простые стратегии для первого игрока, близкие к оптимальным [7]. Затем Чикалезе и Ваккаро улучшили этот результат в [27], получив асимптотическую оценку на оптимальное число вопросов, равную 3е при достаточно больших значениях общего числа элементов и возможных ошибок. На практике числа должны быть действительно большими, чтобы можно было пренебречь возникающими константами, но всё равно, результаты оказались гораздо лучше, чем изначально можно было предположить. В частности, для изначального М = 220 мы получаем значение для необходимого числа вопросов всего 3е + 26.

1.1.3 Задачи с различной степенью адаптивности

Рассмотрим теперь типы задач поиска с более строгими ограничениями. Начнём со случаев, когда отсутствует полная адаптивность, то есть перед очередным вопросом у нас может не быть всей информации о предыдущих результатах. Очень часто такое ограничение оказывается необходимым для эффективного практического применения. Это ограничение возникает в ряде приложений.

Например, проведение теста, необходимого для ответа на каждый вопрос может быть достаточно дорогим. Тогда, если мы можем проводить тест параллельно на нескольких объектах, не дожидаясь каждого результата по отдельности, мы сильно сэкономим. Или же мы можем получить значительный выигрыш во времени. Скажем, космический корабль, находящийся далеко

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

Полное отсутствие обратной связи фактически приводит нас к задаче кодирования, о которой подробнее будет рассказано позже. По сути, мы задаём все вопросы сразу и, получив список ответов, должны дать ответ. Подробное исследование данного случая описано в [20].

Дополнительно стоит отметить, что между случаями полной обратной связи и её отсутствием есть весьма большая разница в результатах. А потому весьма интересными оказываются случаи с частичной обратной связью. Здесь вопросы задаются группами, которые обычно называются «пачками». После каждой пачки вопросов происходит анализ и решение о последующей стратегии. Исследования Чикалезе и Мундичи [28; 29] показали, что для М, являющегося степенью двойки, достаточно минимального добавления адаптивности, чтобы достичь результата, аналогичного случаю полной адаптивности. То есть при помощи всего двух пачек вопросов, если нет прочих ограничений на задачу, можно получить такой же результат, как при анализе стратегии после каждого вопроса. Чикалезе обобщил этот результат для произвольного числа элементов в [30].

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

1.1.4 Задачи с различными типами вопросов

Исследуем различные ограничения на тип задаваемых вопросов. В случаях до этого мы имели дело с произвольными «да-нет» вопросами. По сути, они были эквиваленты вопросам «принадлежит ли искомый элемент некоторому указанному подмножеству?». Теперь при некоторых ограничениях первому игроку иногда будет сложнее сокращать варианты правильного ответа, однако есть и случаи, которые наоборот помогают ему делать это гораздо быстрее.

Поставим элементам пространства поиска в соответствие подряд идущие целые числа от 0 до М — 1. Тогда можно использовать вопросы типа «верно ли, что искомое число меньше чем а?», где а - это тоже целое число от 1 до М — 1. Задачи с таким типом вопросов были названы сравнительными и изучались Ривестом в [31]. Он получил оценку необходимого числа вопросов для выигрыша первого игрока с полной адаптивностью. В случае возможных е ошибок это число не превосходило 1с^2 М + е • 1с^2 1с^2 М + о(е • 1с^2 е).

Для случая с не более чем одной ошибкой Спенсер получил более сильную формулу в [32].

Также был рассмотрен случай и частичной адаптивности. Для этой задачи количество обратных связей оказалось принципиальным, что показал Негро в [33], исследовав случаи к пачек вопросов. Примерно в то же время вышла работа Пелча [34], где рассматривался безошибочный случай данной вариации.

Ещё с таким типом вопросов была изучена задача с задержкой ответа вместо ошибки. Понятие задержки было введено Амбайнисом в [35]. Оно подразумевает, что ответ приходит не сразу, а после того, как будет задано ещё какое-то количество вопросов 4. Каким образом такое изменение влияет на стратегию было показано Ваккаро и Чикалезе в [36].

Перейдём теперь к так называемым «префиксным» вопросам. В этом случае все элементы пространства поиска представляются в двоичном виде. Вопрос строится по конструкции «является ли некая двоичная подпоследовательность в началом искомого элемента (то есть, по сути, его

префиксом)». Этот случай может иллюстрировать поиск по упорядоченному списку, например, биологический определитель растений или поисковик болезней по симптомам. Пелч разрешил случай для количества элементов, равного степени двойки, при наличии не более одной ошибки [37]. Алгоритм поиска для читателей знакомых с теорией графов напоминает построение бинарного дерева из вариантов ответов. Глубина такого графа и будет количеством вопросов необходимых для решения. Было доказано, что асимптотически ответ стремится к значению в случае «да-нет» вопросов с не более чем 1 ошибкой для больших значений М.

Следующий тип вопросов - это вопросы фиксированной мощности. Проверяется, принадлежит ли искомый элемент подмножеству размером не более заранее обговоренного к. Это часто актуально из-за ограничений на максимальное число объектов, которое можно единовременно проверить в эксперименте. Макула построил верхнюю мощностную границу на требуемое количество вопросов при одной ошибке в неадаптивном случае [15]. Обобщение этой задачи с произвольным числом ошибок было позже решено Катоной в [38]. Однако для решения пришлось накладывать ограничения на к в зависимости от М.

Предположим теперь, что один из ответов на вопрос более нежелателен для нас. Допустим, какая-то бракованная деталь перегружает сеть, если при проверке будет слишком много перегрузок, это может привести к поломке оборудования. Тогда при поиске гораздо выгоднее получать ответ, что никакая из проверяемых деталей не поломана. Такой тип ограничений будем называть вопросами с ценовым распределением. Самые значимые результаты здесь были получены Серено в [39]. Он рассматривал «да-нет» вопросы с не более чем е ошибок, с ограничением, что не более чем на В вопросов может быть ответ «да». Им была получена нижняя граница оценки оптимального числа вопросов.

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

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

Задачи с д-ичными вопросами оказались весьма популярными. Это как раз тот случай, когда тип вопроса помогает первому игроку быстрее найти ответ. Можно узнать, к какому из д выбранных подмножеств принадлежит искомый элемент. Внимательный читатель поймёт, что д = 2 - это обычные «да-нет» вопросы, а значит, нас интересуют д > 2. Для неадаптивного случая естественным образом получаем задачу д-ичного кодирования. Данная постановка задачи встречалась, например, в [41]. Пелч предлагал разрешить задачу с фальшивыми монетками разного веса и чашечными весами. Сравнивая вес монеток на разных чашах, мы можем получить три разных результата: перевес левой чаши, перевес правой чаши и равенство. Соответственно, получается троичный случай. Данная задача была решена для произвольного числа монет. После возникла идея обобщения на д-ичный случай. Адаптивный случай задачи такого типа для одной ошибки был рассмотрен Малиновским в [42], а затем Аигнером в [43]. В обеих работах были приведены оптимальные стратегии и доказаны оценки на сложность. Аналогичную задачу, но уже с 2 ошибками, решил Чикалезе в [44]. Затем получилось обобщить данное решение и получить верхнюю оценку на минимальное число вопросов в [29]. Для произвольного числа ошибок была доказана весьма сильная асимптотическая оценка: Бассалыго в [45] получил точное значение не только для любого константного количества ошибок, но и для не слишком быстро растущего их числа.

Закончим перечисление возможных ограничений на вопросы интервальными множествами. Здесь фиксируется количество интервалов к, про объединение которых можно узнать, принадлежит ли ему искомый элемент. Формулировку придумали Мундичи и Тромбета, и они же решили би-интервальный случай (к = 2) для не более чем двух ошибок [46]. Кроме того, к этому типу можно в частности отнести задачи группового тестирования, о которых будет отдельно рассказано подробнее во второй части данной работы.

1.1.5 Задачи с различными допустимыми видами ошибок

Перейдём теперь к разделению по возможным типам ошибок, которые могут встречаться. До сих пор почти во всех случаях мы имели дело с константным ограничением числа ошибок. Однако часто получается так, что число ошибок зависит от числа проводимых тестов. А значит, чем больше вопросов в нашей стратегии, тем больше может быть ошибок. Начнём с вероятностных вариаций ограничений на число ошибок.

Введём приблизительную вероятность ошибки р для каждого вопроса. Тогда возможно использовать ограничение, что произойти может не более, чем р * п ошибок, где п это число вопросов в стратегии. Пелч в [47] изучал неадаптивный случай и доказал мощностную оценку для р < 0.25. Для значений вероятности строго больше четверти было доказано невозможность существования решения. Затем Спенсер и Винклер доказали существование и оптимальность стратегии для вероятности р = 0.25. Также ими был изучен адаптивный вариант, где задача оказалась разрешимой при р < 1/3. Всё это было описано в их работе [48].

Позже Дхагат в [49] исследовал схожую задачу, но использовал более строгое ограничение на тип вопросов (он спрашивал, является ли г-й бит двоичного представления искомого числа нулём), а также изучал случай с сравнительными вопросами. Было доказано для этих случаев, что неадаптивный поиск невозможен, а для адаптивного доля ошибок должна быть строго меньше одной трети. Его результаты позже были чуть улучшены Педротти в [50; 51], а также в работе Альберса и Дамашке [52].

Для случая вероятности между одной третьей и одной второй была рассмотрена задача с допущением, что в виде ответа можно привести небольшой список чисел (константного или логарифмического размера относительно общего числа элементов). Стоит отметить, что подобное допущение используется и в одной из задач моей тематики, так что оно мне близко. С его учетом была доказана возможность построить оптимальную стратегию с сравнительными вопросами. Сделать это в итоге смогли Боргстром и Косараджу в [53].

Следующее допущение не даёт происходить слишком большому числу ошибок подряд. Так называемое префиксное ограничение на долю ошибок гарантирует, что в любых % подряд идущих вопросах не будет более чем р * % ошибок. Первым подобную задачу рассматривал Пелч в [47] для произвольных «да-нет» вопросов и неадаптивного случая. В последствии он же изучил адаптивный вариант со сравнительными вопросами в [54]. Он смог получить оптимальные результаты для р < 1/3 и доказать невозможность существования решения для вероятности больше половины. Однако, как обстояло дело в промежуточным случаях, оставалось открытым вопросом.

Продолжили исследование независимо друг от друга Аслам с Дхагатом в [55] и Спенсер с Винклером в [48]. Им удалось получить схожие по мощности оценки для неисследованных значений вероятности. Обобщили и поставили точку в виде окончательного решения данной задачи Боргстром и Косаражу в уже упоминавшийся работе [53]. В итоге были получены оптимальные стратегии для произвольного значения вероятности, которая меньше половины. Схожая, однако менее вероятностная задача была рассмотрена Пелчем, Лакшмананом и Чижовичем в [56]. В их случае запрещалось более одной ошибке в г подряд идущих вопросах. Были получены конструкции оптимальных стратегий, а также асимптотические оценки для случаев большого числа элементов в пространстве поиска.

Достаточно обобщенным является вариант с использованием случайных ошибок. Здесь просто есть вероятность ошибки на каждый вопрос. Она может изменяться, а можем всегда быть постоянной. Изначально вариацию с постоянной вероятностью ошибки (но при этом с её значением не более половины) вводил еще Реньи в [11]. Большинство вариаций общего случая было изучено Пелчем в [54], а случай с префиксным вероятностным ограничением был рассмотрен Боргстромом и Косаражу в [53]. Случай детерминированного адаптивного поиска был описан Шалквейком в [57]. Изучив данные работы можно получить представление и о многих прочих вариациях вероятностных ограничений на ошибки. Однако эти случаи далеки от решаемой мной задачи комбинаторного поиска движущегося элемента. Поэтому перейдём к другому типу ограничений на ошибки, приводящего к более родственным задачам.

Частичные ошибки - это когда один из ответов не может оказаться неправильным. Например, ответ «да» всегда точно верен, а вот получив ответ «нет» нельзя сказать наверняка была ли ошибка. Неадаптивным случай сразу приводит нас к задаче кодирования в асимметричном канале, или по-другому ^-канале. Такое укороченное название ему дали из-за графа возможных переходов символов 0 и 1 после возможной ошибки. Видно, что 0 может перейти только в 0 (ведь единица не может получиться в результате ошибки), а 1 может перейти куда угодно. В итоге получаем рисунок в точности похожий на букву 2. Подробнее с неадаптивным случаем можно ознакомиться в [58].

Адаптивный же случай для частичных ошибок раньше всего был изучен Ривестом в [31]. Позже свои результаты с оценками на число вопросов в оптимальной стратегии получили Чикалезе и Мундичи в [59]. Мотивация частичных ошибок понятна. Часто можно встретить ситуацию, где сигнал может потеряться при передаче. Тогда, по сути, вместо 1 мы получили 0 (отсутствие сигнала). Для получения в точности асимметричной модели 2 канала осталось допустить, что сигнал не может взяться ниоткуда. Такая ситуация довольно типична.

Ограничения на ошибки такого типа могут быть весьма разнообразны. Например, движение искомого элемента можно тоже воспринимать как неточность в ответах, которая со временем меняется. Однако случай с движением мы рассмотрим позже отдельно.

1.1.6 Задачи с различными пространствами поиска

Перейдём к некоторым разновидностям пространств поиска. Очевидно, что не всегда можно представить список всех возможных ответов в виде целых чисел от 1 до М.

Список литературы диссертационного исследования кандидат наук Лебедев Алексей Владимирович, 2024 год

Список литературы

1. Kabatianski G., Lebedev V., Thorpe J. The Mastermind game and the rigidity of the Hamming space. — 2000. — с. 375—380.

2. Реньи А. Трилогия о математике. Диалоги о математике. Письма о вероятности. Дневник записки студента по теории информации. -Москва 1980.

3. Dorfman R. The detection of defective members of large populations. т. 14. -JSTOR, 1943. — с. 436—440.

4. Du D., Hwang F. Combinatorial Group Testing and its Applications. — World Scientific, Singapore, 1993.

5. Bonis A. D., Gargano L., Vaccaro U. Group testing with unreliable tests. — Inform. Sci. 96, 1997. — с. 1—14.

6. Czyzowicz J., Mundici D., Pelc A. Ulam's searching game with lies. т. 52. — 1989. — с. 62—76.

7. Lawler E. L., Sarkissian S. An algorithm for "Ulam's Game" and its application to error correcting codes. т. 56. — 1995. — с. 89—93.

8. Mundici D. Algebras of Ulam's games with lies. — Atti del Congresso Nuovi problemi della logica edella filosofia della scienza Viareggio, Italy, 1990. — с. 151—162.

9. Negro A., Sereno M. Solution of Ulam's problem on binary search with three lies. — J. Combin. Theory Ser. A 59, 1992. — с. 149—154.

10. Pelc A. Solution of Ulam's problem on searching with a lie. — J. Combin. Theory Ser. A 44, 1987. — с. 129—140.

11. Renyi A. On a problem of information theory. — MTA Mat. Kut. Int. Kozl. 6B, 1961. — с. 505—516.

12. Renyi A. A Diaryon Information Theory. — Wiley, New York, 1984.

13. Ulam S. Adventures of a Mathematician. — Scribner, New York, 1976.

14. Guzicki W. Ulam's searching game with two lies. — J. Combin. Theory Ser. A 54, 1990. — с. 1—19.

15. Macula A. A nonadaptive version of Ulam's problem with one lie. — J. Statist. Plann. Inference 61, 1997. — c. 175—180.

16. Mundici D. The logic of Ulam's game with lies. — C. Bicchieri, M.L. Dalla Chiara (Eds.), Knowledge, Belief, Strategic Interaction, Cambridge University Press, Cambridge, 1992. — c. 275—284.

17. Negro A., Sereno M. Ulam's searching game with three lies. — Adv. Appl. Math. 13, 1992. — c. 404—428.

18. Berlekamp E. Block coding for the binary symmetric channel with noiseless, delayless feedback. — H.B. Mann (Ed.), Error-Correcting Codes, Wiley, New York, 1968. — c. 61—85.

19. Hamming R. Error detecting and error correcting codes. — Bell Systems Tech. J. 29, 1950. — c. 147—160.

20. MacWilliams F., Sloane N. The Theory of Error-Correcting Codes. — Elsevier Science, New York, 1977.

21. Czyzowicz J., Mundici D., Pelc A. Solution of Ulam's problem on binary search with two lies. — J. Combin. TheorySer. A 49, 1988. — c. 384—388.

22. Hill R., Karim J. Searching with lies: the Ulam problem. — Discrete Math. 106-107, 1992. — c. 273—283.

23. Auletta V., Negro A., Parlati G. Some results on searching with lies. — Proc. 4th Italian Conf. on Theoretical Computer Science, 1992. — c. 24—37.

24. Deppe C. Solution of Ulam's searching game with three lies or an optimal adaptive strategy for binary three-error-correcting codes. — Discrete Math. 224, 2000. — c. 79—98.

25. Auletta V., Negro A., Parlati G. Solution of Ulam's problem on binary search with four lies. — Technical Report, Columbia University, 1993.

26. Spencer J. Ulam's searching game with a fixed number of lies. — Theoret. Comput. Sci. 95, 1992. — c. 307—321.

27. Cicalese F., Vaccaro U. An improved heuristic for the "Ulam-Renyi game". -Inform. Process. Lett. 73, 2000. — c. 119—124.

28. Cicalese F., Mundici D. Optimal binary search with two unreliable tests and minimum adaptiveness. — Proc. 7th Annu. European Symp. on Algorithms, Lecture Notes in Computer Science, Vol. 1643, Berlin, Springer, 1999. -c. 257—266.

29. Cicalese F., Mundici D. Perfect two-fault tolerant search with minimum adaptiveness. — Adv. Appl. Math. 25, 2000. — c. 65—101.

30. Cicalese F., Mundici D., Vaccaro U. Least adaptive optimal search with unreliable tests. — Proc. Scand. Workshop on Algorithm Theory(SWAT 2000), Lecture Notes in Computer Science, Vol. 1851, Springer, Berlin, 2000. — c. 547—562.

31. Coping with errors in binary search procedures / R. Rivest [h gp.]. ■ J.Comput. System Sci. 20, 1980. — c. 396—404.

32. Spencer J. Guess a number—with lying. — Math. Mag. 57, 1984. — c. 105—108.

33. Negro A., Parlati G., Ritrovato P. Optimal adaptive search: reliable and unreliable models. — Proc. 5th Italian Conf. on Theoretical Computer Science, 1995. — c. 211—231.

34. Pelc A. Weakly adaptive comparison searching. — Theoret. Comput. Sci. 66, 1989. — c. 105—111.

35. Ambainis A., Bloch S., Schweizer D. Playing twenty questions with a procrastinator. — Proc. 10th Ann. ACM-SIAM Symp. on Discrete Algorithms, 1999. — c. 844—845.

36. Cicalese F., Vaccaro U. Coping with delays and time-outs in binary search procedures. — Proc. 11th Annu. Internat. Symp. on Algorithms, Computation (ISAAC 2000), Lecture Notes in Computer Science, Vol. 1969, Springer, Berlin, 2000. — c. 96—107.

37. Pelc A. Prefix search with a lie. — J. Combin. Theory Ser. A 48, 1988. — c. 165—173.

38. Katona G. Search with small sets in presence of a liar. — Journal of statistical planning, inference, Vol.100, 2002. — c. 319—336.

39. Sereno M. Binary search with errors and variable cost queries. — Inform. Process. Lett. 68, 1998. — c. 261—270.

40. Pelc A. Searching with permanently faulty tests. — Ars Combin. 38, 1994. -с. 65—76.

41. Pelc A. Detecting a counterfeit coin with unreliable weightings. — Ars Combin. 27, 1989. — с. 181—192.

42. Malinowski A. K-ary searching with a lie. — Ars Combin. 37, 1994. ■ с. 301—308.

43. Aigner M. Searching with lies. — J. Combin. Theory Ser. A 74, 1996. — с. 43—56.

44. Cicalese F. Q-ary searching with lies. — U. Vaccaro et al. (Eds.), Proc. 6th Italian Conf. on Theoretical Computer Science, Prato, Italy, World Scientific, Singapore, 1998. — с. 228—240.

45. Бассалыго Л. А. Недвоичные коды, исправляющие ошибки при наличии одноразовой безошибочной обратной связи. — Проблемы передачи информации, 2005, том 41, № 2, — С. 63-67.

46. Mundici D., Trombetta A. Optimal comparison strategies in Ulam's searching game with two errors. — Theoret. Comput. Sci. 182, 1997. — с. 217—232.

47. Pelc A. Coding with bounded error fraction. — Ars Combin. 24, 1987. — с. 17—22.

48. Spencer J., Winkler P. Three thresholds for a liar. — Combin. Probab. Comput. 1, 1992. — с. 81—93.

49. Dhagat A., Gacs P., Winkler P. On Playing "Twenty Questions"with a Liar. — SODA, 1992. — с. 16—22.

50. Pedrotti A. Searching with a constant rate of malicious lies. — Proc. Internat. Conf. Fun with Algorithms, Carleton Scientific, 1999. — с. 137—147.

51. Pedrotti A. Playing by searching: two strategies against a linearly bounded liar. — Theoret. Computer Science, 2002. — с. 285—302.

52. Albers F., Damaschke P. Delayed correction—binary search with errors made very simple but efficient. — X. Lyn (Ed.), Proc. 4th Auskalasian Theory Symp., CATS'98, Australian Computer Science Communications, vol. 20(3), Springer, Berlin. — с. 97—105.

53. Borgstrom R., Kosaraju S. Comparison based search in the presence of errors. — Proc. 25th Annu. ACM Symp. on Theory of Computing, 1993. -c. 130—136.

54. Pelc A. Searching with known error probability. — Theoret. Comput. Sci. 63, 1989. — c. 185—202.

55. Aslam J., Dhagat A. Searching in the presence of linearly bounded errors. — Proc. 23rd Annu. ACM Symp. on Theory of Computing, 1991. — c. 486—493.

56. Czyzowicz J., Lakshmanan K., Pelc A. Searching with local constraints on error patterns. — European J. Combin. 15, 1994. — c. 217—222.

57. Schalkwijk J. A class of simple and optimal strategies for block coding on the binary symmetric channel with noiseless feedback. — IEEE Trans. Inform. Theory 17, 1971. — c. 283—287.

58. Pierce J. Optical channels: Practical limits with foton counting. — IEEE Trans. Comm. COM-26, 1978. — c. 1819—1821.

59. Cicalese F., Mundici D. Optimal coding with one asymmetric error: below the sphere packing bound. — Proc. Annu. Int. Conf. on Computing, Combinatorics (COCOON 2000), Sydney, Australia, Lecture Notes in Computer Science, Vol. 1858, Springer, Berlin, 2000. — c. 159—169.

60. Bentley J., Yao A. An almost optimal algorithm for unbounded searching. — Inform. Process. Lett. 5, 1976. — c. 82—87.

61. Beigel R. Unbounded searching algorithms. — SIAM J. Comput. 19, 1990. — c. 522—537.

62. Ravikumar B., Lakshmanan K. Coping with known patterns of lies in a search game. — Theoret. Comput. Sci. 33, 1984. — c. 85—94.

63. Ravikumar B., Lakshmanan K., Ganesan K. Coping with erroneous information while sorting. — IEEE Trans. Comput. 40, 1991. — c. 1081—1084.

64. Bagchi A. On sorting in the presence of erroneous information. — Inform. Process. Lett. 43, 1992. — c. 213—215.

65. Long P. Sorting and searching with a faulty comparison oracle. — Technical Report UCSC-CRL-92-15, University of California at Santa Cruz, 1992.

66. Aigner M. Finding the maximum and minimum. — Discrete Appl. Math. 74, 1997. — с. 1—12.

67. Computing with noisy information / U. Feige [и др.]. — SIAM J. Comput. 23, 1994. — с. 1001—1018.

68. Piotrow M. Depth optimal sorting networks resistant to k passive faults. -Proc. 7th ACM-SIAM Symp. on Discrete Algorithms, 1966. — с. 242—251.

69. Stachowiak G. Proc. Scand. Workshop on Algorithm Theory. — SWAT 2000, Lecture Notes in Computer Science, Vol. 1851, Springer, Berlin, 2000. — с. 535—548.

70. Assaf S., Upfal E. Fault-tolerant sorting networks. — Proc. 32nd Annu. IEEE Symp. on Foundations of Computer Science, 1990. — с. 275—284.

71. Leighton T., Ma Y. Breaking the (n log2 n) barrier for sorting with faults. — Proc. 34th IEEE Annu. Symp. on Foundations of Computer Science, 1993. — с. 734—743.

72. Ravikumar B., Ganesan K., Lakshmanan K. On selecting the largest element in spite of erroneous information. — Proc. 4th Annu. Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 247, Springer, Berlin, 1987. — с. 88—99.

73. Selection in the presence of noise: the design of playoff systems / M. Adler [и др.]. — Proc. 5th Annu. ACM-SIAM Symp. on Discrete Algorithms, 1994. — с. 564—572.

74. A. R. Combinatorial geometry and coding theory. — Fundamenta Informatica. Vol. 145, 2016. — с. 359—369.

75. Kranakis E., Krizanc D. Searching with uncertainty. — Proc. 6th Internat. Colloq. on Structural Information, Communication Complexity, SIROCCO'99, Lacanau-Ocean, France, 1999. — с. 194—203.

76. Hanusse N., Kranakis E., Krizanc D. Searching with mobile agents in networks with liars. — Proc. Europar 2000, Lecture Notes in Computer Science, Vol. 1900, Springer, Berlin, 2000. — с. 583—590.

77. Locating information with uncertainty in fully interconnected networks with applications to World Wide Web retrieval / A. Kaporis [и др.]. — Computer J., Vol 44 N4, 2001. — с. 221—229.

78. Locating information with uncertainty in fully interconnected networks / L. Kirousis [h gp.]. — Proc. 14th Internat. Conf. on Distributed Computing (DisC 2000), Toledo Spain, Lecture Notes in Computer Science, Vol. 1914, Springer, Berlin, 2000. — c. 283—296.

79. Preparata F., G. Metze R. C. On the connection assignment problem of diagnosable systems. — IEEE Trans. Electron. Comput. 16, 1967. -c. 848—854.

80. Lee S., Shin K. Probabilistic diagnosis of multiprocessor systems. — ACM Comput. Surveys 26, 1994. — c. 121—139.

81. Masson G., Blough D., Sullivan G. System diagnosis. — D.K. Pradhan (Ed.), Fault-Tolerant Computer System Design, Prentice-Hall, Englewood Cliffs, 1996. — c. 478—536.

82. Isaacs R. Differential Games. — Dover, New York, 1999.

83. Arculus R. A Discrete search-ambush game with a silent predator. — Search Theory, a Game Theoretic Approach, S. Alpern et al., eds, Springer, New York, 2013. — c. 249—263.

84. Ambush frequency should increase over time during optimal predator search for prey / S. Alpern [h gp.]. — J. Roy. Soc. Interface, 8, 2011.

85. Spider's attack versus cricket's escape: Velocity modes determine success / O. Dangles [h gp.]. — Animal Behaviour, 72, 2006. — c. 603—610.

86. Hohzaki R. The search allocation game. Wiley Encyclopedia of Operations Research and Management Science. — John Wiley & Sons, Online-version, 2013. — c. 1—10.

87. Stewart T. A two-cell model of search for an evading target. — European Journal of Operational Research, 8, 1981. — c. 369—378.

88. Cohen N. An attack-defense game with matrix strategies. — Naval Research Logistics Quarterly, 13, 1966. — c. 391—402.

89. Hausken K. Defense and attack of complex and dependent systems. — Reliability Engineering, System Safety, 95, 2010. — c. 29—42.

90. Hausken K. Protecting complex infrastructures against multiple strategic attackers. — International Journal of Systems Science, 42, 2011. — c. 11—29.

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

Koopman B. Search and screening. — Persimmon Press, New York, 1946.

Ahlswede R., Deppe C., Lebedev V. Nonbinary error correcting codes with noiseless feedback, localized errors or both. — Annals of European Academy of Sciences, No. 1, 2005. — c. 285—309.

A Combinatorial Model of Two-Sided Search / H. Aydinian [h gp.]. -International Journal of Foundations of Computer Science 29 (04), 2018. — c. 481—504.

Shannon C. A mathematical theory of communication. — Bell Systems Tech. J. 27, 1948. — c. 379—423.

Shannon C. Zero-capacity of noisy channels. — IEEE Trans. Inform. TheoryIT2, 1956. — c. 8—19.

Dobrushin R. Information transmission in a channel with feedback. — Theory Probab. Appl. 34, 1958. — c. 367—383.

Dumitriu I., Spencer J. The two-batch liar game over an arbitrary channel. — SIAM Journal on Discrete Mathematics. 2005. V. 19, № 4. — c. 1056—1064.

Optimal strategies for a model of combinatorial two-sided search / H. Aydinian [h gp.]. — Seventh International Workshop on Optimal Codes, Related Topics, 2013. — c. 7—12.

Beluhov N., Kolev E. Search for a moving target in a graph. — International Workshop on Algebraic, Combinatorial Coding Theory, 2016. — c. 47—52.

Tosic R. Vertex-to-vertex search in a graph. — Graph theory, Dubrovnik, 1985.

Britnell J., Wildon M. Finding a princess in a palace: A pursuit-evasion problem. — Electron. J. Comb., 20 (1), 2013.

How to hunt an invisible rabbit on a graph / T. Abramovskaya [h gp.]. — Eur. J. Comb., 52 (A), 2016. — c. 12—26.

Bernshteyn A., Lee E. Searching for an Intruder on Graphs and Their Subdivisions. — arXiv:2104.01739, 2021.

Ahlswede R., Wegener I. Suchprobleme, Teubner. — 1979.

Aigner M. Combinatorial Search. — John Wiley, Sons, 1988.

Knuth D. The Art of Computer Programming. — Addison-Wesley Publishing, vol. 3, 1973.

107. Cicalese F. Fault-Tolerant Search Algorithms. — Springer-Verlag, 2013.

108. Aldridge M. Adaptive group testing as channel coding with feedback. -IEEE International Symposium on Information Theory Proceedings, 2012. -с. 1832—1836.

109. Baldassini L., Johnson O., Aldridge M. The capacity of adaptive group testing. — IEEE International Symposium on Information Theory, 2013. -с. 2676—2680.

110. Benkoski S., Monticino M., Weisinger J. A Survey of the Search Theory Literature. — Naval Research Logistics, Vol. 38, 1991. — с. 469—494.

111. Ahlswede R., Deppe C., Lebedev V. The capacity of adaptive group testing. — IEEE International Symposium on Information Theory, 2013. — с. 2676—2680.

112. Лебедев В. С. Кодирование при наличии бесшумной обратной связи — Пробл. передачи информ., 52:2, 2016 — С. 3-14.

113. Berlekamp E. Block Coding with Noiseless Feedback. — PhD thesis, MIT EE Dept., 1964.

114. Зигангиров К. Ш. О числе исправляемых ошибок при передаче по ДСК с обратной связью — Проблемы передачи информации, том 12, № 2, 1976

- С. 3-19.

115. Ahlswede R., Deppe C., Lebedev V. Non-binary error correcting codes with noiseless feedback, localized errors, or both. — Annals of the European Academy of Sciences, 2005. — с. 285—309.

116. Delsarte P., Piret P. Bounds and constructions for binary asymmetric error-correcting codes (corresp.) — IEEE Transactions on Information Theory. Vol. 27, No 1, 1981. — с. 125—128.

117. Klove T. Upper bounds on codes correcting asymmetric errors (Corresp.) — IEEE Transactions on Information Theory. Vol. 27, No 1, 1981. — с. 128—131.

118. J. Weber C. de Vroedt D. B. New upper bounds on the size of codes correcting asymmetric errors (Corresp.) — IEEE transactions on information theory. Vol. 33, No 3, 1987. — с. 434—437.

119. Зиновьев В., Кацман Г. Универсальные семейства кодов — Проблемы передачи информации, том 29, вып. 2, 1993, — С. 63-67.

120. Kim W., Freiman C. Single error-correcting codes for asymmetric binary channels. т. 5. — IEEE, 1959. — с. 62—66.

121. Varshamov R. R. On the theory of asymmetric codes. т. 164. — 1965. -с. 757—760.

122. Lebedev A., Lebedev V., Polyanskii N. Two-Stage Coding Over the Z-Channel. IEEE Transactions on Information Theory vol. 68, no. 4. ■ 2022. — с. 2290—2299.

123. Borden J. A low-rate bound for asymmetric error-correcting codes (Corresp.) т. 29. — IEEE, 1983. — с. 600—602.

Список рисунков

2.1 Схема случаев в доказательстве Утверждения 2....................47

3.1 Пропускная способность для двоично- симметричного канала с обратной связью........................................................65

3.2 Канал с обратной связью..............................................68

3.3 Граф ошибок троичного однонаправленного канала................68

3.4 Граф ошибок............................................................90

3.5 Двухшаговая декодирующая стратегия для передачи сообщений через Z-канал............................................................93

Список таблиц

1 Таблица максимальных количеств передаваемых сообщений в двоичном симметричном канале с одной ошибкой с одной обратной связью и с полной обратной связью............ 74

2 Оптимальное количество свободных точек (п, М, 1) кодов..... 78

3 Оптимальные весовые распределения................ 78

4 Количество передаваемых сообщений по асимметричному

каналу с одной обратной связью и с одной ошибкой........ 79

5 Мощности кодов для асимметричного канала с полной обратной связью и с одной ошибкой ....................... 81

6 Максимальная доля исправляемых асимметричных ошибок для кодов заданного размера ........................ 96