Введение в теорию информации

Общая информация
ЛекторА. Е. Ромащенко
Семестрвесна 2015
Дата начала04.04.2015
Количество пар10
Язык курсарусский
Вопросы к экзамену
Аннотация

Сколько информации содержится в генетическом коде человека? Какова взаимная информация между текстами романов “Война и мир” и “Анна Каренина”?

Чтобы попытаться ответить на эти вопросы (или хотя бы понять, есть в них какой-то смысл), нужно уточнить понятие “количество информации”. Математики и инженеры в разных контекстах используют разные определения информации: комбинаторное определение информации по Хартли, вероятностное определение энтропии Шеннона, алгоритмическое определение сложности по Колмогорову.

В курсе мы изучим эти определения и обсудим их области применения:

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

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция 1. Комбинаторный подход к определению понятия информации, информация по Хартли.
(04.04.2015 - 17:20 - 18:55)

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

https://www.youtube.com/watch?v=jrT5WquxjqA
2. Лекция 2. Вероятностный подход к определению понятия информации, информация по Шеннону.
(04.04.2015 - 19:15 - 20:50)

Определение энтропии Шеннона; относительная энтропия и взаимная информация. Комбинаторные приложения: нижние оценки и эвристики в алгоритмах поиска.

https://www.youtube.com/watch?v=pnyg3v9caK0
3. Лекция 3. Вокруг теоремы Шеннона об оптимальном кодировании.
(05.04.2015 - 11:15 - 12:50)

Однозначно декодируемые и префиксные коды, неравенство Крафта. Теорема Шеннона об оптимальном кодировании случайной величины. Код Шеннона-Фано, код Хаффмана, арифметическое кодирование.

https://www.youtube.com/watch?v=dd8cj5UESyU
4. Лекция 4. Блоковое кодирование.
(05.04.2015 - 13:00 - 14:35)

Метод типичных последовательностей. Теорема о блоковом кодировании последовательности независимых одинаково распределенных случайных величин (с сильным обращением).

https://www.youtube.com/watch?v=BW95ILm_aY4
5. Лекция 5. Энтропийные профили наборов случайных величин и информационные неравенства.
(05.04.2015 - 15:35 - 17:10)

Энтропийные профили для пар и троек случайных величин. Классические неравенства для шенноновской энтропии. Условное неравенство для взаимной информации тройки случайных величин и его комбинаторное приложение.

https://www.youtube.com/watch?v=PcTXyF-pFkQ
6. Лекция 6. Энтропия в классической криптографии.
(11.04.2015 - 17:20 - 18:55)

Оценка Шеннона для длины ключа в симметричной схеме шифрования. Схемы совершенного разделения секрета. Идеальное разделение секрета, схема Шамира для пороговых структур доступа. Нижние оценки для размера доли секрета; пример Чирмаза с избыточностью $ \Omega(n/\log n) $ для схемы с $ n $ участниками.

https://www.youtube.com/watch?v=fk-7zb5fJLM
7. Лекция 7. Колмогоровская сложность.
(11.04.2015 - 19:15 - 20:50)

Простая колмогоровская сложность: определение и теорема о существовании оптимального декомпрессора. Энтропия Шеннона как верхняя оценка для колмогоровской сложности. Теорема Колмгорова—Левина о сложности пары. Симметричность взаимной информации и информационные неравенства для колмогоровской сложности.

https://www.youtube.com/watch?v=em0cadlcU1E
8. Лекция 8. Приложения колмогоровской сложности.
(12.04.2015 - 11:15 - 12:50)

Метод несжимаемых слов. Оценка сложности распознавания языка палиндромов на одноленточной машине Тьюринга. Теорема об иерархии для автоматов с несколькими читающими головками. Нижние оценки для схемной сложности. Сравнение вероятностного метода и метода несжимаемых слов.

https://www.youtube.com/watch?v=CVPvcgaicb0
9. Лекция 9. Случайность по Мартин-Лёфу.
(12.04.2015 - 13:00 - 14:35)

Префиксная сложность. Случайные по Мартин-Лёфу последовательности. Закон больших чисел в форме Харди и Литтлвуда. Дефект случайности и величина выигрыша в азартной игре.

https://www.youtube.com/watch?v=ZjmuFau8Hy4
10. Лекция 10. Коммуникационная сложность.
(12.04.2015 - 15:35 - 17:10)

Детерминированная модель коммуникационной сложности; доказательство нижних оценок методом трудного множества. Вероятностные коммуникационные модели; сложность предиката равенства. Экспоненциальный зазор между вероятностной и детерминированной коммуникационной сложностью. Нижние оценки для схемной сложности.

https://www.youtube.com/watch?v=zJTUoppdmNI
Ваша оценка: Пусто Средняя: 5 (10 votes)
Share |
Андрей Ромащенко и студенты
Андрей Ромащенко
Андрей Ромащенко
Андрей Ромащенко
Андрей Ромащенко