Автоматический вывод информационных неравенств (проект)

Ментор	Ромащенко Андрей
Учебный семестр	Осень 2016
Учебный курс	2-й курс
Проект можно развивать на летней практике
Максимальное количество студентов, выбравших проект: 1

Что это за проект?

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

Программа минимум: воспроизвести/проверить машинные доказательства некоторых теорем из теории информации, для которых не известно "человеческих" (без машинных вычислений) доказательств.

Программа максимум: улучшить известные оценки эффективности для некоторых схем разделения секрета и других задач теории информации.

Чему вы научитесь?

- Выводить (руками и с помощью компьютера) новые теоретико-информационные неравенства.

- Сводить задачу об эффективности разделения секрета к задаче линейного программирования.

- Применять linear programming солверы к задачам большой размерности.

Какие начальные требования?

Необходимо: базовые представления об энтропии Шеннона и классической теории информации.

Желательно: базовые представления о линейном программировании.

Какие будут использоваться технологии?

Различные библиотеки для решения задач линейного программирования и некоторые методы параллелизации вычислений.

Направления развития

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

Критерии оценки

4-5: Написать действующую программу, генерирующую новые информационные неравенства одним из известных теоретических методов; применить один из существующих LP солверов для получения оценок эффективности для схем разделения секрета на матроиде Вамоса.

6-7: Использовать параллельных вычислений для вывода информационных неравенств большой размерности. Подготовить пакет алгоритмов, которым смогли бы пользоваться в своей работе (без долгого и подробного инструктажа) специалисты по теории информации.

8-10: Сравнить между собой разные методы вывода информационных неравенств; улучшить известные оценки в задачах разделения секрета и hat guessing games.

Ориентировочное расписание занятий

Доступен для разговоров по Skype. Время для бесед лучше уточнять по ходу дела (разница в часовых поясах, летнее/зимнее время).