Просеминар для 2-го курса "Избранные вопросы дискретной математики и математической кибернетики"
Информация о просеминаре 2022-2023 учебного года.
Общая информация
Просеминар предназначен для знакомства студентов 2 курса с основными направлениями и наиболее интересными результатами проводимых на кафедре и в лаборатории исследований в области дискретной математики, теории графов, сложности алгоритмов, теории синтеза, надёжности и контроля дискретных управляющих систем, а также с применением этих результатов при решении некоторых задач проектирования СБИС и программирования.
Просеминар начинает свою работу с 28.02.2023 и проводится в форме независимых лекций-семинаров, на которые приглашаются все заинтересованные студенты 1 и 2 курсов. Предварительных знаний не требуется.
Занятия проходят по вторникам с 16:20 до 17:55 в ауд. 503. На первых семинарах 28 февраля и 7 марта с общей информацией о научной тематике кафедры, а также с интересными примерами решаемых задач выступят зав. кафедрой профессор С.А.Ложкин и профессор В.Б.Алексеев.
Общая информация о кафедре для студентов 2 курса бакалавриата.
Программа просеминара
Сложность алгебраических вычислений - примеры быстрых алгоритмов и нерешенные задачи.
- Докладчик: Алексеев В.Б.
- Дата: 28 февраля.
- Аннотация: Будет рассказано про нерешенную до конца («зависшую») проблему быстрого умножения матриц, про неожиданный алгоритм Штрассена для этой задачи и его обобщения, про следствия для быстрых алгоритмов на графах и в целом про сложность алгебраических вычислений.
Оптимальная реализация некоторых монотонных симметрических функций формулами на основе двоичных кодов.
- Докладчик: Ложкин С.А.
- Дата: 7 марта.
- Аннотация.
Сложность алгоритмов на графах.
- Докладчик: Алексеев В.Б.
- Дата: 14 марта.
- Аннотация: быстрый алгоритм транзитивного замыкания графа, быстрый приближенный алгоритм для поиска минимального вершинного покрытия, эйлеровы и гамильтоновы циклы, задача коммивояжера.
Проблемы сложности, надежности и контроля на примере реализации линейной и некоторых других булевых функций в модели контактных схем и BDD.
- Докладчик: Ложкин С.А.
- Дата: 21 марта.
- Аннотация: Решение основных проблем и задач теории дискретных управляющих систем, указанных в теме семинара, будет рассмотрено на примере счетчика четности, то есть суммы по модулю 2 заданного числа булевых переменных, при его реализации в классах контактных схем, являющихся моделью транзисторного уровня современных сверхбольших интегральных схем, и BDD. Для счетчика четности будут построены: минимальная контактная схема и близкий к минимальному тест, диагностирующий обрыв одного из ее контактов; минимальная схема, корректирующая обрыв одного контакта.
Сложность проверки свойств функций алгебры логики, заданных полиномами Жегалкина.
- Докладчик: Селезнева С.Н.
- Дата: 28 марта.
- Аннотация: При решении прикладных задач часто возникает необходимость в проверке свойств функций алгебры логики. При этом функции заданы определенным образом, в частности, нормальными формами. Одним из таких представлений являются полиномы Жегалкина. Будут рассмотрены свойства монотонности, четности, периодичности, уравновешенности функции алгебры логики и показано, с какой сложностью можно проверить эти свойства функции по ее полиному Жегалкина.
Материалы докладов прошлых лет
Программируемые логические интегральные схемы. (2016, Шуплецов М.С.)
Математические методы проектирования топологии СБИС. (2016, бывш. сотр. Марченко А.М.)
Дискретные модели и задачи управления компьютерными сетями. (2016, Захаров В.А. и Подымов В.В.)
