Версия 17:03, 9 января 2018 (просмотреть исходный код) Nvereshagin (обсуждение | вклад) (Новая страница: «= Дискретная математика на 2-ом курсе ПМИ (основной поток)= Лекции проходят по вторникам в…»)		Текущая версия на 15:00, 11 июня 2018 (просмотреть исходный код) Kozachinskiy (обсуждение | вклад) (→‎Проведённые семинары)
(не показано 95 промежуточных версии 2 участников)
Строка 1:		Строка 1:
−	= Дискретная математика на 2-ом курсе ПМИ (основной поток)=	+	= Сложность вычислений и логика в теоретической информатике (3-ий курс ТИ) 2018 год =
−	Лекции проходят по вторникам в аудитории 622 в 10:30-11:50. Первая лекция 5 сентября.	+	Лекции проходят по вторникам в аудитории 306 в 15:10-16:30. Семинары по вторникам 16:40-18:00. Первая лекция и семинар 9 января.
		+	'''[https://t.me/joinchat/AAAAAEpqVLPKBWkKxDWT1Q Канал в telegram]'''
	==Новости==		==Новости==
		+	* 5 июня: Выложены [https://www.dropbox.com/s/mi726hpmpr5mctb/colloq.pdf?dl=0 вопросы к коллоквиуму].
		+	* 16 мая: лекция и семинар 22 мая отменяются из-за того, что большинство студентов уезжают в С.Петербург.
−	* '''(22 декабря)''' Проверены экзаменационные работы. Баллы за задачи и критерии их оценки (на последнем листе) находятся [https://www.dropbox.com/s/nnubzvb9gg5299o/exam-results-base.xls?dl=0 здесь]. Показ работ 23 декабря в 16:40 в ауд. 402. Решения задач [https://www.dropbox.com/s/vgj8vcm2yyx63rg/main-17-12-21-sol.pdf?dl=0 здесь]	+	* 15 мая: Назначены даты коллоквиума и письменного экзамена. Коллоквиум: 13 июня СР, 15:10-18:00, ауд.435. Экзамен: 19 июня ВТ, 10:30-13:30, ауд.400.
−	* (18 декабря) Экзамен состоится в четверг 21 декабря с 15 до 18 в ауд. 622.  Объявление для группы 164: После сдачи экзаменационной работы можно будет защитить шестое ДЗ.	+	* 28 апреля: выложены ссылки на статьи с изложением алгоритма Мозера-Тардоша.
−	* (14 декабря) Объявление для группы 164: в пятницу 15 декабря после коллоквиума (до 17:15) можно защитить пятое домашнее задание Н.К. Верещагину (ауд. 617). Другого дня для защиты пятого ДЗ лектору не будет.	+	* 4 апреля: выложены конспекты лекций об экспандеров, полученные переработкой книги Ромащенко.
−	* (5 декабря) Выложено расписание коллоквиума:	+	==Лектор==
−	12 декабря  (вторник)	+	Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com
−	Группа 161	+	==Семинарист==
−	13:40-16:30 (первая пара 300, затем 622)	+
−	Группа 162	+	Козачинский Александр Николаевич, kozlach@mail.ru
−	15:10-18:00 (первая пара 622, затем 435)	+
−	Группа 163
−	16:40-18:00 (и до победного конца) (ауд. 311).
−	Подгруппы 164-2, 165-1:
−	12:10 - 15:00 (первая пара 622, потом 505)
−	Группа 166	+	==Краткое описание==
−	12:10 - 15:00 (первая пара 622, потом 219)	+
−	15 декабря (Пятница)	+	Теоремы Геделя о неполноте для формальной арифметики и теории множеств.
−	Подгруппы 164-1 и 165-2:	+	Разрешимость элементарных теорий упорядоченного поля действительных чисел (теорема Тарского-Зайденберга и
−	время 13:40-16:30 -- ауд.205.	+	поля комплексных чисел.
		+	Экспандеры и теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти.
		+	Лемма Ловаса и быстрые алгоритмы для SAT.
		+	Сложность пропозициональных доказательств.
−	* (24 ноября) Выложены [https://www.dropbox.com/s/bfx9cnut2w2ww3z/colloq.pdf?dl=0 Вопросы к коллоквиуму]
−	* (23 ноября) Выложено [https://www.dropbox.com/s/6v2r2l9rswfctnc/hw6.pdf?dl=0 Домашнее задание №6]. Срок сдачи для 164 и 166 групп - 5 декабря.	+	==Отчётность по курсу и критерии оценки==
−	* (7 ноября) Выложено [https://www.dropbox.com/s/bea4pllf8tspigb/hw5.pdf?dl=0 Домашнее задание №5]. Срок сдачи для 164 и 166 групп - 21 ноября.	+	4 домашних заданий, коллоквиум и экзамен.
−	* (27 октября) Выложено [https://www.dropbox.com/s/18bd95cvk526cuu/hw4.pdf?dl=0 Домашнее задание №4]. Срок сдачи для 164 и 166 групп - 7 ноября.	+	Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.
		+	Сдача домашних заданий после их срока невозможна.
−	* (19 октября) Дедлайн защиты второго домашнего задания для группы 164 сдвинут на 31 октября (из-за сессии)	+	Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.
−	* '''(12 октября) Внимание!''' По ошибке в третьем домашнем задании первые две задачи совпадали с некоторыми задачами из второго домашнего задания. Они заменены на новые задачи.	+	Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме  не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными.
−	* (10 октября) Крайний срок сдачи третьего домашнего задания для групп 164, 166 сдвинут на 24 октября (поскольку 24 октября каникулы, при сдаче 24 октября задание надо послать по компьютерной почте).	+	Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2.
−	* (3 октября) Выложено [https://www.dropbox.com/s/1dkxcvze0u8930l/hw3.pdf?dl=0 Домашнее задание №3]	+	Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной.
−	* (19 сентября) Выложено [https://www.dropbox.com/s/jmqm4vdw0l19oqg/hw2.pdf?dl=0 Домашнее задание №2]	+	====Правила округления====
−	* (1 сентября) Лекции 12 и 26 сентября переносятся на 15 и 29 сентября, соответственно (на то же время) в ауд. 509. Это относится и к семинарам в группе 164, переносящимся в ауд. 301.	+	В вычислениях текущие оценки и промежуточные величины не округляются. Результат
		+	вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок.
		+	Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной
		+	оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6
		+	округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3,
		+	5,48 – до 5, 5,54 – до 6, 7.12 – до 8.
−	* (1 сентября) Выложено [https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]	+	====Коллоквиум====
−	==Лектор==	+	Коллоквиум состоится 13 июня СР, 15:10-18:00, ауд.435.
−	Н.К. Верещагин nikolay.vereshchagin@gmail.com	+	[https://www.dropbox.com/s/mi726hpmpr5mctb/colloq.pdf?dl=0 Вопросы к коллоквиуму.]
−	==Семинаристы==	+	====Экзамен====
−	163 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Дискин Михаил Сергеевич, yhn1124@gmail.com, t.me/yhn112	+	Письменный экзамен назначен на 19 июня ВТ, 10:30-13:30, ауд.400.
−		+
−	164 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com, ассистент Денисова Елена Алексеевна,	+
−	lena97denisova@mail.ru	+
−	165 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Моисеев Андрей Андреевич, andrei.moiseev213@yandex.ru	+	==Сроки контрольных мероприятий==
−	166 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Ребенко Ярослав Алексеевич, yarebenko@gmail.com	+	Первое домашнее выложено 6.2.2018, срок сдачи 20.2.2018.
−	==Краткое описание==	+	Второе домашнее будет выложено 6.3.2018, срок сдачи 20.3.2018.
−	Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:	+	Третье домашнее будет выложено 24.4.2018, срок сдачи 8.5.2018.
−	что это такое, в каких областях оно применяется, двойственность в линейном программировании и	+
−	симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:	+
−	формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами	+
−	логики предикатов, исчисление резолюций.	+
−	==Отчётность по курсу и критерии оценки==	+	Четвертое домашнее будет выложено 5.6.2018, срок сдачи 19.6.2018.
−	6 домашних заданий, коллоквиум и экзамен.	+	==Домашние задания  ==
		+	[https://www.dropbox.com/s/0tyqdtt7kth7ftj/results.xlsx?dl=0 Оценки]
−	Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий.	+	[https://www.dropbox.com/s/fl7etvks3q79ari/hw_1.pdf?dl=0 Домашнее задание 1.] Cрок сдачи 20.2.2018 в 15:10 MSK.
−	На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.	+
−	Сдача домашних заданий после их срока невозможна.	+
−	Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.	+	[https://www.dropbox.com/s/f6bh6l18pfcn0zs/hw_2.pdf?dl=0 Домашнее задание 2.] Cрок сдачи 20.3.2018 в 15:10 MSK.
−	Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме  не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по линейному	+	[https://www.dropbox.com/s/7kfkccsbx9mb1z8/hw_3.pdf?dl=0 Домашнее задание 3.] Cрок сдачи 15.5.2018 в 15:10 MSK. ''В этом ДЗ есть две бонусные задачи. Каждая из них дает +1 к оценке коллоквиума (но больше 10 за коллоквиум получить все равно нельзя, так что эти задачи можно воспринимать как подстраховку). Чтобы бонус засчитался, нужно за основную часть ДЗ получить не менее половины от максимально возможного балла.''
−	программированию, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов	+
−	соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях.	+
−	Экзамен состоит из 8 задач с указанием количества баллов за каждую	+
−	задачу. Эти баллы в сумме дают 10 баллов. Задачи нужно решить за две пары.	+
−	Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2.	+	[https://www.dropbox.com/s/l4d2dnra0ng5fua/hw_4.pdf?dl=0 Домашнее задание 4.] Cрок сдачи 19.6.2018 в 15:10 MSK.
−	Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его	+	==Прочитанные лекции==
−	сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной.	+
−	====Правила округления====	+	====Лекция 1 (9 января).  ====
−	В вычислениях текущие оценки и промежуточные величины не округляются. Результат	+	Формулировки первой и второй теоремы Гёделя для формальной арифметики и теории множеств. Понятие финитного и сугубо финитного доказательства. Программа Гильберта обоснования математики.
−	вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок.	+
−	Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной	+
−	оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6	+
−	округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3,	+
−	5,48 – до 5, 5,54 – до 6, 7.12 – до 8.	+
−	====Экзамен====	+	====Лекция 2 (16 января).  ====
−	Баллы за задачи и критерии их оценки (на последнем листе) находятся [https://www.dropbox.com/s/nnubzvb9gg5299o/exam-results-base.xls?dl=0 здесь]. Показ работ 23 декабря в 16:40 в ауд. 402. Решения задач [ https://www.dropbox.com/s/vgj8vcm2yyx63rg/main-17-12-21-sol.pdf?dl=0 здесь]	+	Нефинитное доказательство существования сколь угодно больших чисел. Нефинитное доказательство непротиворечивости PA.
−	==Сроки контрольных мероприятий==	+	Тезис арифметичности (любая арифметическая формула, имеющая финитное доказательство, выводима в PA). Принцип свертывания (без доказательства).
−	Эти сроки немного различаются для разных групп (поскольку семинары в разные дни).	+	Принцип отражения в PA. Первая теорема Геделя о неполноте для PA.
		+	Вторая теорема Геделя о неполноте для PA.
−	'''Сроки сдачи ДЗ для 164 и 166 группы:'''	+	====Лекция 3 (23 января).  ====
−	Первое домашнее задание  19 сентября (защита до 10 октября [для 166 группы до 17 октября]) .	+	Аксиомы Бернайса и вывод из них второй теоремы о неполноте.
−	Второе домашнее задание 3 октября (защита до 24 октября).	+	Первая теорема Геделя в форме Россера для PA.
−	Третье домашнее задание 24 октября (защита до 14 ноября).	+
−	Четвертое домашнее задание 7 ноября (защита до 28 ноября).	+
−	Пятое домашнее задание  21 ноября (защита до 12 декабря).	+
−	Шестое домашнее задание 5 декабря (защита до 26 декабря).	+
−	'''Сроки сдачи ДЗ для 163 и 165 группы:'''	+	====Лекция 4 (30 января).  ====
−	Первое домашнее задание 22 сентября (защита до 13 октября).	+	Разрешимость элементарной теории поля комплексных чисел.
−	Второе домашнее задание 6 октября (защита до 27 октября).	+
−	Третье домашнее задание 3 ноября (защита до 17 ноября).	+
−	Четвертое домашнее задание 17 ноября (защита до 1 декабря).	+
−	Пятое домашнее задание 1 декабря (защита до 15 декабря).	+
−	Шестое домашнее задание 15 декабря (защита до 29 декабря).	+
		+	Разрешимость элементарной теории упорядоченного поля действительных чисел (теорема Тарского-Зайденберга) (начало).
−	Коллоквиум пройдет с 11 по 15 декабря. [https://www.dropbox.com/s/bfx9cnut2w2ww3z/colloq.pdf?dl=0 Вопросы к коллоквиуму]	+	====Лекция 5 (6 февраля). ====
−	Экзамен (письменный) с 21 по 31 декабря.	+	Разрешимость элементарной теории упорядоченного поля действительных чисел (теорема Тарского-Зайденберга) (окончание).
−	==Домашние задания  ==	+	Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
−	'''[https://docs.google.com/spreadsheets/d/1nWh4-qMKA8gTQJ3aNhWkeVEwxaOJbSxd4Sek5plUaUg Оценки за домашние задания (группа 163)]'''	+
−	'''[https://www.dropbox.com/s/vi2j0bsa6j4y8fm/164.xls?dl=0 Оценки за домашние задания (группа 164)]'''	+	====Лекция 6 (13 февраля).  ====
−	'''[https://www.dropbox.com/s/6cvpur8awoocuku/165.xls?dl=0 Оценки за домашние задания (группа 165)]'''	+	Реберное расширение и его связь с вершинным расширением. Матрица графа и ее собственные числа. Expander mixing lemma.
−	'''[https://docs.google.com/spreadsheets/d/1IwSAme4B9Of6xg-e-ZilB1mDy7B_PYeSuAJErX4yZKE/edit?usp=sharing Оценки за домашние задание (группа 166)]'''	+	====Лекция 7 (20 февраля).  ====
−	'''[https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны:  для сдачи 19 сентября, для защиты 10 октября (для групп 164 и 166).	+	L_2-расстояние до равномерного распределения при одном шаге случайного блуждания.
		+	Лапласиан графа. От спектрального экспадера к комбинаторному.
−	[https://www.dropbox.com/s/jmqm4vdw0l19oqg/hw2.pdf?dl=0 Домашнее задание №2] -- дедлайны:  для сдачи 3 октября, для защиты 24 октября (для группы 166) и 31 октября (для группы 164).	+	====Лекция 8 (27 февраля). ====
−	[https://www.dropbox.com/s/1dkxcvze0u8930l/hw3.pdf?dl=0 Домашнее задание №3] -- дедлайны:  для сдачи 17 или 24 октября, для защиты 7 ноября (для групп 164 и 166).	+	Нижняя оценка на второе собственное числа d-регулярного графа. Вероятностное доказательство существования спектрального экспандера.
−	[https://www.dropbox.com/s/18bd95cvk526cuu/hw4.pdf?dl=0 Домашнее задание №4]. Срок сдачи для 164 и 166 групп - 7 ноября. Защита до 28 ноября.	+	====Лекция 9 (6 марта). ====
−	[https://www.dropbox.com/s/bea4pllf8tspigb/hw5.pdf?dl=0 Домашнее задание №5]. Срок сдачи для 164 и 166 групп - 21 ноября. Защита до 12 декабря.	+	Тензорное произведение и зигзаг-произведение двух графов и их собственные числа. Построение спектрального экспандера с использованием первой оценки для зигзаг-произведения (слабо и сильно эффективные конструкции).
−	[https://www.dropbox.com/s/6v2r2l9rswfctnc/hw6.pdf?dl=0 Домашнее задание №6]. Срок сдачи для 164 и 166 групп - 5 декабря. Защита до 26 декабря.	+	====Лекция 10 (13 марта). ====
−	==Примерное содержание лекций==	+	Уменьшение вероятности ошибки с помощью экспандеров без использования дополнительной случайности.
−	* Общая задача линейного программирования.	+	Уменьшение вероятности ошибки с помощью экспандеров путем t шагов случайного блуждания с использованием O(t) дополнительных случайных битов.
−	* Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях	+	Вторая спектральная оценка для зигзаг-произведения.
−	* Метод исключения переменных.	+	====Лекция 11 (20 марта). ====
−	* Способы докательства оптимальности линейных программ.	+	Алгоритм Рейнголда.
−	* Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема	+	27 марта лекции нет (сессия).
−	двойственности	+
−	* Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.	+	====Лекция 12 (3 апреля). ====
−	* Симплекс метод.	+	Экспандер Маргулиса.
−	* Исчисление резолюций для пропозициональных формул.	+	====Лекция 13 (10 апреля). ====
−	* Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели. Доказательства элементарной эквивалентности с помощью игр Эренфойхта	+	Двудольные экспандеры: необходимое и достаточное условие существования. Экспандер с коэффициентом увеличения близким к степени.
−	* Исчисление резолюций для формул первого порядка.	+	Экспандер Варди-Парвареша (конструкция).
−	* Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.	+	====Лекция 14 (17 апреля). ====
−	* Логическое следование и аксиоматические теории.	+	Экспандер Варди-Парвареша (доказательство расширения).
−	==Прочитанные лекции==	+	====Лекция 15 (24 апреля).  ====
		+
		+	Экспандерные коды: последовательный и параллельный алгоритм декодирования.
		+
		+	1 и 8 мая лекций не будет (каникулы)
		+
		+	====Лекция 16 (15 мая).  ====
		+
		+	Алгоритм Мозера-Тардоша (эффективная версия локальной леммы Ловаса).
		+
		+	====22 мая лекция и семинар отменяется из-за того, что большинство студентов уезжают в С.Петербург.  ====
		+
		+	====Лекция 17 (29 мая).  ====
		+
		+	Деревья разрешения (детерминированные, недетерминированные и вероятностные). Метод противника для доказательства нижних оценок детерминированной сложности. Сертификаты. Соотношение между P детерминированной, недетерминированной и вероятностной  сложностью.
		+
		+	====Лекция 18, последняя (5 июня).  ====
		+
		+
		+
		+	Нижние оценки для схем ограниченной глубины. Метод ограничений и теорема First-Saxe-Sipser-Yao-Hastad нижней оценке для функции PARITY. Switching lemma. Теорема Разборова Смоленского о нижней оценке для схем ограниченной глубины с функциями MOD_p.
		+
		+	====12 июня лекции не будет (праздник)====
		+
		+	==Проведённые семинары  ==
		+
		+	===Семинар 1 (9 января)===
		+	Beta-функция Геделя. Задачи на выразимость предикатов в арифметике ("x --- совершенное число", "x равно целой части e^y"). Построение формулы, выражающей непротиворечивость PA. Некоторые простые свойства ZF  (почему множество не может принадлежать самому себе, почему существует декартово произведение).
		+
		+	===Семинар 2 (16 января)===
		+	Транзитивные множества и ординалы. Пример транзитивного множества, не являющегося ординалом. Порядок на ординалах. В любом множестве ординалов есть минимальный. Для любого ординала есть непосредственно следующий за ним ординал. Линейность порядка на ординалах.
		+
		+	===Семинар 3 (23 января)===
		+	Ложность аксиом Бернайса при неестественном определении выводимости. Определение натуральных чисел в ZF (если ZF непротиворечива, то PA непротиворечива). Вывод транзитивности и коммутативности сложения из PA. Сугубо финитное доказательство принципа свертывания (не до конца).
		+
		+	===Семинары 4-19 ===
		+	'''[https://www.dropbox.com/s/zv5bvq8fd4v7est/cw_4.pdf?dl=0 Семинар 4. Задачи (30 января)]'''
		+
		+	'''[https://www.dropbox.com/s/udcg4dn9wzmr6im/cw_5.pdf?dl=0 Семинар 5. Задачи (6 февраля)]'''
		+
		+	'''[https://www.dropbox.com/s/h3zp5mppz50tnjg/cw_6.pdf?dl=0 Семинар 6. Задачи (13 февраля)]'''
		+
		+	'''[https://www.dropbox.com/s/b4f4kbf0hmflfif/cw_7.pdf?dl=0 Семинар 7. Задачи (20 февраля)]'''
		+
		+	'''[https://www.dropbox.com/s/xayaklvx5xdd6zk/cw_8.pdf?dl=0 Семинар 8. Задачи (27 февраля)]'''
		+
		+	'''[https://www.dropbox.com/s/uorlkdgsxcrm69x/cw_9.pdf?dl=0 Семинар 9. Задачи (6 марта)]'''
		+
		+	'''[https://www.dropbox.com/s/qvtxouxveic7z8o/cw_10.pdf?dl=0 Семинар 10. Задачи (13 марта)]'''
		+
		+	'''[https://www.dropbox.com/s/wc82c09jcwvgh32/cw_11.pdf?dl=0 Семинар 11. Задачи (20 марта)]'''
		+
		+	'''[https://www.dropbox.com/s/gcia9sawocgcn68/cw_12.pdf?dl=0 Семинар 12. Задачи (3 апреля)]'''
		+
		+	'''[https://www.dropbox.com/s/hpk27suaer48jlk/cw_13.pdf?dl=0 Семинар 13. Задачи (10 апреля)]'''
		+
		+	'''[https://www.dropbox.com/s/0b5pisyfytk9d13/cw_14.pdf?dl=0 Семинар 14. Задачи (17 апреля)]'''
		+
		+	'''[https://www.dropbox.com/s/giofyz33nhb4o6n/cw_15.pdf?dl=0 Семинар 15. Задачи (24 апреля)]'''
		+
		+	'''[https://www.dropbox.com/s/jax1c4w39vmwgty/cw_16.pdf?dl=0 Семинар 16. Задачи (15 мая)]'''
		+
		+	'''[https://www.dropbox.com/s/0ycuylf84mhpp1v/cw_17.pdf?dl=0 Семинар 17. Задачи (29 мая)]'''
		+
		+	'''[https://www.dropbox.com/s/a9bpf6mh8aqbgyr/cw_18.pdf?dl=0 Семинар 18. Задачи (5 июня)]'''
		+
		+	==Конспекты лекций==
		+	[https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 Конспекты лекций об экспандерах, полученные переработкой книги Ромащенко]
		+
		+	[https://www.dropbox.com/s/dt9ld9c5x5kfa25/ar.pdf?dl=0 Конспекты лекций о теоремах Геделя для арифметики Пеано]
		+
		+	[https://www.dropbox.com/s/8p86uddpv74c39o/ZF.pdf?dl=0 Конспекты лекций об аксиоматической теории множеств ZF, теоремах Гёделя для ZF и доказательствах независимости от ZF]
		+
		+	==Консультации ==
		+
		+	Козачинский вт. 13:30-15:00, ср 16:00-18:00 в 617
		+
		+	==Рекомендуемая литература  ==
		+
		+	[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://arxiv.org/pdf/1305.1535.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]
−	====Лекция 1 (5 сентября). ====	+	N. Nisan, CREW PRAM's and decision trees, STOC 1989, pages 327-335.

---

Текущая версия на 15:00, 11 июня 2018

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

Лекции проходят по вторникам в аудитории 306 в 15:10-16:30. Семинары по вторникам 16:40-18:00. Первая лекция и семинар 9 января.

Канал в telegram

Новости

• 5 июня: Выложены вопросы к коллоквиуму.
• 16 мая: лекция и семинар 22 мая отменяются из-за того, что большинство студентов уезжают в С.Петербург.

• 15 мая: Назначены даты коллоквиума и письменного экзамена. Коллоквиум: 13 июня СР, 15:10-18:00, ауд.435. Экзамен: 19 июня ВТ, 10:30-13:30, ауд.400.

• 28 апреля: выложены ссылки на статьи с изложением алгоритма Мозера-Тардоша.

• 4 апреля: выложены конспекты лекций об экспандеров, полученные переработкой книги Ромащенко.

Лектор

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

Семинарист

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

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

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

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

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

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

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

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

Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2.

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

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

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

Коллоквиум

Коллоквиум состоится 13 июня СР, 15:10-18:00, ауд.435.

Вопросы к коллоквиуму.

Экзамен

Письменный экзамен назначен на 19 июня ВТ, 10:30-13:30, ауд.400.

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

Первое домашнее выложено 6.2.2018, срок сдачи 20.2.2018.

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

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

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

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

Оценки

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

Домашнее задание 2. Cрок сдачи 20.3.2018 в 15:10 MSK.

Домашнее задание 3. Cрок сдачи 15.5.2018 в 15:10 MSK. В этом ДЗ есть две бонусные задачи. Каждая из них дает +1 к оценке коллоквиума (но больше 10 за коллоквиум получить все равно нельзя, так что эти задачи можно воспринимать как подстраховку). Чтобы бонус засчитался, нужно за основную часть ДЗ получить не менее половины от максимально возможного балла.

Домашнее задание 4. Cрок сдачи 19.6.2018 в 15:10 MSK.

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

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

Формулировки первой и второй теоремы Гёделя для формальной арифметики и теории множеств. Понятие финитного и сугубо финитного доказательства. Программа Гильберта обоснования математики.

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

Нефинитное доказательство существования сколь угодно больших чисел. Нефинитное доказательство непротиворечивости PA.

Тезис арифметичности (любая арифметическая формула, имеющая финитное доказательство, выводима в PA). Принцип свертывания (без доказательства).

Принцип отражения в PA. Первая теорема Геделя о неполноте для PA. Вторая теорема Геделя о неполноте для PA.

Лекция 3 (23 января).

Аксиомы Бернайса и вывод из них второй теоремы о неполноте. Первая теорема Геделя в форме Россера для PA.

Лекция 4 (30 января).

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

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

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

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

Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).

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

Реберное расширение и его связь с вершинным расширением. Матрица графа и ее собственные числа. Expander mixing lemma.

Лекция 7 (20 февраля).

L_2-расстояние до равномерного распределения при одном шаге случайного блуждания. Лапласиан графа. От спектрального экспадера к комбинаторному.

Лекция 8 (27 февраля).

Нижняя оценка на второе собственное числа d-регулярного графа. Вероятностное доказательство существования спектрального экспандера.

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

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

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

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

Уменьшение вероятности ошибки с помощью экспандеров путем t шагов случайного блуждания с использованием O(t) дополнительных случайных битов.

Вторая спектральная оценка для зигзаг-произведения.

Лекция 11 (20 марта).

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

27 марта лекции нет (сессия).

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

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

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

Двудольные экспандеры: необходимое и достаточное условие существования. Экспандер с коэффициентом увеличения близким к степени.

Экспандер Варди-Парвареша (конструкция).

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

Экспандер Варди-Парвареша (доказательство расширения).

Лекция 15 (24 апреля).

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

1 и 8 мая лекций не будет (каникулы)

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

Алгоритм Мозера-Тардоша (эффективная версия локальной леммы Ловаса).

22 мая лекция и семинар отменяется из-за того, что большинство студентов уезжают в С.Петербург.

Лекция 17 (29 мая).

Деревья разрешения (детерминированные, недетерминированные и вероятностные). Метод противника для доказательства нижних оценок детерминированной сложности. Сертификаты. Соотношение между P детерминированной, недетерминированной и вероятностной сложностью.

Лекция 18, последняя (5 июня).

Нижние оценки для схем ограниченной глубины. Метод ограничений и теорема First-Saxe-Sipser-Yao-Hastad нижней оценке для функции PARITY. Switching lemma. Теорема Разборова Смоленского о нижней оценке для схем ограниченной глубины с функциями MOD_p.

12 июня лекции не будет (праздник)

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

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

Beta-функция Геделя. Задачи на выразимость предикатов в арифметике ("x --- совершенное число", "x равно целой части e^y"). Построение формулы, выражающей непротиворечивость PA. Некоторые простые свойства ZF (почему множество не может принадлежать самому себе, почему существует декартово произведение).

Семинар 2 (16 января)

Транзитивные множества и ординалы. Пример транзитивного множества, не являющегося ординалом. Порядок на ординалах. В любом множестве ординалов есть минимальный. Для любого ординала есть непосредственно следующий за ним ординал. Линейность порядка на ординалах.

Семинар 3 (23 января)

Ложность аксиом Бернайса при неестественном определении выводимости. Определение натуральных чисел в ZF (если ZF непротиворечива, то PA непротиворечива). Вывод транзитивности и коммутативности сложения из PA. Сугубо финитное доказательство принципа свертывания (не до конца).

Семинары 4-19

Семинар 4. Задачи (30 января)

Семинар 5. Задачи (6 февраля)

Семинар 6. Задачи (13 февраля)

Семинар 7. Задачи (20 февраля)

Семинар 8. Задачи (27 февраля)

Семинар 9. Задачи (6 марта)

Семинар 10. Задачи (13 марта)

Семинар 11. Задачи (20 марта)

Семинар 12. Задачи (3 апреля)

Семинар 13. Задачи (10 апреля)

Семинар 14. Задачи (17 апреля)

Семинар 15. Задачи (24 апреля)

Семинар 16. Задачи (15 мая)

Семинар 17. Задачи (29 мая)

Семинар 18. Задачи (5 июня)

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

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

Конспекты лекций о теоремах Геделя для арифметики Пеано

Конспекты лекций об аксиоматической теории множеств ZF, теоремах Гёделя для ZF и доказательствах независимости от ZF

Консультации

Козачинский вт. 13:30-15:00, ср 16:00-18:00 в 617

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

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

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.

Статья Румянцева и Шеня с изложением алгоритма Мозера-Тардоша

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.