Текущая версия на 14:23, 18 февраля 2025

Информация о просеминаре в весеннем семестре 2024-2025 учебного года.

Общая информация

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

Просеминар проводится в форме независимых лекций-семинаров, на которые приглашаются все заинтересованные студенты 1 и 2 курсов. Предварительных знаний не требуется. Занятия проходят по пятницам с 16:20 до 17:55 в ауд. 579. Первое занятие - 21.02.2025.

Общая информация о кафедре для студентов 2 курса бакалавриата.

Программа просеминара

Задачи структурной реализации дискретных функций в некоторых классах графов

• Докладчик: С.А. Ложкин
• Дата: 21.02.2025.
• Решение основных задач теории дискретных управляющих систем будет рассмотрено на примере дешифратора, т.е. системы из всех элементарных конъюнкций ранга n от n булевых переменных, n = 1, 2, ... . Для него будет построена асимптотически минимальная по сложности схема из функциональных элементов в стандартном базисе, а также асимптотически минимальная по площади клеточная схема, являющаяся математической моделью сверхбольших интегральных схем (СБИС).

Временные автоматы и их эквивалентность

• Докладчик: В.В. Подымов
• Дата: 28.02.2025.
• Доклад посвящён разновидности автоматов, выполняющихся в условиях "непрерывно текущего" реального времени и предназначенных для моделирования и анализа вычислительных систем, компоненты которых имеют директивные сроки выполнения своих подзадач. Для этих автоматов будут обсуждаться некоторые результаты, касающиеся проверки их эквивалентности (схожести поведения) - относительно давние и относительно свежие, полученные докладчиком и не только.

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

Материалы докладов прошлых лет

2024

Оптимальная структурная реализация булевых функций и графов в некоторых моделях

• Докладчик: С.А. Ложкин
• Дата: 16.02.2024 и 01.03.2024.

2023

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

• Докладчик: Селезнева С.Н.
• Дата: 04.04.2023.
• Аннотация: При решении прикладных задач часто возникает необходимость в проверке свойств функций алгебры логики. При этом функции заданы определенным образом, в частности, нормальными формами. Одним из таких представлений являются полиномы Жегалкина. В докладе будут рассмотрены свойства монотонности, четности, периодичности, уравновешенности функции алгебры логики и показано, с какой сложностью можно проверить эти свойства функции по ее полиному Жегалкина.

Прикладные задачи автоматизации проектирования интегральных схем.

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

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

• Докладчик: Ложкин С.А.
• Дата: 21.03.2023.
• Аннотация: Решение основных проблем и задач теории дискретных управляющих систем, указанных в теме семинара, будет рассмотрено на примере счетчика четности, то есть суммы по модулю 2 заданного числа булевых переменных, при его реализации в классах контактных схем, являющихся моделью транзисторного уровня современных сверхбольших интегральных схем, и BDD. Для счетчика четности будут построены: минимальная контактная схема и близкий к минимальному тест, диагностирующий обрыв одного из ее контактов; минимальная схема, корректирующая обрыв одного контакта.

Сложность алгоритмов на графах.

• Докладчик: Алексеев В.Б.
• Дата: 14.03.2023.
• Аннотация: быстрый алгоритм транзитивного замыкания графа, быстрый приближенный алгоритм для поиска минимального вершинного покрытия, эйлеровы и гамильтоновы циклы, задача коммивояжера.

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

• Докладчик: Ложкин С.А.
• Дата: 07.03.2023.
• Аннотация.

Сложность алгебраических вычислений - примеры быстрых алгоритмов и нерешенные задачи.

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

2016

Программируемые логические интегральные схемы. (2016, Шуплецов М.С.)

Математические методы проектирования топологии СБИС. (2016, бывш. сотр. Марченко А.М.)

Дискретные модели и задачи управления компьютерными сетями. (2016, Захаров В.А. и Подымов В.В.)