Дискретная математика и математическая кибернетика — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
 
(не показаны 45 промежуточные версии 2 участников)
Строка 1: Строка 1:
 
Научно-исследовательский семинар для преподавателей, научных сотрудников, аспирантов и студентов.  
 
Научно-исследовательский семинар для преподавателей, научных сотрудников, аспирантов и студентов.  
−
Семинар проходит по пятницам, раз в две недели, с 18:20 до 20:00 в ауд. 609.
+
В 2020-2021 уч.г. семинар проходит по пятницам (по объявлениям) с 16-30 до 18-00 онлайн с помощью zoom.
−
 
+
−
Присутствие аспирантов кафедры математической кибернетики обязательно.
+
  
 
== Расписание докладов ==
 
== Расписание докладов ==
 +
 +
===2020-2021 учебный год===
  
 
{| class="wide" width="100%"
 
{| class="wide" width="100%"
Строка 10: Строка 10:
 
! Тема доклада
 
! Тема доклада
 
! Докладчик
 
! Докладчик
 +
|-
 +
| 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 учебный год===
 +
 +
{| class="wide" width="100%"
 +
! Дата
 +
! Тема доклада
 +
! Докладчик
 +
|-
 +
|27 марта 2015 г.
 +
| Методы синтеза и оценки сложности схем с некоторыми структурными ограничениями [[Media:Konovodov_27_03.pdf|аннотация доклада]]
 +
| Коноводов В. А. (МГУ имени М.В. Ломоносова, ф-т ВМК)
 +
|-
 +
| 13 февраля 2015 г.
 +
| Об оценках функций Шеннона длин тестов при некоторых неисправностях входов схем
 +
| Морозов Е.В. (МГУ имени М.В. Ломоносова, ф-т ВМК)
 +
|-
 +
| 28 ноября 2014 г.
 +
| Применение произведения Адамара степенных рядов в комбинаторных и вероятностных задачах
 +
| Потехина Е.А. (Череповецкий государственный университет)
 +
|-
 +
| 14 ноября 2014 г.
 +
| Вентильная сложность обратимых схем как мера сложности четных подстановок
 +
| Закаблукова Д.В. (МГТУ им. Н.Э. Баумана)
 +
|-
 +
| 17 октября 2014 г.
 +
| Идеальные языки и синхронизируемые автоматы ([[Media: maslennikova-m-i.pdf|аннотация доклада]])
 +
| Масленникова М.И. (Уральский федеральный университет)
 +
|-
 +
| 3 октября 2014 г.
 +
| Асимптотически наилучшие методы синтеза схем из функциональных элементов
 +
в некоторых моделях глубины и задержки
 +
| Данилов Б.Р. (ф-т ВМК МГУ имени М.В. Ломоносова)
 +
|-
 +
|}
 +
 +
===2013-2014 учебный год===
 +
 +
{| class="wide" width="100%"
 +
! Дата
 +
! Тема доклада
 +
! Докладчик
 +
|-
 +
| 23 мая 2014 г.
 +
| О тестах при некоторых неисправностях на входах схем
 +
| Антюфеев Г.В. (ф-т ВМК МГУ имени М.В.Ломоносова)
 +
|-
 +
| 16 мая 2014 г.
 +
| Экстремальные свойства графов расстояний
 +
| Рубанов О.И. (мех-мат ф-т МГУ имени М.В.Ломоносова)
 +
|-
 +
| 25 апреля 2014 г.
 +
| Быстрые алгоритмы проверки эквивалентности программ в моделях с полугрупповой семантикой
 +
| Подымов В.В. (ф-т ВМК МГУ имени М.В.Ломоносова)
 +
|-
 +
| 11 апреля 2014 г.
 +
| Эквивалентность и эквивалентные преобразования в перегородчатых моделях программ
 +
| Молчанов А.Э. (ф-т ВМК МГУ имени М.В.Ломоносова)
 +
|-
 +
| 28 марта 2014 г.
 +
| Синтез надежных схем, реализующих функции трехзначной логики
 +
| Алехина М.А. (Пензенский государственный университет)
 +
|-
 +
| 14 марта 2014 г.
 +
| Методы получения оценок билинейной сложности матричных тензоров малого ранга
 +
| Трефилов А.П. (ф-т ВМК МГУ имени М.В. Ломоносова)
 +
|-
 +
| 28 февраля 2014 г.
 +
| Оператор FE-замыкания на множестве функций счетнозначной логики
 +
| Сенилова И.С. (ф-т ВМК МГУ имени М.В. Ломоносова)
 +
|-
 +
| 14 февраля 2014 г.
 +
| Адаптивная двухфазная схема решения задачи "структура-свойство"
 +
| Прохоров Е.И. (мех-мат ф-т МГУ имени М.В. Ломоносова)
 +
|-
 +
| 7 февраля 2014 г.
 +
| Проблемы Борсука и Нелсона-Хадвигера в рациональных пространствах
 +
| Пономаренко Е.И. (МФТИ)
 
|-
 
|-
 
| 6 декабря 2013 г.
 
| 6 декабря 2013 г.
Строка 26: Строка 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 г. Некоторые методы ресурсного анализа сетей Петри Башкин В.А. (Ярославский государственный университет)

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

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

Источник — «https://mk.cs.msu.ru/index.php?title=Дискретная_математика_и_математическая_кибернетика&oldid=7744»