Project Seminar 2019 2020

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Расписание

Семинар проходить по четвергам с 18.10 по 19.30

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

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

Задача равенства нулю многочлена. Лемма Шварца-Зиппеля.


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

Применение задачи равенства нулю многочлена для решения задачи о паросочетаниях. Дерандомизация задачи о равенстве нулю многочлена для случая небольшого числа ненулевых мономов.

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

Дерандомизация задачи о равенстве нулю многочлена с помощью теорем типа Сильвестра-Галлаи.

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

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

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

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

Анонс:


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

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

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

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

Эффективное решение задачи SAT для КНФ маленькой ширины.

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

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

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

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

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

О задаче QBF для КНФ маленькой ширины

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

Доклад Анастасии Чистопольской.

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

Введение в Grain-Fine complexity

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

Введение в Grain-Fine complexity (продолжение)

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

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