Объявления

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Современное развитие искусственного интеллекта и машинного обучения значительно связано с прогрессом в области глубоких нейронных сетей (ГНС), которые черпают вдохновение в работе человеческого мозга. Эти сети добились выдающихся результатов в таких областях, как компьютерное зрение, обработка естественного языка, автономное вождение и других, что привело к революции в современных технологиях. Однако, несмотря на успех, проблема обобщающей способности ГНС, то есть их способность работать с новыми данными, остаётся важной и активно исследуемой. Обобщение зависит от множества факторов, включая архитектуру сети, методы обучения и свойства тренировочных данных.

В данной работе исследуется проблема обобщения в ГНС и предлагается новый метод её улучшения через механизм "градиентной маски", вдохновлённый биологическими принципами, в частности механизмом нейронного торможения. В рамках исследования разработаны два подхода к маскированию градиентов: первый основан на латеральном торможении, а второй реализован на уровне весов нейронной сети. Оба метода продемонстрировали значительное улучшение обобщающей способности ГНС.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Работа нацелена на изучение различных способов вычисления с частичным оракулом. В отличие от вычислений с тотальным оракулом различные модели вычислений с частичным оракулом порождают различные классы функций.

Даны три различных определения вычисления с частичным оракулом. Показана неэквивалентность этих трех подходов вычисления, а также то, что множества функций, вычислимых с частичным оракулом согласно этим определениям, строго вложены друг в друга.

Рассмотрены сводимости, порождаемые различными способами вычислений с частичным оракулом. Доказана импликация сводимостей, соответсвующих различным определениям вычислений с оракулом, и выявлена связь этих сводимостей с сводимостью по перечислению.

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

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

В докладе будет представлено содержание диссертации на соискание ученой степени кандидата физико-математических наук по специальности 1.2.3 -"Теоретическая информатика, кибернетика".

Схема из функциональных элементов реализует булеву функцию. На входах схемы возникают неисправности, которые влияют на аргументы реализуемой функции и могут приводить к тому, что схема начинает реализовывать отличную от исходной функцию. Подавая на входы схемы множество двоичных векторов и анализируя соответствующие значения реализуемой функции, выясняется, была ли неисправность на входах или нет. Такое множество двоичных векторов называется проверяющим тестом. Если же множество двоичных векторов позволяет конкретизировать неисправность, то оно называется диагностическим тестом. Естественным образом возникает задача поиска минимальных тестов для различных источников неисправностей, а также получения оценок функции Шеннона. Функция Шеннона отражает зависимость размера минимального теста самой труднотестируемой булевой функции от числа переменных этой функции. В диссертации получены результаты для константного источника неисправностей и его модификации. Константный источник неисправностей является исторически первым источником, исследуемым в теории тестов. Также в диссертации получены результаты для различных модификаций мультипликативных и сдвиговых неисправностей. Все исследуемые неисправности могут представлять практический интерес при разработке и тестировании микроэлектронных устройств.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

В докладе будут представлены результаты, полученные в рамках совместного научного проекта механико-математического, химического факультетов и факультета биоинженерии и биоинформатики МГУ, поддержанного грантом междисциплинарной научно-образовательной школы "Мозг, когнитивные системы, искусственный интеллект" МГУ. Будет рассказано о задаче поиска группы симметрии молекул, задаче поиска оптимального положения иона метала на поверхности молекулы, задаче предсказания отклонения дипольного момента молекулы, задаче предсказания константы устойчивости молекулярных комплексов металлов, задаче представления поверхностей макромолекул (белков и нуклеиновых кислот), задаче предсказания участков связываний белков, задаче синтеза белков, связывающихся с целевым белком.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Предложено новое понятие – автоматной системы, обобщающее все известные в дискретной математике вычислительные модели. Фактически, автоматная система – это произвольный конечный автомат, или группа автоматов, с (бесконечной) внешней памятью. Т.е. это автомат, преобразующий произвольное множество Х. Состояние такой модели в каждый момент времени задаётся парой (q,x), где q – состояние автомата в данный момент, а х – значение вычисляемого системой параметра в этот момент.

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

Рассмотрен случай, когда автоматная система распадается на некоторое количество более простых автоматных систем. Введены операции декомпозиции автоматной системы на компоненты и обратная операция объединения автоматных систем. Показано, что в результате произвольного сокращения траекторий автоматной системы, получается траектория, которая также может быть реализована некоей автоматной системой.

На множестве автоматных (вычислительных) систем введены несколько отношений эквивалентности. Полностью изучена связь всех этих видов эквивалентности. Получен критерий сильной эквивалентности вычислительных систем.

Показано, что сложные автоматные системы, состоящие из конечного числа автоматов, сводятся к обычным автоматным системам (состоящим из одного автомата).

Фактически, автоматные системы – это общая модель для описания всех известных и перспективных вычислителей. Теория автоматных систем даёт новый взгляд на понятие алгоритма.

Заседание состоится в 18-30 в дистанционном формате в zoom-конференции zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

.В докладе рассматривается эквивалентность понятий автомата в многообразии алгебр и алгебры с операторами. Вводится понятие полигона (над полугруппой) в многообразии алгебр и показывается, что оно также эквивалентно понятию автомата в многообразии. Тем самым, возникает возможность использования хорошо разработанного аппарата универсальной алгебры (в частности, теории алгебр с операторами) и аппарата теории полигонов в многообразиях при исследовании автоматов в многообразиях.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

В докладе рассматриваются GF(2)-операции над формальными языками – варианты классической конкатенации и звездочки Клини, в определениях которых операции булевой логики (дизъюнкция и конъюнкция) заменены операциями в двухэлементном поле (конъюнкция и исключающее ИЛИ). Показывается замкнутость и незамкнутость различных семейств языков относительно этих операций. Для регулярных языков устанавливается замкнутость и приводятся точные нижние оценки сложности по числу состояний для этих операций при различных размерах алфавитов. Также показывается замкнутость класса языков, распознаваемых перестановочными автоматами, относительно операции GF(2)-конкатенация и незамкнутость этого класса относительно операции GF(2)-звёздочка. Кроме того, показывается, что языки, распознаваемые клеточными автоматами, не замкнуты относительно ни одной из операций, но замкнуты относительно GF(2)-конкатенации с регулярными языками.

Также доказывается незамкнутость языков, определяемых линейными, однозначными и однозначными линейными грамматиками, относительно GF(2)-конкатенации с множеством {\varepsilon, d} с обеих сторон. В то же время для LR(k)-грамматик устанавливается замкнутость относительно GF(2)-конкатенации с регулярным множеством справа, но не слева.

Наконец, определяется класс формальных грамматик, основанных на GF(2)-операциях, и показывается, что он имеет ту же вычислительную сложность, что и обычные грамматики с объединением и конкатенацией.

По техническим причинам семинар "Теория автоматов" 02 октября отменяется.

Заседание состоится в 16-45 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Пожалуйста, обратите внимание на нестандартное время начала!

Анонс доклада:

В докладе рассматриваются механизм дифракционных нейронных сетей и перспективы создания на их основе аналоговых фотонных сопроцессоров.

Название доклада: «Оценки количества красок, необходимого автомату для определения свойства графа быть графом-кактусом»

Анонс доклада:

В докладе будут представлены результаты, связанные с обходом автоматами с красками связных плоских простых неориентированных графов с целью установления их свойств. В частности, будет рассмотрен алгоритм, в соответствии с которым автомат, осуществляющий обход, может определить, является ли граф кактусом (графом, в котором любое ребро принадлежит не более чем одному циклу, а любые два цикла могут иметь не более одной общей вершины). Автомату доступно некоторое количество стираемых красок, которые он наносит на рёбра графа. Во время обхода автомат обладает частичной информацией о вершинах, которые он посещает, и инцидентных им рёбрах. В докладе будет описан алгоритм, в соответствии с которым автомат с 6 красками может установить, является ли граф, обход которого он осуществляет, кактусом. Кроме того, будет представлена нижняя оценка количества красок, необходимого для установления этого свойства.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Математическое моделирование вирусной динамики в клеточных линиях представляет интерес в силу нескольких причин: модели получаются более простыми в силу отсутствия адаптивного иммунного ответа и клеток врожденного иммунитета, имеется возможность измерения существенно большего количества параметров по сравнению со случаем in vivo, сами измерения оказываются менее шумными. В докладе рассматривается модель из шести интегро-дифференциальных уравнений, описывающих динамику числа здоровых, информированных и зараженных клеток, а также числа вирусных частиц, цитокинов и внутриклеточной вирусной РНК при заражении клеточных линий вирусом SARS-CoV-2.  Модель с достаточно высокой точностью воспроизводит экспериментальные данные для штаммов Дельта и Омикрон на двух клеточных линиях – Caco-2 (эпителий кишечника человека) и Calu-3 (эпителий легких). В терминах модели разница между штаммами объясняется тремя параметрами – скоростью проникновения вирусов в клетку, скоростью выработки цитокинов (то есть врожденным иммунным ответом) в зараженных клетках, а также устойчивостью к заражению клеток, информированных цитокинами. Выявленные различия могут быть обоснованы с биологической точки зрения.

Д.Н. Бабин – крупный ученый, талантливый математик, автор фундаментальных работ в области теории автоматов и распознавания образов. В 1987 году им получен выдающийся научный результат – решен аналог 13 проблемы Гильберта для конечных автоматов путем доказательства теоремы о суперпозиционной полноте автоматов арности два. Более того, ему удалось показать, что система, состоящая из одноместных автоматов и всех булевых функций, также суперпозиционно полна. В докторской диссертации Д.Н. Бабина построена классификация автоматных базисов по свойству разрешимости задачи полноты для них и была установлена явная граница в терминах решетки Поста, отделяющая разрешимые случаи от неразрешимых. В определенном смысле, она дала окончательный ответ на поставленный вопрос и сейчас известна каждому учёному, занимающемуся теорией конченых автоматов.

Прикладные разработки Бабина Д.Н. относятся к области создания конкретных систем распознавания образов. Группой сотрудников и аспирантов кафедры под его руководством была разработана система распознавания речи в условиях производственных шумов, а также система распознавания жестов, доведённая до практической реализации. Он имеет более 60 печатных работ и монографий, более 30 отечественных и зарубежных патентов по распознаванию образов, является членом редколлегии двух журналов из списка ВАК.

Д.Н. Бабин окончил механико-математический факультет МГУ в 1976 году по специальности математика и поступил в аспирантуру механико-математического факультета МГУ, которую окончил в 1979 году. С 1985 г. по 1990 г. преподавал информатику в ФМШ-18.

Бабин Д.Н. читает спецкурсы «Дискретные системы и процессы», «Современные проблемы прикладной дискретной математики» и руководит семинаром Теория дискретных функций и приложения, руководит научной работой студентов и аспирантов. Д.Н. Бабин – замечательный педагог. Под руководством Бабина Д.Н. было защищено более 7 кандидатских диссертаций и более 40 дипломных работ.

Сердечно поздравляем Дмитрия Николаевича с юбилеем, желаем крепкого здоровья, творческого долголетия и счастья.

20 июля 2024 года исполнилось 70 лет доценту кафедры математической теории интеллектуальных систем механико-математического факультета МГУ, кандидату физико-математических наук Строгалову Александру Сергеевичу.

А.С. Строгалов – известный ученый, талантливый математик, преподаватель, автор работ в области теории автоматов, теории обучения, теории интеллектуальных систем. Строгаловым А.С. введено и исследовано понятие эпсилон-моделирования поведения конечных автоматов, получены исчерпывающие результаты по взаимному моделированию поведения конечных автоматов с заданной мерой точности. Под руководством А.С. Строгалова разработан целый ряд компьютерных обучающих систем для различных предметных областей.

А.С. Строгалов родился 20 июля 1954 года в г. Саратов, окончил школу номер 32 с физико-математическим уклоном г. Костромы. В 1977 году закончил факультет вычислительной математики и кибернетики МГУ. В 1985 году защитил кандидатскую диссертацию "Об эпсилон-моделировании поведения конечных автоматов" и в 1986 году был приглашен на должность старшего научного сотрудника лаборатории проблем теоретической кибернетики механико-математического факультета МГУ. С 1991 года работает в должности доцента кафедры МАТиС.

А.С. Строгалов – не только талантливый ученый, но и прекрасный организатор. В разные годы, являясь сотрудником МГУ, он был руководителем Московского научного центра по компьютерным и информационным технологиям, директором Центра компьютерных технологий обучения РГГУ, руководителем филиала МГУ в г. Ташкенте, в трудные годы эпидемиологических ограничений являлся старшим экзаменатором по математике в МГУ. Результаты активной научно-педагогической деятельности А.С. Строгалова включают в себя многочисленные обязательные и специальные курсы, прочитанные им на механико-математическом факультете и в филиалах МГУ, четыре кандидатские диссертации и более ста дипломных работ, подготовленных под его научным руководством. В 2019 году Учёным советом МГУ А.С. Строгалову было присвоено почётное звание Заслуженный преподаватель.

Сердечно поздравляем Александра Сергеевича с юбилеем, желаем крепкого здоровья, благополучия и счастья.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс докладов:

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

"О поиске ассоциативных зависимостей в медицинских данных": В докладе рассматривается применение алгоритма поиска ассоциативных зависимостей Apriori к результатам общего клинического анализа крови. Рассмотрен вопрос о поиске оптимального метода разбиения данных для улучшения качества правил. Протестирована гипотеза об улучшении показателей достоверности правил путем дискретизации в условиях работы с клиническими данными. Особое внимание уделено специфике применения алгоритма в сфере медицины, поскольку, в отличие от экономики, где приоритет отдается самым распространенным, "стандартным" случаям, медицина оперирует "нестандартными", то есть заболеваниями, отклонениями от нормы. Особенности структуры исследуемых данных вносят коррективы в методы дискретизации и границы допустимых значений для полученных правил.

"Возможности и ограничения генеративного интеллекта в задаче синтеза изображений": Доклад посвящен анализу возможностей и ограничений генеративного искусственного интеллекта (ГИИ) в задаче синтеза изображений. Рассматриваются принципы работы ГИИ, способного генерировать новые изображения, дается краткий обзор конкретных инструментов, таких как Flair, Illustroke, PatternedAI и Stockimg, и примеры их использования. Обсуждаются ключевые проблемы ГИИ, включая сложности с генерацией связного текста, созданием и улучшением сложных изображений, пониманием количественных и пространственных понятий. Предлагается подход к преодолению этих ограничений для задачи дизайна на основе нечетких модификаторов и поиска по ним.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Построение палеогеографических карт проводится на основании анализа состава горных пород (фаций). Исходными данным могут быть как точки на плоскости – координаты скважин, в которых встречаются определенные фации, – так и карта скоростей накопления осадков. Предполагается, что одинаковые фации должны иметь близкие скорости осадконакопления. Задача реконструкции палеогеографической карты заключается в определении границ областей распространения фаций. В работе предлагается сведение задачи построения карты к задаче раскраски графов, которая, в свою очередь, решается методами целочисленного линейного программирования. Такой подход позволяет автоматически строить реалистичные карты – то есть карты, удовлетворяющей экспертным ограничениям и правилам.

Ссылка на видеозапись https://us02web.zoom.us/rec/share/NX1eOwtkGM592yeQ4vV6xrNUR0YUye-pzImHpIn5m2-WUmjr5Ix5iDNDJgK6q6su.pgRMJ7mlNN87XzVQ.

Пароль: .I?07ELb

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:Доклад посвящен деятельности, проведенной в рамках Лаборатории Бернулли МГУ им. М.В. Ломоносова. Будет рассказано о задачах, решаемых в рамках проектов по созданию комплексов тактильной диагностики и поддержки системы жизнеобеспечения Ангел. В частности, будет дан обзор языка описания медицинских протоколов и приведены результаты распознавания сенсорных образов с помощью тактильного механорецептора.

10 апреля в 18.30 в ауд. 1408 состоится встреча со студентами второго курса.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

В докладе будет изложена математическая модель криптографических протоколов, и будут приведён пример применения этой модели для решения задач верификации криптографических протоколов.

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

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

В докладе обсуждаются функции, вычисляемые различными видами автоматов: классическим автоматом, автоматом с остановками, двусторонним автоматом. Рассмотрены свойства кодировок, преобразующих числа во входные последовательности для автомата и обратно. Найдены классы функций, вычислимые указанными трёмя видами автоматов в этих кодировках.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

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

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада "Восстановление изображения по стертому коду с точностью до аффинной или метрической эквивалентности”:

Ранее в работах В.Н. Козлова были исследованы так называемые "правильные" коды для изометрических и аффинных преобразований. Код называется правильным для некоторого семейства преобразований, если совпадение кодов равносильно эквивалентности изображений относительно этого семейства. В докладе рассматривается задача восстановления изображения по стертому коду, т.е. коду, в котором были удалены индексы. Предложены алгоритмы, решающие (при некоторых дополнительных условиях) эту задачу за полиномиальное время.

Анонс доклада "Влияние метода подготовки обучающего материала на точность сегментации на примере нейронной сети DAUNet”:

Сбор и обработка реальных данных часто сопряжены с большими затратами. Синтетические данные могут стать хорошей альтернативой для обучения моделей. Также, важную роль на качество обучаемых моделей оказывает разметка данных. В докладе рассматривается задача сегментации трещин на изображениях дорожного покрытия. На первом этапе исследования было проведено обучение нейронной сети DAUNet на основе специально ухудшенной разметки. Показана зависимость метрик AIU, sODS, SOIS от качества разметки. На втором этапе исследования было проведено обучение нейронной сети DAUNet на основе синтетического обучающего материала. Показана зависимость метрик AIU, sODS, sOIS от процента содержания в обучающем материале синтетических данных.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Умножение n-значных чисел за время O(n) клеточным автоматом с локаторами": Будет рассказан алгоритм умножения чисел, в двоичном представлении которых n бит, за время порядка n с помощью клеточных автоматов с локаторами.

Анонс доклада:

"Решение задачи линейного программирования клеточными автоматами с локаторами": Будет предложен алгоритм решения двумерной задачи целочисленного линейного программирования с помощью клеточных автоматов с локаторами. Будет показано, что время работы алгоритма – это некоторая константа, не зависящая от числа точек в исходном множестве.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Доклад посвящен проблеме статистических выводов о причинно-следственных зависимостях в моделях высокой размерности, связанной с неравномерной сходимостью распределения оценок. Кратко описываются подходы к идентификации причинно-следственных связей – модель потенциальных исходов Рубина и модели на ациклических ориентированных графах, применимые (в отличие от методологии рандомизированных экспериментов) к данным на основе пассивных наблюдений. Подробно разбирается решение проблемы неравномерности с помощью методов ортогонального машинного обучения, включая двойной выбор как частный случай.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Предложено новое понятие автоматной системы, обобщающее все известные в дискретной математике вычислительные модели. Фактически, автоматная система – это произвольный конечный автомат, или группа автоматов, с внешней памятью.

Введён специальный класс графов, задающих вычислительные системы. Показано, что каждая автоматная система является вычислительной системой и наоборот, каждая вычислительная система является автоматной системой. Вводятся понятия эквивалентности и сильной эквивалентности автоматных (вычислительных систем). Получен критерий сильной эквивалентности вычислительных систем.

Задача определения класса функций, вычисляемых конкретным типом (классом) автоматных систем, решена путём сведения её к нахождению класса функций, вычисляемых автоматными системами данного типа за один такт.  Этот подход позволяет найти новые базисы во множестве вычислимых (по Тьюрингу) функций.

Показано, что сложные автоматные системы, состоящие из конечного числа автоматов, сводятся к обычным автоматным системам (состоящим из одного автомата).

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

Представляется, что теория автоматных систем заполнит ряд пробелов в теории алгоритмов. Кроме того, она даёт ёмкий язык для описания функционирования ряда хорошо известных вычислителей. Фактически, автоматные системы – это общая модель для описания всех известных и перспективных вычислителей.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

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

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

В докладе мы обсудим как алгебраическую  часть результата, так и её применение к задаче удовлетворения ограничениям.

22 декабря 2023 Ефимов Алексей Андреевич успешно защитил кандидатскую диссертацию на тему «Оценки энергопотребления объёмных схем»

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

ИРИС представляет собой библиотеку на языке C++, позволяющую описывать сложные конфигурируемые аппаратные схемы в рамках автоматной модели. Для этого в библиотеке имеется набор макрокоманд, формирующих встроенный в C++ язык для описания схем. Также в библиотеке имеются возможности для тестирования, оценки сложности и генерации описания на языке Verilog для последующего синтеза. В первой части доклада будет показано, как выглядит описание простых аппаратных модулей на языке ИРИС, как происходит тестирование, а также некоторые другие возможности библиотеки ИРИС. Во второй части доклада будут приведены планы по развитию ИРИС и задачи которые предстоит решить в следующем году. В частности, будет рассказано про задачу автоматической расстановки и балансировки задержек на критических путях, а также задачи, связанные с автоматизацией тестирования.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Проблема выразимости автоматов относительно суперпозиции долгое время считаласьнеразрешимой. В 2015 году она получила дальнейшее развитие в работах А.А Летуновского. Возник алгоритм проверки выразимости автоматов с безусловными переходами при наличии в выражающей системе автоматов "штрих Шеффера" и "задержки". Суперпозиция с такой добавкой получила название расширенной суперпозиции. Для такой суперпозиции множество всех автоматов распалось на две части: те автоматы, для которых есть алгоритм проверки выразимости, и те, для которых это неизвестно. К первой группе кроме автоматов с безусловными переходами были отнесены автоматы с простыми внутренними группами переходов и линейные автоматы. В настоящем докладе речь пойдёт о добавлении к этой группе автоматов с линейными переходами над произвольным конечным полем.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Рассматривается применение модели клеточного автомата с локаторами к задаче поиска ближайшего соседа на прямой. Модель клеточного автомата с локаторами подразумевает возможность каждой ячейке автомата передавать через эфир сигнал на сколь угодно большие расстояния. Ранее было показано, что такая возможность позволяет решать задачу поиска ближайшего соседа за логарифмическое время. В докладе обсуждается логарифмическая нижняя оценка для сложности этой задачи.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

В докладе будут представлены результаты, связанные с обходом автоматами с красками связных плоских простых неориентированных графов с целью установления их свойств. В частности, будут рассмотрены алгоритмы, в соответствии с которыми автомат, осуществляющий обход, может определить, является ли граф деревом, псевдодеревом (графом, из которого достаточно удалить одно ребро для того, чтобы он стал деревом) и графом-кактусом (графом, в котором любое ребро принадлежит не более чем одному циклу, а любые два цикла могут иметь не более одной общей вершины). Автомату доступно некоторое количество стираемых красок, которые он наносит на рёбра в течение обхода графа. Во время обхода автомат обладает частичной информацией о вершинах, которые он посещает, и инцидентных им рёбрах. В частности, в любой момент времени автомату известно, красил ли он только что некоторое ребро, благодаря чему он может обнаруживать циклы. Определены условия, при достижении которых автомат устанавливает, что граф не относится к рассматриваемым классам, а также признаки завершения обхода деревьев, псевдодеревьев и графов-кактусов..

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Одним из разделов математической кибернетики является теория управляющих систем. Интенсивное развитие науки и вычислительной техники в XX веке породило одно из интереснейших направлений в этой области – задачу синтеза схем, вычисляющих булевы функции и операторы. Автор решает эту задачу, разрабатывая универсальные методы синтеза схем и получая фундаментальные нижние оценки сложности схем, показывающие оптимальность применяемых методов.

В докладе будут представлены результаты, составившие содержание диссертации на соискание степени кандидата физико-математических наук по специальности 1.1.5 – Математическая логика, алгебра и теория чисел. После доклада нужно принять заключение кафедры на эту работу. Текст диссертации и проект заключения приложены к письму. Если у Вас не получится присутствовать на заседании семинара, большая просьба выразить свое мнение по электронной почте.

Заседание состоится в 18-30 в смешанном формате. Очная часть пройдет в аудитории 13-27 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

В докладе рассматривается проблема полноты для функциональных систем полиномиальных и рациональных функций, а также задачи функционального характера, порожденные ее решением (изучение структуры замкнутых и предполных классов, задача о базисах, ...). Особое внимание уделяется алгоритмически неразрешимым проблемам.

Заседание состоится в 18-30 в аудитории 13-27 Главного здания МГУ.

Анонс доклада:

Линейная автоматная система – это набор автоматов, взаимодействующих между собой посредством среды, параметры которой задаются целыми числами. Автоматы могут знать значения этих чисел, в случае, если они (по модулю) не превосходят обзор автоматов R, и могут постепенно менять их значения. Также числовые параметры системы могут быть связаны между собой линейными уравнениями. Тип автоматной линейной системы определяется количеством и областью значения её числовых параметров, количеством автоматов и конкретным способом их взаимодействия, а также уравнениями, связывающими параметры системы между собой.

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

Вводятся понятия манёвра линейной автоматной системы и функций маневра. Вводятся обобщённые дискретные функции как пары счётнозначных функций. На таких функциях вводятся операции обобщённой суперпозиции и обобщённой рекурсии, а также оператор замыкания (замыкание Илхомова), порождённый этими операциями. Сформулирована (и доказана в ряде частных случаев) гипотеза о том, что класс функций, вычисляемых автоматными системами каждого конкретного типа есть замыкание Илхомова класса функций манёвра, которые реализуют линейные автоматные системы данного типа.

Модель линейных автоматных систем позволяет рассматривать разные физические вычислители, описываемые одними же и теми же каноническими уравнениями, как разные геометрические образы одной и той же вычислительной системы. Также есть надежда, что озвученные в докладе подходы позволят найти новые структуры в иерархии классов вычислимых функций.

Заседание состоится в 18-30 в аудитории 13-27 Главного здания МГУ.

Анонс доклада:

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

Заседание состоится в 18-30 в аудитории 13-27 Главного здания МГУ.

Анонс доклада:

В последнее время растет интерес к использованию в криптографических (и теоретико-кодовых) приложениях некоммутативных и неассоциативных алгебраических структур (в частности, квазигрупп). Задание квазигруппы в виде "таблицы умножения" непрактично, поскольку размер требуемой для её хранения памяти растет крайне быстро при росте "длины" перемножаемых элементов. Одним из возможных вариантов обойти это ограничение является функциональное задание квазигрупповой операции, при котором координаты произведения (z_1, ..., z_n) задаются функциями от координат сомножителей: z_i = f_i(x_1, ..., x_n, y_1, ..., y_n).

А.Е. Панкратьев – известный ученый и педагог, талантливый алгебраист, специалист в области защиты информации.

А.Е. Панкратьев родился 23 августа 1973 года. В 1995 году закончил механико-математический факультет МГУ. В 2001 году защитил кандидатскую диссертацию "Гиперболические произведения групп".

В 1998-2001 гг. А.Е. Панкратьев опубликовал цикл работ о гиперболических произведениях групп. В последующие годы в фокусе исследований оказались конечные квазигруппы и их приложения в криптографии. К настоящему моменту А.Е. Панкратьев является автором более 50 статей в рецензируемых журналах.

Помимо фундаментальных исследований А.Е. Панкратьев занимается приложениями. Среди тем НИР, в которых он принимал участие, отметим совместный российско-индийский проект "Криптография на базе квазигрупп: анализ безопасности и развитие криптопримитивов и алгоритмов", в котором на финальной стадии А.Е. Панкратьев был ответственным исполнителем с российской стороны.

А.Е. Панкратьев активно работает со студентами и аспирантами. Под его научным руководством защищено более 30 дипломных работ и одна кандидатская диссертация. На механико-математическом факультете А.Е. Панкратьев читает курсы "Алгебраические алгоритмы и их сложность", "Кодирование и защита информации" и "Elements of cryptography", а также является руководителем специального семинара "Современные проблемы криптографии".

Отдельного упоминания заслуживает деятельность А.Е. Панкратьева, связанная с чемпионатами мира по программированию. Результатом здесь стали чемпионские титулы, завоеванные университетскими командами на самом высоком уровне.

А.Е. Панкратьев внес существенный вклад в работу со школьниками. Долгое время он возглавлял Малый мехмат. А.Е. Панкратьев неизменно активно участвует в организации и проведении Московской математической олимпиады.

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

Поздравляем Антона Евгеньевича с юбилеем и желаем здоровья, счастья и дальнейших успехов в научной и педагогической работе.

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Современный процесс создания чипа можно условно разделить на два этапа. На первом этапе создается дизайн вычислительного устройства. На втором этапе данный дизайн реализуется в <<кремнии>>, в реальном физическом устройстве. Надо отметить, что дизайн создается поэтапно от абстрактного описания функционирования вычислительного устройства к схеме из функциональных элементов (или ячеек) и затем к соединению транзисторов.

Транзистор является многослойной структурой, а соединения транзисторов также размещаются на отдельном слое. В итоге дизайн передается на производство как несколько слоев, где каждый слой это множество <<манхетоновских>> многоугольников.

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

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Кванторная задача удовлетворения ограничениям – это массовая задача, где на вход подаётся утверждение с кванторами, конъюнкциями и предикатами из некоторого множества допустимых предикатов, и нужно проверить верно ли это утверждение. Даже на конечных множествах сложность этой задачи для конкретного множества допустимых предикатов остаётся открытым вопросом, поэтому на бесконечных множествах мы пока рассматриваем только предикаты специального вида. В 2007 году была опубликована полная классификация сложности для множеств допустимых предикатов, которые задаются булевыми комбинациями равенств, но в ней была обнаружена ошибка и с тех пор вопрос о полной классификации оставался открытым. Спустя 15 лет мы получили полную классификацию, причем не только для кванторной задачи удовлетворения ограничениям, но и для всевозможных ограниченных альтернаций.

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

В докладе представляется метод повышения качества обучения сверточных искусственных нейронных сетей (ИНС) за счет разделения параметров по их возможности расширения рецептивного поля. При обучении ResNet50 достигается увеличение точности за счет чередуемой остановки обучения в 4-х слоях, расширяющих рецептивное поле. Показано, что повышение обобщающей способности модели при использовании предложенного метода достигается за счет устранения избыточного вклада отдельных существенных (окклюзивных) элементов изображения при формировании карт признаков. В пользу указанных предположений приводятся результаты экспериментов в задаче transfer learning и рассуждения относительно существования указанной проблемы. Демонстрируется существование подобных проблем и в прочих (не сверточных) архитектурах ИНС: например, в задаче выявления отклонений с применением автоассциативных ИНС.

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Понятие правильного семейства функций было введено В.А. Носовым в 1998 году.Оказалось, что с помощью правильных семейств функций можно порождать параметрические множества квазигрупп большой мощности. В процессе дальнейших исследований удалось установить ряд критериев правильности семейства, построить значительное число содержательных примеров, получить утверждения о сложности задачи распознавания правильности. В 2020 году К.Д. Царегородцев заметил, что в булевом случае имеется ествественным образом определенное взаимно однозначное соответствие между правильными семействами и одностоковыми ориентациями ребер булева куба; в процессе доказательства было найдено еще одно критериальное свойство – существование и единственность неподвижной точки у отображения, задаваемого правильным семейством, и всех его проекций. И одностоковые ориентации (Unique Sink Orientation, USO), и булевы сети с единственной неподвижной точкой являются известными математическими объектами, которым посвящено значительное число публикаций. В первой части доклада будет сделан обзор результатов по одностоковым ориентациям и булевым сетям с неподвижной точкой и показана связь этих результатов с правильными семействами; вторая часть посвщена анализу k-значного случая при k > 2.

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Сюръективным гомоморфизмом графов называется сюръективное отображение вершин одного графа в вершины другого, которое сохраняет ребра. Задача о существовании сюръективного гомоморфизма на граф H – массовая задача, в которой по данному графу G требуется определить, существует ли сюръективный гомоморфизм из G на H. Сложность этой задачи долгое время оставалась неизвестной даже для очень простых графов H, таких как циклы: только недавно были получены результаты о сложности для рефлексивного цикла длины 4 и нерефлексивного цикла длины 6. В докладе будет описана сложность задачи для рефлексивных циклов длины n = 7, n > 8.

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

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

Доклад посвящен свойствам конфигурации паросочетаний графа. В докладе будет построено взаимно-однозначное соответствие между регионами конфигурации паросочетаний и LP-ориентациями многогранника паросочетаний. Также будут рассказаны результаты о характеристическом многочлене конфигурации паросочетаний некоторых семейств графов.

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Микробиота желудочно-кишечного тракта (ЖКТ) насчитывает примерно 10^14 микробных клеток. В норме у взрослого человека более 90 % бактерий данного биотопа относится к типам Firmicutes, Bacteroidetes, Actinobacteria и Proteobacteria, в то время как остальные типы представлены в незначительном количестве. На сегодня микробиота ЖКТ рассматривается как самостоятельный орган, который регулирует множество метаболических процессов в организме хозяина и по своей значимости не уступает любому другому жизненно важному органу. Значительная часть функций микробиоты осуществляется при помощи промежуточных и конечных продуктов обмена веществ. Возможность изучения микробного состава, его изменения при различных нозологических формах представляет несомненный практический интерес.

Разнообразие микробиоты — крайне важный параметр оценки: чем больше видов бактерий, тем выше компенсаторный потенциал всей микробиоты. При высоком видовом разнообразии, в случае исчезновения одного или нескольких видов бактерий вследствие приема антибиотиков или несбалансированного питания, их функции могут взять на себя другие бактерии, чего не отмечается при низком видовом разнообразии.

Молекулярно-генетические методы исследования являются перспективным направлением в изучении структуры сообществ микроорганизмов и особенностей их функционирования в норме и патологии. К таким методам относятся полимеразная цепная реакция (ПЦР), таргетное секвенирование, и полногеномное секвенирование. Функцию отдельных групп микроорганизмов отражают метаболиты, образуемые микробиотой при метаболизме углеводов, белков и жиров. К наиболее изученным метаболитам относят образуемые микробиотой газы (водород, метан, сероводород, углекислый газ), короткоцепочечные жирные кислоты (уксусная, пропионовая и масляная), а также триметиламин (ТМА) и его окисленный печенью продукт ТМАО. Важной и нерешенной задачей является создание математической модели, позволяющей прогнозировать микробный состав микробиоты по результатам анализа газовых и других метаболитов.

В среду, 15 февраля на заседании кафедрального семинара "Теория автоматов" состоится доклад Е.А. Сажневой "Сложность GF(2)-операций над регулярными языками".

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Классические операции в теории формальных языков – объединение и конкатенация. Цель доклада – исследование свойств операций над формальными языками, в определениях которых булева логика (дизъюнкция и конъюнкция) заменена на операции в двухэлементном поле GF(2) – исключающее ИЛИ и конъюнкцию. После такой замены появляются две новые операции – GF(2)-конкатенация и взятие GF(2)-обратного языка. В докладе будет показано, что класс регулярных языков замкнут относительно этих операций. Будут приведены алгоритмы построения ДКА, распознающего GF(2)-конкатенацию двух регулярных языков, и ДКА, распознающего GF(2)-обратный язык. Кроме этого будет показано, что все построения являются оптимальными по числу состояний, а также дан ответ на вопрос о сложности данных операций в случае различных размеров алфавитов. В заключение будет кратко рассказано о последних исследованиях в области: применение GF(2)-операций к другим классическим моделям, а также GF(2)-варианты некоторых операций над языками.

В среду, 8 февраля на заседании кафедрального семинара "Теория автоматов" состоится доклад Н.В. Муравьева "О порядках линейных автоматов".

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Автоматы с совпадающим входным-выходным алфавитом образуют моноид относительно операции суперпозиции. Рассматривается задача определения порядка элемента в этом моноиде. В 2017 году было доказано, что данная задача алгоритмически неразрешима даже для обратимых конечных автоматов. В докладе будет показано, что она разрешима для класса линейных автоматов над конечными полями и полем рациональных чисел. Более того, будет доказана точная верхняя оценка порядка линейного автомата над этими полями, зависящая от размерности входного-выходного алфавита.

Поздравляем сотрудника кафедры МаТИС доц. Панкратьева А.Е. с получением премии имени М.В. Ломоносова за педагогическую деятельность!

Кафедра МаТИС искренне поздравляет кандидата физико-математических наук, старшего научного сотрудника с 50-летием!

И.Л. Мазуренко – известный ученый, талантливый математик и инженер в области искусственного интеллекта, автор работ по распознаванию речи и визуальных образов.

И.Л. Мазуренко родился 12 января 1973 года. В 1995 году закончил механико-математический факультет МГУ. В 2001 году защитил кандидатскую диссертацию "Автоматные методы распознавания речи".

В 1998-2014 гг. участвует в совместных проектах МГУ с отечественными и зарубежными заказчиками по цифровой обработке сигналов, изображений и видео. В рамках этих работ разработан и внедрен в производство ряд модулей цифровой обработки аудио-сигналов для систем цифровой телефонии и мобильной связи.

С 2014 года И.Л. Мазуренко участвует в совместных проектах кафедры МаТИС с компанией Huawei, где руководит научно-исследовательской лабораторией. На основе данного опыта в МГУ открыта совместная (двухгодичная) бесплатная образовательная программа SHARE (Школа опережающего научного образования Huawei в МГУ им. М. В. Ломоносова), в настоящий момент включающая более полутора десятков курсов и семинаров, целями которой являются преподавание и освещение передовых направлений исследований в области науки о данных, синтеза чипов, теории информации и помехоустойчивых кодов для систем хранения данных и беспроводной связи, цифровой обработки и сжатия сигналов и изображений, машинного обучения, компьютерного зрения, теории нейронных сетей, а также необходимых программных и аппаратных решений для работы с перечисленным; вовлечение студентов и аспирантов естественно-научных факультетов в реальный цикл современного исследовательского процесса; налаживание связей между индустрией и академией.

И.Л. Мазуренко читает годовой специальный курс "Математические основы цифровой обработки сигналов и изображений", является соведущим специального семинара "Приложения теории дискретных функций". Он является автором более 20 статей и более 70 российских и международных патентов.

23 декабря 2022 Анастасия Викторовна Быстрыгова успешно защитила кандидатскую диссертацию на тему «Параметро-эффективная расшифровка булевых функций»

Кафедра МаТИС искренне поздравляет кандидата физико-математических наук, ведущего научного сотрудника, заместителя заведующего лабораторией Павла Александровича Алисейчика с 60-летием!

Павел Александрович родился в городе Горький, в 1985 году закончил механико-математический факультет МГУ, в 1988 году – защитил кандидатскую диссертацию "О максимальной длине базиса в Pk". На мехмате он работает с 1986 года.

Павел Александрович – известный ученый, талантливый математик, автор работ в области теории автоматов, многозначных логик и обучающих систем. Им исследованы схемы автоматов, работающих в непрерывном времени, базисы в Pk, дана оценка максимальной длины базиса.

Павел Александрович является ведущим разработчиком программного обеспечения для первого российского контроллера твердотельного накопителя информации, созданного в рамках проекта "Пирамида" на мехмате МГУ. Он создал компьютерную обучающую систему "Идея". Павел Александрович – соавтор 30 патентов.

На мехмате Павел Александрович читает авторский курс лекций "Объектно-ориентированные технологии проектирования сложных систем" и ведет "Математический практикум по специальности", спецсеминар "Дискретный анализ и интеллектуальные системы". В филиале МГУ в г. Ташкенте он читает курс лекций "Проектирование больших систем на языке программирования С++" и руководит всеми математическими практикумами на ЭВМ. Под научным руководством Павла Александровича защищено большое количество дипломных и курсовых работ.

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

В.А. Буевич ввел понятие аппроксимационного замыкания (А-замыкания) в классе конечных автоматов над двухэлементной логикой P^2_{о.д.} что, по сравнению с замыканием по операциям композиции (К-замыкания), позволило увеличивать выразительные возможности его подмножеств. Вячеслав Александрович показал, что мощность множества А-предполных классов в P^2_{о.д.} счетна, а не континуальна, как для оператора К-замыкания (В.Б. Кудрявцев). Несмотря на это, задача проверки А-полноты конечных подмножеств конечных автоматов, как и в случае К-замыкания, осталась алгоритмически неразрешимой (М.И. Кратко).

Для подкласса L^2_{о.д.} класса P^2_{о.д.}, состоящего из линейных автоматов, количество К-предполных классов счетно, количество А-предполных классов конечно, задачи проверки К-полноты и А-полноты конечных подмножеств алгоритмически разрешимы. Эти же утверждения справедливы для классов линейных автоматов над конечными полями.

Доклад посвящен изучению А-предполных классов в L^2_{о.д.}. Для них построены А-базисы, найдены все их А-предполные подклассы. Таим образом, в решетке А-замкнутых классов L^2_{о.д.} определены два слоя максимальных собственных подклассов. Несмотря на континуальность А-замкнутых подклассов в классе L^2_{о.д.}, количество А-предполных и А-предпредполных классов в нем конечно, что располагает к дальнейшим исследованиям задачи А-выразимости в L^2_{о.д.}.

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ..

Анонс доклада:

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

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Доклад посвящен проблеме выполнимости булевых формул и подходах к ее решению. Будет рассказано о различных моделях формальных систем, представляющих как общий, так и частные случаи проблемы выполнимости. В докладе рассматриваются ограничения на класс допустимых формул и перечень используемых тактик. Будет представлен сравнительных обзор известных результатов по этой теме.

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Доклад посвящен проблеме выполнимости булевых формул и подходах к ее решению. Будет рассказано о различных моделях формальных систем, представляющих как общий, так и частные случаи проблемы выполнимости. В докладе рассматриваются ограничения на класс допустимых формул и перечень используемых тактик. Будет представлен сравнительных обзор известных результатов по этой теме.

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

В докладе речь пойдёт о различных мерах активности для схем из функциональных элементов и клеточных схем. Различные меры сложности схем моделируют различные характеристики чипов. Например, сложность схемы отражает площадь чипа, глубина схемы отражает задержку сигнала на выходе, что в свою очередь определяет тактовую частоту устройства. Активность (также называемая мощностью) схемы – мера сложности, отражающая энергопотребление физического устройства. Одним из наиболее естественных способов определить активность схемы – посчитать максимальное (или среднее) число единиц на выходах элементов, где максимум (или среднее) берётся по всевозможным входным наборам. Это наиболее исследованная мера активности схем, однако есть и другие способы определять активность, о которых будет рассказано в первой части доклада. Также будет дан обзор известных результатов об активности схем из функциональных элементов.

Во второй доклада части речь пойдёт об активности плоских и объёмных клеточных схем. Будут рассказаны результаты о связи мер сложности и активности, а также результаты о поведении функции Шеннона активности плоских и объёмных клеточных схем для класса частичных операторов. На примере класса всех булевых функций от n переменных будут проиллюстрированы несколько основных идей, используемых в доказательствах этих результатов.

В среду, 9 ноября на заседании кафедрального семинара "Теория автоматов" состоится доклад Г.В. Калачева "Об укладках схем из функциональных элементов на плоскости и в пространстве".

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

В докладе будет рассказано о различных моделях схем, учитывающих ограничения на размещение элементов на плоскости или в пространстве. Первая часть доклада будет посвящена обзору различных результатов о сложности реализации булевых функций (и операторов) клеточными схемами, известные асимптотические оценки для клеточных схем. Во второй части доклада будет кратко рассказано о связи сложности клеточных схем со сложностью в других схожих моделях, таких как планарные схемы, клеточные схемы ограниченной ширины, трехмерные клеточные схемы, многослойные схемы. Рассматривается функция сложности преобразования схемы из одной модели в другую, и в терминах этой функции формулируются результаты о связи сложности в различных моделях. В связи с этим естественным образом возникает класс задач, где для данной пары моделей нужно оценить функцию сложности преобразования из одной модели в другую. Несмотря на то, что иногда эта функция оценивается с использованием уже известных результатов, для многих пар моделей вопрос остаётся открытым.

В 1979 году Анвар Адхамович поступил на мехмат МГУ, его дипломная работа «Двойственность в теории гомологий» была успешна защищена в 1984 году и опубликована в журнале «Вестник Московского Университета». В 1990 году Анвар Адхамович защитил кандидатскую диссертацию «Топология пространства фредгольмовых операторов». С 1989 года он работает на кафедре МАТиС мехмата МГУ.

В 1999 году Анвар Адхамович получил степень Executive M.B.A. в бизнес-школе IEDC-Bled School of Management. По совместительству он работает начальником отдела интеллектуальных систем Исследовательского центра компании Samsung Electronics.

Научные интересы Анвара Адхамовича связаны с задачами биометрии, машинного обучения, распознавания образов, комбинаторики, математической экономики, дискретной оптимизации, алгебраической топологии и функционального анализа. Он является автором F-топологии в пространстве фредгольмовых операторов и IM-топологии в пространстве компактных операторов. Широко известны полученные им нижние оценки числа пороговых функций на основе оригинальной комбинаторно-вероятностной конструкции, а также с использованием комбинаторно-топологических методов.

Под руководством Анвара Адхамовича инженеров компании S1 Co. Ltd. (Samsung Group Affiliate) была создана автоматическая система распознавания лиц, которая успешно используется в системах контроля доступа.

Анвар Адхамович – лауреат престижной награды Alumni Achievement Award 2012 года.

На мехмате Анвар Адхамович читает "Алгоритмы вычислительной геометрии", "Математические модели экономического расчета", "Введение в алгебраическую теорию кодирования", является одним из руководителей спецсеминаров «Геометрия и дискретный анализ», «Вероятностные методы в анализе дискретных функций», «Некоммутативная геометрия и топология», «Топология и анализ». Под его научным руководством написано более 80 курсовых и дипломных работ.

Поздравляем Анвара Адхамовича с юбилеем, желаем ему здоровья, благополучия и успехов в дальнейшей научной и педагогической работе.

В среду, 26 октября на заседании кафедрального семинара "Теория автоматов" состоится доклад В.Н. Козлова "Цифровая подпись на основе кодов, определяющих изображения с точностью до аффинных преобразований".

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Первый "допотопный" вариант защиты документа от подделки (используется, однако, и поныне) – это так называемая "живая" подпись (или факсимиле), и канцелярская печать. Но в наши дни документооборот большей частью электронный, и, зачастую, с очень большим числом документов (электронные торги, банковские платежные системы, сделки в криптовалютах, и пр.). Факсимиле в этом случае неудобно, а главное – крайне ненадежно. Здесь работает возникшая около тридцати лет назад цифровая подпись (или электронная цифровая подпись – ЭЦП). Как правило, сердцевиной этой конструкции, т.е. ЭЦП, является функция, у которой ее значение при заданном значении аргумента, вычисляется легко, а обратное, т.е. вычисление значения аргумента при известном значении функции, очень трудно. В докладе описывается аналог цифровой подписи на другой принципиальной основе – на использовании кодов, определяющих изображения с точностью до аффинных преобразований. Это способ защиты электронного изображения от подделки и проверки подлинности полученной информации. Способ предназначен для работы с любыми изображениями (потенциально и с трехмерными), или с информацией, приводимой к изображениям (например, со звуком). В целом способ может быть использован для защиты канала связи между отправителем информации в виде изображения и получателем от попыток третьих сторон отправить получателю информацию под видом информации от отправителя, а также аутентификации полученного изображения или информации, приводимой к виду изображения.

В среду, 19 октября на заседании кафедрального семинара "Теория автоматов" состоится доклад А.В. Тарасова "Булевы биюнктивные функции и порождаемые ими системы булевых уравнений".

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Доклад посвящен результатам из области исследования булевых биюнктивных функций. Класс биюнктивных функций (функций, представимых в виде 2-КНФ) является одним из классов Шефера, порождающих полиномиально решаемые системы булевых уравнений.

Ряд задач, связанных с этими функциями, является труднорешаемыми. К таковым относится, в частности, задача нахождения веса функции по её 2-КНФ, известная как задача #2-SAT. Вместе с тем, 2-КНФ, представляющие биюнктивные функции, допускают компактное представление в виде ориентированных графов. В докладе обсуждаются методы эффективного оценивания веса биюнктивных функций. Данная задача фактически эквивалентна задаче оценки числа решений булевой двучленной системы уравнений.

Поскольку класс биюнктивных функций относится к классам Шефера, в докладе обсуждаются вопросы связи класса биюнктивных функций с другими классами Шефера. Центральным результатом здесь является описание групп преобразований n-мерного векторного пространства, стабилизирующих множество биюнктивных функций от n переменных и ряд его подмножеств.

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

Во вторник, 4 октября, в 18-30 на семинаре "Компьютерная безопасность" состоится доклад В.Н. Козлова "Защита электронного изображения на основе аффинных преобразований и способ аутентификации электронного изображения".

Краткая аннотация доклада:

Первый "допотопный" вариант защиты документа от подделки (используется, однако, и поныне) – это так называемая "живая" подпись (или факсимиле), и канцелярская печать. Но ныне документооборот большей частью электронный, и, зачастую, с очень большим числом документов (электронные торги, банковские платежные системы, сделки в криптовалютах, и пр.) . Факсимиле в этом случае неудобно, а главное – крайне ненадежно. Здесь работает возникшая около тридцати лет назад цифровая подпись (или электронная цифровая подпись – ЭЦП). Как правило, сердцевиной этой конструкции, т.е. ЭЦП, является функция, у которой ее значение при заданном значении аргумента, вычисляется легко, а обратное, т.е. вычисление значения аргумента при известном значении функции, очень трудно.

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

Заседания семинара проводятся в аудитории 1503 Главного здания. Приглашаются все желающие.

Ведущие инженеры-исследователи Российского Исследовательского Института Huawei совместно с профессорско-преподавательским составом механико-математического факультета МГУ представляют новую образовательную программу, в рамках которой проведут слушателя от основ машинного обучения и компьютерного зрения до state-of-the-art решений в компьютерном интеллекте, от основ теории графов и помехоустойчивых кодов к принципам проектирования электронных схем. Онлайн презентация программы пройдет 30 сентября в 17.00. Для участия в презентации заполните анкету на Timepad по ссылке: https://sharemsu.timepad.ru/event/2178424/ . Ссылка на подключение к онлайн-встрече будет выслана на указанный Вами в анкете e-mail.

Заполнить анкету на Timepad можно до 30 сентября 15.00.

Заполнить анкету для участия в конкурсном отборе на программу SHARE 2022-2024 можно по ссылке:https://forms.yandex.ru/cloud/6329d09f8f8c19567f69fbe5/

Заполнить анкету на Яндекс.Формах можно до 6 октября 18.00.

Больше информации о программе Вы можете найти на нашем сайте https://sharemsu.ru/ , а также в телеграм канале программы всем организационным вопросам просьба писать на почту SHARE@intsys.msu.ru .

В среду, 14 сентября на заседании кафедрального семинара "Теория автоматов" состоится доклад А.В. Быстрыговой "Параметро-эффективная расшифровка булевых функций".

Заседание состоится в 18-30 в аудитории 12-25 Главного здания МГУ.

Анонс доклада:

Расшифровка функций (learning theory) – направление математики, которое началось развиваться практически полвека назад. Эта область остается актуальной и по сей день, поскольку связана с восстановлением оптимальным образом информации об исследуемом объекте на основе частичных сведений о нем. Более формально, под расшифровкой функции из заданного класса F понимают игру между "учеником" и "учителем", в которой учитель загадывает одну функцию из класса F, а ученик, зная этот класс F полностью, но не зная выбор учителя, задает учителю запросы разрешенного типа, получает ответы от учителя и на основе этих ответов восстанавливает какую-то информацию про выбранную функцию.

Чтобы оценить, насколько быстро можно расшифровать функции из того или иного класса, вводят понятие сложности расшифровки как максимальное число запросов, которое ученик должен задать учителю для расшифровки самой "плохой" функции. Иными словами, ученик выбирает "лучшую" стратегию восстановления функции. Затем проверяется, сколько запросов потребуется задать ученику, используещему эту стратегию, чтобы восстановить каждую функцию из класса. За сложность расшифровки принимают максимум среди этих значений.

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

Поздравляем сотрудников кафедры МаТИС доц. Пантелеева П.А. и м.н.с. Калачева Г.В. с получением награды за лучшую статью на ежегодном симпозиуме ACM по теории вычислений (STOC 2022) за работу «Асимптотически хорошие квантовые и локально трестируемые классические LDPC коды».

24-31 августа в пансионате МГУ "Красновидово" пройдет первая студенческая летняя школа "Машинное обучение, нейронные сети и верификация программ".

Руководитель школы – доцент кафедры МаТИС Андрей Михайлович Миронов.

Летняя школа проводится при поддержке научно-образовательной школы МГУ "Мозг, когнитивные системы, искусственный интеллект".

В рамках летней школы будет организовано 2 трека: трек по машинному обучению и нейронным сетям и трек по верификации программ.

Участники трека по машинному обучению получат необходимые знания, навыки и компетенции для полноценного старта карьеры и научных исследований в области глубинного обучения и нейронных сетей. Программа летней школы рассчитана на охват большого количества самых современных ветвей науки о нейронных сетях, а также предлагает участникам большое количество практики в виде семинарских занятий и лабораторных работ, результаты которых станут хорошим дополнением к резюме каждого из студентов. Приобретенные навыки будут полезны как для ведения собственной научной работы практически в любой естественнонаучной области, так и для развития коммерческих проектов в рамках стартапов или же крупных корпораций.

Участники летней школы, обучающиеся в рамках потока по верификации программ методами искусственного интеллекта, получат необходимые знания, навыки и компетенции для полноценного старта научных исследований и практической деятельности в области применения систем искусственного интеллекта для формальной верификации программного обеспечения. Будет предоставлена необходимая теоретическая база, а также будут показаны практические применения верификации для осознания участниками школы основной задачи верификации. Школа также даст компетенции и в других областях, например, системах распределенного реестра (технологии блокчейн), а также смарт-контрактах: в одном из блоков программы будут рассмотрены ключевые особенности протоколов распределенного реестра с их последующей верификацией. Участникам будет показано несколько методов формальной верификации, которые применяются в зависимости от поставленной задачи, данная школа ставит перед собой цель – развить у обучающихся навыки для верификации в выбранной ими области. Также участники получат необходимые компетенции в функциональном программировании, которые требуются при реализации индустриальных проектов.

Участие, проживание, питание и транспорт для участников летней школы, прошедших конкурсный отбор, бесплатные.

Более подробная информация о школе будет размещаться на страничке https://vk.com/mm_ml_school_2022

Кандидатам на участие в школе необходимо зарегистрироваться по ссылке https://forms.gle/Me3ZGqfnhLsjet7A7

Кафедра Математической теории интеллектуальных систем поздравляет аспиранта Комкова Степана Алексеевича с успешной защитой диссертации "Темпы роста произвольных конечных структур" на соискание степени кандидата физико-математических наук.

В среду, 18 мая, на заседании кафедрального семинара "Теория автоматов" состоится доклад А.А. Ирматова "Асимптотика числа пороговых функций и асимптотика числа вырожденных {±1}-матриц".

Заседание состоится в 18-30 в zoom-конференции

https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09

Meeting ID: 886 6514 1982

Passcode: 965515

Аннотация доклада

Заседание кафедры МаТИС пройдет сегодня в 18.30 в zoom конференции:

https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09

Meeting ID: 886 6514 1982

Passcode: 965515

В среду 20 апреля в 18.30 в рамках спецсеминара ректора МГУ В.А.Садовничего «Время, хаос и математические проблемы» состоится доклад Э.Э.Гасанова, А.Ю.Кравцова, Р.Р.Юсупова, А.Ю.Дроздова «Российские микросхемы». Семинар будет проходить в дистанционном формате. Ссылка для подключения и дополнительная информация о докладе будет размещена сайте https://expert.msu.ru/.

Аннотация: В докладе будет рассказано о проекте создания предприятия по проектированию и производству микросхем и изделий на их основе, которое планируется организовать в технологическом кластере «Долина МГУ». Будет рассказано задачах предприятия и о командах-учредителях предприятия, а именно о АО «Крафтвэй корпорэйшн ПЛС» (Крафтвэй), ЗАО «Оптимизирующие технологии» (ТимТех) и о кафедре математической теории интеллектуальных систем (МаТИС). Также будет рассказано об интересных инженерных и научных задачах, которые возникали в процессе проектирования микросхем, в частности, о новых достижениях в теории управляющих систем и в теории помехоустойчивого кодирования.

В среду, 13 апреля на заседании кафедрального семинара "Теория автоматов" состоится доклад А.Н. Кана "Вопросы выразимости в классах кусочно-линейных функций".

Заседание состоится в 18-30 в zoom-конференции

https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09

Meeting ID: 886 6514 1982

Passcode: 965515

Анонс доклада:

Кусочно-линейные функции используются при проектировании искусственных нейронных сетей, к ним относятся суперпозиции из линейных функций и ReLU. Работа продолжает исследования В.С. Половникова по выразимости через суперпозиции в классах кусочно-линейных функций, содержащих линейные функции. При этом ограничении для класса кусочно-линейных функций найдены предполные классы. Одним из них является класс согласованных функций, который содержит единственный предполный подкласс, включающий линейные функции. Показано, что любая кусочно-линейная непрерывная функция двух переменных выражается через линейные функции и ReLU. Построена решетка одноместных следов замкнутых классов кусочно-линейных функций с рассматриваемым ограничением.

7 апреля (четверг) в 16:45 состоится встреча кафедры со студентами 2 курса.

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

https://us02web.zoom.us/j/86856372603?pwd=U0t1dUlmN1A1YTI1d3QrY2dtUXZadz09

Код доступа: 576004

В аудитории будет организовано подключение к конференции и трансляция.

6 апреля, в 16.45 в ауд. 1225 состоится защита кандидатской диссертации Дмитрия Ронжина «Линейные автоматы над подкольцами рациональных чисел».

В среду, 23 марта, на заседании кафедрального семинара "Теория автоматов" состоится доклад А.А. Ефимова "Оценки энергопотребления объёмных схем".

Заседание состоится в 18-30 в zoom-конференции

https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09

Meeting ID: 886 6514 1982

Passcode: 965515

Анонс доклада:

Ещё в середине XX века в связи с интенсивным развитием вычислительной техники возникла задача синтеза схем, вычисляющих булевы функции и операторы. Одной из основных и наиболее подробно исследованных моделей схем является схема из функциональных элементов (СФЭ). В качестве характеристики оптимальности СФЭ можно рассматривать сложность – количество функциональных элементов, содержащихся в схеме. Таким образом, под сложностью булевой функции или оператора будем понимать минимальную сложность схемы, реализующую данную функцию или оператор.

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

В докладе рассматриваются объёмные схемы, являющиеся укладкой схем функциональных элементов в пространстве. Был рассмотрен класс объёмных схем, реализующих булевы операторы. Для этого класса получены верхняя и нижняя оценка потенциала – меры мощности, равной количеству элементов схемы, выдающих единицу на данном входном наборе. Получен порядок функции Шеннона потенциала для класса всюду определенных операторов для объёмных схем без ограничений и схем с близкими выходами, а также нижняя оценка для частичных операторов.

На семинаре «Теория дискретных функций и приложения» под руководством проф. Бабина Д.Н. в понедельник, 21 марта в 16:45 состоится доклад аспиранта Ищенко Р.А. «Математические методы в банковских задачах».

Код конференции:

https://us04web.zoom.us/j/4528320761?pwd=cWo0SWpKUUxnRUxJWWlrMzhkOG1udz09

Meeting ID: 452 832 0761

Passcode: 8gdJck

На семинаре «Теория дискретных функций и приложения» под руководством проф. Бабина Д.Н. в понедельник, 14 марта в 16:45 состоится доклад аспиранта Муравьёва Н.В. «О порядках конечных автоматов».

https://us04web.zoom.us/j/4528320761?pwd=cWo0SWpKUUxnRUxJWWlrMzhkOG1udz09

Meeting ID: 452 832 0761

Passcode: 8gdJck

В среду, 9 марта, на заседании кафедрального семинара "Теория автоматов" состоится доклад Д.Н. Жука "Предикаты k-значной логики и задача удовлетворения ограничениям".

Заседание состоится в 18-30 в zoom-конференции

https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09

Meeting ID: 886 6514 1982

Passcode: 965515

Анонс доклада:

В 1969 году была открыта удивительная связь между функциями и предикатами, а именно, было построено взаимно-однозначное соответствие между замкнутыми классами функций и замкнутыми классами предикатов. Несмотря на этот результат, многие годы именно функции были главным объектом исследований, а предикаты (отношения) оставались вспомогательным инструментом для описания предполных и замкнутых классов.

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

В среду, 2 марта, на заседании кафедрального семинара "Теория автоматов" состоится доклад П.А. Пантелеева и Г.В. Калачева "Асимптотически хорошие семейства классических и квантовых LDPC кодов".

Заседание состоится в 18-30 в zoom-конференции

https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09

Meeting ID: 886 6514 1982

Passcode: 965515

Анонс доклада:

Классические LDPC коды являются важными компонентами современных систем хранения и передачи данных. Их квантовые аналоги (qLDPC коды) обещают значительную экономию ресурсов в протоколах для отказоустойчивых квантовых вычислений. Начиная с основополагающей работы Роберта Галлагера в начале 1960-х годов было известно, что существуют асимптотически хорошие семейства классических LDPC кодов, т. е. семейства, где размерность и минимальное расстояние растет линейно с ростом длины кода. Более того, 35 лет спустя Сипсер и Спилмен нашли эффективный способ построения таких кодов на основе графов расширителей (экспандерные коды). В то же время, вопрос о существовании асимптотически хороших квантовых LDPC кодов (qLDPC гипотеза) оставался открытым уже более двух десятилетий.

В докладе будет рассказано об аналоге экспандерных кодов Сипсера и Спилмена, позволяющем строить асимптотически хорошие семейства квантовых LDPC кодов на основе первых групп гомологий некоторого двумерного цепного комплекса, что доказывает qLDPC гипотезу. Более того, будет продемонстрировано как рассматривая вторые группы гомологий полученных цепных комплексов можно доказать существование классических локально тестируемых кодов с оптимальными асимптотическими параметрами, что в свою очередь решает другую важную открытую проблему, называемую c^3-гипотезой, ответ на которую также недавно независимо был получен в работе arXiv: 2111.04808.

В выступлении предполагается дать обзор конструкции и показать некоторые основные идеи, используемые в доказательстве, такие как понятие локальной минимальности, заимствованное из теории многомерных расширителей. Доклад основан на совместной работе с Г. В. Калачевым (arXiv: 2111.03654).

16 февраля, в среду состоится защита диссертации Ищенко Романа Андреевича на соискание ученой степени кандидата физико-математических наук на тему «О свойствах разложимых графов».

Официальное время начала защиты – 16:45, ауд 14-08. Научный руководитель – д.ф.-м.н., профессор Бабин Д.Н. Официальные оппоненты – профессор, д.ф.-м.н. Фролов А.Б., доцент, д.ф.-м.н. Романов Д.С., к.ф.-м.н. Пархоменко Д.В.

Математики МГУ предложили нейросеть для эффективного мониторинга качества дорожного покрытия

Ученые МГУ представили собственную комбинацию известных методов на основе архитектуры нейросети U-Net. Разработка точно и надежно обнаруживает трещины на изображениях дорожного полотна, превосходя аналоги по эффективности и скорости. Подход может дать начало новым системам мониторинга дорог в реальном времени, что поможет улучшить обслуживание отечественной инфраструктуры и обеспечить ее безопасность. Результатами своего исследования математики поделились на страницах журнала IEEE Access.

В 2019 году стартовал национальный проект «Безопасные качественные дороги», одна из основных задач которого — улучшить состояние трасс и магистралей. На данный момент и половина дорог регионального значения не соответствует нормативным требованиям, при этом около трети всех ДТП происходит из-за плохого дорожного покрытия. Именно поэтому необходимо разрабатывать новые способы отслеживания появляющихся дефектов, чтобы устранять их еще на ранних этапах.

Сотрудники НОШ МГУ «Мозг, когнитивные системы, искусственный интеллект» разработали практический метод для мониторинга качества дорожного покрытия.

«Мы используем известные методы, но находим новые комбинации, которые приводят к созданию практичного алгоритма, имеющего большое значение в реальном мире», – рассказал научный руководитель работы, сотрудник кафедры математической теории интеллектуальных систем механико-математического факультета МГУ Владимир Половников.

В основу разработки легла архитектура сверточной нейросети U-Net, которую изначально создали для сегментации биомедицинских изображений, то есть их разделения на сегменты (например, пиксели). Проблемы при решении этой задачи почти такие же, как и при работе с фотографиями дефектных дорог: большое разнообразие форм искомого объекта, низкая контрастность, плохо видимые границы и прочие. Авторы использовали различные подходы к обработке изображений, двухэтапную процедуру обучения нейросети градиентными методами с эффективными функциями потерь, а также предложили быстрые методы оценки качества сегментирования. Сравнение с другой аналогичной системой показало превосходство разработки московских математиков и по эффективности, и по скорости.

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

Результаты работы выложены в общественный доступ и могут быть использованы другими исследователями.

Прощание с Валерием Борисовичем Кудрявцевым состоится 28 декабря в 12:00 в Доме культуры МГУ.

Отпевание состоится 28 декабря в 14:00 в храме Иоанна Предтечи на Хованском Центральном кладбище по адресу Москва, Сосенское поселение, Подмосковная улица, д.1 стр. 3 (координаты 55.606870, 37.448045). Автобус от Дома культуры МГУ отправится в 13:15.

Место захоронения: Хованское Центральное кладбище, участок № 42и (координаты 55.613204, 37.440368).

Ректорат и механико-математический факультет МГУ имени М.В. Ломоносова с глубоким прискорбием сообщают, что 23 декабря 2021 г. скончался выдающийся деятель науки и культуры России, заведующий кафедрой «Математической теории интеллектуальных систем», доктор физико-математических наук, профессор Валерий Борисович Кудрявцев (04.07.1936-23.12.2021).

Кудрявцев В.Б. родился в городе Егорьевске Московской области в семье военнослужащего. После окончания в 1955 г. средней школы с золотой медалью он поступил на механико-математический факультет МГУ им. М. В. Ломоносова, с которым оказалась связанной вся его научная и педагогическая деятельность: на факультете он прошел весь путь от студента и аспиранта до профессора и заведующего кафедрой.

В 1964 г. В. Б. Кудрявцев защитил кандидатскую диссертацию, в 1972 г. защитил докторскую диссертацию по теории функциональных систем. С 1974 г. В. Б. Кудрявцев работал заместителем декана механико-математического факультета сначала по международным связям, а затем заместителем декана по научно-исследовательской части и проработал на этом посту до 1986 г., внеся значимый вклад в развитие факультета и превращение его в ведущий центр фундаментальных и прикладных исследований.

С 1986 г. В. Б. Кудрявцев заведует вновь созданной на факультете лабораторией теоретической кибернетики, которая входила в созданный ректором МГУ В.А. Садовничим «Отдел прикладных исследований по математике и механике».

В 1991 году В.Б. Кудрявцев выступил с инициативой создания новой кафедры – «Математической теории интеллектуальных систем»- и стал ее первым заведующим.

За прошедшие годы кафедра превратилась в крупнейший учебно-научный центр России, в котором под руководством В.Б. Кудрявцева широким фронтом велись фундаментальные и прикладные работы по современным направлениям науки.

С 2006 г. по 2018 г. В. Б. Кудрявцев руководил филиалом Московского государственного университета им. М. В. Ломоносова в Ташкенте, который под его руководством достиг больших успехов в подготовке кадров высшей квалификации для Республики Узбекистан.

Научные интересы В. Б. Кудрявцева охватывали различные области дискретной математики, математической кибернетики и информатики. Ему принадлежат фундаментальные результаты в теории автоматов, дискретных функций, распознавания образов, интеллектуальных систем и др. Полученные В.Б. Кудрявцевым результаты опубликованы более чем в 230 статьях, 17 книгах, в 35 патентах США по микроэлектронике. В. Б. Кудрявцевым создана большая научная школа, включающая 27 докторов и 88 кандидатов наук по математике и её приложениям.

В 1996 г. В. Б. Кудрявцев основал журнал «Интеллектуальные системы» и был бессменным главным редактором этого издания, являясь одновременно заместителем главного редактора журнала «Дискретная математика». Многие годы В. Б. Кудрявцев входил в состав советов по защите докторских диссертаций и ВАК, являлся членом Ученого совета механико-математического факультета.

Достижения В. Б. Кудрявцева были отмечены избранием его академиком РАТН, РАЕН и МАИ, ему присвоены звания «Заслуженный деятель науки РФ» и «Заслуженный профессор МГУ», он был избран почётным доктором Белградского университета.

Родные и близкие, друзья и коллеги скорбят о невосполнимой утрате…

С 29 ноября по 3 декабря проводится XII Международная научная конференция «Интеллектуальные системы и компьютерные науки», приуроченная к 85-летию со дня рождения профессора Московского университета В.Б. Кудрявцева. Более подробную информацию можно найти на сайте: https://event.msu.ru/aiconference.

В среду, 17 ноября, на заседании кафедрального семинара "Теория автоматов" под руководством академика В. Б. Кудрявцева состоится доклад С.А. Комкова "Темпы роста произвольных конечных структур".

Заседание состоится в 18-30 в смешанном формате. Очная часть будет проведена в аудитории 1201 (кафедра МаТИС), дистанционная – в zoom-конференции

Meeting ID: 886 6514 1982
Passcode: 965515

Анонс доклада:

В докладе будут представлены результаты автора, полученные в рамках исследования темпов роста произвольных конечных структур. Темп роста – характеристика, описывающая силу и исчислимость множества операций, заданных на структуре. Известно, что это не просто количественная характеристика. От темпа роста некоторой внутренней структуры задачи может зависеть класс сложности этой задачи. Исследование темпов роста ведётся с 70-х годов прошлого века. Однако ранее исследователи ограничивались в основном алгебраическими методами. Рассмотрение конечной структуры как пары (k-значная логика, множество функций k-значной логики) позволяет получить новые интересные результаты.

В рамках доклада будет рассмотрен ряд утверждений, описывающих темпы роста для различных "крайних" случаев: точное описание темпов роста двухэлементных структур; критерии минимального темпа роста и решётка клонов с минимальным темпом роста; темпы роста для задач с конечным языком ограничений; описание разнообразия максимальных возможных темпов роста.

В среду, 10 ноября, на заседании кафедрального семинара "Теория автоматов" под руководством академика В. Б. Кудрявцева состоится доклад Д.Н. Жука "О решетке замкнутых классов функций по модулю гомоморфной и минорной эквивалентностей".

Заседание состоится в 18-30 в zoom-конференции

https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09

Meeting ID: 886 6514 1982
Passcode: 965515

Анонс доклада:
На множестве клонов (замкнутых классов функций) k-значной логики определяем два отношения эквивалентности. Два клона называем гомоморфно эквивалентными, если существует отображение из одного клона в другой (и наоборот), сохраняющее арность, селекторы и операцию композиции. Аналогично, два клона называем минорно эквивалентными, если существует отображение из одного клона в другой (и наоборот), сохраняющее арность и операции подстановки переменных. В результате можно изучать решетки замкнутых классов с точностью до таких эквивалентностей. Следует отметить, что эти эквивалентности имеют естественную интерпретацию в терминах отношений, сохраняемых данных клоном. Было показано, что решетка клонов самодвойственных функций в трехзначной логике остается континуальной относительно гомоморфной эквивалентности, но становится счетной относительно минорной эквивалентности. Следовательно решетка клонов относительно гомоморфной эквивалентности по-прежнему континуальна, но остается надежда, что решетка всех клонов становится счетной относительно минорной эквивалентности и может быть полностью описана.

В среду, 20 октября, на заседании кафедрального семинара "Теория автоматов" под руководством академика В. Б. Кудрявцева состоится доклад Д.В. Алексеева и С.А. Нерсисяна "Моделирование динамики COVID-19 в клетках инфицированного организма".

Заседание состоится в 18-30 в смешанном формате. Очная часть будет проведена в аудитории 1201 (кафедра МаТИС), дистанционная – в zoom-конференции
https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09
Meeting ID: 886 6514 1982
Passcode: 965515

Анонс доклада:

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

В среду, 20 октября, в 15:00 на семинаре "Вопросы сложности алгоритмов поиска" под руководством д.ф.-м.н, профессора Гасанова Э.Э. с докладом "Нижняя оценка числа состояний клеточного автомата, реализующего двунаправленное движение на луче со скоростью движения вперёд 1/3" выступит Екатерина Кузнецова.

Форма проведения – онлайн (zoom):

https://us02web.zoom.us/j/9423397823?pwd=NS90YzgyVUxrL3VtaTB1M0xKdFlsdz09

Идентификатор конференции: 942 339 7823

Код доступа: 944214

Аннотация доклада

В докладе рассматривается движение точки на экране, который реализован, как клеточный автомат на бесконечной в правую сторону полосе шириной в одну клетку. Изучается класс законов движения этого автомата, для которых движение вперёд возможно со скоростью, не большей, чем 1/3. Движение вперёд на одну клетку осуществляется с двумя остановками. Возможно движение назад со скоростью 1, также точка может стоять на месте произвольное количество тактов.

Доказано, что невозможно построить клеточный автомат с количеством состояний, меньшим пяти, реализующий законы движения из рассматриваемого класса. Результат получен для случая, когда до появления точки на экране все клетки находятся в состоянии покоя.

Кафедра Математической теории интеллектуальных систем сердечно поздравляет Анатолия Александровича Часовских с успешной защитой докторской диссертации на тему "Полнота и выразимость в классах линейных автоматов".

С 29 ноября по 3 декабря 2021 года будет проходить XII Международная научная конференция «Интеллектуальные системы и компьютерные науки», приуроченная к 85-летию со дня рождения В.Б. Кудрявцева. В приложении – первое информационное письмо.

В среду, 13 октября, на заседании кафедрального семинара "Теория автоматов" под руководством академика В. Б. Кудрявцева состоится доклад Р. А. Ищенко "Восстановление диаграммы переходов автомата по его графу".

Заседание состоится в 18-30 в смешанном формате. Очная часть будет проведена в аудитории 1201 (кафедра МаТИС), дистанционная – в zoom-конференции:

https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09

Meeting ID: 886 6514 1982
Passcode: 965515

Анонс доклада:

Если мы сотрем все отметки на ребрах диаграммы Мура, то получим ориентированный граф. Обратная задача гораздо сложнее. В докладе рассматривается вопрос, в каких случаях ребра ориентированного графа можно разметить так, чтобы получить диаграмму Мура автомата заданного класса (группового, дефинитного, абелевого), оценить число решений этой задачи, а также получить условия, когда такое восстановление единственно и существует эффективный алгоритм для осуществления данной разметки.

1-9 ноября 2021 в университете Сириус (г. Сочи) состоится студенческая школа "Формальные методы дизайна и верификации программного обеспечения", подробности можно найти на странице https://sochisirius.ru/obuchenie/graduates/smena1089/5250.

Описание учебной программы можно найти по адресу https://docs.google.com/document/d/1olGc2eUTwFKynSGaw73NrrwrRkOWxtXR/edit?usp=sharing&ouid=105126782492556654297&rtpof=true&sd=true.

Школа проводится при поддержке Междисциплинарной научно-образовательной школы МГУ «Мозг, когнитивные системы, искусственный интеллект».

Участие в школе бесплатное, включая перелет из Москвы в Сочи и обратно.

Уважаемые слушатели и потенциальные участники нового набора программы SHARE 2021-2023!

Онлайн презентация программы SHARE 2021-2023 пройдет 30 сентября в 17.00. Для участия в презентации, пожалуйста, заполните анкету на Timepad.

Ссылка на подключение к онлайн-встрече будет выслана на указанный Вами в анкете e-mail.

Заполнить анкету для участия в конкурсном отборе на программу SHARE 2021-2023 можно до 2 октября 18.00 по ссылке: https://forms.yandex.ru/b2b/61449a6ea334c3fe7b462fd4/.

По всем организационным вопросам просьба писать на почту SHARE@intsys.msu.ru либо в Telegram ответственному секретарю программы, Кочетковой Татьяне, +79255976919

В четверг, 23 сентября в 16:45 на спецсеминаре «Теория дискретных функций и приложения» под руководством проф. Бабина Д.Н. и с.н.с. Мазуренко И.Л. состоится доклад Д.А. Шачнева «Методы поиска экспертов в CRIS-системах с учётом тематической принадлежности и значимости результатов». Доклад о работающей системе автоматической обработки естественных языков.

Код конференции:
https://us04web.zoom.us/j/4528320761?pwd=cWo0SWpKUUxnRUxJWWlrMzhkOG1udz09.

В среду, 22 сентября в 15:00 на семинаре "Вопросы сложности алгоритмов поиска" под руководством д.ф.-м.н, профессора Гасанова Э.Э. с докладом "Построение кратчайшего пути клеточными автоматами с локаторами при наличии препятствий" выступит Артем Пропажин.

Форма проведения – онлайн (zoom):
https://us02web.zoom.us/j/9423397823?pwd=NS90YzgyVUxrL3VtaTB1M0xKdFlsdz09
Идентификатор конференции: 942 339 7823
Код доступа: 944214

В среду, 22 сентября, на заседании кафедрального семинара "Теория автоматов" под руководством академика В. Б. Кудрявцева состоится доклад Д. В. Ронжина "О полноте в классе линейных автоматов, функционирующих над бесконечными структурами".

Заседание состоится в 18-30 в смешанном формате. Очная часть будет проведена в аудитории 1201 (кафедра МаТИС), дистанционная – в zoom-конференции

Meeting ID: 848 7171 6165
Passcode: 495724

Анонс доклада:
В докладе будут представлены результаты исследования вопросов полноты по операциям суперпозиции (S) и композиции (K), а также А-замыкания в классе линейных автоматов, функционирующих над полем рациональных чисел и кольцом двоично-рациональных чисел. В случае поля рациональных чисел показано отсутствие конечных К-полных систем, а также наличие счетных К-полных и S-полных систем. Также показано наличие S-полных систем, не содержащих базиса. В случае двоично-рациональных чисел выделен счетный набор А-предполных классов, и в терминах данных классов сформулированы условия А-полноты систем линейных автоматов с добавками. Исследован вопрос алгоритмической разрешимости проверки непринадлежности конечных систем линейных автоматов найденным А-предполным классам, а также вопросы конечной порожденности по операциям А-замыкания упомянутых А-предполных классов.

15 сентября в 15:00 на семинаре "Вопросы сложности алгоритмов поиска" под руководством д.ф.-м.н, профессора Гасанова Э.Э. состоится доклад выпускника кафедры МаТИС Ронжина Дмитрия Владимировича.

Тема доклада: .Линейные автоматы над подкольцами рациональных чисел.

Аннотация: Одной из классических задач теории автоматов является задача проверки полноты конечных автоматных систем по заданным операциям замыкания. Известно, что на множестве конечных автоматов задачи проверки конечных автоматных систем на А-полноту и К-полноту являются алгоритмически неразрешимыми, однако в случае линейных автоматов, функционирующих над конечными полями Часовских Анатолием Александровичем было показано, что эти же задачи являются алгоритмически разрешимыми.

В докладе будут представлены результаты исследования автором вопросов полноты и выразимости в классе линейных автоматов, функционирующих над некоторыми бесконечными структурами – полем рациональных и кольцом двоично-рациональных чисел. Будут сформулированы условия полноты для конечных систем с добавками по операциям композиции, суперпозиции и А-замыкания.

Форма проведения – онлайн (zoom):
https://us02web.zoom.us/j/9423397823?pwd=NS90YzgyVUxrL3VtaTB1M0xKdFlsdz09
Идентификатор конференции: 942 339 7823
Код доступа: 944214