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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
Строка 97: Строка 97:
  
 
https://drive.google.com/file/d/1RSDYWnDeZPgALWHFZZ0HZcuBieTOei6F/view?usp=sharing
 
https://drive.google.com/file/d/1RSDYWnDeZPgALWHFZZ0HZcuBieTOei6F/view?usp=sharing
 +
 +
====Семинар 17 (16 июня).  ====
 +
Доклад Юрия Шуклова о коммуникационной сложности.
 +
 +
https://drive.google.com/file/d/1iGY5bnvsHsG4-AQkWTMZffXxmA1eaCz_/view?usp=sharing
  
 
==Преподаватели==
 
==Преподаватели==

Текущая версия на 11:05, 17 июня 2022

Во втором семестре семинар проходит по четвергам 16:20-17.40 в zoom: https://us02web.zoom.us/j/82449258784?pwd=ajBZa09jYVZGK05RQitxL2YxdStIZz09)

Экзамен будет 21.06 в 10.00. Ссылка: https://us02web.zoom.us/j/84083320210?pwd=eGlZcG1Db003Wk8yL1dibzEvKzhkdz09

Семинар проходит онлайн по пятницам 16.20-17.40 в Google meet: meet.google.com/koc-mbtj-ihc


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

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

O_и = 0,6 * О_с + 0,4 * О_э. Далее полученное число округляется по обычным правилам.


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

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

https://drive.google.com/file/d/1KD0jCXeXVcCq2uK28x-oyyuA66QNDjSZ/view?usp=sharing

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

https://drive.google.com/file/d/1SjuYTo96tePD5WCS2Atw0BxZM-0Eh6X5/view?usp=sharing


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

https://drive.google.com/file/d/1MTJwD_gb9kM9WY75VS5pA--zQ5iTK53z/view?usp=sharing

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

https://drive.google.com/file/d/1rrh_Y2fUcd9oYrfETO55snxSShROnRkN/view?usp=sharing


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

https://drive.google.com/file/d/1MJbrciN6If2tSLOd3SBWv3L2_aJZJr_8/view?usp=sharing


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

https://drive.google.com/file/d/10cbkjsjVo4BvjGl6fo2XAGejDhHAGibP/view?usp=sharing

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

https://drive.google.com/file/d/11whBhjxYG68R2CVSmoOvCMMTOK145ULW/view?usp=sharing

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

https://drive.google.com/file/d/1BXF2lwV6S_yUwFlg1R1dwZd-t3dAQVSG/view?usp=sharing


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

https://drive.google.com/file/d/1MXZWhfa27vkKJgEMIyIs1-hpj7QKZ03g/view?usp=sharing

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

https://drive.google.com/file/d/1G6NBvW0lFV2LHwOrZIF65DEgZt9cs_T8/view?usp=sharing

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

Доклад Анны Енгоян. Анонс:

В теоретической информатике важной областью является анализ булевых функций. Сложность вычисления булевых функций можно измерять различными способами, один из распространенных – глубина разрешающих деревьев. Я расскажу основные соотношения между сложностными характеристиками булевых функций, а также обобщу полученные факты для анализа класса трехзначных функций.

https://drive.google.com/file/d/1nMM7KcboMAt81fCSH8NZqBme3QWM-LVo/view?usp=sharing

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

https://drive.google.com/file/d/1-WaDsNRbk2k7bcGp-wMhppoZUft1fIb7/view?usp=sharing

Доклад Григория Резникова.

Игры Карчмера-Вигдерсона. Получение нижних оценок на размеры булевых схем является в общем случае крайне сложной задачей, однако в некоторых моделях существуют достаточно универсальные методы их доказательства. Одной из таких техник являются игры Карчмера-Вигдерсона, позволяющие получать нижние оценки на формулы де Моргана (древовидные булевы схемы с гейтами AND и OR) при помощи оценок на коммуникационную сложность некоторых задач. Мы рассмотрим использование игр Карчмера-Вигдерсона на примере оценки Храпченко, а также поговорим о тесно связанной с играми Карчмера-Вигдерсона гипотезой Карчмера-Раза-Вигдерсона (KRW conjecture), имеющую важные следствия в схемной сложности.

Семинар 13 (7 апреля).

https://drive.google.com/file/d/19k5KVKTPudMLxIvfiHahaWsE0Fa3oKMq/view?usp=sharing

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

Доклад Ярослава Иванашева о кернелизации. https://drive.google.com/file/d/1RSDYWnDeZPgALWHFZZ0HZcuBieTOei6F/view?usp=sharing

Семинар 15 (2 июня).

Доклад Полины Долговой. Анонс: Существует некоторая связь между паросочетаниями в графах и определителями матриц. Особенно интересны матрицы Татта, весьма наглядно демонстрирующие эту связь. На семинаре мы обсудим алгоритмы по поиску максимального паросочетания, основанные на этих матрицах и PIT (polynomial identity testing).


https://drive.google.com/file/d/12BZyn2E9cVMsT8bEkvXKmAkWHNIhDxpf/view?usp=sharing

Семинар 16 (9 июня).

Доклад Александра Левина. Временные автоматы и региональные графы. Одной из главных проблем при разработке сложной системы является проверка её корректности, например, достижимости определённого состояния. Но что делать, если у системы бесконечное число состояний? Тут на помощь приходят региональные графы. Мы рассмотрим устройство временных автоматов, графов регионов и зон и методы решения проблемы достижимости с их помощью.

https://drive.google.com/file/d/1RSDYWnDeZPgALWHFZZ0HZcuBieTOei6F/view?usp=sharing

Семинар 17 (16 июня).

Доклад Юрия Шуклова о коммуникационной сложности.

https://drive.google.com/file/d/1iGY5bnvsHsG4-AQkWTMZffXxmA1eaCz_/view?usp=sharing

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

Милованов Алексей, almas239@gmail.com, telegram: AlexeySMilovanov.

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

http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf