Project Seminar 2020 2021 — различия между версиями

Версия 14:31, 15 октября 2020

Правила оценивания

Итоговая оценка (О_и) получается из оценки за семестр (О_с) и оценки за экзамен (О_э) по следующей формуле

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.

Семинар 4 (15 октября).

Доклад Дмитрия Правоторова о Gibbard-Satterthwaite Theorem (любая система голосования обладает какием-то "плохим" свойством), а также о популярных способах голосования, уязвимых для манипуляций.

Предлагаемые статьи для рассказа на семинаре

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