Теория Информации 2018/2019 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
Курс Теория информации проходит по пятницам в аудитории Кембридж ШАД Яндекса. Первая лекция 14 сентября.
 
Курс Теория информации проходит по пятницам в аудитории Кембридж ШАД Яндекса. Первая лекция 14 сентября.
  
−
**Лектор:** Николай Константинович Верещагин  
+
==Лектор==
 +
Николай Константинович Верещагин nikolay.vereshchagin@gmail.com
  
−
**Семинарист:** Александр Козачинский
+
==Семинарист==
  
−
**Контакты:** nikolay.vereshchagin@gmail.com, kozlach@mail.ru  
+
Александр Козачинский kozlach@mail.ru  
  
−
Для того, чтобы сдавать курс, необходимо зарегистрироваться на него в системе AnyTask. Чтобы сделать это, введите инвайт:  ?????? ((http://anytask.org/course/212 странице курса)).
 
  
−
{{ToC from=h2 to=h4}}
 
  
  
−
===Краткое описание===
+
==Краткое описание==
 
В науке не существует единого подхода к определению понятия информации. В разных областях это понятие трактуется по-разному. Имеются информация по Хартли, энтропия Шеннона, Колмогоровская сложность, коммуникационная сложность. Каждое из этих понятий отражает некоторую грань интуитивного понятия информации. В курсе будет рассказано об этих понятиях и как они применяются в решении разных задач.
 
В науке не существует единого подхода к определению понятия информации. В разных областях это понятие трактуется по-разному. Имеются информация по Хартли, энтропия Шеннона, Колмогоровская сложность, коммуникационная сложность. Каждое из этих понятий отражает некоторую грань интуитивного понятия информации. В курсе будет рассказано об этих понятиях и как они применяются в решении разных задач.
  
  
−
===Отчётность по курсу и критерии оценки===
+
==Отчётность по курсу и критерии оценки==
  
−
Всего будет 6 заданий и каждое оценивается по десятибальной системе (10 означает решение всех задач ДЗ). Таким образом, максимально возможное количество баллов за ДЗ равно 60. Оценка за каждое ДЗ будет выставляться в общую ведомость (в системе Any Task) примерно через неделю после дедлайна. Домашние задания можно сдать перед началом семинара (но не на самом семинаре или после него) семинаристу или послать по электронной почте в виде PDF по адресу kozlach@mail.ru или через систему Any Task.
+
Всего будет 6 заданий и каждое оценивается по десятибальной системе (10 означает решение всех задач ДЗ) и коллоквиум, оцениваемый тоже по 10-балльной системе.
 +
Оценка за каждое ДЗ будет выставляться в общую ведомость (в системе Any Task) примерно через неделю после дедлайна. Домашние задания можно сдать перед началом семинара (но не на самом семинаре или после него) семинаристу или послать по электронной почте в виде PDF по адресу kozlach@mail.ru или через систему Any Task.
 
Вопросы по оценке за ДЗ просьба присылать не в Any Task, а на kozlach@mail.ru (проще отвечать).  
 
Вопросы по оценке за ДЗ просьба присылать не в Any Task, а на kozlach@mail.ru (проще отвечать).  
 +
Среднее арифметическое оценок за домашние задания составляют накопленную оценку.
  
−
Сдача домашних заданий после их срока, а также сдача курса после окончания семестра невозможна (за исключением тех, кому нужно сдать курс для отчетности в ВШЭ - для них возможна пересдача, при которой накопленная
+
Сдача домашних заданий после их срока невозможна.
−
оценка аннулируется).
+
  
−
Отчетность для заочников не будет отличаться от отчетности для очников.
+
Коллоквиум состоит из двух теоретических вопросов, которые оцениваются в 5 баллов и состоится в сессию после второго модуля.
 +
 +
Итоговая оценка равна сумме оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/3.  Таким образом, каждое домашнее задание входит в итоговую оценку с коэффициентом 1/9.  
  
−
Итоговая оценка студентов ШАД рассчитывается по следующей таблице:
+
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать коллоквиум, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. 
−
30 баллов - зачет
+
−
39 баллов - хорошо
+
−
48 баллов - отлично
+
  
 +
====Правила округления====
  
 +
В вычислениях текущие оценки и промежуточные величины не округляются. Результат
 +
вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок.
 +
Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной
 +
оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6
 +
округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3,
 +
5,48 – до 5, 5,54 – до 6, 7.12 – до 8.
  
 
====Контрольные мероприятия и их сроки====
 
====Контрольные мероприятия и их сроки====
  
−
По курсу будет 6 домашних заданий, контрольных и промежуточных экзаменов не будет.
+
По курсу будет 6 домашних заданий, контрольных и экзаменов не будет.
  
 
Примерные сроки сдач заданий
 
Примерные сроки сдач заданий
  
−
Первое домашнее задание 22 сентября.
+
Первое домашнее задание 5 октября.
−
Второе домашнее задание 6 октября.  
+
Второе домашнее задание 19 октября.
−
Третье домашнее задание 20 октября.
+
Третье домашнее задание 2 ноября.
−
Четвертое домашнее   задание 10 ноября.
+
Четвертое домашнее задание 16 ноября.
−
Пятое домашнее задание 1 декабря.
+
Пятое домашнее задание 30 ноября.
−
Шестое домашнее задание 15 декабря.
+
Шестое домашнее задание 14 декабря.
 +
 
 +
Коллоквиум состоится с 20 по 26 декабря.
  
  
 
===Домашние задания  ===
 
===Домашние задания  ===
  
−
((file:dz1.pdf  Домашнее задание №1)) -- дедлайн  22 сентября.
 
  
−
((file:dz2.pdf  Домашнее задание №2)) -- дедлайн  6 октября.
 
  
−
((file:dz3.pdf  Домашнее задание №3)) -- дедлайн  20 октября.
+
==Программа курса==
−
 
+
−
((file:dz4.pdf  Домашнее задание №4)) -- дедлайн  3 ноября.
+
−
 
+
−
((file:dz5.pdf  Домашнее задание №5)) -- дедлайн  24 ноября.
+
−
 
+
−
((file:dz6.pdf  Домашнее задание №6)) -- дедлайн  15 декабря.
+
−
 
+
−
 
+
−
 
+
−
===Программа курса===
+
  
 
Информация по Хартли (двоичный логарифм количества возможных исходов).
 
Информация по Хартли (двоичный логарифм количества возможных исходов).
Строка 121: Строка 117:
 
Подход Р. Соломонова к прогнозировании битов последовательности, случайной по данному неизвестному распределению вероятностей; универсальные предсказатели.
 
Подход Р. Соломонова к прогнозировании битов последовательности, случайной по данному неизвестному распределению вероятностей; универсальные предсказатели.
  
−
===Прочитанные лекции===
+
==Планируемые  лекции==
  
−
====Лекция 1. (8 сентября) ====
+
====Лекция 1. (14 сентября) ====
 
Информация по Хартли в сообщении неизвестного исхода (двоичный логарифм количества возможных исходов). Информация в данном сообщении. Аддитивность информации при двух последовательных сообщениях. Применение информации по Хартли для получения верхних и нижних оценок в задачах сортировки (нижняя оценка для n монет, верхняя оценка для 5 монет) и поиска фальшивой монетки на чашечных весах (нижняя и верхняя оценка для n монет, верхняя оценка для 12 монет)
 
Информация по Хартли в сообщении неизвестного исхода (двоичный логарифм количества возможных исходов). Информация в данном сообщении. Аддитивность информации при двух последовательных сообщениях. Применение информации по Хартли для получения верхних и нижних оценок в задачах сортировки (нижняя оценка для n монет, верхняя оценка для 5 монет) и поиска фальшивой монетки на чашечных весах (нижняя и верхняя оценка для n монет, верхняя оценка для 12 монет)
  
−
====Лекция 2. (15 сентября) ====
+
====Лекция 2. (21 сентября) ====
 
Коммуникационные протоколы. Разбиение матрицы функции на прямоугольники. Метод трудных множеств, метод размера прямоугольников и метод ранга матрицы. Оценки этими методами коммуникационной сложности предикатов EQ, GT, DISJ, GT.
 
Коммуникационные протоколы. Разбиение матрицы функции на прямоугольники. Метод трудных множеств, метод размера прямоугольников и метод ранга матрицы. Оценки этими методами коммуникационной сложности предикатов EQ, GT, DISJ, GT.
  
−
====Лекция 3. (22 сентября) ====
+
====Лекция 3. (5 октября) ====
 
Определение энтропии Шеннона. Задача о префиксном кодировании. Неравенство Крафта. Нижняя и верхняя оценки средней длины префиксного кода с помощью энтропии. Сбалансированные коды.
 
Определение энтропии Шеннона. Задача о префиксном кодировании. Неравенство Крафта. Нижняя и верхняя оценки средней длины префиксного кода с помощью энтропии. Сбалансированные коды.
  
−
====Лекция 4. (29 сентября) ====
+
====Лекция 4. (12 октября) ====
 
Код Шеннона-Фано и арифметический код.  
 
Код Шеннона-Фано и арифметический код.  
 
Совместно распределенные случайные величины. Условная энтропия.
 
Совместно распределенные случайные величины. Условная энтропия.
 
Теорема об энтропии пары (она не превосходит суммы энтропий). Независимость и энтропия.
 
Теорема об энтропии пары (она не превосходит суммы энтропий). Независимость и энтропия.
  
−
====Лекция 5. (6 октября) ====
+
====Лекция 5. (19 октября) ====
 
Теорема Макмиллана (на прошлой лекции её не было). Оценка среднего количества переданных бит в коммуникационных протоколах с помощью энтропии Шеннона. Условная энтропия и её свойства (она неотрицательна и не превосходит безусловной энтропии, она равна разности двух безусловных). Понятие количества информации и его свойства. Информационные неравенства: метод релятивизации, метод диаграмм. Общая информация тройки слов и пример, когда она отрицательна.
 
Теорема Макмиллана (на прошлой лекции её не было). Оценка среднего количества переданных бит в коммуникационных протоколах с помощью энтропии Шеннона. Условная энтропия и её свойства (она неотрицательна и не превосходит безусловной энтропии, она равна разности двух безусловных). Понятие количества информации и его свойства. Информационные неравенства: метод релятивизации, метод диаграмм. Общая информация тройки слов и пример, когда она отрицательна.
  
  
−
====Лекция 6. (13 октября) ====  
+
====Лекция 6. (26 октября) ====  
  
 
Еще раз об основных информационных неравенствах. Базисное неравенство, неравенство треугольника. Цепное правило. Марковская цепь и ее свойство.  
 
Еще раз об основных информационных неравенствах. Базисное неравенство, неравенство треугольника. Цепное правило. Марковская цепь и ее свойство.  
Строка 147: Строка 143:
 
Теорема Шеннона об идеальном шифре. Неравенство Фано. Неравенство Фано для классификаторов.
 
Теорема Шеннона об идеальном шифре. Неравенство Фано. Неравенство Фано для классификаторов.
  
−
====Лекция 7. (20 октября) ====  
+
====Лекция 7. (2 ноября) ====  
  
 
Неравенство Ромащенко-Каседа (для количества квадратов).  
 
Неравенство Ромащенко-Каседа (для количества квадратов).  
Строка 154: Строка 150:
 
Сбалансированные слова и их количество. Кодирование, основанное на частотах диграмм. Оценки количества слов с данным набором диграмм.
 
Сбалансированные слова и их количество. Кодирование, основанное на частотах диграмм. Оценки количества слов с данным набором диграмм.
  
−
====Лекция 8. (27 октября) ====  
+
====Лекция 8. (9 ноября) ====  
  
 
Еще раз об оценке количества слов с данным набором диграмм.  
 
Еще раз об оценке количества слов с данным набором диграмм.  
 
Стационарные источники. Теорема Шеннона о бесшумном канале.
 
Стационарные источники. Теорема Шеннона о бесшумном канале.
  
−
====Лекция 9. (3 ноября) ====  
+
====Лекция 9. (16 ноября) ====  
  
−
Теорема Вольфа-Слепяна.
+
Теорема Вольфа-Слепяна (без доказательства в трудную сторону).
 
Каналы с шумом и их пропускная способность.
 
Каналы с шумом и их пропускная способность.
 +
Теорема Шеннона о канале с шумом (без доказательства).
  
−
====Лекция 10. (10 ноября) ====  
+
====Лекция 10. (23 ноября) ====  
−
 
+
−
Теорема Шеннона о канале с шумом.
+
 
Игры по предсказанию битов данной последовательности. Мартингалы.
 
Игры по предсказанию битов данной последовательности. Мартингалы.
−
 
−
====Лекция 11. (17 ноября) ====
 
−
 
 
Теорема об определении мартингалов стратегиями. Предсказания с экспертами. Случай логарифмического штрафа (ставки в казино) и случай единичного штрафа за ошибку.
 
Теорема об определении мартингалов стратегиями. Предсказания с экспертами. Случай логарифмического штрафа (ставки в казино) и случай единичного штрафа за ошибку.
  
−
====Лекция 12. (24 ноября) ====  
+
====Лекция 11. (30 ноября) ====  
 
Выпуклые функции штрафа. Условие Блэквела. Линейный, полиномиальный
 
Выпуклые функции штрафа. Условие Блэквела. Линейный, полиномиальный
 
и экспоненциальный предсказатели.
 
и экспоненциальный предсказатели.
  
−
====Лекция 13. (1 декабря) ====  
+
====Лекция 12. (7 декабря) ====  
−
 
+
 
PAC learning и размерность Вапника - Червоненкиса.
 
PAC learning и размерность Вапника - Червоненкиса.
 
Лемма Зауэра - Шелаха. Оценка качества
 
Лемма Зауэра - Шелаха. Оценка качества
 
эмпирически наилучшего предсказателя через количество концепций.
 
эмпирически наилучшего предсказателя через количество концепций.
  
−
====Лекция 14. (8 декабря) ====  
+
====Лекция 13. (14 декабря) ====  
−
 
+
 
Декомпрессоры. Колмогоровская сложность и теорема Колмогорова-Соломонова. Оценка на число слов колмогоровской сложности не больше n. Неубывание колмогоровской сложности при алгоритмических преобразований. Невычислимость колмогоровской сложности и  теорема Геделя о неполноте в форме Чейтина.
 
Декомпрессоры. Колмогоровская сложность и теорема Колмогорова-Соломонова. Оценка на число слов колмогоровской сложности не больше n. Неубывание колмогоровской сложности при алгоритмических преобразований. Невычислимость колмогоровской сложности и  теорема Геделя о неполноте в форме Чейтина.
  
−
====Лекция 15. (15 декабря) ====
 
−
 
−
Сложность других конструктивных объектов. Неравенство для сложности пары. Условная сложность.
 
−
Теорема Колмогорова - Левина о сложности пары. Количество информации. Его свойства. Релятивизация.
 
−
Сложность и энтропия Шеннона. Теорема Ромащенко о совпадении классов неравенств.
 
  
 
===Проведённые семинары===
 
===Проведённые семинары===
  
−
**Семинар 1** (8 сентября)
+
**Семинар 1** (14 сентября)  
−
Упорядочивания камней. Отгадывания числа с разной ценой за ответ ДА и за ответ НЕТ. Отгадывание перестановки, если можно задавать вопросы, чему равен образ некоторого подмножества (на примере доски 8 на 8 и расстановки 64 чисел)
+
  
−
**Семинар 2** (15 сентября)  
+
**Семинар 2** (21 сентября)  
−
Ранги коммуникационных матриц предикатов IP и DISJ. Коммуникационная сложность матрицы смежности любого графа не меньше логарифма его хроматического числа.
+
  
−
**Семинар 3** (22 сентября)  
+
**Семинар 3** (5 октября)  
−
Задача о мировой серии (две команды играют до 4 побед, по радио сообщают результаты всех матчей,  чему равна энтропия этого сообщения?). Достаточное условие существования fix-free кодов (кодов, являющихся и префиксными, и суффиксными). Несбалансированность кода Хаффмана.
+
  
−
**Семинар 4** (29 сентября)  
+
**Семинар 4** (12 октября)  
−
Неравенство $H(f(X)) \le H(X)$. Применение неравенства Крафта: коммуникационный протокол, находящий пересечение двух множеств размера не больше $n$, за $n\log_2 3$ битов. Онлайн-алгоритм построения префиксного кода.
+
  
−
**Семинар 5** (6 октября)
+
**Семинар 5** (19 октября)
−
Алгоритм проверки общезначимости линейного неравенства от энтропий трех случайных величин и энтропий кортежей, составленных из них. Неравенство Шерера и его применения: неравенство Лумиса-Уитни, оценка числа треугольников в графе через число ребер. Обобщенное неравенство Шерера.
+
  
−
**Семинар 6** (13 октября)
+
**Семинар 6** (26 октября)
−
Нематериализуемость условной энтропии. Оценка модуля разности энтропий двух распределений через статистическое расстояние при помощи неравенства Фано. Начало задачи про то, насколько можно сжать случайную строку, чтобы любую координату можно было восстановить с вероятностью 1/2 + \delta
+
  
−
**Семинар 7** (20 октября)
+
**Семинар 7** (2 ноября)
−
Неравенство H(\alpha, \beta)/2 \ge H(\beta|\alpha) для первой и второй буквы случайной биграммы. Задача на минимально возможную информативность классификатора при заданной точности и заданном покрытии.
+
  
−
**Семинар 8** (27 октября)
+
**Семинар 8** (9 ноября)
−
Еще одно применение неравенства Фано: чтобы каждую координату случайной строки можно было восстановить с вероятностью 1/2 + \delta, необходимо и достаточно сжать строку в 1/\delta^2 раз. Верхняя оценка покрытия классификатора при известной точности и информативности.
+
  
−
**Семинар 9** (3 ноября)
+
**Семинар 9** (16 ноября)
−
Задачи про хеш-функции. Пример на нахождение минимальной вероятности ошибки при кодирования одного бита в шумном канале. Пропускная способность бинарного симметричного канала. Различные соединения каналов.
+
  
−
**Семинар 10** (10 ноября)
+
**Семинар 10** (23 ноября)
−
Пропускная способность последовательного соединения двух каналов не превосходит минимума пропускных способностей соединяемых каналов и может быть меньше. Формула для пропускной способности прямой суммы двух каналов.
+
  
−
**Семинар 11** (17 ноября)
+
**Семинар 11** (30 ноября)
−
Полиномиальный алгоритм поиска номера данного слова в лексикографическом порядке среди всех слов с тем же буквенным составом. Задача о предсказывании последовательности с равным количеством нулей и единиц в случае единичного штрафа за ошибку. Предсказывание выпадений граней кубика с неравновероятными гранями.
+
  
−
**Семинар 12** (24 ноября)
+
**Семинар 12** (7 декабря)
−
Задача про подсчет количества слов с данным биграммным составом. Разные определения мартингалов. Любой мартингал можно переделать так, что если раньше мартингал был  неограничен на каких-то последовательностях, то новый мартингал на тех же последовательностях стремится к бесконечности. Предсказывание граней кубика с равновероятными, но неравнозначными гранями.
+
  
−
**Семинар 13** (1 декабря)
+
**Семинар 13** (14 декабря)
−
VC-размерность семейства полупространств. VC-размерность семейства индикаторов прямоугольников на плоскости со сторонами, параллельными координатным осям. Изучение семейства индикаторов прямоугольников в модели PAC-learning
+
  
−
**Семинар 14** (8 декабря)
 
−
VC-размерность семейства конъюнкций. С какой точностью верно неравенство между сложностью пары и суммой сложностей? Максимальное время работы оптимального декомпрессора на входах длины не более n.
 
  
−
**Семинар 15** (15 декабря)
 
−
Колмогоровская сложность максимального времени работы оптимального декомпрессора на входах длины не более n (учитывая только те входы, на которых он останавливается) равна n + O(\log n). Самый сложный граф на n вершинах имеет цикл и является связным. Для любого оптимального декомпрессора количество кратчайших описаний у любого слова ограничено константой.
 
  
  
−
===Материалы по курсу===
+
==Рекомендуемая литература  ==
  
−
====Видеолекции  ====
 
−
 
−
https://wiki.school.yandex.ru/shad/Videocollections2.0/FirstYear/videoInformationTheory/
 
−
 
−
====Рекомендуемая литература  ====
 
−
 
−
1. ((file:Sch_Ver.pdf  Н.К. Верещагин, Е.В. Щепин. Информация, кодирование и предсказание.)) Москва, МНЦМО 2012.
 
 
   
 
   
−
2. ((https://www.dropbox.com/s/zyxfaiqyqqm1gmn/information.pdf?dl=0 Конспекты лекций.))
+
1. ((https://www.dropbox.com/s/zyxfaiqyqqm1gmn/information.pdf?dl=0 Конспекты лекций.))
  
 
3. А.M. Яглом, И.М. Яглом. Вероятность и информация.
 
3. А.M. Яглом, И.М. Яглом. Вероятность и информация.

Версия 14:20, 12 сентября 2018

Курс Теория информации проходит по пятницам в аудитории Кембридж ШАД Яндекса. Первая лекция 14 сентября.

Лектор

Николай Константинович Верещагин nikolay.vereshchagin@gmail.com

Семинарист

Александр Козачинский kozlach@mail.ru



Краткое описание

В науке не существует единого подхода к определению понятия информации. В разных областях это понятие трактуется по-разному. Имеются информация по Хартли, энтропия Шеннона, Колмогоровская сложность, коммуникационная сложность. Каждое из этих понятий отражает некоторую грань интуитивного понятия информации. В курсе будет рассказано об этих понятиях и как они применяются в решении разных задач.


Отчётность по курсу и критерии оценки

Всего будет 6 заданий и каждое оценивается по десятибальной системе (10 означает решение всех задач ДЗ) и коллоквиум, оцениваемый тоже по 10-балльной системе. Оценка за каждое ДЗ будет выставляться в общую ведомость (в системе Any Task) примерно через неделю после дедлайна. Домашние задания можно сдать перед началом семинара (но не на самом семинаре или после него) семинаристу или послать по электронной почте в виде PDF по адресу kozlach@mail.ru или через систему Any Task. Вопросы по оценке за ДЗ просьба присылать не в Any Task, а на kozlach@mail.ru (проще отвечать). Среднее арифметическое оценок за домашние задания составляют накопленную оценку.

Сдача домашних заданий после их срока невозможна.

Коллоквиум состоит из двух теоретических вопросов, которые оцениваются в 5 баллов и состоится в сессию после второго модуля.

Итоговая оценка равна сумме оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/3. Таким образом, каждое домашнее задание входит в итоговую оценку с коэффициентом 1/9.

Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать коллоквиум, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной.

Правила округления

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок. Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.

Контрольные мероприятия и их сроки

По курсу будет 6 домашних заданий, контрольных и экзаменов не будет.

Примерные сроки сдач заданий

Первое домашнее задание 5 октября. Второе домашнее задание 19 октября. Третье домашнее задание 2 ноября. Четвертое домашнее задание 16 ноября. Пятое домашнее задание 30 ноября. Шестое домашнее задание 14 декабря.

Коллоквиум состоится с 20 по 26 декабря.


Домашние задания

Программа курса

Информация по Хартли (двоичный логарифм количества возможных исходов).

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

Применения информационного подхода в коммуникационной сложности: метод прямоугольников.

Распределения вероятностей на буквах данного алфавита (случайные величины со значениями в данном конечном множестве). Однозначные и префиксные бинарные коды букв данного алфавита. Средняя длина кода одной буквы.

Определение энтропии Шеннона и ее связь со средней длинной оптимального префиксного кода. Код Шеннона-Фано.

Неравенство Крафта-Макмиллана и нижняя оценка средней длины любого однозначного кода.

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

Пары совместно распределенных случайных величин с конечными множествами исходов. Неравенство для энтропии Шеннона пары.

Условная энтропия Шеннона и ее свойства.

Независимость и энтропия. Информация в одной случайной величине о другой. Коммутативность информации.

Игра по угадыванию исхода случайной величины. Стоимость инсайдерской информации и энтропия Шеннона. Использование экспертов и аггрегационный алгоритм Вовка.

Информационные неравенства. Базисные неравества и их следствия (шенноновские неравенства).

Близкие случайные величины и неравенство Фано.

Классификаторы и их информативность.

Теорема Шеннона о блочном кодировании (Shannon noiseless coding theorem).

Пропускная способность канала с шумом и теорема о блочном кодировании для каналов с шумом (без полного доказательтсва).

Передача информации при наличии исходной информации у потребителя. Теорема Вольфа-Слепяна (без полного доказательтсва).

Предсказание с использованием экспертов

PAC learning: нахождение значения одной одной случайной величины по известному значению другой при неизвестном заранее совместном распределении вероятностей. Размерность Вапника-Червоненкиса. Бустинг.

Сжатие информации и универсальные декомпрессоры. Количество информации в данном тексте (файле) по Колмогорову (колмогоровская сложность)

Свойства колмогоровской сложности: сложность не превосходит длины, сложность не увеличивается при алгоритмических преобразованиях, сложность невычислима, но перечислима сверху.

Количество слов малой сложности, несжимаемые слова.

Применения колмогоровской сложности для оценки времени работы алгоритмов (оценка количества шагов для копирования одноленточной машиной Тьюринга)

Условная колмогоровская сложность. Сложность пары слов и теорема Колмогорова-Левина.

Аналогия между колмогороской сложностью, шенноновской энтропией и информацией по Хартли.

Связь колмогоровской сложности и энтропии Шеннона: колмогоровская сложность слова, состоящего из последовательности независимых одинаково распределенных букв равна его энтропии Шеннона.

Подход Р. Соломонова к прогнозировании битов последовательности, случайной по данному неизвестному распределению вероятностей; универсальные предсказатели.

Планируемые лекции

Лекция 1. (14 сентября)

Информация по Хартли в сообщении неизвестного исхода (двоичный логарифм количества возможных исходов). Информация в данном сообщении. Аддитивность информации при двух последовательных сообщениях. Применение информации по Хартли для получения верхних и нижних оценок в задачах сортировки (нижняя оценка для n монет, верхняя оценка для 5 монет) и поиска фальшивой монетки на чашечных весах (нижняя и верхняя оценка для n монет, верхняя оценка для 12 монет)

Лекция 2. (21 сентября)

Коммуникационные протоколы. Разбиение матрицы функции на прямоугольники. Метод трудных множеств, метод размера прямоугольников и метод ранга матрицы. Оценки этими методами коммуникационной сложности предикатов EQ, GT, DISJ, GT.

Лекция 3. (5 октября)

Определение энтропии Шеннона. Задача о префиксном кодировании. Неравенство Крафта. Нижняя и верхняя оценки средней длины префиксного кода с помощью энтропии. Сбалансированные коды.

Лекция 4. (12 октября)

Код Шеннона-Фано и арифметический код. Совместно распределенные случайные величины. Условная энтропия. Теорема об энтропии пары (она не превосходит суммы энтропий). Независимость и энтропия.

Лекция 5. (19 октября)

Теорема Макмиллана (на прошлой лекции её не было). Оценка среднего количества переданных бит в коммуникационных протоколах с помощью энтропии Шеннона. Условная энтропия и её свойства (она неотрицательна и не превосходит безусловной энтропии, она равна разности двух безусловных). Понятие количества информации и его свойства. Информационные неравенства: метод релятивизации, метод диаграмм. Общая информация тройки слов и пример, когда она отрицательна.


Лекция 6. (26 октября)

Еще раз об основных информационных неравенствах. Базисное неравенство, неравенство треугольника. Цепное правило. Марковская цепь и ее свойство.

Теорема Шеннона об идеальном шифре. Неравенство Фано. Неравенство Фано для классификаторов.

Лекция 7. (2 ноября)

Неравенство Ромащенко-Каседа (для количества квадратов).

Количество слов с данными частотами. Сбалансированные слова и их количество. Кодирование, основанное на частотах диграмм. Оценки количества слов с данным набором диграмм.

Лекция 8. (9 ноября)

Еще раз об оценке количества слов с данным набором диграмм. Стационарные источники. Теорема Шеннона о бесшумном канале.

Лекция 9. (16 ноября)

Теорема Вольфа-Слепяна (без доказательства в трудную сторону). Каналы с шумом и их пропускная способность. Теорема Шеннона о канале с шумом (без доказательства).

Лекция 10. (23 ноября)

Игры по предсказанию битов данной последовательности. Мартингалы. Теорема об определении мартингалов стратегиями. Предсказания с экспертами. Случай логарифмического штрафа (ставки в казино) и случай единичного штрафа за ошибку.

Лекция 11. (30 ноября)

Выпуклые функции штрафа. Условие Блэквела. Линейный, полиномиальный и экспоненциальный предсказатели.

Лекция 12. (7 декабря)

PAC learning и размерность Вапника - Червоненкиса. Лемма Зауэра - Шелаха. Оценка качества эмпирически наилучшего предсказателя через количество концепций.

Лекция 13. (14 декабря)

Декомпрессоры. Колмогоровская сложность и теорема Колмогорова-Соломонова. Оценка на число слов колмогоровской сложности не больше n. Неубывание колмогоровской сложности при алгоритмических преобразований. Невычислимость колмогоровской сложности и теорема Геделя о неполноте в форме Чейтина.


Проведённые семинары

    • Семинар 1** (14 сентября)
    • Семинар 2** (21 сентября)
    • Семинар 3** (5 октября)
    • Семинар 4** (12 октября)
    • Семинар 5** (19 октября)
    • Семинар 6** (26 октября)
    • Семинар 7** (2 ноября)
    • Семинар 8** (9 ноября)
    • Семинар 9** (16 ноября)
    • Семинар 10** (23 ноября)
    • Семинар 11** (30 ноября)
    • Семинар 12** (7 декабря)
    • Семинар 13** (14 декабря)



Рекомендуемая литература

1. ((https://www.dropbox.com/s/zyxfaiqyqqm1gmn/information.pdf?dl=0 Конспекты лекций.))

3. А.M. Яглом, И.М. Яглом. Вероятность и информация.

4. В.А. Успенский, Н.К. Верещагин, А. Шень. Колмогоровская сложность. http://www.mccme.ru/free-books/shen/kolmbook.pdf

5. Li M., Vitanyi P., An Introduction to Kolmogorov Complexity and Its Applications, Second Edition, Springer, 1997. (638 pp.)

6. Кернер, Чисар. Теория информации.

7. Nicolo Cesa-Bianchi, Gabor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.

Полезные ссылки

Материалы иного рода.

Новости

Источник — «http://wiki.cs.hse.ru/index.php?title=Теория_Информации_2018/2019&oldid=29021»