Дневник лекций 2013 года
18 сентября 2013
Многоленточные машины Тьюринга и РАМ (равнодоступные адресные машины).
Моделирование многоленточных машин Тьюринга на одноленточных машинах
Тьюринга.
Моделирование одноленточных машин Тьюринга на РАМ.
25 сентября 2013
Сложность выполнения арифметических операций на машинах Тьюринга.
Моделирование РАМ на машинах Тьюринга.
Полиномиальные алгоритмы. Полиномиальность алгоритма Эвклида.
Класс P.
25 сентября 2013
Класс NP. Примеры. Сводимость Карпа и ее свойства. NP полные задачи.
Сводимость Кука. Сводимость задач поиска к задачам разрешения.
2 октября 2013
Теорема Кука-Левина об NP полноте задачи выполнимости схем из функциональных элементов.
9 октября 2013
NP полнота задачи выполнимости формул в КНФ.
16 октября 2013
Схемы из функциональных элементов. Экспоненциальная верхняя
и нижняя оценки количества элементов в схеме, вычисляющей
булеву функцию от n переменных.
Класс n.u.P. Включение P в n.u.P.
23 октября 2013
Вероятностные полиномиальные алгоритмы. Класс BPP.
Вероятностный полиномиальный алгоритм проверки
алгебраического тождества.
30 октября 2013
Уменьшение вероятности ошибки за счет повторения.
Коды с исправлением ошибок и их параметры.
Оценка Хэмминга и граница Гилберта
6 ноября 2013
Вероятностное доказательство оценки Гилберта.
Линейные коды и граница Гилберта-Варшамова.
Коды Хэмминга.
13 ноября 2013
Неравенство Синглтона. Коды Рида — Соломона.
Эффективное декодирование кода Рида — Соломона.
Каскадные коды. Эффективное декодирование каскадного кода, если
внешний код является кодом Рида — Соломона.
20 ноября 2013
Эффективное декодирование каскадного кода, если
внешний код является кодом Рида — Соломона.
Коды Возенкрафта для скорости передачи 1/2
27 ноября 2013
Коды Возенкрафта для любой скорости передачи.
Коды Форни — Возенкрафта — Юстесена.
Оценка Плоткина для бинарного алфавита.
4 декабря 2013
Обобщение оценки Плоткина для относительного кодового расстояния 1/2.
Кривая Плоткина.
Код Адамара его декодирование за полиномиальное от длины сообщения время
11 декабря 2013 (последняя лекция)
Оценка Элайеса — Бассалыго
Коды БЧХ