Дискретная математика и математическая кибернетика — различия между версиями
Материал из Кафедра математической кибернетики
(→2017-2018 учебный год) |
(→Расписание докладов) |
||
| Строка 5: | Строка 5: | ||
== Расписание докладов == | == Расписание докладов == | ||
| + | |||
| + | ===2019-2020 учебный год=== | ||
| + | |||
| + | {| class="wide" width="100%" | ||
| + | ! Дата | ||
| + | ! Тема доклада | ||
| + | ! Докладчик | ||
| + | |- | ||
| + | 29 ноября 2019 г. | ||
| + | |'''Нижние оценки на схемную сложность: открытые задачи'''. | ||
| + | Аннотация доклада. Чтобы доказать, что классы сложности P и NP не совпадают, достаточно доказать суперполиномиальную нижнюю оценку на булеву сложность какой-нибудь функции из класса NP. На данный момент мы очень далеки от этой цели: мы не умеем доказывать даже нижнюю оценку 4n. Ещё более печально то, что и методов доказательства нижних оценок на схемную сложность известно мало. В докладе мы рассмотрим несколько подходов, | ||
| + | которые потенциально могут привести к усилению известных нижних оценок на сложность схем без ограничений (на глубину, базис или исходящую степень). | ||
| + | | Куликов А.С. (Санкт-Петербургский государственный университет) | ||
| + | |- | ||
| + | }} | ||
===2017-2018 учебный год=== | ===2017-2018 учебный год=== | ||
Версия 14:28, 27 ноября 2019
Научно-исследовательский семинар для преподавателей, научных сотрудников, аспирантов и студентов. В 2016-2017 уч.г. семинар проходит по средам (по объявлениям) с 15:30 до 17:00 в ауд. 582.
Присутствие аспирантов кафедры математической кибернетики обязательно.
Содержание
Расписание докладов
2019-2020 учебный год
| Дата | Тема доклада | Докладчик |
|---|---|---|
| Нижние оценки на схемную сложность: открытые задачи.
Аннотация доклада. Чтобы доказать, что классы сложности P и NP не совпадают, достаточно доказать суперполиномиальную нижнюю оценку на булеву сложность какой-нибудь функции из класса NP. На данный момент мы очень далеки от этой цели: мы не умеем доказывать даже нижнюю оценку 4n. Ещё более печально то, что и методов доказательства нижних оценок на схемную сложность известно мало. В докладе мы рассмотрим несколько подходов, которые потенциально могут привести к усилению известных нижних оценок на сложность схем без ограничений (на глубину, базис или исходящую степень). |
Куликов А.С. (Санкт-Петербургский государственный университет) |
| Дата | Тема доклада | Докладчик |
|---|---|---|
| 22 ноября 2017 г. | Упаковки и покрытия путей в графах и кёниговы графы аннотация доклада | Мокеев Д.Б. (ННГУ им. Н.И. Лобачевского) |
2015-2016 учебный год
| Дата | Тема доклада | Докладчик |
|---|---|---|
| 30 октября 2015 г. | Кибернетический подход к моделированию и изучению конфликтных систем обслуживания | Зорин А.В. (ННГУ им. Н.И. Лобачевского) |
| 23 октября 2015 г. (в 16-20) | New bounds on Klarner's constant | Gill Barequet (университет Технион, Израиль) |
2014-2015 учебный год
| Дата | Тема доклада | Докладчик |
|---|---|---|
| 27 марта 2015 г. | Методы синтеза и оценки сложности схем с некоторыми структурными ограничениями аннотация доклада | Коноводов В. А. (МГУ имени М.В. Ломоносова, ф-т ВМК) |
| 13 февраля 2015 г. | Об оценках функций Шеннона длин тестов при некоторых неисправностях входов схем | Морозов Е.В. (МГУ имени М.В. Ломоносова, ф-т ВМК) |
| 28 ноября 2014 г. | Применение произведения Адамара степенных рядов в комбинаторных и вероятностных задачах | Потехина Е.А. (Череповецкий государственный университет) |
| 14 ноября 2014 г. | Вентильная сложность обратимых схем как мера сложности четных подстановок | Закаблукова Д.В. (МГТУ им. Н.Э. Баумана) |
| 17 октября 2014 г. | Идеальные языки и синхронизируемые автоматы (аннотация доклада) | Масленникова М.И. (Уральский федеральный университет) |
| 3 октября 2014 г. | Асимптотически наилучшие методы синтеза схем из функциональных элементов
в некоторых моделях глубины и задержки |
Данилов Б.Р. (ф-т ВМК МГУ имени М.В. Ломоносова) |
2013-2014 учебный год
| Дата | Тема доклада | Докладчик |
|---|---|---|
| 23 мая 2014 г. | О тестах при некоторых неисправностях на входах схем | Антюфеев Г.В. (ф-т ВМК МГУ имени М.В.Ломоносова) |
| 16 мая 2014 г. | Экстремальные свойства графов расстояний | Рубанов О.И. (мех-мат ф-т МГУ имени М.В.Ломоносова) |
| 25 апреля 2014 г. | Быстрые алгоритмы проверки эквивалентности программ в моделях с полугрупповой семантикой | Подымов В.В. (ф-т ВМК МГУ имени М.В.Ломоносова) |
| 11 апреля 2014 г. | Эквивалентность и эквивалентные преобразования в перегородчатых моделях программ | Молчанов А.Э. (ф-т ВМК МГУ имени М.В.Ломоносова) |
| 28 марта 2014 г. | Синтез надежных схем, реализующих функции трехзначной логики | Алехина М.А. (Пензенский государственный университет) |
| 14 марта 2014 г. | Методы получения оценок билинейной сложности матричных тензоров малого ранга | Трефилов А.П. (ф-т ВМК МГУ имени М.В. Ломоносова) |
| 28 февраля 2014 г. | Оператор FE-замыкания на множестве функций счетнозначной логики | Сенилова И.С. (ф-т ВМК МГУ имени М.В. Ломоносова) |
| 14 февраля 2014 г. | Адаптивная двухфазная схема решения задачи "структура-свойство" | Прохоров Е.И. (мех-мат ф-т МГУ имени М.В. Ломоносова) |
| 7 февраля 2014 г. | Проблемы Борсука и Нелсона-Хадвигера в рациональных пространствах | Пономаренко Е.И. (МФТИ) |
| 6 декабря 2013 г. | О свойствах некоторых линейных преобразований дискретных функций | Мазуров А.А. (ф-т ВМК МГУ имени М.В. Ломоносова) |
| 22 ноября 2013 г. | Некоторые методы ресурсного анализа сетей Петри | Башкин В.А. (Ярославский государственный университет) |
