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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 61: Строка 61:
 
====Семинар 14 (19 февраля).  ====
 
====Семинар 14 (19 февраля).  ====
 
Доклад Павла Захарова
 
Доклад Павла Захарова
 +
 +
 +
====Семинар 15 (26 февраля).  ====
 +
Доклад Антона Гнатенко
 +
 +
====Семинар 16 (11 марта).  ====
 +
Доклад Антона Гнатенко.
  
 
==Предлагаемые статьи для рассказа на семинаре==
 
==Предлагаемые статьи для рассказа на семинаре==

Версия 01:14, 13 марта 2020

Расписание

Семинар проходить по четвергам с 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 (продолжение)


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

Доклад Азата

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

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


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

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

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

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

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

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