Просеминар для 2-го курса — различия между версиями
(→Программа просеминара) |
PodymovVV (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
= Программа просеминара = | = Программа просеминара = | ||
| − | '''Сложность | + | '''Сложность проверки свойств функций алгебры логики, заданных полиномами Жегалкина.''' |
| − | * Докладчик: [[ | + | * Докладчик: [[Селезнева Светлана Николаевна |Селезнева С.Н.]] |
| − | * Дата: 28 | + | * Дата: 28 марта. |
| − | * Аннотация: | + | * Аннотация: При решении прикладных задач часто возникает необходимость в проверке свойств функций алгебры логики. При этом функции заданы определенным образом, в частности, нормальными формами. Одним из таких представлений являются полиномы Жегалкина. В докладе будут рассмотрены свойства монотонности, четности, периодичности, уравновешенности функции алгебры логики и показано, с какой сложностью можно проверить эти свойства функции по ее полиному Жегалкина. |
| − | ''' | + | '''Проблемы сложности, надежности и контроля на примере реализации линейной и некоторых других булевых функций в модели контактных схем и BDD.''' |
* Докладчик: [[Ложкин Сергей Андреевич|Ложкин С.А.]] | * Докладчик: [[Ложкин Сергей Андреевич|Ложкин С.А.]] | ||
| − | * Дата: | + | * Дата: 21 марта. |
| − | * | + | * Аннотация: Решение основных проблем и задач теории дискретных управляющих систем, указанных в теме семинара, будет рассмотрено на примере счетчика четности, то есть суммы по модулю 2 заданного числа булевых переменных, при его реализации в классах контактных схем, являющихся моделью транзисторного уровня современных сверхбольших интегральных схем, и BDD. Для счетчика четности будут построены: минимальная контактная схема и близкий к минимальному тест, диагностирующий обрыв одного из ее контактов; минимальная схема, корректирующая обрыв одного контакта. |
'''Сложность алгоритмов на графах.''' | '''Сложность алгоритмов на графах.''' | ||
| Строка 33: | Строка 33: | ||
* Аннотация: быстрый алгоритм транзитивного замыкания графа, быстрый приближенный алгоритм для поиска минимального вершинного покрытия, эйлеровы и гамильтоновы циклы, задача коммивояжера. | * Аннотация: быстрый алгоритм транзитивного замыкания графа, быстрый приближенный алгоритм для поиска минимального вершинного покрытия, эйлеровы и гамильтоновы циклы, задача коммивояжера. | ||
| − | ''' | + | '''Оптимальная реализация некоторых монотонных симметрических функций формулами на основе двоичных кодов.''' |
* Докладчик: [[Ложкин Сергей Андреевич|Ложкин С.А.]] | * Докладчик: [[Ложкин Сергей Андреевич|Ложкин С.А.]] | ||
| − | * Дата: | + | * Дата: 7 марта. |
| − | * | + | * [[Media: Proseminar 2023.03.07 annotation.pdf|Аннотация]]. |
| − | '''Сложность | + | '''Сложность алгебраических вычислений - примеры быстрых алгоритмов и нерешенные задачи.''' |
| − | * Докладчик: [[ | + | * Докладчик: [[Алексеев Валерий Борисович|Алексеев В.Б.]] |
| − | * Дата: 28 | + | * Дата: 28 февраля. |
| − | * Аннотация: | + | * Аннотация: Будет рассказано про нерешенную до конца («зависшую») проблему быстрого умножения матриц, про неожиданный алгоритм Штрассена для этой задачи и его обобщения, про следствия для быстрых алгоритмов на графах и в целом про сложность алгебраических вычислений. |
= Материалы докладов прошлых лет = | = Материалы докладов прошлых лет = | ||
Версия 13:30, 26 марта 2023
Информация о просеминаре 2022-2023 учебного года.
Общая информация
Просеминар предназначен для знакомства студентов 2 курса с основными направлениями и наиболее интересными результатами проводимых на кафедре и в лаборатории исследований в области дискретной математики, теории графов, сложности алгоритмов, теории синтеза, надёжности и контроля дискретных управляющих систем, а также с применением этих результатов при решении некоторых задач проектирования СБИС и программирования.
Просеминар начинает свою работу с 28.02.2023 и проводится в форме независимых лекций-семинаров, на которые приглашаются все заинтересованные студенты 1 и 2 курсов. Предварительных знаний не требуется.
Занятия проходят по вторникам с 16:20 до 17:55 в ауд. 503. На первых семинарах 28 февраля и 7 марта с общей информацией о научной тематике кафедры, а также с интересными примерами решаемых задач выступят зав. кафедрой профессор С.А.Ложкин и профессор В.Б.Алексеев.
Общая информация о кафедре для студентов 2 курса бакалавриата.
Программа просеминара
Сложность проверки свойств функций алгебры логики, заданных полиномами Жегалкина.
- Докладчик: Селезнева С.Н.
- Дата: 28 марта.
- Аннотация: При решении прикладных задач часто возникает необходимость в проверке свойств функций алгебры логики. При этом функции заданы определенным образом, в частности, нормальными формами. Одним из таких представлений являются полиномы Жегалкина. В докладе будут рассмотрены свойства монотонности, четности, периодичности, уравновешенности функции алгебры логики и показано, с какой сложностью можно проверить эти свойства функции по ее полиному Жегалкина.
Проблемы сложности, надежности и контроля на примере реализации линейной и некоторых других булевых функций в модели контактных схем и BDD.
- Докладчик: Ложкин С.А.
- Дата: 21 марта.
- Аннотация: Решение основных проблем и задач теории дискретных управляющих систем, указанных в теме семинара, будет рассмотрено на примере счетчика четности, то есть суммы по модулю 2 заданного числа булевых переменных, при его реализации в классах контактных схем, являющихся моделью транзисторного уровня современных сверхбольших интегральных схем, и BDD. Для счетчика четности будут построены: минимальная контактная схема и близкий к минимальному тест, диагностирующий обрыв одного из ее контактов; минимальная схема, корректирующая обрыв одного контакта.
Сложность алгоритмов на графах.
- Докладчик: Алексеев В.Б.
- Дата: 14 марта.
- Аннотация: быстрый алгоритм транзитивного замыкания графа, быстрый приближенный алгоритм для поиска минимального вершинного покрытия, эйлеровы и гамильтоновы циклы, задача коммивояжера.
Оптимальная реализация некоторых монотонных симметрических функций формулами на основе двоичных кодов.
- Докладчик: Ложкин С.А.
- Дата: 7 марта.
- Аннотация.
Сложность алгебраических вычислений - примеры быстрых алгоритмов и нерешенные задачи.
- Докладчик: Алексеев В.Б.
- Дата: 28 февраля.
- Аннотация: Будет рассказано про нерешенную до конца («зависшую») проблему быстрого умножения матриц, про неожиданный алгоритм Штрассена для этой задачи и его обобщения, про следствия для быстрых алгоритмов на графах и в целом про сложность алгебраических вычислений.
Материалы докладов прошлых лет
Программируемые логические интегральные схемы. (2016, Шуплецов М.С.)
Математические методы проектирования топологии СБИС. (2016, бывш. сотр. Марченко А.М.)
Дискретные модели и задачи управления компьютерными сетями. (2016, Захаров В.А. и Подымов В.В.)
