Project Seminar 2019 2020

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

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

O_и = 0,6 * О_с + 0,4 * О_э. Далее полученное число округляется по обычным правилам.

Оценка за семестр ставится за сделанные доклады, посещение и работу на семинарах.

На экзамене студенту нужно рассказать о любых (кроме сделанных самим студентом) 3-k докладах, где k --- количество сделанных студентом докладов.

Текущие оценки

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

Семинар 1 (12 сентября).

Задача равенства нулю многочлена. Лемма Шварца-Зиппеля. https://eccc.weizmann.ac.il//report/2009/101/

Семинар 2 (19 сентября).

Применение задачи равенства нулю многочлена для решения задачи о паросочетаниях. Дерандомизация задачи о равенстве нулю многочлена для случая небольшого числа ненулевых мономов. https://eccc.weizmann.ac.il//report/2009/101/

Семинар 3 (26 сентября).

Дерандомизация задачи о равенстве нулю многочлена с помощью теорем типа Сильвестра-Галлаи. https://eccc.weizmann.ac.il//report/2009/101/

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

Доклад Антона Гнатенко https://www.semanticscholar.org/paper/Principles-of-model-checking-Baier-Katoen/2bbf4707b8555fd001b1d3248ca0b9815ac9bd46

Семинар 5 (10 октября).

Доклад Антона Гнатенко.

Анонс:

Конечные автоматы, задающие преобразования потоков входных сигналов в последовательности элементарных действий, являются простейшей моделью вычислений, пригодной для описания поведения реагирующих систем. Это поведение проявляется в соответствии между потоком входных сигналов и последовательностью элементарных действий, выполняемых системой. Для формальной спецификации и верификации реагирующих систем такого рода требуются более сложные и выразительные средства спецификации, нежели традиционные темпоральные логики. В докладе будет предложена расширенная темпоральная логика Reg-CTL*, в которой темпоральные операторы параметризованы регулярными выражениями. Мы рассмотрим алгоритмы верификации автоматов-преобразователей относительно формул некоторых фраментов этой логики, а также её выразительные возможности. На правах "work in progress" будет изложена идея алгоритма верифкации относительно произвольных формул Reg-CTL*.

https://www.semanticscholar.org/paper/Principles-of-model-checking-Baier-Katoen/2bbf4707b8555fd001b1d3248ca0b9815ac9bd46

Семинар 6 (17 октября).

Доклад Антона Гнатенко. https://www.labri.fr/perso/igw/Papers/igw-mu.pdf

Семинар 7 (31 октября).

Эффективное решение задачи SAT для КНФ маленькой ширины. http://www.frontiersinai.com/ecai/ecai2004/ecai04/pdf/p0161.pdf

Семинар 8 (7 ноября).

Доклад Андрея Фёдорова.

Семинар 9 (14 ноября).

Доклад Виктора.

https://cp-algorithms.com/data_structures/fenwick.html

Семинар 10 (5 декабря).

О задаче QBF для КНФ маленькой ширины http://www.frontiersinai.com/ecai/ecai2004/ecai04/pdf/p0161.pdf

Семинар 11 (12 декабря).

Доклад Анастасии Чистопольской. https://drive.google.com/file/d/1Q1QDsA5esACcKIliTEcoXgxQjHqJvivv/view?usp=sharing

Семинар 12 (21 января).

Введение в Grain-Fine complexity http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf

Семинар 13 (28 января).

Введение в Grain-Fine complexity (продолжение) http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf

Семинар 14 (11 февраля).

Доклад Азата https://e-maxx.ru/algo/tutte_matrix http://m.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mp&paperid=170&option_lang=rus

Семинар 14 (19 февраля).

Доклад Павла Захарова

https://drive.google.com/file/d/1B6m9V77a0BvnhgzL8YWkMPJlA_ya_ucL/view?usp=sharing

Семинар 15 (26 февраля).

Доклад Антона Гнатенко

https://drive.google.com/file/d/1Gf_CQocvKgGAtce3mLSSbkX6CofJCqLA/view?usp=sharing

Семинар 16 (11 марта).

Доклад Антона Гнатенко.

https://drive.google.com/file/d/1Gf_CQocvKgGAtce3mLSSbkX6CofJCqLA/view?usp=sharing

Семинар 17 (25 марта).

Введение в алгоритмическую статистику. https://www.mccme.ru/free-books/shen/kolmbook.pdf

Семинар 18 (8 апреля).

Доклад Никиты Лукьяненко. https://drive.google.com/file/d/1ePSO5PWdA-qTivHu3hrYfE42SOyzIgUV/view?usp=sharing

Семинар 19 (15 апреля).

Доклад Никиты Лукьяненко. https://drive.google.com/file/d/1ePSO5PWdA-qTivHu3hrYfE42SOyzIgUV/view?usp=sharing

Семинар 20 (22 апреля).

Доклад Никиты Лукьяненко. https://cstheory.stackexchange.com/questions/44382/a-game-on-several-graphs/46571#46571

Семинар 21 (29 апреля).

Доклад Андрея Фёдорова. https://www.cs.cornell.edu/courses/cs4820/2014sp/notes/maxcoverage.pdf

Семинар 21 (5 мая).

Доклад Антона Гнатенко.

https://www.sciencedirect.com/science/article/pii/S0019995883800047

Семинар 22 (12 мая).

Доклад Антона Гнатенко.

https://www.sciencedirect.com/science/article/pii/S0019995886800092

Семинар 23 (19 мая).

Доклад Максима Голядкина.

Семинар 23 (26 мая).

Доклад Азата. https://arxiv.org/pdf/1602.08254.pdf

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

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