https://wikicshse.ru/index.php?action=history&feed=atom&title=InfTheory2022 2026-06-06T13:25:08Z История изменений этой страницы в вики MediaWiki 1.45.3 https://wikicshse.ru/index.php?title=InfTheory2022&diff=343&oldid=prev 2022-12-08T10:39:02Z

<p>Migrated current public revision from wiki.cs.hse.ru</p> <p><b>Новая страница</b></p><div>=Теория информации 2022=<br /> <br /> Cпециальный курс ШАД Яндекса. <br /> <br /> Проходит по вторникам онлайн, лекция 18:00 - 19:25, семинар 19:35 - 21:00. Первая лекция и семинар 13 сентября. <br /> <br /> [ Оценки]<br /> <br /> Лектор: Николай Константинович Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> Семинарист: Алексей Милованов almas239@gmail.com <br /> <br /> Консультации: meet.google.com/vru-rkzp-gnv<br /> <br /> Контакты: группа в телеграме для вопросов https://t.me/+xmPSxuaN1wZlYzky<br /> <br /> ===Новости===<br /> <br /> ===Краткое описание===<br /> В науке не существует единого подхода к определению понятия информации. В разных областях это понятие трактуется по-разному. Имеются информация по Хартли, энтропия Шеннона, Колмогоровская сложность, коммуникационная сложность. Каждое из этих понятий отражает некоторую грань интуитивного понятия информации. В курсе будет рассказано об этих понятиях и как они применяются в решении разных задач.<br /> <br /> <br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> Оценка за курс складывается из оценки за домашние задания и оценки за экзамен с коэффициентами 0.6 и 0.4, соответственно. Таким образом, каждое домашнее задание входит в итоговую оценку с коэффициентом 0.1. <br /> <br /> Всего будет 6 заданий и каждое оценивается по десятибальной системе (10 означает решение всех задач ДЗ).<br /> Оценка за каждое ДЗ будет выставляться в общую ведомость примерно через неделю после дедлайна. Домашние задания можно послать по электронной почте в виде PDF по адресу almas239@gmail.com или через систему LMS. Крайне рекомендуется использовать TeX. Вопросы по оценке за ДЗ просьба присылать на almas239@gmail.com или в телеграм (проще отвечать). <br /> <br /> Сдача в виде фото или скана рукописных решений возможна. Однако такие решения в силу естественных причин проверяются дольше. Неразборчивые места при проверке пропускаются, что может привести к снижению оценки.<br /> *Не будут проверяться решения, в которых изображения не сведены в один файл.<br /> <br /> Устный экзамен состоит из двух теоретических вопросов, которые оцениваются в 5 баллов и состоится в сессию после второго модуля. Таким образом максимальная оценка за устный экзамен равна 10.<br /> <br /> Те, кто не смог прийти на устный экзамен по болезни, могут его сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать устный экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. <br /> <br /> ===Правила округления=== <br /> <br /> В вычислениях текущие оценки и промежуточные величины не округляются. Результат<br /> вычисляется точно и округляется только в момент выставления оценки за ДЗ и итоговой оценок.<br /> Округление при выставлении обоих оценок арифметическое. Т.е. 5,49 округляется до 5,<br /> а 5,5 – до 6.<br /> <br /> ===Экзамен===<br /> <br /> Экзамен состоится 21 или 23 декабря (по выбору студента) с 10:00. [https://www.dropbox.com/s/x4almde6cuuh481/program2022.pdf?dl=0 Программа экзамена.]<br /> <br /> Запись на экзамен [https://docs.google.com/spreadsheets/d/1C-jBzDVaSdfCVBU44aj-JGW-facfD9mMAZfmSzsiZ3M/edit?usp=sharing в эту таблицу].<br /> Экзамен проводится на платформе Зум, каждый присоединяется к конференции в то время, на которое записался. В начале ответа Вы получите билет, в котором будет два теоретических вопроса из программы экзамена. Отвечать надо будет без подготовки в режиме реального времени: рассуждать и вспоминать нужно будет устно в присутствии экзаменатора. При доказательстве теоремы можно расшарить свою запись или конспект и аннотировать их при необходимости. Оценка формируется следующим образом. Полный ответ на каждый из первых двух вопросов оценивается в 5 баллов (всего 10 баллов). При ответе на вопрос можно пользоваться любыми документами (электронными или бумажными).<br /> <br /> ===Программа курса===<br /> <br /> Информация по Хартли (двоичный логарифм количества возможных исходов).<br /> <br /> Применения информационного подхода для решения задач о взвешиваниях (сортировки): нижняя оценка n log n для количества сравнений, необходимых для сортировки n чисел, оценка количества сравнений необходимых для нахождения фальшивой монетки (или радиоактивного элемента).<br /> <br /> Применения информационного подхода в коммуникационной сложности: метод прямоугольников.<br /> <br /> Распределения вероятностей на буквах данного алфавита (случайные величины со значениями в данном конечном множестве). Однозначные и префиксные бинарные коды букв данного алфавита. Средняя длина кода одной буквы.<br /> <br /> Определение энтропии Шеннона и ее связь со средней длиной оптимального префиксного кода. Код Шеннона-Фано.<br /> <br /> Неравенство Крафта-Макмиллана и нижняя оценка средней длины любого однозначного кода.<br /> <br /> Реальные тексты, как марковские цепи небольшого порядка и верхняя оценка количества информации в них. Избыточность.<br /> <br /> Пары совместно распределенных случайных величин с конечными множествами исходов. Неравенство для энтропии Шеннона пары.<br /> <br /> Условная энтропия Шеннона и ее свойства.<br /> <br /> Независимость и энтропия. Информация в одной случайной величине о другой. Коммутативность информации.<br /> <br /> Игра по угадыванию исхода случайной величины. Стоимость инсайдерской информации и энтропия Шеннона. Использование экспертов и аггрегационный алгоритм Вовка.<br /> <br /> Информационные неравенства. Базисные неравества и их следствия (шенноновские неравенства).<br /> <br /> Близкие случайные величины и неравенство Фано. <br /> <br /> Классификаторы и их информативность.<br /> <br /> Теорема Шеннона о блочном кодировании (Shannon noiseless coding theorem).<br /> <br /> Пропускная способность канала с шумом и теорема о блочном кодировании для каналов с шумом (без полного доказательтсва).<br /> <br /> Передача информации при наличии исходной информации у потребителя. Теорема Вольфа-Слепяна (без полного доказательтсва).<br /> <br /> Предсказание с использованием экспертов<br /> <br /> PAC learning: нахождение значения одной одной случайной величины по известному значению другой при неизвестном заранее совместном распределении вероятностей. Размерность Вапника-Червоненкиса.<br /> Бустинг.<br /> <br /> Сжатие информации и универсальные декомпрессоры. Количество информации в данном тексте (файле)<br /> по Колмогорову (колмогоровская сложность)<br /> <br /> Свойства колмогоровской сложности: сложность не превосходит длины, сложность не увеличивается при алгоритмических преобразованиях, сложность невычислима, но перечислима сверху.<br /> <br /> Количество слов малой сложности, несжимаемые слова.<br /> <br /> Применения колмогоровской сложности для оценки времени работы алгоритмов (оценка количества шагов для копирования одноленточной машиной Тьюринга)<br /> <br /> Условная колмогоровская сложность. Сложность пары слов и теорема Колмогорова-Левина.<br /> <br /> Аналогия между колмогороской сложностью, шенноновской энтропией и информацией по Хартли.<br /> <br /> Связь колмогоровской сложности и энтропии Шеннона: колмогоровская сложность слова, состоящего из последовательности независимых одинаково распределенных букв равна его энтропии Шеннона.<br /> <br /> Подход Р. Соломонова к прогнозировании битов последовательности, случайной по данному неизвестному распределению вероятностей; универсальные предсказатели.<br /> <br /> ===Планируемые лекции===<br /> <br /> ====Лекция 1. ====<br /> Информация по Хартли в сообщении неизвестного исхода (двоичный логарифм количества возможных исходов). Информация в данном сообщении. Аддитивность информации при двух последовательных сообщениях. Применение информации по Хартли для получения верхних и нижних оценок в задачах сортировки (нижняя оценка для n монет, верхняя оценка для 5 монет) и поиска фальшивой монетки на чашечных весах (нижняя и верхняя оценка для n монет, верхняя оценка для 12 монет)<br /> <br /> ====Лекция 2. ====<br /> Деревья разрешения. <br /> <br /> Коммуникационные протоколы. Разбиение матрицы функции на прямоугольники. Метод трудных множеств и метод размера прямоугольников. Оценки этими методами коммуникационной сложности предикатов EQ, GT, IT (без доказательства).<br /> <br /> ====Лекция 3. ====<br /> Определение энтропии Шеннона. Задача о префиксном кодировании. Неравенство Крафта. Теорема Макмиллана. Нижняя и верхняя оценки средней длины префиксного кода с помощью энтропии. <br /> <br /> ====Лекция 4. ====<br /> <br /> Когда энтропия распределения на n исходах максимальна.<br /> Применение энтропии для нижней оценки среднего количества вопросов для деревьев разрешения.<br /> <br /> Сбалансированные коды. Код Шеннона-Фано и арифметический код. Код Хаффмана.<br /> Совместно распределенные случайные величины. <br /> Теорема об энтропии пары (она не превосходит суммы энтропий). Независимость и энтропия.<br /> <br /> ====Лекция 5. ====<br /> Условная энтропия и её свойства (она неотрицательна и не превосходит безусловной энтропии, она равна разности двух безусловных).<br /> Понятие количества информации и его свойства. Информационные неравенства: метод релятивизации, метод диаграмм. Общая информация тройки слов и пример, когда она отрицательна.<br /> Неравенство треугольника. Цепное правило. Неравенство Шерера и вывод из него <br /> неравенства Лумиса-Уитни. <br /> <br /> ====Лекция 6. ==== <br /> <br /> Неравенство Ромащенко-Каседа и вывод из него неравенства для количества квадратов. <br /> Марковская цепь и ее свойство. <br /> Теорема Шеннона об идеальном шифре. Неравенство Фано. Неравенство Фано для классификаторов. <br /> <br /> <br /> ====Лекция 7. ==== <br /> Количество слов с данными частотами. Сбалансированные слова и их количество.<br /> Кодирование, основанное на частотах диграмм. Оценки количества слов с данным набором диграмм.<br /> <br /> ====Лекция 8. ==== <br /> <br /> Стационарные источники.<br /> Теорема Шеннона о бесшумном канале.<br /> <br /> ====Лекция 9. ==== <br /> Теорема Вольфа-Слепяна (c доказательством).<br /> Каналы с шумом и их пропускная способность.<br /> <br /> ====Лекция 10. ==== <br /> Теорема Шеннона о канале с шумом (без подробного доказательства).<br /> Игры по предсказанию битов данной последовательности. Мартингалы.<br /> Теорема об определении мартингалов стратегиями. <br /> <br /> <br /> ====Лекция 11. ==== <br /> Предсказания с экспертами. Логарифмический штраф и предсказатель Соломонова.<br /> Выпуклые функции штрафа. Условие Блэквела. Линейный предсказатель.<br /> <br /> ====Лекция 12. ==== <br /> Полиномиальный и экспоненциальный предсказатели.<br /> PAC learning и размерность Вапника - Червоненкиса.<br /> Лемма Зауэра - Шелаха.<br /> <br /> ====Лекция 13. ====<br /> Декомпрессоры. Колмогоровская сложность и теорема Колмогорова-Соломонова. Оценка на число слов колмогоровской сложности не больше n. Сложность и длина. Неубывание колмогоровской сложности при алгоритмических преобразований. <br /> Неравенство для сложности пары. Условная сложность. <br /> <br /> ====Лекция 14. ====<br /> Теорема Колмогорова - Левина о сложности пары.<br /> Количество информации. Сложность и энтропия Шеннона. Теорема Ромащенко<br /> о совпадении классов неравенств.<br /> <br /> ===Материалы по курсу===<br /> <br /> ====Видеолекции ====<br /> <br /> https://wiki.school.yandex.ru/shad/Videocollections2.0/FirstYear/videoInformationTheory/<br /> <br /> ====Рекомендуемая литература ====<br /> <br /> 1. [https://wiki.school.yandex.ru/shad/groups/2018/Semester1/InformationTheory/Sch_Ver.pdf Н.К. Верещагин, Е.В. Щепин. Информация, кодирование и предсказание.] Москва, МНЦМО 2012.<br /> <br /> 2. [https://www.dropbox.com/s/wf05hwmzbjaelrr/main.pdf?dl=0 Конспекты лекций.]<br /> <br /> 3. А.M. Яглом, И.М. Яглом. Вероятность и информация.<br /> <br /> 4. В.А. Успенский, Н.К. Верещагин, А. Шень.<br /> Колмогоровская сложность.<br /> http://www.mccme.ru/free-books/shen/kolmbook.pdf<br /> <br /> 5. Li M., Vitanyi P., An Introduction to Kolmogorov<br /> Complexity and Its Applications, Second Edition, Springer,<br /> 1997. (638 pp.)<br /> <br /> 6. Кернер, Чисар. Теория информации.<br /> <br /> 7. Nicolo Cesa-Bianchi, Gabor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.<br /> <br /> ====Полезные ссылки ====<br /> <br /> ====Материалы иного рода. ====</div>

imported>Nvereshagin