CCTI 2020 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
м (Откат правок Seosky (обсуждение) к версии Milovanov)
 
(не показано 185 промежуточных версии 3 участников)
Строка 1: Строка 1:
 
= Сложность вычислений и логика в теоретической информатике (3-ий курс ТИ) 2020 год =
 
= Сложность вычислений и логика в теоретической информатике (3-ий курс ТИ) 2020 год =
  
−
Лекции проходят по средам в аудитории G120 в 15:10-16:30.
+
Лекции проходят по вторникам  15:10-16:30, семинары  16:40-18:00 по ссылке https://zoom.us/j/461361055
−
Семинары по средам в аудитории G120 в 16:40-18:00.  
+
−
Первая лекция и семинар 22 января.
+
  
−
'''[https://t.me/joinchat/GQufoBIS_oUktcWHuqSjZg Группа в телеграме для вопросов]'''
+
Первая лекция и семинар 21 января.
  
 
==Новости==
 
==Новости==
 +
====20 июня====
 +
Экзамен состоится 22 июня в 12.10 и будет продолжаться 90 минут. Более подробная инструкция тут:
  
 +
1.  Экзамен письменный и проходит с прокторингом через Зум в двух конференциях
 +
https://zoom.us/j/91507546088
 +
https://zoom.us/j/94570444864
 +
(распределение по конференциям [https://docs.google.com/spreadsheets/d/1mrsKOieGXr-98mUCnjiJFAgPKH9RlvFvybqQmocLQB8/edit#gid=0 здесь)]. Присоединиться к конференции надо на десять минут раньше, то есть, в 12:00. В 12:10 станут доступны задания, которые надо  загрузить по ссылке https://www.dropbox.com/s/ualljvsdkp2mg35/exam22-06-2020.pdf?dl=0 (сейчас по этой ссылке находятся прошлогодние задания). Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com.  Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.
  
 +
2.  Экзамен длится 90 минут. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций: https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0, https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.
 +
 +
3.  Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.
 +
 +
====19 июня====
 +
Выложен
 +
[https://www.dropbox.com/s/185mhm4yq9279gq/exam_train.pdf?dl=0 тренировочный вариант] экзамена. Задачи на самом экзамене могут сильно отличаться.
 +
 +
====14 июня====
 +
Коллоквиум будет проходить по следующей ссылке
 +
https://zoom.us/j/92034518702
 +
 +
====4 июня====
 +
Перенос лекции на субботу ОТМЕНЯЕТСЯ. А коллоквиум переносится на 15 июня 10:00.
 +
Последняя лекция и семинар состоятся 9 июня с 15:10 по обычному расписанию.
 +
 +
====2 июня====
 +
По просьбе студентов, последняя лекциия и семинар переносятся со вторника 9 июня на субботу 6 июня. Лекция 10-11:20, семинар 11:30-12:50.
 +
Коллоквиум можно будет сдавать, как 6 июня с 13:00, так и 9 июня с 15:10, предварительно записавшись на некоторый слот
 +
в таблицу [https://docs.google.com/spreadsheets/d/1Ehpo-1t8jbEjVx4oqQ29CCVwB7IG2zoSvzYCR6ZKmss/edit?usp=sharing Таблица времени прихода на коллоквиум]
 +
 +
====1 июня====
 +
Выложена
 +
[https://docs.google.com/spreadsheets/d/1Ehpo-1t8jbEjVx4oqQ29CCVwB7IG2zoSvzYCR6ZKmss/edit?usp=sharing Таблица времени прихода на коллоквиум]
 +
 +
====26 мая====
 +
Выложена программа коллоквиума 6 июня. [https://www.dropbox.com/s/gm3ezn8ygyk54te/colloq2020.pdf?dl=0 Программа.]
 +
 +
====20 мая====
 +
Коллоквиум состоится 6 июня в 10.00.
 +
 +
Письменный экзамен состоится 22 июня в 12.10.
 +
 +
====21 апреля====
 +
Платформа webinar.ru оказалась неудобной для наших лекций. Начиная со следующего вторника мы возвращаемся в Zoom https://zoom.us/j/461361055
 +
Но теперь в конце или середине каждой лекции будет экспресс-тест на 10 минут, проводимый с помощью Гугл-формы. Те, кто заработают за тесты более половины максимально возможного количества баллов, получат 1 бонусный балл к итоговой оценке. Оценки за тесты выставляются в обычную ведомость https://www.dropbox.com/s/akpdy4oyflgd6zi/results_2020.xlsx?dl=0
 +
Сссылка на лекции и семинары: https://zoom.us/j/461361055
 +
 +
====28 марта====
 +
Согласно приказу ректора, все занятия 31 марта отменяются!
 +
 +
====21 марта====
 +
Лекция 24 марта (вторник) в 15:10-16:30 состоится в виде  вебинара. Вот ссылка на вебинар: https://zoom.us/j/912901893
 +
Преимущество вебинара перед Ютуб трансляцией в том, что удобнее задавать вопросы по ходу лекции (это можно делать и устно, и письменно).
 +
 +
====20 марта====
 +
Весенняя сессия отменяется, поэтому лекция и семинар 31 марта состоятся.
 +
 +
====16 марта====
 +
C 17 марта 2020 года ВШЭ  перешла на дистанционное обучение (карантинная мера, вызванная распостранением коронавируса). Лекции курса будут транслироваться и записываться в обычное время (по вторникам с 15:10 до 16:30) на Ютуб канале https://www.youtube.com/channel/UCQpMy-jk_5qdi91U9NsBVdQ?view_as=subscriber
 +
 +
Во время трансляции можно задавать вопросы в чате, на которые лектор сможет отвечать примерно с полминутной задержкой. Очередная трансляция состоится 17 марта.
 +
 +
[https://www.youtube.com/watch?v=UisbwObZ1QY Лекция 17 марта]
  
 
==Лектор==  
 
==Лектор==  
Строка 18: Строка 76:
  
 
Милованов Алексей Сергеевич almas239@gmail.com
 
Милованов Алексей Сергеевич almas239@gmail.com
 +
 +
Консультации (защиты): по вторникам 14-15, 18-19 и по средам 15.10-16 в S832.
  
 
==Краткое описание==
 
==Краткое описание==
Строка 28: Строка 88:
  
 
Разрешимость элементарных теорий упорядоченного поля действительных чисел (теорема Тарского-Зайденберга и  
 
Разрешимость элементарных теорий упорядоченного поля действительных чисел (теорема Тарского-Зайденберга и  
−
поля комплексных чисел.  
+
поля комплексных чисел.
−
 
+
  
 
==Отчётность по курсу и критерии оценки==
 
==Отчётность по курсу и критерии оценки==
Строка 35: Строка 94:
 
4 домашних задания, коллоквиум и экзамен.
 
4 домашних задания, коллоквиум и экзамен.
  
−
Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.
+
Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. Кроме этого в домашних задания могут бонусные задачи, за решение которых даются дополнительные баллы на коллоквиуме или экзамене (1 задача= 1 балл).  На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.
 
Сдача домашних заданий после их срока невозможна.
 
Сдача домашних заданий после их срока невозможна.
  
Строка 53: Строка 112:
 
====Коллоквиум====
 
====Коллоквиум====
  
 +
Коллоквиум состоится 15 июня в 10:00.
 +
Записываться в таблицу: [https://docs.google.com/spreadsheets/d/1Ehpo-1t8jbEjVx4oqQ29CCVwB7IG2zoSvzYCR6ZKmss/edit?usp=sharing Таблица времени прихода на коллоквиум]
 +
 +
[https://www.dropbox.com/s/gm3ezn8ygyk54te/colloq2020.pdf?dl=0 Программа коллоквиума.]
 +
Ссылка на Зум конференцию для тех, кто оказался записанным к лектору: https://us02web.zoom.us/j/82787088715
  
 
====Экзамен====
 
====Экзамен====
  
 +
Экзамен состоится 22 июня в 12.10 и будет продолжаться 90 минут. Более подробная инструкция тут:
  
−
====Пересдачи====
+
1.  Экзамен письменный и проходит с прокторингом через Зум в двух конференциях:
 +
https://zoom.us/j/91507546088
 +
https://zoom.us/j/94570444864
 +
(распределение по конференциям [https://docs.google.com/spreadsheets/d/1mrsKOieGXr-98mUCnjiJFAgPKH9RlvFvybqQmocLQB8/edit#gid=0 здесь)].https://zoom.us/j/94570444864. Присоединиться к конференции надо на десять минут раньше, то есть, в 12:00. В 12:10 станут доступны задания, которые надо  загрузить по ссылке https://www.dropbox.com/s/ualljvsdkp2mg35/exam22-06-2020.pdf?dl=0 (сейчас по этой ссылке находятся прошлогодние задания). Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com.  Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.
  
 +
2.  Экзамен длится 90 минут. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций: https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0, https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.
  
 +
3.  Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.
 +
 +
====Пересдачи====
  
 
==Примерные сроки контрольных мероприятий==
 
==Примерные сроки контрольных мероприятий==
  
−
Первое домашнее будет выложено 29.1.2019, срок сдачи 12.2.2019.
+
Первое домашнее будет выложено 29.1.2020, срок сдачи 11.2.2020.
  
−
Второе домашнее будет выложено 5.3.2019, срок сдачи 02.4.2019.
+
Второе домашнее будет выложено 3.3.2020, срок сдачи 31.3.2020.
  
−
Третье домашнее будет выложено 9.4.2019, срок сдачи 23.4.2019.
+
Третье домашнее будет выложено 24.4.2020, срок сдачи 19.5.2020.
  
−
Четвертое домашнее будет выложено 14.5.2019, срок сдачи 28.5.2019.
+
Четвертое домашнее будет выложено 14.5.2020, срок сдачи 9.6.2020.
  
 
==Домашние задания  ==
 
==Домашние задания  ==
  
−
''Скорее всего, во всех дз будет по 2 бонусных задачи. Каждая из них дает +1 к оценке коллоквиума или экзамена, по выбору студента.  Чтобы бонус засчитался, нужно за основную часть ДЗ получить не менее половины от максимально возможного балла.''
 
  
−
[https://www.dropbox.com/s/zhm6lzkimton7k3/results_2019.xlsx?dl=0 Оценки]
 
  
−
[https://www.dropbox.com/s/q2xzohnb5bqs83k/hw_1.pdf?dl=0 Домашнее задание 1.] Cрок сдачи 12.2.2019 в 12:10 MSK.
 
  
−
[https://www.dropbox.com/s/xx5nun615qm2591/hw_2.pdf?dl=0 Домашнее задание 2.] Срок сдачи 02.4.2019 в 12:10 MSK.
+
[https://www.dropbox.com/s/wcevcspilg63qep/hw1_expanders.pdf?dl=0 Домашнее задание 1]. Cрок сдачи 12.2.2020 в 12:10 MSK.
  
−
[https://www.dropbox.com/s/yrrpzd7ws2jxb9z/hw_3.pdf?dl=0 Домашнее задание 3.] Срок сдачи 30.4.2019 в 12:10 MSK.
+
[https://www.dropbox.com/s/oksggnm5e2pm7rh/hw2_expanders.pdf?dl=0 Домашнее задание 2] Срок сдачи 7.4.2020 в 16.40 MSK.
  
−
[https://www.dropbox.com/s/jt78vj3un9jg070/hw_4.pdf?dl=0 Домашнее задание 4.] Срок сдачи до коллоквиума.
+
[https://www.dropbox.com/s/p8y52xy7dg50u5y/CCTI_3.pdf?dl=0 Домашнее задание 3] Срок сдачи 19.5.2020 в 16.40 MSK.
  
−
==Прочитанные лекции==
+
[https://www.dropbox.com/s/dd98kswtswqubmf/CCTI_4.pdf?dl=0 Домашнее задание 4] Срок сдачи 16.6.2020 в 16.40 MSK.
  
 +
==Результаты ==
 +
[https://www.dropbox.com/s/j6vnaesx569p4cv/results_2020.xlsx?dl=0 Общая ведомость оценок]
  
 +
[https://www.dropbox.com/s/8hm8r0z8bdxtmx0/test1.xlsx?dl=0  Результаты теста 1]
 +
 +
[https://docs.google.com/spreadsheets/d/11jWr5fzwdTRnD2UH3u8oRMkW6VomdH3fiwmLoNz2-Jc/edit?usp=sharing  Результаты теста 2]
 +
 +
[https://docs.google.com/spreadsheets/d/1-2JQgSmIafNuwJkyn5EcYlGY94MNgyyzue25F2NI5qw Результаты теста 3.]
 +
 +
[https://docs.google.com/spreadsheets/d/1pL7eabfoztAlA8iLps9x_oyW4zuPbU7YMRFmLfc_-qY Результаты теста 4]
 +
 +
[https://docs.google.com/spreadsheets/d/1m3-9zWvk3MhApp6Di0KfK0qSYlPdcDykOsEIiCnZ5-s Результаты теста 5]
 +
 +
[https://docs.google.com/spreadsheets/d/1l2UfO8t68lIjt98LaibTY80KNl1edWY1MF1Ypmn7AhU Результаты теста 6 ]
 +
 +
==Прочитанные лекции==
  
−
====Лекция 1 (15 января).  ====
+
====Лекция 1 (21 января).  ====
  
 
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
 
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
 
Реберное расширение и его связь с вершинным расширением. Матрица графа и ее собственные числа.
 
Реберное расширение и его связь с вершинным расширением. Матрица графа и ее собственные числа.
  
−
====Лекция 2 (22 января).  ====
+
====Лекция 2 (28 января).  ====
 +
Максимальное по абсолютной величине собственное число регулярного графа. От чего зависит кратность
 +
собственного числа d. Второе по абсолютной величине собственное число двудольного графа.
  
 
Лемма о перемешивании. От спектрального экспандера к комбинаторному.
 
Лемма о перемешивании. От спектрального экспандера к комбинаторному.
  
−
====Лекция 3 (29 января).  ====
+
====Лекция 3 (4 февраля).  ====
 +
Вторая лемма о перемешивании.
 +
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа.
  
−
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа.  
+
====Лекция 4 (11 февраля). ====
 +
Формула для числа Каталана.
 
Вероятностное доказательство существования  d-регулярного спектрального экспандера с d^c вершинами.
 
Вероятностное доказательство существования  d-регулярного спектрального экспандера с d^c вершинами.
  
−
====Лекция 4 (5 февраля). ====
+
====Лекция 5 (18 февраля). ====
−
 
+
Степень графа и тензорное произведение графов и их собственные числа.  
−
Степень графа и тензорное произведение графов и их собственные числа. Зигзаг-произведение графов и первая оценка его собственных чисел. Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
+
Зигзаг-произведение графов и первая оценка его собственных чисел. Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
−
 
+
−
====Лекция 5 (12 февраля). ====
+
  
 +
====Лекция 6 (25 февраля). ====
 
Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
 
Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
 +
Вторая оценка для спектральной щели зигзаг-произведения.
  
−
Вторая оценка для спекртальной щели зигзаг-произведения.
+
====Лекция 7 (3 марта). ====
  
−
Алгоритм Рейнгольда.
+
Второе собственное число связного недвудольного графа.
  
−
====Лекция 6 (19 февраля). ====
 
 
Алгоритм Рейнгольда.
 
Алгоритм Рейнгольда.
−
Применение экспандеров для дерандомизации.
 
  
−
====Лекция 7 (26 февраля). ====
+
====Лекция 8 (10 марта). ====
 +
Применение экспандеров для дерандомизации.
  
−
Экспандер Маргулиса.
+
====Лекция 9 (17 марта). ====
 +
[https://www.youtube.com/watch?v=UisbwObZ1QY Экспандер Маргулиса.]
  
−
====Лекция 8 (5 марта). ====
+
====Лекция 10 (24 марта). ====
 +
[https://zoom.us/j/912901893 Двудольные экспандеры: определение и вероятностное доказательство существования.]
  
−
Экспандер Маргулиса (окончание доказательства).
+
====Лекция 11 (7 апреля). ====
  
−
Двудольные экспандеры: определение и вероятностное доказательство существования.
+
[https://youtu.be/K2K3oWc3J4A Экспандер Варди - Парвареша.]
  
−
====Лекция 9 (12 марта). ====
+
====Лекция 12 (14 апреля). ====
 +
[https://youtu.be/OfQgPjzH97Q Коды с исправлением ошибок и их параметры. Линейные коды. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.]
  
−
Экспандер Варди - Парвареша.
+
====Лекция 13 (21 апреля).  ====
 +
[https://events.webinar.ru/21463024/4301788/record-new/4390364 Линейные коды, проверочная матрица. Оценка Хэмминга и коды Хэмминга. Кодирование и декодирование для кодов Хэмминга.]
 +
https://events.webinar.ru/event/4301788/4390364
  
−
====Лекция 10 (19 марта). ====
+
====Лекция 14 (28 апреля) ====
  
−
Экспандерные коды: определение, параллельный и последовательный алгоритмы декодирования.
+
[https://youtu.be/cxtahdNgzGc Оценка Гилберта. Функция Шеннона. Графики оценок Хэмминга и Гилберта. Оценка Варшамова - Гилберта. Случайные линейные коды.]
−
====Лекция 11 (2 апреля). ====
+
  
−
Разрешимость элементарной теории поля комплексных чисел.
+
[https://docs.google.com/spreadsheets/d/11jWr5fzwdTRnD2UH3u8oRMkW6VomdH3fiwmLoNz2-Jc/edit?usp=sharing  Результаты теста 2]
  
−
====Лекция 12 (9 апреля). ====
+
====Лекция 15 (12 мая) ====
−
Разрешимость элементарной теории упорядоченного поля
+
[https://youtu.be/_xzNHL9eBKA Коды Возенкрафта. Каскадные коды. Декодирование каскадного кода.]
−
действительных чисел.
+
  
−
====Лекция 13 (16 апреля). ====
+
[https://docs.google.com/spreadsheets/d/1-2JQgSmIafNuwJkyn5EcYlGY94MNgyyzue25F2NI5qw Результаты теста 3.]
  
−
Деревья разрешения, метод противника. Сертификатная и недетерминированная сложность.
+
====Лекция 16. (19 мая) ====
−
Чувстительность и блочная чувствительность.  
+
[https://youtu.be/VPMnROaELpA Декодирование каскадного кода и коды Форни. Экспандерные коды: определение, последовательный алгоритм декодирования.]
−
Неравенства D < C_0 C_1, D< C_0 bs_1
+
  
−
====Лекция 14 (23 апреля). ====
+
[https://docs.google.com/spreadsheets/d/1pL7eabfoztAlA8iLps9x_oyW4zuPbU7YMRFmLfc_-qY Результаты теста 4]
  
−
Неравенство C_0< bs_0 s_1. Вероятностные деревья и неравенство bs = O(R)
+
====Лекция 17  (26 мая) ====
  
−
Представление булевых функций многочленами с действительными коэффициентами.
+
[https://youtu.be/HWNXos5uS1k Оценки Плоткина и коды Адамара. Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.]
  
−
Теорема Маркова.
+
====Лекция 18(2 июня ) ====
 +
[https://youtu.be/x-md75lO-c0 Деревья разрешения, метод противника. Сертификатная и недетерминированная сложность. Чувстительность и блочная чувствительность. Неравенствo D < C^2]
  
−
====Лекция 15 (30 апреля). ====
+
[https://docs.google.com/spreadsheets/d/1m3-9zWvk3MhApp6Di0KfK0qSYlPdcDykOsEIiCnZ5-s/edit#gid=1731981645 Результаты теста 5]
  
−
Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди).
+
====Лекция 19 (9 июня). ====
 +
Неравенствo D < C*bs
 +
Неравенство C< bs*s. Вероятностные деревья и неравенство bs = O(R)
  
−
Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ
+
[https://docs.google.com/spreadsheets/d/1l2UfO8t68lIjt98LaibTY80KNl1edWY1MF1Ypmn7AhU Результаты теста 6 ]
  
−
Связь между размером дерева и представлением функции в виде m,*-ДНФ и m,*-КНФ (Эренфойхт - Хауслер).
+
==== Не удалось рассказать:  ====
  
−
====Лекция 16 (14 мая). ====
 
  
 +
Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ
 
Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ (Эренфойхт - Хауслер).
 
Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ (Эренфойхт - Хауслер).
 +
Теорема Маркова.
 +
Представление булевых функций многочленами с действительными коэффициентами.
 +
Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди).
  
−
Метод Храпченко доказательства нижних оценок формульной сложности.
+
Разрешимость элементарной теории поля комплексных чисел.
−
 
+
Разрешимость элементарной теории упорядоченного поля
−
====Лекция 17 (21 мая). ====
+
действительных чисел.
−
 
+
−
Ограничения булевой функции. Нижняя оценка формульной сложности функции Андреева.
+
−
 
+
−
Теорема Разборова - Смоленского о нижней оценке размера формул ограниченной глубины.
+
−
 
+
−
====Лекция 18 (28 мая). ====
+
−
 
+
−
Коды с исправлением ошибок и их параметры. Линейные коды.
+
−
 
+
−
Оценка Синглтона и коды Рида - Соломона.
+
−
Декодирование кодов Рида - Соломона.
+
−
 
+
−
====Лекция 19 (4 июня). ====
+
−
 
+
−
Оценка Хэмминга и коды Хэмминга (без доказательства и построения)
+
−
 
+
−
Случайные коды и оценка Варшамова - Гилберта.
+
−
Коды Возенкрафта.
+
−
 
+
−
====Лекция 20 (11 июня). ====
+
−
 
+
−
Каскадные коды и коды Форни. Декодирование каскадного кода.
+
  
 
==Задачи для семинаров  ==
 
==Задачи для семинаров  ==
Строка 201: Строка 275:
 
'''[https://www.dropbox.com/s/mr072cifyo8gwou/listok1.pdf?dl=0 Листок 1  (комбинаторные экспандеры)]'''
 
'''[https://www.dropbox.com/s/mr072cifyo8gwou/listok1.pdf?dl=0 Листок 1  (комбинаторные экспандеры)]'''
  
−
'''[https://www.dropbox.com/s/mp1ki1l1gr57u7k/listok2.pdf?dl=0 Листок 2  (еще комбинаторные экспандеры)]'''
 
  
−
'''[https://www.dropbox.com/s/ts0c25lkv4904vr/listok3.pdf?dl=0 Листок 3 (спектр графов)]'''
+
'''[https://www.dropbox.com/s/2zmdygbscfbxcuz/cw2.pdf?dl=0 Листок 2 (спектр графов)]'''
  
−
'''[https://www.dropbox.com/s/2r8414hb714t63k/listok4.pdf?dl=0 Листок 4  (спектр графов и спектральные экспандеры)]'''
+
[https://www.dropbox.com/s/q1fa1zqbvnxg93k/cw3.pdf?dl=0 Листок 3]
  
−
'''[https://www.dropbox.com/s/m1grmoyst9ob6dg/listok5.pdf?dl=0 Листок 5  (случайные блуждания)]'''
+
[https://www.dropbox.com/s/tabqdex6vpeep6s/cw4.pdf?dl=0 Листок 4]
  
−
'''[https://www.dropbox.com/s/hxuhzdkov857vin/listok6.pdf?dl=0 Листок 6  (log-space алгоритмы)]'''
+
[https://www.dropbox.com/s/jp9o8n60yp4cfuq/cw5.pdf?dl=0 Листок 5]
  
−
'''[https://www.dropbox.com/s/di35x1lk5m6o2ck/listok7.pdf?dl=0 Листок 7  (продолжаем спектральные экспандеры)]'''
+
[https://www.dropbox.com/s/jlrezpzll64s256/cw6.pdf?dl=0 Листок 6]
  
−
'''[https://www.dropbox.com/s/ovlo3e3g9d58rad/listok8.pdf?dl=0 Листок 8  (аффинная плоскость и другие экспандеры)]'''
+
[https://www.dropbox.com/s/lwjgxpvfgs1btrn/cw7.pdf?dl=0 Листок 7]
  
−
'''[https://www.dropbox.com/s/hc5pl51oyh66o3k/listok9.pdf?dl=0 Листок 9  (двудольные экспандеры)]'''
+
[https://www.dropbox.com/s/3shmqxxxtr1y3gi/cw8.pdf?dl=0 Листок 8]
  
−
'''[https://www.dropbox.com/s/o3q2tm3a90zrho0/listok10.pdf?dl=0 Листок 10 (болты и гайки)]'''
+
[https://www.dropbox.com/s/u1l4jmfp966y78k/cw9.pdf?dl=0 Листок 9]
  
−
'''[https://www.dropbox.com/s/fs9w2gh3kwbz5wb/listok11.pdf?dl=0 Листок 11 (выразимость, элиминация кванторов)]'''
+
[https://www.dropbox.com/s/ar65k6q9wvcmsbb/cw10.pdf?dl=0 Листок 10]
  
−
'''[https://www.dropbox.com/s/mzkm72hplcwb7js/listok12.pdf?dl=0 Листок 12 (еще элиминация кванторов)]'''
+
[https://www.dropbox.com/s/adczqg30m0bl5pr/cw11.pdf?dl=0 Листок 11]
  
−
'''[https://www.dropbox.com/s/222ezqqshecm8b7/listok14.pdf?dl=0 Листок 14 (еще деревья разрешения)]'''
+
[https://www.dropbox.com/s/q46hx0t3fi8mqv5/cw12.pdf?dl=0 Листок 12]
  
−
'''[https://www.dropbox.com/s/znhfveu6cxi3n3r/listok15.pdf?dl=0 Листок 15 (деревья разрешения + немного схем)]'''
+
[https://www.dropbox.com/s/rr4bxw4xdbd4jra/cw13.pdf?dl=0 Листок 13]
  
−
'''[https://www.dropbox.com/s/8l2szgu7t7gzoez/listok16.pdf?dl=0 Листок 16 (схемы)]'''
+
[https://www.dropbox.com/s/ycz3cuzutsn2kg4/cw14.pdf?dl=0 Листок 14]
  
−
'''[https://www.dropbox.com/s/t9689386f5c89kv/listok17.pdf?dl=0 Листок 17 (еще схемы)]'''
+
[https://www.dropbox.com/s/z6nquyb30kz5bto/cw15.pdf?dl=0 Листок 15]
  
−
'''[https://www.dropbox.com/s/nvj71sfc4juo4v9/listok18.pdf?dl=0 Листок 18 (схемы + коды)]'''
+
[https://www.dropbox.com/s/f24dt6a4dw933jq/cw16.pdf?dl=0 Листок 16]
  
−
'''[https://www.dropbox.com/s/ygyjf2wm7jtxb24/listok19%20-%20%D0%BA%D0%BE%D0%BF%D0%B8%D1%8F.pdf?dl=0 Листок 19 (коды)]'''
+
[https://www.dropbox.com/s/xr27ls89kfbwlwa/cw17.pdf?dl=0 Листок 17]
  
 
==Семинары  ==
 
==Семинары  ==
  
 
=== Семинар 1 (15 января) ===
 
=== Семинар 1 (15 января) ===
−
 
−
Разобраны задачи 1-5 из первого листка. Кроме этого, частично разобрана задача 7.
 
−
 
−
=== Семинар 2 (22 января) ===
 
−
 
−
Решены задачи 1 и 4.
 
−
 
−
=== Семинар 3 (29 января) ===
 
−
 
−
Решены задачи 1, 4 и 6а, а также 5 в одну сторону.
 
−
 
−
=== Семинар 4 (5 февраля) ===
 
−
 
−
Решили задачи 4 и 5. Для этого рассказал о графах Кели.
 
−
 
−
=== Семинар 5 (12 февраля) ===
 
−
 
−
Решена задача 4. Решали 5-ую, но не до конца.
 
−
 
−
=== Семинар 6 (19 февраля) ===
 
−
 
−
Решили все задачи из листка.
 
−
 
−
=== Семинар 7 (26 февраля) ===
 
−
 
−
Решили первую и часть четвертой задачи.
 
−
 
−
=== Семинар 8 (5 марта) ===
 
−
 
−
Решили первые три задачи.
 
−
 
−
=== Семинар 9 (12 марта) ===
 
−
 
−
Решена первая задача.
 
−
 
−
=== Семинар 10 (19 марта) ===
 
−
 
−
Решена первая задача. Остальное время обсуждали 2-ую задачу.
 
−
 
−
=== Семинар 11 (2 апреля) ===
 
−
 
−
Решены задачи 1, 2a, 4.
 
−
 
−
=== Семинар 12 (9 апреля) ===
 
−
 
−
Решены задачи 1, 2а, 2б, 3а, 6а.
 
−
 
−
=== Семинар 13 (16 апреля) ===
 
−
 
−
Решены задачи 1, 2, 4.
 
−
 
−
=== Семинар 14 (23 апреля) ===
 
−
 
−
Решены задачи 1 и 4а)
 
−
 
−
=== Семинар 15 (30 апреля) ===
 
−
 
−
Разобрали первую задачи + обсудили схемы, отношения Карчмера --- Видгерсона, как доказать, что для Majority нужна глубина хотя бы 2\log_2(n).
 
−
 
−
=== Семинар 16 (14 мая) ===
 
−
 
−
Решили задачи 1, 2 и 3а.
 
−
 
−
=== Семинар 17 (21 мая) ===
 
−
 
−
Решили задачи 1 и 2.
 
−
 
−
=== Семинар 18 (28 мая) ===
 
−
 
−
Решили 5 задачу и частично 6а)
 
−
 
−
=== Семинар 19 (4 июня) ===
 
  
 
==Конспекты лекций==
 
==Конспекты лекций==
Строка 316: Строка 317:
 
[https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0 Конспект лекций о деревьях разрешения.]
 
[https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0 Конспект лекций о деревьях разрешения.]
  
−
[https://www.dropbox.com/s/ofsc0q70yg9ptsp/all.pdf?dl=0 Конспект лекций о кодах с исправлением ошибок] (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."
+
[https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0 Конспект лекций о кодах с исправлением ошибок] (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."
  
 
==Рекомендуемая литература  ==
 
==Рекомендуемая литература  ==
Строка 322: Строка 323:
 
[https://www.mccme.ru/~anromash/courses/expanders-notes-2014.pdf А.Е. Ромащенко. Экспандеры: конструкции и приложения.]
 
[https://www.mccme.ru/~anromash/courses/expanders-notes-2014.pdf А.Е. Ромащенко. Экспандеры: конструкции и приложения.]
  
−
[https://arxiv.org/abs/0903.0544 Moser  R.A., Tardos  G.,  A  constructive  proof  of  the general  Lovasz  Local  Lemma,Journal of the ACM, 2010, 57(2), 11.1–11.15.]
+
[https://www.researchgate.net/publication/2508255_On_the_Degree_of_Boolean_Functions_as_Real_Polynomials Noam Nisan, Mario Szegedy. On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4(4) · January 1995] 
  
−
[https://arxiv.org/pdf/1305.1535.pdf Статья Румянцева и Шеня с изложением алгоритма Мозера-Тардоша]
+
[https://www.dropbox.com/s/exx1jyype7dks5b/sensitivity.pdf?dl=0 Ivan Petrenko. Sensitivity for dummies (решение  Sensitivity conjecture).]
−
 
+
−
[https://www.researchgate.net/publication/2508255_On_the_Degree_of_Boolean_Functions_as_Real_Polynomials Noam Nisan, Mario Szegedy. On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4(4) · January 1995] 
+
  
 
N. Nisan, CREW PRAM's and decision trees, STOC 1989, pages 327-335.
 
N. Nisan, CREW PRAM's and decision trees, STOC 1989, pages 327-335.
  
 
Alexander Razborov, Nikolay Vereshchagin. One Property of Cross-Intersecting Families. ECCC TR99-014.  https://eccc.weizmann.ac.il/report/1999/014/
 
Alexander Razborov, Nikolay Vereshchagin. One Property of Cross-Intersecting Families. ECCC TR99-014.  https://eccc.weizmann.ac.il/report/1999/014/
−
 
−
[http://www.cs.columbia.edu/~rocco/Teaching/S17/6998/Boppana-Sipser.pdf Ravi B. Boppana, Michael Sipser. The Complexity of Finite Functions.]
 
−
(Обзор Алона и Боппаны с изложением доказательства теоремы Разборова - Смоленского, метода ограничений и леммы Субботовской, и нижней оценки формульной сложности функции Андреева.)
 

Текущая версия на 13:36, 26 августа 2022

Содержание

Сложность вычислений и логика в теоретической информатике (3-ий курс ТИ) 2020 год

Лекции проходят по вторникам 15:10-16:30, семинары 16:40-18:00 по ссылке https://zoom.us/j/461361055

Первая лекция и семинар 21 января.

Новости

20 июня

Экзамен состоится 22 июня в 12.10 и будет продолжаться 90 минут. Более подробная инструкция тут:

1. Экзамен письменный и проходит с прокторингом через Зум в двух конференциях 

https://zoom.us/j/91507546088 
https://zoom.us/j/94570444864

(распределение по конференциям здесь). Присоединиться к конференции надо на десять минут раньше, то есть, в 12:00. В 12:10 станут доступны задания, которые надо загрузить по ссылке https://www.dropbox.com/s/ualljvsdkp2mg35/exam22-06-2020.pdf?dl=0 (сейчас по этой ссылке находятся прошлогодние задания). Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.

2. Экзамен длится 90 минут. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций: https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0, https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.

3. Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.

19 июня

Выложен тренировочный вариант экзамена. Задачи на самом экзамене могут сильно отличаться.

14 июня

Коллоквиум будет проходить по следующей ссылке https://zoom.us/j/92034518702

4 июня

Перенос лекции на субботу ОТМЕНЯЕТСЯ. А коллоквиум переносится на 15 июня 10:00. Последняя лекция и семинар состоятся 9 июня с 15:10 по обычному расписанию.

2 июня

По просьбе студентов, последняя лекциия и семинар переносятся со вторника 9 июня на субботу 6 июня. Лекция 10-11:20, семинар 11:30-12:50. Коллоквиум можно будет сдавать, как 6 июня с 13:00, так и 9 июня с 15:10, предварительно записавшись на некоторый слот в таблицу Таблица времени прихода на коллоквиум

1 июня

Выложена Таблица времени прихода на коллоквиум

26 мая

Выложена программа коллоквиума 6 июня. Программа.

20 мая

Коллоквиум состоится 6 июня в 10.00.

Письменный экзамен состоится 22 июня в 12.10.

21 апреля

Платформа webinar.ru оказалась неудобной для наших лекций. Начиная со следующего вторника мы возвращаемся в Zoom https://zoom.us/j/461361055 Но теперь в конце или середине каждой лекции будет экспресс-тест на 10 минут, проводимый с помощью Гугл-формы. Те, кто заработают за тесты более половины максимально возможного количества баллов, получат 1 бонусный балл к итоговой оценке. Оценки за тесты выставляются в обычную ведомость https://www.dropbox.com/s/akpdy4oyflgd6zi/results_2020.xlsx?dl=0 Сссылка на лекции и семинары: https://zoom.us/j/461361055

28 марта

Согласно приказу ректора, все занятия 31 марта отменяются!

21 марта

Лекция 24 марта (вторник) в 15:10-16:30 состоится в виде вебинара. Вот ссылка на вебинар: https://zoom.us/j/912901893 Преимущество вебинара перед Ютуб трансляцией в том, что удобнее задавать вопросы по ходу лекции (это можно делать и устно, и письменно).

20 марта

Весенняя сессия отменяется, поэтому лекция и семинар 31 марта состоятся.

16 марта

C 17 марта 2020 года ВШЭ перешла на дистанционное обучение (карантинная мера, вызванная распостранением коронавируса). Лекции курса будут транслироваться и записываться в обычное время (по вторникам с 15:10 до 16:30) на Ютуб канале https://www.youtube.com/channel/UCQpMy-jk_5qdi91U9NsBVdQ?view_as=subscriber

Во время трансляции можно задавать вопросы в чате, на которые лектор сможет отвечать примерно с полминутной задержкой. Очередная трансляция состоится 17 марта.

Лекция 17 марта

Лектор

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

Семинарист

Милованов Алексей Сергеевич almas239@gmail.com

Консультации (защиты): по вторникам 14-15, 18-19 и по средам 15.10-16 в S832.

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

Экспандеры и их применения:теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти, экспандерные коды.

Коды с исправлением ошибок для компьютерных наук.

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

Разрешимость элементарных теорий упорядоченного поля действительных чисел (теорема Тарского-Зайденберга и поля комплексных чисел.

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

4 домашних задания, коллоквиум и экзамен.

Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. Кроме этого в домашних задания могут бонусные задачи, за решение которых даются дополнительные баллы на коллоквиуме или экзамене (1 задача= 1 балл). На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара. Сдача домашних заданий после их срока невозможна.

Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.

Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными.

Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2.

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

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

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценок.

Коллоквиум

Коллоквиум состоится 15 июня в 10:00. Записываться в таблицу: Таблица времени прихода на коллоквиум

Программа коллоквиума. Ссылка на Зум конференцию для тех, кто оказался записанным к лектору: https://us02web.zoom.us/j/82787088715

Экзамен

Экзамен состоится 22 июня в 12.10 и будет продолжаться 90 минут. Более подробная инструкция тут:

1. Экзамен письменный и проходит с прокторингом через Зум в двух конференциях: 

https://zoom.us/j/91507546088 
https://zoom.us/j/94570444864

(распределение по конференциям здесь).https://zoom.us/j/94570444864. Присоединиться к конференции надо на десять минут раньше, то есть, в 12:00. В 12:10 станут доступны задания, которые надо загрузить по ссылке https://www.dropbox.com/s/ualljvsdkp2mg35/exam22-06-2020.pdf?dl=0 (сейчас по этой ссылке находятся прошлогодние задания). Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.

2. Экзамен длится 90 минут. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций: https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0, https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.

3. Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.

Пересдачи

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

Первое домашнее будет выложено 29.1.2020, срок сдачи 11.2.2020.

Второе домашнее будет выложено 3.3.2020, срок сдачи 31.3.2020.

Третье домашнее будет выложено 24.4.2020, срок сдачи 19.5.2020.

Четвертое домашнее будет выложено 14.5.2020, срок сдачи 9.6.2020.

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

Домашнее задание 1. Cрок сдачи 12.2.2020 в 12:10 MSK.

Домашнее задание 2 Срок сдачи 7.4.2020 в 16.40 MSK.

Домашнее задание 3 Срок сдачи 19.5.2020 в 16.40 MSK.

Домашнее задание 4 Срок сдачи 16.6.2020 в 16.40 MSK.

Результаты

Общая ведомость оценок

Результаты теста 1

Результаты теста 2

Результаты теста 3.

Результаты теста 4

Результаты теста 5

Результаты теста 6

Прочитанные лекции

Лекция 1 (21 января).

Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство). Реберное расширение и его связь с вершинным расширением. Матрица графа и ее собственные числа.

Лекция 2 (28 января).

Максимальное по абсолютной величине собственное число регулярного графа. От чего зависит кратность собственного числа d. Второе по абсолютной величине собственное число двудольного графа.

Лемма о перемешивании. От спектрального экспандера к комбинаторному.

Лекция 3 (4 февраля).

Вторая лемма о перемешивании. Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа.

Лекция 4 (11 февраля).

Формула для числа Каталана. Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами.

Лекция 5 (18 февраля).

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

Лекция 6 (25 февраля).

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

Лекция 7 (3 марта).

Второе собственное число связного недвудольного графа.

Алгоритм Рейнгольда.

Лекция 8 (10 марта).

Применение экспандеров для дерандомизации.

Лекция 9 (17 марта).

Экспандер Маргулиса.

Лекция 10 (24 марта).

Двудольные экспандеры: определение и вероятностное доказательство существования.

Лекция 11 (7 апреля).

Экспандер Варди - Парвареша.

Лекция 12 (14 апреля).

Коды с исправлением ошибок и их параметры. Линейные коды. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.

Лекция 13 (21 апреля).

Линейные коды, проверочная матрица. Оценка Хэмминга и коды Хэмминга. Кодирование и декодирование для кодов Хэмминга. https://events.webinar.ru/event/4301788/4390364

Лекция 14 (28 апреля)

Оценка Гилберта. Функция Шеннона. Графики оценок Хэмминга и Гилберта. Оценка Варшамова - Гилберта. Случайные линейные коды.

Результаты теста 2

Лекция 15 (12 мая)

Коды Возенкрафта. Каскадные коды. Декодирование каскадного кода.

Результаты теста 3.

Лекция 16. (19 мая)

Декодирование каскадного кода и коды Форни. Экспандерные коды: определение, последовательный алгоритм декодирования.

Результаты теста 4

Лекция 17 (26 мая)

Оценки Плоткина и коды Адамара. Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.

Лекция 18(2 июня )

Деревья разрешения, метод противника. Сертификатная и недетерминированная сложность. Чувстительность и блочная чувствительность. Неравенствo D < C^2

Результаты теста 5

Лекция 19 (9 июня).

Неравенствo D < C*bs Неравенство C< bs*s. Вероятностные деревья и неравенство bs = O(R)

Результаты теста 6

Не удалось рассказать:

Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ (Эренфойхт - Хауслер). Теорема Маркова. Представление булевых функций многочленами с действительными коэффициентами. Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди).

Разрешимость элементарной теории поля комплексных чисел. Разрешимость элементарной теории упорядоченного поля действительных чисел.

Задачи для семинаров

Листок 1 (комбинаторные экспандеры)


Листок 2 (спектр графов)

Листок 3

Листок 4

Листок 5

Листок 6

Листок 7

Листок 8

Листок 9

Листок 10

Листок 11

Листок 12

Листок 13

Листок 14

Листок 15

Листок 16

Листок 17

Семинары

Семинар 1 (15 января)

Конспекты лекций

Конспекты лекций об экспандерах, полученные переработкой книги Ромащенко

Конспект лекций о деревьях разрешения.

Конспект лекций о кодах с исправлением ошибок (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."

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

А.Е. Ромащенко. Экспандеры: конструкции и приложения.

Noam Nisan, Mario Szegedy. On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4(4) · January 1995 

Ivan Petrenko. Sensitivity for dummies (решение Sensitivity conjecture).

N. Nisan, CREW PRAM's and decision trees, STOC 1989, pages 327-335.

Alexander Razborov, Nikolay Vereshchagin. One Property of Cross-Intersecting Families. ECCC TR99-014. https://eccc.weizmann.ac.il/report/1999/014/

Источник — «http://wiki.cs.hse.ru/index.php?title=CCTI_2020&oldid=71181»