https://www.wikicshse.ru/index.php?action=history&feed=atom&title=Project_Seminar_2021_2022 2026-06-06T12:14:00Z История изменений этой страницы в вики MediaWiki 1.45.3 https://www.wikicshse.ru/index.php?title=Project_Seminar_2021_2022&diff=585&oldid=prev 2022-06-17T08:05:08Z

<p>Migrated current public revision from wiki.cs.hse.ru</p> <p><b>Новая страница</b></p><div>Во втором семестре семинар проходит по четвергам 16:20-17.40 в zoom: https://us02web.zoom.us/j/82449258784?pwd=ajBZa09jYVZGK05RQitxL2YxdStIZz09)<br /> <br /> Экзамен будет 21.06 в 10.00. Ссылка: https://us02web.zoom.us/j/84083320210?pwd=eGlZcG1Db003Wk8yL1dibzEvKzhkdz09<br /> <br /> Семинар проходит онлайн по пятницам 16.20-17.40 в Google meet: meet.google.com/koc-mbtj-ihc<br /> <br /> <br /> ==Правила оценивания==<br /> <br /> Итоговая оценка (О_и) получается из оценки за семестр (О_с) и оценки за экзамен (О_э) по следующей формуле<br /> <br /> O_и = 0,6 * О_с + 0,4 * О_э. Далее полученное число округляется по обычным правилам. <br /> <br /> <br /> ==Проведённые семинары ==<br /> <br /> ====Семинар 1 (10 сентября). ====<br /> <br /> https://drive.google.com/file/d/1KD0jCXeXVcCq2uK28x-oyyuA66QNDjSZ/view?usp=sharing<br /> <br /> ====Семинар 2 (17 сентября). ====<br /> <br /> https://drive.google.com/file/d/1SjuYTo96tePD5WCS2Atw0BxZM-0Eh6X5/view?usp=sharing<br /> <br /> <br /> ====Семинар 3 (24 сентября). ====<br /> <br /> https://drive.google.com/file/d/1MTJwD_gb9kM9WY75VS5pA--zQ5iTK53z/view?usp=sharing<br /> <br /> ====Семинар 4 (1 октября). ====<br /> <br /> https://drive.google.com/file/d/1rrh_Y2fUcd9oYrfETO55snxSShROnRkN/view?usp=sharing<br /> <br /> <br /> ====Семинар 5 (8 октября). ====<br /> <br /> <br /> https://drive.google.com/file/d/1MJbrciN6If2tSLOd3SBWv3L2_aJZJr_8/view?usp=sharing<br /> <br /> <br /> ====Семинар 6 (15 октября). ====<br /> https://drive.google.com/file/d/10cbkjsjVo4BvjGl6fo2XAGejDhHAGibP/view?usp=sharing<br /> <br /> ====Семинар 7 (12 ноября). ====<br /> https://drive.google.com/file/d/11whBhjxYG68R2CVSmoOvCMMTOK145ULW/view?usp=sharing<br /> <br /> ====Семинар 8 (19 ноября). ====<br /> https://drive.google.com/file/d/1BXF2lwV6S_yUwFlg1R1dwZd-t3dAQVSG/view?usp=sharing<br /> <br /> <br /> ====Семинар 9 (26 ноября). ====<br /> https://drive.google.com/file/d/1MXZWhfa27vkKJgEMIyIs1-hpj7QKZ03g/view?usp=sharing<br /> <br /> ====Семинар 10 (3 декабря). ====<br /> https://drive.google.com/file/d/1G6NBvW0lFV2LHwOrZIF65DEgZt9cs_T8/view?usp=sharing<br /> <br /> ====Семинар 11 (3 февраля). ====<br /> <br /> Доклад Анны Енгоян. Анонс:<br /> <br /> В теоретической информатике важной областью является анализ булевых функций. Сложность вычисления булевых функций можно измерять различными способами, один из распространенных – глубина разрешающих деревьев.<br /> Я расскажу основные соотношения между сложностными характеристиками булевых функций, а также обобщу полученные факты для анализа класса трехзначных функций.<br /> <br /> https://drive.google.com/file/d/1nMM7KcboMAt81fCSH8NZqBme3QWM-LVo/view?usp=sharing<br /> <br /> ====Семинар 12 (17 марта). ====<br /> <br /> https://drive.google.com/file/d/1-WaDsNRbk2k7bcGp-wMhppoZUft1fIb7/view?usp=sharing<br /> <br /> Доклад Григория Резникова.<br /> <br /> Игры Карчмера-Вигдерсона.<br /> Получение нижних оценок на размеры булевых схем является в общем случае крайне сложной задачей, однако в некоторых моделях существуют достаточно универсальные методы их доказательства. Одной из таких техник являются игры Карчмера-Вигдерсона, позволяющие получать нижние оценки на формулы де Моргана (древовидные булевы схемы с гейтами AND и OR) при помощи оценок на коммуникационную сложность некоторых задач. Мы рассмотрим использование игр Карчмера-Вигдерсона на примере оценки Храпченко, а также поговорим о тесно связанной с играми Карчмера-Вигдерсона гипотезой Карчмера-Раза-Вигдерсона (KRW conjecture), имеющую важные следствия в схемной сложности.<br /> <br /> ====Семинар 13 (7 апреля). ====<br /> https://drive.google.com/file/d/19k5KVKTPudMLxIvfiHahaWsE0Fa3oKMq/view?usp=sharing<br /> <br /> ====Семинар 14 (26 мая). ====<br /> Доклад Ярослава Иванашева о кернелизации.<br /> https://drive.google.com/file/d/1RSDYWnDeZPgALWHFZZ0HZcuBieTOei6F/view?usp=sharing<br /> <br /> ====Семинар 15 (2 июня). ====<br /> Доклад Полины Долговой.<br /> Анонс:<br /> Существует некоторая связь между паросочетаниями в графах и определителями матриц.<br /> Особенно интересны матрицы Татта, весьма наглядно демонстрирующие эту связь.<br /> На семинаре мы обсудим алгоритмы по поиску максимального паросочетания, основанные на этих матрицах и PIT (polynomial identity testing).<br /> <br /> <br /> https://drive.google.com/file/d/12BZyn2E9cVMsT8bEkvXKmAkWHNIhDxpf/view?usp=sharing<br /> <br /> ====Семинар 16 (9 июня). ====<br /> Доклад Александра Левина. <br /> Временные автоматы и региональные графы.<br /> Одной из главных проблем при разработке сложной системы является проверка её корректности, например, достижимости определённого состояния. Но что делать, если у системы бесконечное число состояний? Тут на помощь приходят региональные графы.<br /> Мы рассмотрим устройство временных автоматов, графов регионов и зон и методы решения проблемы достижимости с их помощью.<br /> <br /> https://drive.google.com/file/d/1RSDYWnDeZPgALWHFZZ0HZcuBieTOei6F/view?usp=sharing<br /> <br /> ====Семинар 17 (16 июня). ====<br /> Доклад Юрия Шуклова о коммуникационной сложности.<br /> <br /> https://drive.google.com/file/d/1iGY5bnvsHsG4-AQkWTMZffXxmA1eaCz_/view?usp=sharing<br /> <br /> ==Преподаватели==<br /> Милованов Алексей, almas239@gmail.com, telegram: AlexeySMilovanov.<br /> <br /> ==Предлагаемые статьи для рассказа на семинаре==<br /> <br /> http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf</div>

imported>Milovanov