Project Seminar 2020 2021 — различия между версиями
Milovanov (обсуждение | вклад) |
Milovanov (обсуждение | вклад) (→Проведённые семинары) |
||
Строка 131: | Строка 131: | ||
https://drive.google.com/file/d/1eUjAjyzc0ENuuu88B9t8ZpRNjRJs_9Kj/view?usp=sharing | https://drive.google.com/file/d/1eUjAjyzc0ENuuu88B9t8ZpRNjRJs_9Kj/view?usp=sharing | ||
+ | |||
+ | ====Семинар 25 (15 апреля). ==== | ||
+ | |||
+ | https://drive.google.com/file/d/1lFd7APQw2y0i7PxFhfhgnNPKbjgMuqhC/view?usp=sharing | ||
==Предлагаемые статьи для рассказа на семинаре== | ==Предлагаемые статьи для рассказа на семинаре== |
Версия 15:35, 22 апреля 2021
Содержание
- 1 Правила оценивания
- 2 Проведённые семинары
- 2.1 Семинар 1 (17 сентября).
- 2.2 Семинар 2 (24 сентября).
- 2.3 Семинар 3 (1 октября).
- 2.4 Семинар 4 (8 октября).
- 2.5 Семинар 5 (15 октября).
- 2.6 Семинар 6 (29 октября).
- 2.7 Семинар 7 (5 ноября).
- 2.8 Семинар 8 (12 ноября).
- 2.9 Семинар 9 (19 ноября).
- 2.10 Семинар 10 (26 ноября).
- 2.11 Семинар 11 (3 декабря).
- 2.12 Семинар 12 (10 декабря).
- 2.13 Семинар 13 (17 декабря).
- 2.14 Семинар 14 (14 января).
- 2.15 Семинар 15 (21 января).
- 2.16 Семинар 16 (28 января).
- 2.17 Семинар 17 (4 февраля).
- 2.18 Семинар 18 (11 февраля).
- 2.19 Семинар 19 (18 февраля).
- 2.20 Семинар 20 (25 февраля).
- 2.21 Семинар 21 (4 марта).
- 2.22 Семинар 22 (18 марта).
- 2.23 Семинар 23 (25 марта).
- 2.24 Семинар 24 (8 апреля).
- 2.25 Семинар 25 (15 апреля).
- 3 Предлагаемые статьи для рассказа на семинаре
- 4 Преподаватели
Правила оценивания
Итоговая оценка (О_и) получается из оценки за семестр (О_с) и оценки за экзамен (О_э) по следующей формуле
O_и = 0,6 * О_с + 0,4 * О_э. Далее полученное число округляется по обычным правилам.
Оценка за семестр ставится за сделанные доклады, посещение и работу на семинарах.
Проведённые семинары
Семинар 1 (17 сентября).
Задача равенства нулю многочлена. Лемма Шварца-Зиппеля. Применение PIT для нахождения паросочетаний.
Семинар 2 (24 сентября).
Доклад Дмитрия Правоторова о статье "Truth, justice, and cake cutting" (Chen et al., 2013). В статье приводится описание двух алгоритмов разрезания торта, удволетворяющих некоторым свойствам справедливости.
Семинар 3 (1 октября).
Введение в алгоритмическую статистику
Семинар 4 (8 октября).
Дерондомизация PIT для схем глубины 3.
Семинар 5 (15 октября).
Доклад Дмитрия Правоторова о Gibbard-Satterthwaite Theorem (любая система голосования обладает какием-то "плохим" свойством), а также о популярных способах голосования, уязвимых для манипуляций. https://drive.google.com/file/d/1pNegxQGoTCVmzEkoBjt5Bg4vgU-vDN3D/view?usp=sharing
Семинар 6 (29 октября).
Введение в Property testing https://www.hse.ru/mirror/pubs/share/182501491
Семинар 7 (5 ноября).
https://drive.google.com/file/d/11Emea-Lf1C6wtyIDFw-Hk3gQwfubyhAl/view?usp=sharing
Семинар 8 (12 ноября).
https://drive.google.com/file/d/11Emea-Lf1C6wtyIDFw-Hk3gQwfubyhAl/view?usp=sharing
Семинар 9 (19 ноября).
https://drive.google.com/file/d/1FDoTGOFyuZXKosvo7WtFg0umlHbJ00OL/view?usp=sharing
Семинар 10 (26 ноября).
https://www.dropbox.com/s/xr27ls89kfbwlwa/cw17.pdf?dl=0
Семинар 11 (3 декабря).
Введение в Fined-Grained complexity
http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf
Семинар 12 (10 декабря).
Доклад Александра Панаетова о числах Рамсея. https://drive.google.com/file/d/1siai9QaAR5bfEamtkN4P1UR2B_cp_VZW/view?usp=sharing
Семинар 13 (17 декабря).
Доклад Павла Корозевцева о кодах, исправляющих ошибки.
https://drive.google.com/file/d/1-rfWfmNp09JkEFewzQ00zxnYkDjO0wr8/view?usp=sharing
Семинар 14 (14 января).
https://drive.google.com/file/d/1aEX5bNfmTqJC3R3fxULvTc0uEASshK0c/view?usp=sharing
Семинар 15 (21 января).
https://drive.google.com/file/d/1t9yetCm6Cy3Vl5XXMN-HVLXzIZPfWqrg/view?usp=sharing
Семинар 16 (28 января).
https://drive.google.com/file/d/1t9yetCm6Cy3Vl5XXMN-HVLXzIZPfWqrg/view?usp=sharing
Семинар 17 (4 февраля).
https://drive.google.com/file/d/1nI6xYAjjM8v9hdAqXRcTZFfmDiJcjRnV/view?usp=sharing
Семинар 18 (11 февраля).
Доклад Андрея Недолужко о Пфаффианах.
https://drive.google.com/file/d/1023IMfVawOY0TGJOe2WYg5oVaM8Vuzit/view?usp=sharing
Семинар 19 (18 февраля).
Доклад Дмитрия Правоторова про некоторые онлайн аукционы, гарантирующие почти оптимальную прибыль.
https://drive.google.com/file/d/1023IMfVawOY0TGJOe2WYg5oVaM8Vuzit/view?usp=sharing
Семинар 20 (25 февраля).
Доклад Никиты Лукьяненко про задачу о расписании.
https://drive.google.com/file/d/1R_3KLBrtRfUB3_wHv_NYFBqG8gDKmV9W/view?usp=sharing
Семинар 21 (4 марта).
Доклад Павла Захарова: Краткий экскурс в историю случайных графов, основные модели и определения. Далее предлагается подробно остановиться на биномиальной модели G(n, p) и разобраться с несколькими теоремами про "эволюцию" -- область, изучающую всё, что связано с компонентами случайного графа: их количество, размер и сложность.
https://drive.google.com/file/d/1tXoNmzLSukdF42GNRI2jCVFR34sOVtAK/view?usp=sharing
Семинар 22 (18 марта).
Доклад Азата Султанова.
https://drive.google.com/file/d/1dMPNjtOtdg2txzo43VdJyWc7YUeU8xn-/view?usp=sharing
Семинар 23 (25 марта).
Доклад Антона Гнатенко:
Конечные автоматы -- слабая, но простая для анализа и удобная для использования в алгоритмах модель вычислений. Грубо говоря, конечный автомат -- это машина Тьюринга, у которой отобрали ленту. Автоматы традиционно используются для распознавания и преобразования слов, но их можно обобщить и на более сложные структуры. Мы рассмотрим два вида автоматов, работающих с деревьями: традиционные и хорошо изученные древесные автоматы и менее известные древоходные автоматы. Постараемся разобраться в интересной теореме: детерминированные древоходные автоматы слабее недетерминированных (нечасто встречающееся в теории автоматов явление)
https://drive.google.com/file/d/1FPkkOURB2gN5hjYbGvl74U_6yWU8LsvZ/view?usp=sharing
Семинар 24 (8 апреля).
Доклад Павла Захарова: Павел Захаров. Анонс:
Максимальный разрез в случайном гиперграфе -- явно некая случайная величина. Давайте посмотрим на случай p = cn/binom(n, k). Можно показать, что: max-q-cut(H(n, p, k)) / n сходится по вероятности к константе gamma(c, k, q). Установление этого факта не даёт никаких оценок на предельную величину, так что мы ещё приведем две оценки, представимые в виде: A_{k, q} * c + B_{k, q} * √c + o(√c), где A_{k, q} вычислена точно, а на B_{k, q} даны верхняя и нижняя оценки с зазором порядка √k.
https://drive.google.com/file/d/1eUjAjyzc0ENuuu88B9t8ZpRNjRJs_9Kj/view?usp=sharing
Семинар 25 (15 апреля).
https://drive.google.com/file/d/1lFd7APQw2y0i7PxFhfhgnNPKbjgMuqhC/view?usp=sharing
Предлагаемые статьи для рассказа на семинаре
1) Nitin Saxena, Progress on Polynomial Identity Testing https://eccc.weizmann.ac.il/report/2009/101/
2) Лекции Стэндфордского университета о PIT и совершенных паросочетаниях. https://cs.stanford.edu/~mpkim/notes/lec5.pdf
Преподаватели
Милованов Алексей, almas239@gmail.com