https://wikicshse.ru/index.php?action=history&feed=atom&title=%D0%A4%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2_%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9_2020Факультатив Теория вычислений 2020 - История изменений2026-06-06T18:17:04ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://wikicshse.ru/index.php?title=%D0%A4%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2_%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9_2020&diff=2474&oldid=previmported>Antongnatenko: /* Домашние задания */2020-05-08T21:52:38Z<p><span class="autocomment">Домашние задания</span></p>
<p><b>Новая страница</b></p><div>= Факультатив Теория вычислений (2-й курс ПМИ) 2020 год =<br />
<br />
Лекции и семинары проходят по пятницам, лекция в 13:40, семинар в 15:10.<br />
Аудитория: R602. <br />
<br />
<br />
==Новости==<br />
<br />
Изменился номер аудитории, теперь лекции и семинары в ауд. R602. <br />
<br />
Изменилось расписание. Теперь лекция начинается в 13:40, а семинар в 15:10, ауд. R206.<br />
<br />
Лекция 7 февраля не состоялась из-за опоздания лектора (на 3 часа) по ошибке.<br />
<br />
Лекция и семинар 31 января отменяются, поскольку аудитория будет занята Олимпиадой Высшая проба.<br />
<br />
==Лекторы и семинаристы == <br />
<br />
Н. К. Верещагин, А.С. Милованов, М.Н. Вялый, В.В. Подольский, А.А. Рубцов<br />
<br />
С вопросами по курсу можно обращаться к Владимиру Владимировичу Подольскому vpodolskii@hse.ru и к Александру Александровичу Рубцову arubtsov@hse.ru.<br />
<br />
==Краткое описание==<br />
<br />
NP и теорема Кука-Левина. Вероятностные алгоритмы и классы BPP, RP, ZPP.<br />
<br />
Fine-grained сложность.<br />
<br />
Теория формальных языков<br />
<br />
==Отчётность по курсу и критерии оценки==<br />
<br />
Домашнее задание и экзамен.<br />
<br />
Домашнее задание состоит из задач (обычных и дополнительных), постепенно добавляемых в [https://drive.google.com/open?id=1AqLaE1CTa9-UsMFkLU8p646c4xfPhds0 список]. Рядом с каждой задачей (или её пунктом) указано количество баллов, которые можно получить за правильное решение, а также дата сдачи ("дедлайн"). Решения, сданные после дедлайна, получают не более половины баллов.<br />
<br />
Пусть Sреш — сумма баллов, набранных за решение '''обычных''' задач, Sреш_доп — сумма баллов, набранных за решение '''дополнительных''' задач, а S — максимально возможная сумма баллов, которые можно набрать за '''обычные''' задачи. Тогда оценка за домашнее задание вычисляется по формуле: Одз = min{(Sреш + Sреш_доп)/S * 10, 10}.<br />
<br />
Экзамен (устный) оценивается по десятибалльной системе. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными.<br />
<br />
Итоговая оценка вычисляется по формуле: Оитог = Одз*0,3 + Оэкз*0,7<br />
<br />
<br />
Те, кто не смог прийти на экзамен по болезни, могут сдать его отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. <br />
<br />
====Правила округления==== <br />
<br />
В вычислениях текущие оценки и промежуточные величины не округляются. Результат<br />
вычисляется точно и округляется (арифметически) в момент выставления итоговой оценки.<br />
<br />
====Экзамен====<br />
<br />
==Домашние задания ==<br />
[https://drive.google.com/open?id=1AqLaE1CTa9-UsMFkLU8p646c4xfPhds0 Задачи по первой части курса] ([https://drive.google.com/open?id=1kU5vFlR2QPXj0mqYVOSSg0DIQbFmqtnf исходный код]). Рядом с каждой задачей (или её пунктом) указано количество баллов, которые можно получить за правильное решение, а также дата сдачи ("дедлайн"). Решения, сданные после дедлайна, получают не более половины баллов.<br />
<br />
'''В задаче 4 изменено условие. Добавлен дополнительный пункт. Срок сдачи продлён до 15 мая'''<br />
<br />
[https://docs.google.com/spreadsheets/d/1H2U9XhnBaI5dhhtiKAhJaX-oLOVx74AfwsWKhyNi9wI/edit?usp=sharing Таблица с оценками]<br />
<br />
==Прочитанные лекции==<br />
<br />
====Лекция 1 (24 января). ====<br />
Машины Тьюринга. Время и память. Класс P. Полиномиальная m-сводимость (сводимость Карпа).<br />
<br />
====Лекция 2 (14 февраля). ====<br />
Сводимость Кука. Классы NP (определение с недетерминированными машинами и как проекций<br />
предикатов из P) и FNP и сводимость каждой задачи из FNP к некоторой задаче из NP.<br />
<br />
Существование NP полных задач.<br />
<br />
====Лекция 3 (28 февраля). ====<br />
Доказательство NP полноты задачи о замощении квадрата.<br />
Связь между машинами Тьюринга и схемами из функциональных элементов. Класс P/poly <br />
(определение со схемами из функциональных элементов). <br />
Теорема о NP полноте задачи о выполнимости схем.<br />
<br />
====Лекция 4 (6 марта). ====<br />
NP полнота задачи 3-КНФ.<br />
Вероятностные полиномиальные алгоритмы для проверки простоты и для проверки алгебраических тождеств.<br />
<br />
====Лекция 5 (13 марта). ====<br />
Доказательство леммы Шварца - Зиппеля.<br />
Классы BPP, RP. Амплификация и включение BPP в P/poly.<br />
<br />
<br />
==Планируемые лекции==<br />
====Лекция 6 (). ====<br />
Алгоритмы для k-SAT быстрее полного перебора. Формулировка ETH и SETH. <br />
Нижние оценки для задачи о клике и задаче k-SUM, основанные на ETH.<br />
Формулировка нижней оценки для задачи Orthogonal Vectors, основанной на SETH.<br />
<br />
====Лекция 7 () ====<br />
Нижняя оценка для Orthogonal Vectors. Лемма о спарсификации.<br />
<br />
====Лекция 8 (). ====<br />
Нижняя оценка для задач о диаметре графа и наибольшей общей подпоследовательности. Задача 3-SUM и основанная на ней нижняя оценка для задачи о перетаскивании шкафа.<br />
<br />
====Лекция 9 (). ====<br />
Регулярные языки. Эквивалентность определений через регулярные выражения, детерминированные и недетерминированные конечные автоматы. Лемма о накачке. Материал курса по регулярным языкам хорошо освящён в книжке Сипсера, а также [http://rubtsov.su/public/fl/zz_to_publisher1.pdf здесь].<br />
<br />
====Лекция 10 (3 апреля). ====<br />
Регулярные языки. Алгоритм минимизации автоматов и теорема Майхилла-Нероуда.<br />
<br />
====Лекция 11 (10 апреля). ====<br />
Контекстно-свободные языки. Формальные грамматики и магазинные автоматы. Алгоритм построения МП-автомата по грамматике.<br />
<br />
====Лекция 12 (17 апреля). ====<br />
Контекстно-свободные языки. Алгоритм построения КС-грамматики по МП-автомату. Нормальная форма Хомского. Алгоритм Кока–Янгера–Касами. Лемма о накачке для КС-языков.<br />
<br />
====Лекция 13 (24 апреля). ====<br />
Игры достижимости, игры чётности. Существование позиционных выигрышных стратегий. Решение игр чётности лежит в пересечении классов NP и coNP.<br />
'''[https://www.dropbox.com/s/r08owzn7835e8dr/PG-tocfac1.pdf?dl=0 Конспект лекции]'''<br />
<br />
====Лекция 14 (8 мая). ====<br />
Сводимость игр четности к играм достижимости. Автоматы на деревьях. Универсальные деревья квазиполиномиального размера. Алгоритм решения игр четности за квазиполиномиальное время. <br />
'''[https://www.dropbox.com/s/sq44ghjkfffb5rs/ParityGames.pdf?dl=0 Конспект лекций 13-14]'''<br />
<br />
====Лекция 15 (15 мая). ====<br />
Коммуникационная сложность, протокол для задачи о кликах и независимых множествах. Определение детерминированных протоколов, комбинаторные прямоугольники, метод трудных множеств, метод размера прямоугольника, метод ранга. Нижние оценки для EQ, GT, IP, DISJ.<br />
<br />
====Лекция 16 (22 мая). ====<br />
Потоковые алгоритмы. Нахождение элемента, встречающегося более половины раз. Трудность нахождения самого часто встречающегося элемента. Односторонняя вероятностная коммуникационная сложность функции DISJ.<br />
<br />
==Семинары ==<br />
====Семинар 1 (24 января). ====<br />
Классы P, NP и coNP. <br />
'''[https://drive.google.com/open?id=1k2U1smASbdZdfNLJB2PaT8dZ4cF4jrWq Листок 1.]'''<br />
<br />
====Семинар 2 (7 февраля). ====<br />
Классы P, NP и coNP (продолжение). <br />
'''[https://drive.google.com/open?id=1k2U1smASbdZdfNLJB2PaT8dZ4cF4jrWq Ещё раз листок 1.]'''<br />
<br />
====Семинар 3 (14 февраля). ====<br />
Сводимость по Куку и сводимость по Карпу <br />
'''[https://drive.google.com/open?id=1DmX_7lbw_zuBmTP-eZ4XuxIO1AZ-ePHo Листок 2.]'''<br />
<br />
====Семинар 4 (21 февраля). ====<br />
NP-трудность и NP-полнота<br />
'''[https://drive.google.com/open?id=1xfCSjgyfMkzT4sS_ipCyXxIS6yPZAKxl Листок 3.]'''<br />
<br />
====Семинар 5 (28 февраля). ====<br />
NP-трудность и NP-полнота (продолжение)<br />
'''[https://drive.google.com/open?id=1xfCSjgyfMkzT4sS_ipCyXxIS6yPZAKxl Ещё раз листок 3.]'''<br />
<br />
====Семинар 6 (6 марта). ====<br />
Задачи оптимизации (без листочка) и вероятностные алгоритмы<br />
'''[https://drive.google.com/open?id=1aQBRm_VkDP3pp6-Mcf3Y0uJQSeeNgeWN Листок 4 (первая задача).]'''<br />
<br />
====Семинар 7 (13 марта). ====<br />
Вероятностные алгоритмы<br />
'''[https://drive.google.com/open?id=1aQBRm_VkDP3pp6-Mcf3Y0uJQSeeNgeWN Ещё раз листок 4.]'''<br />
<br />
====Семинар 8 (20 марта). ====<br />
Схемы из функциональных элементов<br />
'''[https://drive.google.com/open?id=1YRw_ruf12-zH2QRYvkkUeo_OIqOWK1Q0 Листок 5.]'''<br />
<br />
====Семинар 9 (3 апреля). ====<br />
Коммуникационная сложность<br />
'''[https://www.dropbox.com/s/cgyfft2bun5k9cb/communication.pdf?dl=0 Листок про коммуникационную сложность.]'''<br />
<br />
====Занятие 17 апреля. ====<br />
Теоремы об иерархии<br />
'''[https://www.dropbox.com/s/hn7e2o9ut0mkdm9/sheets.pdf?dl=0 Листок к семинару (с.1-2)]'''<br />
<br />
====Занятие 8 мая. ====<br />
Теоремы об иерархии (окончание). Игры и альтернирующие вычисления.<br />
'''[https://www.dropbox.com/s/hn7e2o9ut0mkdm9/sheets.pdf?dl=0 Листок к семинару (с.2-4)]'''<br />
<br />
==Прошлогодние семинары ==<br />
Здесь временно лежат листочки прошлогодних семинаров.<br />
<br />
'''[https://www.dropbox.com/s/txsb1v0salfk7sn/problems.pdf?dl=0 Листок 5 марта.]'''<br />
<br />
'''[https://www.dropbox.com/s/a11lpv9xkaw7ns3/problems2.pdf?dl=0 Листок 12 марта]'''<br />
<br />
'''[https://www.dropbox.com/s/l9xa355uqkrh9so/problems3.pdf?dl=0 Листок 19 марта]'''<br />
<br />
'''[http://rubtsov.su/public/fl/2016/hse_ct/cw01_ct.pdf Листок 9 и 19 апреля]'''<br />
<br />
'''[http://rubtsov.su/public/fl/2016/hse_ct/cw02_ct.pdf Листок 26 и 30 апреля]'''<br />
<br />
'''[https://www.dropbox.com/s/riohjhnj0c5o9wc/problems4.pdf?dl=0 Листок 31 мая]''' Решили 1-ую и 8-ую задачу.<br />
<br />
'''[https://www.dropbox.com/s/lxchsffmo5rabsw/prob_computing.pdf?dl=0 Листок 4 июня]'''<br />
<br />
==Рекомендуемая литература ==</div>imported>Antongnatenko