https://www.wikicshse.ru/index.php?action=history&feed=atom&title=Project_Seminar_2019_2020 2026-06-06T14:43:13Z История изменений этой страницы в вики MediaWiki 1.45.3 https://www.wikicshse.ru/index.php?title=Project_Seminar_2019_2020&diff=583&oldid=prev 2020-06-13T20:22:16Z

<p>Migrated current public revision from wiki.cs.hse.ru</p> <p><b>Новая страница</b></p><div>==Правила оценивания==<br /> <br /> Итоговая оценка (О_и) получается из оценки за семестр (О_с) и оценки за экзамен (О_э) по следующей формуле<br /> <br /> O_и = 0,6 * О_с + 0,4 * О_э. Далее полученное число округляется по обычным правилам. <br /> <br /> Оценка за семестр ставится за сделанные доклады, посещение и работу на семинарах. <br /> <br /> На экзамене студенту нужно рассказать о любых (кроме сделанных самим студентом) 3-k докладах, где k --- количество сделанных студентом докладов.<br /> <br /> [https://docs.google.com/spreadsheets/d/17-UEyEEubKVfwzXpf_tIDQ5LWFDfJyrJnDaT0ZsCF3A/edit?usp=sharing Текущие оценки]<br /> <br /> ==Проведённые семинары ==<br /> <br /> ====Семинар 1 (12 сентября). ====<br /> <br /> Задача равенства нулю многочлена. Лемма Шварца-Зиппеля. https://eccc.weizmann.ac.il//report/2009/101/<br /> <br /> <br /> ====Семинар 2 (19 сентября). ====<br /> <br /> Применение задачи равенства нулю многочлена для решения задачи о паросочетаниях. <br /> Дерандомизация задачи о равенстве нулю многочлена для случая небольшого числа<br /> ненулевых мономов. https://eccc.weizmann.ac.il//report/2009/101/<br /> <br /> ====Семинар 3 (26 сентября). ====<br /> Дерандомизация задачи о равенстве нулю многочлена с помощью теорем типа<br /> Сильвестра-Галлаи. https://eccc.weizmann.ac.il//report/2009/101/<br /> <br /> ====Семинар 4 (3 октября). ====<br /> Доклад Антона Гнатенко<br /> https://www.semanticscholar.org/paper/Principles-of-model-checking-Baier-Katoen/2bbf4707b8555fd001b1d3248ca0b9815ac9bd46<br /> <br /> ====Семинар 5 (10 октября). ====<br /> Доклад Антона Гнатенко.<br /> <br /> Анонс: <br /> <br /> <br /> Конечные автоматы, задающие преобразования потоков входных сигналов в последовательности элементарных действий, являются простейшей моделью вычислений, пригодной для описания поведения реагирующих систем. Это поведение проявляется в соответствии между потоком входных сигналов и последовательностью элементарных действий, выполняемых системой. Для формальной спецификации и верификации реагирующих систем такого рода требуются более сложные и выразительные средства спецификации, нежели традиционные темпоральные логики. В докладе будет предложена расширенная темпоральная логика Reg-CTL*, в которой темпоральные операторы параметризованы регулярными выражениями. Мы рассмотрим алгоритмы верификации автоматов-преобразователей относительно формул некоторых фраментов этой логики, а также её выразительные возможности. На правах &quot;work in progress&quot; будет изложена идея алгоритма верифкации относительно произвольных формул Reg-CTL*.<br /> <br /> https://www.semanticscholar.org/paper/Principles-of-model-checking-Baier-Katoen/2bbf4707b8555fd001b1d3248ca0b9815ac9bd46<br /> <br /> ====Семинар 6 (17 октября). ====<br /> Доклад Антона Гнатенко. https://www.labri.fr/perso/igw/Papers/igw-mu.pdf<br /> <br /> ====Семинар 7 (31 октября). ====<br /> Эффективное решение задачи SAT для КНФ маленькой ширины.<br /> http://www.frontiersinai.com/ecai/ecai2004/ecai04/pdf/p0161.pdf<br /> <br /> ====Семинар 8 (7 ноября). ====<br /> Доклад Андрея Фёдорова.<br /> <br /> ====Семинар 9 (14 ноября). ====<br /> Доклад Виктора.<br /> <br /> https://cp-algorithms.com/data_structures/fenwick.html<br /> <br /> ====Семинар 10 (5 декабря). ====<br /> О задаче QBF для КНФ маленькой ширины<br /> http://www.frontiersinai.com/ecai/ecai2004/ecai04/pdf/p0161.pdf<br /> <br /> ====Семинар 11 (12 декабря). ====<br /> Доклад Анастасии Чистопольской. https://drive.google.com/file/d/1Q1QDsA5esACcKIliTEcoXgxQjHqJvivv/view?usp=sharing<br /> <br /> ====Семинар 12 (21 января). ====<br /> Введение в Grain-Fine complexity<br /> http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf<br /> <br /> ====Семинар 13 (28 января). ====<br /> Введение в Grain-Fine complexity (продолжение)<br /> http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf<br /> <br /> ====Семинар 14 (11 февраля). ====<br /> Доклад Азата<br /> https://e-maxx.ru/algo/tutte_matrix<br /> http://m.mathnet.ru/php/archive.phtml?wshow=paper&amp;jrnid=mp&amp;paperid=170&amp;option_lang=rus<br /> <br /> ====Семинар 14 (19 февраля). ====<br /> Доклад Павла Захарова<br /> <br /> https://drive.google.com/file/d/1B6m9V77a0BvnhgzL8YWkMPJlA_ya_ucL/view?usp=sharing<br /> <br /> ====Семинар 15 (26 февраля). ====<br /> Доклад Антона Гнатенко<br /> <br /> https://drive.google.com/file/d/1Gf_CQocvKgGAtce3mLSSbkX6CofJCqLA/view?usp=sharing<br /> <br /> ====Семинар 16 (11 марта). ====<br /> Доклад Антона Гнатенко.<br /> <br /> https://drive.google.com/file/d/1Gf_CQocvKgGAtce3mLSSbkX6CofJCqLA/view?usp=sharing<br /> <br /> ====Семинар 17 (25 марта). ====<br /> Введение в алгоритмическую статистику.<br /> https://www.mccme.ru/free-books/shen/kolmbook.pdf<br /> <br /> ====Семинар 18 (8 апреля). ====<br /> Доклад Никиты Лукьяненко.<br /> https://drive.google.com/file/d/1ePSO5PWdA-qTivHu3hrYfE42SOyzIgUV/view?usp=sharing<br /> <br /> ====Семинар 19 (15 апреля). ====<br /> Доклад Никиты Лукьяненко.<br /> https://drive.google.com/file/d/1ePSO5PWdA-qTivHu3hrYfE42SOyzIgUV/view?usp=sharing<br /> <br /> ====Семинар 20 (22 апреля). ====<br /> Доклад Никиты Лукьяненко.<br /> https://cstheory.stackexchange.com/questions/44382/a-game-on-several-graphs/46571#46571<br /> <br /> ====Семинар 21 (29 апреля). ====<br /> Доклад Андрея Фёдорова.<br /> https://www.cs.cornell.edu/courses/cs4820/2014sp/notes/maxcoverage.pdf<br /> <br /> ====Семинар 21 (5 мая). ====<br /> Доклад Антона Гнатенко.<br /> <br /> https://www.sciencedirect.com/science/article/pii/S0019995883800047<br /> <br /> ====Семинар 22 (12 мая). ====<br /> Доклад Антона Гнатенко.<br /> <br /> https://www.sciencedirect.com/science/article/pii/S0019995886800092<br /> <br /> ====Семинар 23 (19 мая). ====<br /> Доклад Максима Голядкина.<br /> <br /> <br /> ====Семинар 23 (26 мая). ====<br /> Доклад Азата.<br /> https://arxiv.org/pdf/1602.08254.pdf<br /> <br /> ==Предлагаемые статьи для рассказа на семинаре==<br /> <br /> 1) Nitin Saxena, Progress on Polynomial Identity Testing<br /> https://eccc.weizmann.ac.il/report/2009/101/<br /> <br /> 2) Лекции Стэндфордского университета о PIT и совершенных паросочетаниях.<br /> https://cs.stanford.edu/~mpkim/notes/lec5.pdf<br /> <br /> ==Преподаватели==<br /> Милованов Алексей, almas239@gmail.com</div>

imported>Milovanov