Задачи по курсу Сложность вычислений и коды с исправлением ошибок
Срок сдачи — 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