Кафедра математической логики и теории алгоритмов

Задачи по курсу Сложность вычислений и коды с исправлением ошибок

Срок сдачи — 23 октября:

1. Доказать, что задача выполнимости формул в 4-КНФ сводится к задачи
выполнимости формул в 3-КНФ (запрещается пользоваться NP полнотой последней задачи).

2. Доказать, что задача выполнимости формул в 2-КНФ принадлежит классу P.

3. Доказать, что задача выполнимости формул в ДНФ принадлежит классу P.

Срок сдачи — 6 ноября:

4. Доказать, что если существует код с параметрами n,k,e,q, то
существует код с параметрами n-2,k,e-1,q.

Срок сдачи — 20 ноября:

5. Докажите, что
для любого кода с расстоянием d, по кодовому слову, в котором
сделали e ошибок и
c стираний, можно восстановить исходное слово, если
2e+c меньше d.

Докажите, что для кода Рида-Соломона это можно сделать за полиномиальное время.

Срок сдачи — 27 ноября:

6. Найти наибольшую скорость передачи k/n для кодов Форни с относительными
кодовыми расстояниями равными d/n=1/50, d/n=1/20, d/n=1/10, d/n=1/5, d/n=3/10.

Срок сдачи — 4 декабря:

7. Доказать оценку Плоткина для алфавита произвольной мощности q:
для всех b> 1-1/q и всех n количество кодовых слов в любом коде
с относительным расстоянием d/n=b не превосходит 1+1/(bq/(q-1)-1)

Срок сдачи — 11 декабря:

8. Доказать, что для алфавита мощности q
для всех n количество кодовых слов в любом коде
с относительным расстоянием d/n >= 1-1/q не превосходит 2n(q-1).

9. Доказать, что для любого кода с параметрами k, n, d над q-буквенным
алфавитом выполнено неравенство k/n + (q/(q-1))(d/n) < 1 + (log_q 3q^2n)/n

10. Найти параметры каскадного кода, в котором внешний код является кодом Рида-Соломона (с произвольной
скоростью передачи), а внутренний код — кодом Адамара.

Срок сдачи — 18 декабря:

11.
Доказать, что кривая Элайеса-Бассалыго
(ее уравнение k/n+H(1/2-sqrt{1-2d/n}/2)=1)
лежит левее прямой k/n+2d/n=1

Сдали задачи:

Лысенко 1-11

Плосконосов 1-11

Абдуллаев 1, 2, 3, 4, 5, 6, 7

Славгородский 1 (-), 2 , 3, 4, 5, 7

Королёв 1, 2 (-), 3, 4, 5, 7

Праведников 1 , 2 (-), 3, 4, 5, 7, 8 (-).

Колосов 1,2,3,4,5,6,7,8

Рогожников 1, 2(- не доказана корректность алгоритма), 3, 4, 5, 6, 7, 8, 9, 10, 11

Свешников 1, 2, 3, 4 , 5

Гришина 1, 2, 3, 4 , 5

Аксенов 1, 3, 5, 7, 8