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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 92: Строка 92:
  
 
https://drive.google.com/file/d/1023IMfVawOY0TGJOe2WYg5oVaM8Vuzit/view?usp=sharing
 
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
  
 
==Предлагаемые статьи для рассказа на семинаре==
 
==Предлагаемые статьи для рассказа на семинаре==

Версия 12:54, 4 марта 2021

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

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

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

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

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