Дискретная математика и математическая кибернетика

Научно-исследовательский семинар для преподавателей, научных сотрудников, аспирантов и студентов. В 2019-2020 уч.г. семинар проходит по пятницам (по объявлениям) с 16-30 до 18-00 в ауд. 612.

Расписание докладов

2020-2021 учебный год

}

2019-2020 учебный год

Дата	Тема доклада	Докладчик
6 ноября 2020	О возможностях построения легкотестируемых контактных схем и схем из функциональных элементов. Аннотация. Исследованы задачи реализации булевых функций контактными схемами и схемами из функциональных элементов, допускающими короткие проверяющие либо диагностические тесты относительно неисправностей заранее оговоренного вида, которые могут происходить в схемах. Указанные задачи были впервые предложены (применительно к контактным схемам) С.В. Яблонским и И.А. Чегис в середине 1950-х годов и изучались многими авторами. Рассмотрены следующие виды неисправностей: обрывы и/или замыкания контактов, константные (однотипные или произвольные) либо инверсные неисправности на входах и/или выходах функциональных элементов. Число допустимых неисправностей в схемах может быть ограничено сверху единицей или заданным натуральным числом либо никак не ограничено. Получен ряд верхних и/или нижних оценок длин минимальных тестов для схем, реализующих заданные, все или почти все булевы функции, при различных исходных условиях. Во многих случаях найдены точные значения этих длин и/или улучшены известные ранее результаты.	Попков К.А. (Институт прикладной математики им. М.В. Келдыша РАН)

Дата	Тема доклада	Докладчик
6 марта 2020 г.	Некоторые вопросы синтеза параллельных схем. Аннотация доклада. В докладе представлены результаты автора в областях минимизации глубины схем и формул, оптимального синтеза при ограничении на глубину, разработки быстрых параллельных алгоритмов. В частности, рассказывается о методах синтеза формул для симметрических булевых функций, асимптотически оптимальном синтезе линейных схем ограниченной глубины, экстремальных отношениях линейных мер сложности булевых матриц, синтезе минимальных параллельных префиксных схем, асимптотически оптимальном синтезе схем и формул ограниченной глубины из многовходовых элементов, алгоритмах быстрого преобразования Фурье над некоторыми кольцами и их приложениях.	Сергеев И.С. (ФГУП "Квант"; МГУ имени М.В. Ломоносова)
29 ноября 2019 г.	Нижние оценки на схемную сложность: открытые задачи. Аннотация доклада. Чтобы доказать, что классы сложности P и NP не совпадают, достаточно доказать суперполиномиальную нижнюю оценку на булеву сложность какой-нибудь функции из класса NP. На данный момент мы очень далеки от этой цели: мы не умеем доказывать даже нижнюю оценку 4n. Ещё более печально то, что и методов доказательства нижних оценок на схемную сложность известно мало. В докладе мы рассмотрим несколько подходов, которые потенциально могут привести к усилению известных нижних оценок на сложность схем без ограничений (на глубину, базис или исходящую степень).	Куликов А.С. (Санкт-Петербургский государственный университет)

2017-2018 учебный год

Дата	Тема доклада	Докладчик
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 г.	Некоторые методы ресурсного анализа сетей Петри	Башкин В.А. (Ярославский государственный университет)

Архив расписания

Руководители

• Ложкин Сергей Андреевич
• Алексеев Валерий Борисович