|
|
| Строка 3: |
Строка 3: |
| | | | |
| | | | |
| − | Лекции проходят по пятницам 13:00-14:20 ауд. N507, семинары также по пятницам 14:40-16:00 ауд. N507 | + | Лекции проходят по вторникам 11:10-12:30 ауд. N507, семинары также по вторникам 13:00-14:20 ауд. N507 |
| | | | |
| | | | |
| − | Первая лекция и семинар 14 января. | + | Первая лекция и семинар 10 января (?). |
| | | | |
| | ==Новости== | | ==Новости== |
| − |
| |
| − | ===23 июня===
| |
| − | Экзамен начнётся 11:00 в R208.
| |
| − | Ссылка для сдающих онлайн: https://us06web.zoom.us/j/88682915534
| |
| − |
| |
| − | ===15 июня ===
| |
| − | [https://docs.google.com/spreadsheets/d/1KIUHUseQc6gJHvSfTLrl5gSTMS1OjAdEnB735mlJsQg/edit?usp=sharing Запись на коллоквиум]
| |
| − |
| |
| − | Ссылка для сдающих онлайн: https://us02web.zoom.us/j/83878035576?pwd=dmxybDk3UzVCU1E2S1k5MWJidk5RQT09
| |
| − |
| |
| − | ===11 июня ===
| |
| − | Выложена [https://www.dropbox.com/s/z6k1vf2xwfr7jv8/colloq2022.pdf?dl=0 программа коллоквиума] Коллоквиум начнется в 11:00 в ауд. N507
| |
| − |
| |
| − | ===3 июня ===
| |
| − |
| |
| − | Коллоквиум будет 17 июня в 11 часов, а экзамен - 24 июня в 11 часов.
| |
| − |
| |
| − | === 20 мая ===
| |
| − |
| |
| − | '''20 мая''' лекция и семинар будут он-лайн https://zoom.us/j/97678829782?pwd=cVVrTDhxaVdTVU5KUU1hNmhpVUliUT09
| |
| − |
| |
| − | Семинар будет по этой ссылке: https://us02web.zoom.us/j/81568389606?pwd=ZEtkeVpjajVBMWxIVkY1eDBPTWxNZz09
| |
| − |
| |
| − | === 11 апреля ===
| |
| − |
| |
| − | '''15 апреля''' лекции не будет. Семинар состоится как обычно.
| |
| − |
| |
| − | === 10 февраля ===
| |
| − |
| |
| − | 11 февраля занятия пройдут онлайн: https://zoom.us/j/97678829782?pwd=cVVrTDhxaVdTVU5KUU1hNmhpVUliUT09
| |
| − |
| |
| − | === 3 февраля ===
| |
| − |
| |
| − | 4 февраля занятия пройдут онлайн: https://zoom.us/j/97678829782?pwd=cVVrTDhxaVdTVU5KUU1hNmhpVUliUT09
| |
| − |
| |
| − | === 9 января ===
| |
| − |
| |
| − | 21 января лекция отменяется. Семинар состоится как обычно.
| |
| − |
| |
| − | ==Контакты==
| |
| | | | |
| | Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com | | Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com |
| Строка 81: |
Строка 41: |
| | вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценки. | | вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценки. |
| | | | |
| − | ====Коллоквиум==== | + | ====Коллоквиум====. |
| − | Коллоквиум будет 17 июня в 11 часов, ауд. N507.
| + | |
| | | | |
| | [https://www.dropbox.com/s/z6k1vf2xwfr7jv8/colloq2022.pdf?dl=0 Программа коллоквиума.] | | [https://www.dropbox.com/s/z6k1vf2xwfr7jv8/colloq2022.pdf?dl=0 Программа коллоквиума.] |
| | | | |
| | ====Экзамен==== | | ====Экзамен==== |
| − | Экзамен состоится 24 июня в 11 часов.
| |
| | | | |
| | ====Пересдачи==== | | ====Пересдачи==== |
| Строка 96: |
Строка 54: |
| | | | |
| | | | |
| − |
| |
| − | Пересдача 8 сентября. Для пересдачи коллоквиума надо подключиться к конференции в 16:00, получить билет из программы коллоквиума и через час его сдавать ([https://www.dropbox.com/s/ef0514u08o7oiaw/colloq2021.pdf?dl=0 по обычным правилам]). Для пересдачи экзамена надо подключиться к конференции в 16:00 и получить вариант. Если студент сдает и коллоквиум, и экзамен, то экзамен сдается сразу после коллоквиума. Экзамен с прокторингом сдается по тем же правилам, что и в сессию, с аналогичным набором задач.
| |
| − |
| |
| − | Пересдача комиссии ... В ходе сдаче студенту может быть дана 1 или 2 задачи. Все полученные ранее оценки аннулируются и выставленная комиссией оценка является итоговой.
| |
| | | | |
| | ==Примерные сроки контрольных мероприятий== | | ==Примерные сроки контрольных мероприятий== |
| Строка 112: |
Строка 66: |
| | | | |
| | ==Домашние задания == | | ==Домашние задания == |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | [https://drive.google.com/file/d/14tkRaF894xNpbZVIhdJexSSwRO4hp5X1/view?usp=sharing Домашнее задание 1] Cрок сдачи 7.03.2022
| |
| − |
| |
| − | [https://drive.google.com/file/d/1fuczHk8gH26iXv-sM_1d4x4WqPUQHzRb/view?usp=sharing Домашнее задание 2] Срок сдачи 15.04.2022
| |
| − |
| |
| − | [https://drive.google.com/file/d/1fHE02fZE56wkbWnVBc8V0iVFmZ1EKlix/view?usp=sharing Домашнее задание 3] Срок сдачи 20.05.2022
| |
| − |
| |
| − | [https://drive.google.com/file/d/12Kb2SeSbm76L7Fh40184Iw0ZyeLdzSOR/view?usp=sharing Домашнее задание 4] Срок сдачи 17.06.2022
| |
| | | | |
| | ==Результаты == | | ==Результаты == |
| | | | |
| − | [https://docs.google.com/spreadsheets/d/1NYPKRymXEYswa5FhPEzu27u9BGGc9zw5cYejcLVU1ak/edit?usp=sharing Результаты]
| |
| − |
| |
| − | ==Прочитанные лекции==
| |
| − |
| |
| − | ====Лекция 1 (14 января). ====
| |
| − |
| |
| − | Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
| |
| − | Реберное расширение и его связь с вершинным расширением.
| |
| − |
| |
| − | ====Лекция 2 (28 января). ====
| |
| − |
| |
| − | Матрица графа и ее собственные числа.
| |
| − | Максимальное по абсолютной величине собственное число регулярного графа. От спектрального экспандера к комбинаторному.
| |
| − | Лемма о перемешивании.
| |
| − | Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа.
| |
| − |
| |
| − | ====Лекция 3 (4 февраля). ====
| |
| − | Нижняя оценка 2sqrt(d-1)-o(1) на второе собственное число d-регулярного графа.
| |
| − |
| |
| − | Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами.
| |
| − |
| |
| − | https://zoom.us/rec/share/NOhVyP3DAcgAyFdpSVpI9nc7vUk1zjdQCeeCXmVpAhkxMm62CPkhnCi32Bbf9p0E.hJ-0tHxBLfyyDGi4?startTime=1643968643000 (Passcode: $.m&J6Bw)
| |
| − |
| |
| − | ====Лекция 4 (11 февраля). ====
| |
| − | Степень графа и тензорное произведение графов и их собственные числа.
| |
| − | Зигзаг-произведение графов и первая оценка его собственных чисел. https://zoom.us/rec/share/w2v90UsyP37UWW9gKdWiPyfIf_GSJSuG2pfqKNgfamWV8M24JVprbICyRHNob2r2.B9WF7cLBqode6WgN?startTime=1644573389000 (Passcode: 3.&CeGk&)
| |
| − |
| |
| − | ====Лекция 5 (18 февраля). ====
| |
| − | Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
| |
| − | Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
| |
| − | Вторая оценка для спектрального зазора зигзаг-произведения. https://us06web.zoom.us/rec/share/LVfLNBQRJouJqvwFWMMs4l5gYIiWvUiUhxwUMc3fH4fyMBuIOlSYlcCiZWbW_mXR.JgJnHEssl3KE6_9K?startTime=1645178357000 (Код доступа: 8nCabA?p)
| |
| − |
| |
| − | ====Лекция 6 (25 февраля). ====
| |
| − | Второе собственное число связного недвудольного графа.
| |
| − |
| |
| − | Алгоритм Рейнгольда.
| |
| − |
| |
| − | ====Лекция 7 (4 марта). ====
| |
| − | Применение экспандеров для дерандомизации.
| |
| − |
| |
| − | ====Лекция 8 (11 марта). ====
| |
| − | Экспандер Маргулиса. https://us06web.zoom.us/rec/share/-aCtmQApQVyS0ba-762NYPsrGCPVm7AVOPuRgDRH-NnLmbn060f649Is2PrkXXPC.y48bojzyHWHkqPCB?startTime=1646992575000 (Код доступа: ^3YntU!t)
| |
| − |
| |
| − | ====Лекция 9 (18 марта). ====
| |
| − | Двудольные экспандеры: определение и вероятностное доказательство существования. https://us06web.zoom.us/rec/share/lRohEAegryfNOxh9a6SuON9EKnoBoezJUtQuFyQjJ46mgGWSJbX3hUfM4N_e63BF.Sv-fP_hTizo9OIRX?startTime=1647597560000 (Код доступа: D*s+3!%K)
| |
| − |
| |
| − | ====Лекция 10 (25 марта). ====
| |
| − |
| |
| − | Экспандер Варди - Парвареша. https://us06web.zoom.us/rec/share/S3TpwT6-nRuuL-OIKYpddFdNtNvvmRiOPdqs0fwXiuD2MbZ9E4Bgd3DsNDgmNh6e.H9ZywqG8i7ICkWIf?startTime=1648202267000 (Код доступа: 5P?UVs5z)
| |
| − |
| |
| − | ====Лекция 11 (8 апреля). ====
| |
| − | Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время. https://us06web.zoom.us/rec/share/39A1_AduE88WzSIa5-QwBMlDozywjXMij1Q6_LGFf-cXUoMR1L9E_YO_zuyrs6At.Rdik0wA-JUqf90Tn?startTime=1649411730000 (Код доступа: 17!!K@TZ)
| |
| − | https://us06web.zoom.us/rec/share/h6hTzwAc_2U3nPCm9t1554_GXXi8_NAI-_caGjx2gtDDUcOehuCangEENXf5uMI.52NW_PS9x0quz3ue?startTime=1649419086000
| |
| − |
| |
| − | ====Лекция 12 (22 апреля). ====
| |
| − | Оценка Хэмминга.
| |
| − | Линейные коды, проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга.
| |
| − | Оценка Гилберта. Функция Шеннона. Графики оценок Хэмминга и Гилберта для двоичного алфавита. https://us06web.zoom.us/rec/share/24fS1mP-6LF46tQn9G4iP0EywiyMGBCXbHWfSHyZLC4MzNQNmMXfmm1Zdy6NIMA.TUOyTocg_q49eWud?startTime=1650627047000
| |
| − | Код доступа: t^g85Y!A
| |
| − |
| |
| − | ====Лекция 13 (29 апреля) ====
| |
| − |
| |
| − | Функция Шеннона и графики оценок Хэмминга и Гилберта
| |
| − | для произвольного алфавита. Оценка Варшамова - Гилберта. Случайные линейные коды. Коды Возенкрафта.
| |
| − |
| |
| − | Каскадные коды.
| |
| − |
| |
| − | ====Лекция 14 (13 мая) ====
| |
| − | Каскадные коды. Декодирование каскадного кода. Коды Форни. https://www.youtube.com/watch?v=6NXJVcnO-5k и https://www.youtube.com/watch?v=NE7dtzZOlWc
| |
| − |
| |
| − | ====Лекция 15. (20 мая) ====
| |
| − | Экспандерные коды: определение, последовательный алгоритм декодирования.
| |
| − | Первая оценка Плоткина для двоичного алфавита.
| |
| − | https://www.youtube.com/playlist?list=PLo3cgfsnO72ctaL2aza8xQ0ZA2S9SqW-c
| |
| − |
| |
| − | ====Лекция 16 (27 мая) ====
| |
| − | Оценки Плоткина и коды Адамара. Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.
| |
| − | [https://drive.google.com/file/d/1BA5LJsAwV4-CjLhPn5-HFf9PhIU81WfF/view?usp=sharing Video]
| |
| − |
| |
| − | ====Лекция 17 (3 июня ) ====
| |
| − | Доказательство оценки Гилберта для декодирования списком.
| |
| − | Улучшение оценки Синглтона для обычного декодирования с исправлением ошибок.
| |
| − | Оценки Джонсона и Элайеса - Бассалыго. [https://drive.google.com/file/d/1bxXB2I_5PrqQQzmISllWH3HSxm4DclIM/view?usp=sharing video]
| |
| − |
| |
| − | ====Лекция 18 (10 июня). ====
| |
| − |
| |
| − | Композиция кодов Рида - Соломона и Адамара и его декодирование списком. [https://drive.google.com/file/d/1wHUig8m4Odjdh1JcxzF5K8-EZS-Sc_TU/view?usp=sharing видео]
| |
| − |
| |
| − | ==Планируемые лекции==
| |
| − |
| |
| − |
| |
| − | Деревья разрешения, метод противника. Сертификатная сложность. Чувствительность и блочная чувствительность. Неравенствo D < C^2
| |
| − |
| |
| − | Вероятностные деревья и неравенство bs = O(R).
| |
| − | Неравенствo D < C*bs. Неравенство C< bs*s.
| |
| − |
| |
| − | Представление булевых функций многочленами с действительными коэффициентами.
| |
| − | Теорема Маркова.
| |
| − | Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди).
| |
| − | Связь между чувствительностью и степенью многочлена (Hao Huang), без доказательства.
| |
| | | | |
| | ==Семинары == | | ==Семинары == |
| − |
| |
| − | === Семинар 1 (14 января) ===
| |
| − | [https://www.dropbox.com/s/zmh1pxi6bpuek1o/cw1.pdf?dl=0 Листок 1 (комбинаторные экспандеры)]
| |
| − |
| |
| − | === Семинар 2 (21 января) ===
| |
| − | [https://www.dropbox.com/s/pu34evbm8y2maqe/cw_2.pdf?dl=0 Листок 2 (спектр графов)]
| |
| − |
| |
| − | === Семинар 3 (28 января) ===
| |
| − | [https://www.dropbox.com/s/4pi5nlbw4xu9wmg/cw_3.pdf?dl=0 Листок 3 ]
| |
| − |
| |
| − | === Семинар 4 (4 февраля) ===
| |
| − |
| |
| − | [https://drive.google.com/file/d/13-msSbArI1hB9OZaWm-r8IZFphJg5cw6/view?usp=sharing Листок 4]
| |
| − | [https://jamboard.google.com/d/1NZu-UqhYAf0BqH3tBkcysGGMTupPArwhehvAfjNHRWA/edit?usp=sharing Доска]
| |
| − |
| |
| − | === Семинар 5 (11 февраля) ===
| |
| − |
| |
| − | [https://drive.google.com/file/d/1IcaqGmvBaFZaGIWiWyLshbRyjAfsk1QW/view?usp=sharing Листок 5]
| |
| − | [https://jamboard.google.com/d/1P54dhuRKpFoEfg72TusQZitsTq1ITA4909B98qgVerQ/edit?usp=sharing Доска]
| |
| − |
| |
| − | === Семинар 6 (18 февраля) ===
| |
| − |
| |
| − | [https://drive.google.com/file/d/13UWkOqLRRHOSI9CBCBMI8DqizGIGTcJk/view?usp=sharing Листок 6]
| |
| − | [https://jamboard.google.com/d/1EfhBXTt2EQp2FnaZYu_WKPISCmaES1Dwjh_Rjp636nc/edit?usp=sharing Доска 6]
| |
| − |
| |
| − | === Семинар 7 (25 февраля) ===
| |
| − |
| |
| − | [https://drive.google.com/file/d/1S1HvWxU6hiZiVCh_cCO1stxcxOzmwYlK/view?usp=sharing Листок 7]
| |
| − |
| |
| − | === Семинар 8 (4 марта) ===
| |
| − |
| |
| − | [https://drive.google.com/file/d/1GO_GwL6iGJLmk7mLZ_q96FyOAgaPHJki/view?usp=sharing Листок 8]
| |
| − |
| |
| − | === Семинар 9 (11 марта) ===
| |
| − | [https://drive.google.com/file/d/1h68XGEU7OWZTFMDUGm-V-zOC5QJnwbAq/view?usp=sharing Листок 9] [https://jamboard.google.com/d/1xc7matGEIdhCJDP-Lm0Bw-Jiwuxs6ORJ0iYKrwprgws/edit?usp=sharing Доска]
| |
| − |
| |
| − | === Семинар 10 (18 марта) ===
| |
| − | [https://www.dropbox.com/s/t6qfr25e8r8mduw/cw_10.pdf?dl=0 Листок 10]
| |
| − | [https://jamboard.google.com/d/1uSzoBF2N3JADQZzSKF8pP7e1LZHSVnpad385onThrvs/edit?usp=sharing Доска]
| |
| − |
| |
| − | === Семинар 11 (25 марта) ===
| |
| − |
| |
| − | [https://drive.google.com/file/d/1o9stiu6NTIyBnGfYGSTGAYsfrEagwC3Z/view?usp=sharing Листок 11][https://jamboard.google.com/d/1hdefVGMZIV5loNBgx3kcNR1rfwVWhG_JU2kIwrAOP0M/edit?usp=sharing Доска]
| |
| − |
| |
| − |
| |
| − | === Семинар 12 (8 апреля) ===
| |
| − |
| |
| − | [https://www.dropbox.com/s/rlwh8uzn2r199ve/cw_12.pdf?dl=0 Листок 12] [https://jamboard.google.com/d/1jTOBiX-gIAlsVdle6cEaHNL7Q9NCWQ_HRFhGCDfUTEo/edit?usp=sharing Прошлогодняя доска]
| |
| − |
| |
| − |
| |
| − | === Семинар 13 (15 апреля) ===
| |
| − | [https://drive.google.com/file/d/1dsh4sZqPtf_F-7RjERFJE3N9llFI_OFv/view?usp=sharing Листок 13] [https://drive.google.com/file/d/16IN9qSYVv_Vg2Qu0H3Ya4ELjCabDSnba/view?usp=sharing Видео]
| |
| − |
| |
| − |
| |
| − | === Семинар 14 (22 апреля) ===
| |
| − | [https://drive.google.com/file/d/1jKgE1JJ6bpfcjzGZi7j7EAjLLLrlxgq6/view?usp=sharing Листок 14]
| |
| − |
| |
| − |
| |
| − | === Семинар 15 (13 мая) ===
| |
| − |
| |
| − | [https://drive.google.com/file/d/1qIi1ceQj_VHcVaIl76Ebabgca02uNqam/view?usp=sharing Листок 15] [https://drive.google.com/file/d/1pUCLDOtOcoz9gE7GPejpADwUxyrWY-hT/view?usp=sharing Видео]
| |
| − |
| |
| − | === Семинар 16 (20 мая) ===
| |
| − |
| |
| − | [https://drive.google.com/file/d/1bV0SVI0R4kV9Bi19s08dCMZnisTOEo48/view?usp=sharing Листок 16] [https://jamboard.google.com/d/1mXr6R4CEhCe5MMNrq1Z45KMGzIdJFRdnlOIaFokVtuI/edit?usp=sharing Доска]
| |
| − |
| |
| − | === Семинар 17 (27 мая) ===
| |
| − |
| |
| − | [https://drive.google.com/file/d/1hSIehIH5Ba9P_I8jYjgDGiv6yXQiHZTk/view?usp=sharing Листок 17]
| |
| − |
| |
| − | === Семинар 18 (3 июня) ===
| |
| − | [https://drive.google.com/file/d/13oUCT-TGyVVr08n00TNCiBS_b9TcaznE/view?usp=sharing Листок 18] [https://drive.google.com/file/d/1ioJaRswhGh_ZRVR0P1zOXEvYdWr-ilw2/view?usp=sharing video]
| |
| − |
| |
| − | === Семинар 19 (10 июня) ===
| |
| − | [https://drive.google.com/file/d/1IZpUA_qecD-0GWuyJrMmeOs5dJhJ9VXa/view?usp=sharing Листок 19] [https://drive.google.com/file/d/1ioJaRswhGh_ZRVR0P1zOXEvYdWr-ilw2/view?usp=sharing видео]
| |
| | | | |
| | ==Конспекты лекций== | | ==Конспекты лекций== |
Лекции проходят по вторникам 11:10-12:30 ауд. N507, семинары также по вторникам 13:00-14:20 ауд. N507
Семинарист: Милованов Алексей Сергеевич almas239@gmail.com, телеграм: AlexeySMilovanov
Экспандеры и их применения: теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти, построение генераторов псевдослучайных чисел, экспандерные коды.
Итоговая оценка складывается из оценок за домашние задания и оценок за коллоквиум и экзамен. Оценки за колллоквиум и экзамен входят в итоговую оценку с коэффициентом 0.4, а оценка за домашние задания - с коэффициентом 0.2. Если произойдет очередной переход на он-лайн занятия и это случится до 1 апреля 2022 (включительно), то на лекциях, проводимых через Zoom, будут даваться тесты. В этом случае результаты тестов будут учитываться с коэффициентом 0.2, а доли коллоквиума и экзамена будут уменьшены до 0.3.
В домашних заданиях иногда будут бонусные задания. За каждую решеннную бонусную задачу к итоговой оценке будет прибавляться 0.5 балла.
В течение двух модулей студентам будет дано 4 домашних задания.
Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается не менее 14 дней, решение ДЗ нужно сдавать семинаристу. Сдача домашних заданий после их срока невозможна.
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен. На пересдачу также могут прийти те, кто в итоге получил менее 4 баллов. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.
В вычислениях текущие оценки и промежуточные величины не округляются. Результат
вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценки.
====Коллоквиум====.
Пересдачи состоятся ... . Пересдача комиссии ... .
Пересдать можно коллоквиум и/или письменный экзамен (ранее полученная оценка при этом аннулируется).
N. Nisan, CREW PRAM's and decision trees, STOC 1989, pages 327-335.
