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

Текущая версия на 23:22, 13 июня 2020

Содержание

1 Правила оценивания
2 Проведённые семинары
3 Предлагаемые статьи для рассказа на семинаре
4 Преподаватели

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

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

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

Семинар 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

@@ Строка 1: / Строка 1: @@
-==Расписание==
+==Правила оценивания==
-Семинар проходить по четвергам с 18.10 по 19.30
+Итоговая оценка (О_и) получается из оценки за семестр (О_с) и оценки за экзамен (О_э) по следующей формуле
+O_и = 0,6 * О_с + 0,4 * О_э. Далее полученное число округляется по обычным правилам.
+Оценка за семестр ставится за сделанные доклады, посещение и работу на семинарах.
+На экзамене студенту нужно рассказать о любых (кроме сделанных самим студентом)  3-k докладах, где k --- количество сделанных студентом докладов.
+[https://docs.google.com/spreadsheets/d/17-UEyEEubKVfwzXpf_tIDQ5LWFDfJyrJnDaT0ZsCF3A/edit?usp=sharing Текущие оценки]
 ==Проведённые семинары ==
@@ Строка 7: / Строка 15: @@
 ====Семинар 1 (12 сентября).  ====
-Задача равенства нулю многочлена. Лемма Шварца-Зиппеля.
+Задача равенства нулю многочлена. Лемма Шварца-Зиппеля. https://eccc.weizmann.ac.il//report/2009/101/
@@ Строка 14: / Строка 22: @@
 Применение задачи равенства нулю многочлена для решения задачи о паросочетаниях.
 Дерандомизация задачи о равенстве нулю многочлена для случая небольшого числа
-ненулевых мономов.
+ненулевых мономов. 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 октября).  ====
@@ Строка 30: / Строка 39: @@
 Конечные автоматы, задающие преобразования потоков входных сигналов в последовательности элементарных действий, являются простейшей моделью вычислений, пригодной для описания поведения реагирующих систем. Это поведение проявляется в соответствии между потоком входных сигналов и последовательностью элементарных действий, выполняемых системой. Для формальной спецификации и верификации реагирующих систем такого рода требуются более сложные и выразительные средства спецификации, нежели традиционные темпоральные логики. В докладе будет предложена расширенная темпоральная логика 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 ноября).  ====
@@ Строка 42: / Строка 54: @@
 ====Семинар 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
 ==Предлагаемые статьи для рассказа на семинаре==

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

Текущая версия на 23:22, 13 июня 2020

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Преподаватели

Навигация

Поиск