Комбинаторные конструкции в теоретической информатике — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 144: Строка 144:
 
====Лекция 12 (14 апреля). ====
 
====Лекция 12 (14 апреля). ====
 
[https://youtu.be/OfQgPjzH97Q Коды с исправлением ошибок и их параметры. Линейные коды. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.]
 
[https://youtu.be/OfQgPjzH97Q Коды с исправлением ошибок и их параметры. Линейные коды. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.]
 +
 +
====Лекция 13 (21 апреля).  ====
 +
[https://events.webinar.ru/21463024/4301788/record-new/4390364 Линейные коды, проверочная матрица. Оценка Хэмминга и коды Хэмминга. Кодирование и декодирование для кодов Хэмминга.]
 +
https://events.webinar.ru/event/4301788/4390364
 +
 +
====Лекция 14 (28 апреля) ====
 +
 +
[https://youtu.be/cxtahdNgzGc Оценка Гилберта. Функция Шеннона. Графики оценок Хэмминга и Гилберта. Оценка Варшамова - Гилберта. Случайные линейные коды.]
 +
 +
[https://docs.google.com/spreadsheets/d/11jWr5fzwdTRnD2UH3u8oRMkW6VomdH3fiwmLoNz2-Jc/edit?usp=sharing  Результаты теста 2]
 +
 +
====Лекция 15 (12 мая) ====
 +
[https://youtu.be/_xzNHL9eBKA Коды Возенкрафта. Каскадные коды. Декодирование каскадного кода.]
 +
 +
[https://docs.google.com/spreadsheets/d/1-2JQgSmIafNuwJkyn5EcYlGY94MNgyyzue25F2NI5qw Результаты теста 3.]
 +
 +
====Лекция 16.  (19 мая) ====
 +
[https://youtu.be/VPMnROaELpA Декодирование каскадного кода и коды Форни. Экспандерные коды: определение, последовательный алгоритм декодирования.]
 +
 +
[https://docs.google.com/spreadsheets/d/1pL7eabfoztAlA8iLps9x_oyW4zuPbU7YMRFmLfc_-qY Результаты теста 4]
 +
 +
====Лекция 17  (26 мая) ====
 +
 +
[https://youtu.be/HWNXos5uS1k Оценки Плоткина и коды Адамара. Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.]
 +
 +
====Лекция 18(2 июня ) ====
 +
[https://youtu.be/x-md75lO-c0 Деревья разрешения, метод противника. Сертификатная и недетерминированная сложность. Чувстительность и блочная чувствительность. Неравенствo D < C^2]
 +
 +
[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)
 +
 +
[https://docs.google.com/spreadsheets/d/1l2UfO8t68lIjt98LaibTY80KNl1edWY1MF1Ypmn7AhU Результаты теста 6 ]
 +
 +
==== Не удалось рассказать:  ====
 +
 +
 +
Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ
 +
Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ (Эренфойхт - Хауслер).
 +
Теорема Маркова.
 +
Представление булевых функций многочленами с действительными коэффициентами.
 +
Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди).
 +
 +
Разрешимость элементарной теории поля комплексных чисел.
 +
Разрешимость элементарной теории упорядоченного поля
 +
действительных чисел.
 +
 +
==Задачи для семинаров  ==
 +
 +
 +
'''[https://www.dropbox.com/s/mr072cifyo8gwou/listok1.pdf?dl=0 Листок 1  (комбинаторные экспандеры)]'''
 +
 +
 +
'''[https://www.dropbox.com/s/2zmdygbscfbxcuz/cw2.pdf?dl=0 Листок 2  (спектр графов)]'''
 +
 +
[https://www.dropbox.com/s/q1fa1zqbvnxg93k/cw3.pdf?dl=0 Листок 3]
 +
 +
[https://www.dropbox.com/s/tabqdex6vpeep6s/cw4.pdf?dl=0 Листок 4]
 +
 +
[https://www.dropbox.com/s/jp9o8n60yp4cfuq/cw5.pdf?dl=0 Листок 5]
 +
 +
[https://www.dropbox.com/s/jlrezpzll64s256/cw6.pdf?dl=0 Листок 6]
 +
 +
[https://www.dropbox.com/s/lwjgxpvfgs1btrn/cw7.pdf?dl=0 Листок 7]
 +
 +
[https://www.dropbox.com/s/3shmqxxxtr1y3gi/cw8.pdf?dl=0 Листок 8]
 +
 +
[https://www.dropbox.com/s/u1l4jmfp966y78k/cw9.pdf?dl=0 Листок 9]
 +
 +
[https://www.dropbox.com/s/ar65k6q9wvcmsbb/cw10.pdf?dl=0 Листок 10]
 +
 +
[https://www.dropbox.com/s/adczqg30m0bl5pr/cw11.pdf?dl=0 Листок 11]
 +
 +
[https://www.dropbox.com/s/q46hx0t3fi8mqv5/cw12.pdf?dl=0 Листок 12]
 +
 +
[https://www.dropbox.com/s/rr4bxw4xdbd4jra/cw13.pdf?dl=0 Листок 13]
 +
 +
[https://www.dropbox.com/s/ycz3cuzutsn2kg4/cw14.pdf?dl=0 Листок 14]
 +
 +
[https://www.dropbox.com/s/z6nquyb30kz5bto/cw15.pdf?dl=0 Листок 15]
 +
 +
[https://www.dropbox.com/s/f24dt6a4dw933jq/cw16.pdf?dl=0 Листок 16]
 +
 +
[https://www.dropbox.com/s/xr27ls89kfbwlwa/cw17.pdf?dl=0 Листок 17]
 +
 +
==Семинары  ==
 +
 +
=== Семинар 1 (21 января) ===
 +
 +
Разобраны задачи 1-6 из первого листка.
 +
 +
=== Семинар 2 (4 февраля) ===
 +
 +
Разобраны задачи 1--5 из второго листка.
 +
 +
=== Семинар 3 (11 февраля) ===
 +
 +
Разобраны задачи 1--2 из третьего листка
 +
 +
=== Семинар 4 (18 февраля) ===
 +
 +
Разобраны задачи 1--2 из четвёртого листка
 +
 +
=== Семинар 5 (25 февраля) ===
 +
 +
Разобраны задачи 1--3 из пятого листка
 +
 +
=== Семинар 6 (3 марта) ===
 +
 +
Разобраны задачи 1--3 из шестого листка
 +
 +
=== Семинар 7 (10 марта) ===
 +
 +
Разобраны задачи 1--3 из седьмого листка
 +
 +
=== Семинар 8 (17 марта) ===
 +
 +
Разобраны задачи 1--4 из восьмого листка
 +
https://www.youtube.com/watch?v=3Kg6yDvRnt0&feature=youtu.be
 +
[https://www.dropbox.com/s/ypt6hmmhe8u8zaz/My-Notes%20%282%29.pdf?dl=0 PDF доски]
 +
 +
=== Семинар 9 (24 марта) ===
 +
Разобраны задачи 1--3 из девятого листка
 +
 +
=== Семинар 10 (7 апреля) ===
 +
Разобраны задачи 1--2 из десятого листка
 +
 +
=== Семинар 11 (14 апреля) ===
 +
Разобраны задачa 1 из одиннадцатого листка
 +
 +
 +
=== Семинар 12 (21 апреля) ===
 +
https://drive.google.com/file/d/1mGv-CEO8_xd9wuygFOHs8vnyHqKVlCuJ/view?usp=sharing
 +
Разобраны задачи 1,2,4 из двенадцатого листка
 +
 +
 +
=== Семинар 13 (28 апреля) ===
 +
Разобраны задачи 1--5 из тринадцатого листка
 +
 +
=== Семинар 14 (12 мая) ===
 +
Разобраны задачи 1--2 из четырнадцатого листка
 +
 +
=== Семинар 15 (19 мая) ===
 +
Разобраны задачи 1--3 из пятнадцатого листка
 +
 +
=== Семинар 16 (26 мая) ===
 +
Разобраны задачи 1--4 из шестнадцатого листка
 +
 +
=== Семинар 17 (2 июня) ===
 +
Разобраны задачи 1--7, 9, 10, 12, 13 из семнадцатого листка
 +
 +
==Конспекты лекций==
 +
[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 Конспект лекций о кодах с исправлением ошибок] (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."
 +
 +
==Рекомендуемая литература  ==
 +
 +
[https://www.mccme.ru/~anromash/courses/expanders-notes-2014.pdf А.Е. Ромащенко. Экспандеры: конструкции и приложения.]
 +
 +
[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://www.dropbox.com/s/exx1jyype7dks5b/sensitivity.pdf?dl=0 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/

Версия 17:10, 11 января 2021

Содержание

Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2021 год

Лекции проходят по пятицам 13:00-14:20, семинары также по пятницам 14:40-16:00 через Zoom по ссылке

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

Новости

Лектор

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

Семинарист

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

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

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

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

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


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

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

Тесты

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

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

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

Коллоквиум и письменный экзамен

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

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

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

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

Коллоквиум

Коллоквиум состоится ... Записываться в таблицу: ...

[ Программа коллоквиума.]

Экзамен

Экзамен состоится ...

Экзамен проходит с прокторингом. Студенты загружают задание по ссылке ... , решают на бумаге, в конце экзамена делают фотографии/сканы решений, сшивают в один PDF файл и загружают по следующей ссылке ... . Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.

Экзамен длится 90 минут. Во время экзамена студенты должны включить камеры. Во время экзамена разрешено смотреть на любые материалы, загруженные на компьютер до начала экзамена, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать загруженные материалы и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.

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


Пересдачи

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

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

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

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

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

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

[Домашнее задание 1]. Cрок сдачи .


Результаты

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

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


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

Лекция 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 (21 января)

Разобраны задачи 1-6 из первого листка.

Семинар 2 (4 февраля)

Разобраны задачи 1--5 из второго листка.

Семинар 3 (11 февраля)

Разобраны задачи 1--2 из третьего листка

Семинар 4 (18 февраля)

Разобраны задачи 1--2 из четвёртого листка

Семинар 5 (25 февраля)

Разобраны задачи 1--3 из пятого листка

Семинар 6 (3 марта)

Разобраны задачи 1--3 из шестого листка

Семинар 7 (10 марта)

Разобраны задачи 1--3 из седьмого листка

Семинар 8 (17 марта)

Разобраны задачи 1--4 из восьмого листка https://www.youtube.com/watch?v=3Kg6yDvRnt0&feature=youtu.be PDF доски

Семинар 9 (24 марта)

Разобраны задачи 1--3 из девятого листка

Семинар 10 (7 апреля)

Разобраны задачи 1--2 из десятого листка

Семинар 11 (14 апреля)

Разобраны задачa 1 из одиннадцатого листка


Семинар 12 (21 апреля)

https://drive.google.com/file/d/1mGv-CEO8_xd9wuygFOHs8vnyHqKVlCuJ/view?usp=sharing Разобраны задачи 1,2,4 из двенадцатого листка


Семинар 13 (28 апреля)

Разобраны задачи 1--5 из тринадцатого листка

Семинар 14 (12 мая)

Разобраны задачи 1--2 из четырнадцатого листка

Семинар 15 (19 мая)

Разобраны задачи 1--3 из пятнадцатого листка

Семинар 16 (26 мая)

Разобраны задачи 1--4 из шестнадцатого листка

Семинар 17 (2 июня)

Разобраны задачи 1--7, 9, 10, 12, 13 из семнадцатого листка

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

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

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

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

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

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

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=Комбинаторные_конструкции_в_теоретической_информатике&oldid=49447»