Дискретная математика и математическая кибернетика — различия между версиями
(→2014-2015 учебный год) |
|||
(не показаны 29 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
Научно-исследовательский семинар для преподавателей, научных сотрудников, аспирантов и студентов. | Научно-исследовательский семинар для преподавателей, научных сотрудников, аспирантов и студентов. | ||
− | + | В 2020-2021 уч.г. семинар проходит по пятницам (по объявлениям) с 16-30 до 18-00 онлайн с помощью zoom. | |
− | + | ||
− | + | ||
== Расписание докладов == | == Расписание докладов == | ||
+ | |||
+ | ===2020-2021 учебный год=== | ||
+ | |||
+ | {| class="wide" width="100%" | ||
+ | ! Дата | ||
+ | ! Тема доклада | ||
+ | ! Докладчик | ||
+ | |- | ||
+ | | 6 ноября 2020 | ||
+ | | '''О возможностях построения легкотестируемых контактных схем и схем из функциональных элементов'''. | ||
+ | Аннотация доклада. Исследованы задачи реализации булевых функций контактными схемами и схемами из функциональных элементов, допускающими короткие проверяющие либо диагностические тесты относительно неисправностей заранее оговоренного вида, которые могут происходить в схемах. Указанные задачи были впервые предложены (применительно к контактным схемам) С.В. Яблонским | ||
+ | и И.А. Чегис в середине 1950-х годов и изучались многими авторами. Рассмотрены следующие виды неисправностей: обрывы и/или замыкания контактов, константные (однотипные или произвольные) либо инверсные неисправности на входах и/или выходах функциональных элементов. Число допустимых неисправностей в схемах может быть ограничено сверху единицей или заданным натуральным числом либо никак не ограничено. Получен ряд верхних и/или нижних оценок длин минимальных тестов для схем, реализующих заданные, все или почти все булевы функции, при различных исходных условиях. Во многих случаях найдены точные значения этих длин и/или улучшены известные ранее результаты. | ||
+ | | '''Попков К.А.''' (Институт прикладной математики им. М.В. Келдыша РАН) | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | ===2019-2020 учебный год=== | ||
+ | |||
+ | {| class="wide" width="100%" | ||
+ | ! Дата | ||
+ | ! Тема доклада | ||
+ | ! Докладчик | ||
+ | |- | ||
+ | |6 марта 2020 г. | ||
+ | |'''Некоторые вопросы синтеза параллельных схем'''. | ||
+ | Аннотация доклада. В докладе представлены результаты автора в областях минимизации глубины схем и формул, оптимального синтеза при ограничении на глубину, разработки быстрых параллельных алгоритмов. В частности, рассказывается о методах синтеза формул для симметрических булевых функций, асимптотически оптимальном синтезе линейных схем ограниченной | ||
+ | глубины, экстремальных отношениях линейных мер сложности булевых матриц, синтезе минимальных параллельных префиксных схем, асимптотически оптимальном синтезе схем и формул ограниченной глубины из многовходовых элементов, алгоритмах быстрого преобразования Фурье над некоторыми | ||
+ | кольцами и их приложениях. | ||
+ | | Сергеев И.С. (ФГУП "Квант"; МГУ имени М.В. Ломоносова) | ||
+ | |- | ||
+ | |29 ноября 2019 г. | ||
+ | |'''Нижние оценки на схемную сложность: открытые задачи'''. | ||
+ | Аннотация доклада. Чтобы доказать, что классы сложности P и NP не совпадают, достаточно доказать суперполиномиальную нижнюю оценку на булеву сложность какой-нибудь функции из класса NP. На данный момент мы очень далеки от этой цели: мы не умеем доказывать даже нижнюю оценку 4n. Ещё более печально то, что и методов доказательства нижних оценок на схемную сложность известно мало. В докладе мы рассмотрим несколько подходов, | ||
+ | которые потенциально могут привести к усилению известных нижних оценок на сложность схем без ограничений (на глубину, базис или исходящую степень). | ||
+ | | Куликов А.С. (Санкт-Петербургский государственный университет) | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | ===2017-2018 учебный год=== | ||
+ | |||
+ | {| class="wide" width="100%" | ||
+ | ! Дата | ||
+ | ! Тема доклада | ||
+ | ! Докладчик | ||
+ | |- | ||
+ | | 22 ноября 2017 г. | ||
+ | | Упаковки и покрытия путей в графах и кёниговы графы [[Media: mokeev-22-11-17.docx|аннотация доклада]] | ||
+ | | Мокеев Д.Б. (ННГУ им. Н.И. Лобачевского) | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | ===2015-2016 учебный год=== | ||
+ | |||
+ | {| class="wide" width="100%" | ||
+ | ! Дата | ||
+ | ! Тема доклада | ||
+ | ! Докладчик | ||
+ | |- | ||
+ | | 30 октября 2015 г. | ||
+ | | Кибернетический подход к моделированию и изучению конфликтных систем обслуживания | ||
+ | | Зорин А.В. (ННГУ им. Н.И. Лобачевского) | ||
+ | |- | ||
+ | | 23 октября 2015 г. (в 16-20) | ||
+ | | New bounds on Klarner's constant | ||
+ | | Gill Barequet (университет Технион, Израиль) | ||
+ | |- | ||
+ | |} | ||
===2014-2015 учебный год=== | ===2014-2015 учебный год=== | ||
Строка 12: | Строка 77: | ||
! Тема доклада | ! Тема доклада | ||
! Докладчик | ! Докладчик | ||
+ | |- | ||
+ | |27 марта 2015 г. | ||
+ | | Методы синтеза и оценки сложности схем с некоторыми структурными ограничениями [[Media:Konovodov_27_03.pdf|аннотация доклада]] | ||
+ | | Коноводов В. А. (МГУ имени М.В. Ломоносова, ф-т ВМК) | ||
+ | |- | ||
+ | | 13 февраля 2015 г. | ||
+ | | Об оценках функций Шеннона длин тестов при некоторых неисправностях входов схем | ||
+ | | Морозов Е.В. (МГУ имени М.В. Ломоносова, ф-т ВМК) | ||
+ | |- | ||
+ | | 28 ноября 2014 г. | ||
+ | | Применение произведения Адамара степенных рядов в комбинаторных и вероятностных задачах | ||
+ | | Потехина Е.А. (Череповецкий государственный университет) | ||
+ | |- | ||
+ | | 14 ноября 2014 г. | ||
+ | | Вентильная сложность обратимых схем как мера сложности четных подстановок | ||
+ | | Закаблукова Д.В. (МГТУ им. Н.Э. Баумана) | ||
|- | |- | ||
| 17 октября 2014 г. | | 17 октября 2014 г. | ||
− | | Идеальные языки и синхронизируемые автоматы [[Media: maslennikova-m-i.pdf| | + | | Идеальные языки и синхронизируемые автоматы ([[Media: maslennikova-m-i.pdf|аннотация доклада]]) |
| Масленникова М.И. (Уральский федеральный университет) | | Масленникова М.И. (Уральский федеральный университет) | ||
|- | |- | ||
Строка 82: | Строка 163: | ||
== Руководители == | == Руководители == | ||
− | |||
− | |||
* [[Ложкин Сергей Андреевич]] | * [[Ложкин Сергей Андреевич]] | ||
+ | * [[Алексеев Валерий Борисович]] | ||
+ | |||
[[Категория:Спецсеминары кафедры математической кибернетики]] | [[Категория:Спецсеминары кафедры математической кибернетики]] |
Текущая версия на 20:58, 1 ноября 2020
Научно-исследовательский семинар для преподавателей, научных сотрудников, аспирантов и студентов. В 2020-2021 уч.г. семинар проходит по пятницам (по объявлениям) с 16-30 до 18-00 онлайн с помощью zoom.
Содержание
Расписание докладов
2020-2021 учебный год
Дата | Тема доклада | Докладчик |
---|---|---|
6 ноября 2020 | О возможностях построения легкотестируемых контактных схем и схем из функциональных элементов.
Аннотация доклада. Исследованы задачи реализации булевых функций контактными схемами и схемами из функциональных элементов, допускающими короткие проверяющие либо диагностические тесты относительно неисправностей заранее оговоренного вида, которые могут происходить в схемах. Указанные задачи были впервые предложены (применительно к контактным схемам) С.В. Яблонским и И.А. Чегис в середине 1950-х годов и изучались многими авторами. Рассмотрены следующие виды неисправностей: обрывы и/или замыкания контактов, константные (однотипные или произвольные) либо инверсные неисправности на входах и/или выходах функциональных элементов. Число допустимых неисправностей в схемах может быть ограничено сверху единицей или заданным натуральным числом либо никак не ограничено. Получен ряд верхних и/или нижних оценок длин минимальных тестов для схем, реализующих заданные, все или почти все булевы функции, при различных исходных условиях. Во многих случаях найдены точные значения этих длин и/или улучшены известные ранее результаты. |
Попков К.А. (Институт прикладной математики им. М.В. Келдыша РАН) |
2019-2020 учебный год
Дата | Тема доклада | Докладчик |
---|---|---|
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 г. | Некоторые методы ресурсного анализа сетей Петри | Башкин В.А. (Ярославский государственный университет) |