Просеминар для 2-го курса — различия между версиями
Материал из Кафедра математической кибернетики
(→Сложность функций алгебры логики в классах полиномиальных форм) |
PodymovVV (обсуждение | вклад) |
||
| (не показаны 29 промежуточные версии 4 участников) | |||
| Строка 1: | Строка 1: | ||
| + | {{DISPLAYTITLE:Просеминар для 2-го курса "Избранные вопросы дискретной математики и математической кибернетики"}} | ||
| + | |||
| + | '''Информация о просеминаре 2023-2024 учебного года.''' | ||
| + | |||
| + | = Общая информация = | ||
| + | |||
Просеминар предназначен для знакомства студентов 2 курса с основными направлениями и наиболее интересными результатами проводимых на кафедре и в лаборатории исследований в области дискретной математики, теории графов, сложности алгоритмов, теории синтеза, надёжности и контроля дискретных управляющих систем, а также с применением этих результатов при решении некоторых задач проектирования СБИС и программирования. | Просеминар предназначен для знакомства студентов 2 курса с основными направлениями и наиболее интересными результатами проводимых на кафедре и в лаборатории исследований в области дискретной математики, теории графов, сложности алгоритмов, теории синтеза, надёжности и контроля дискретных управляющих систем, а также с применением этих результатов при решении некоторых задач проектирования СБИС и программирования. | ||
| − | Просеминар | + | Просеминар проводится в форме независимых лекций-семинаров, на которые приглашаются все заинтересованные студенты 1 и 2 курсов. |
| + | Предварительных знаний не требуется. | ||
| + | Занятия проходят '''по пятницам с 16:20 до 17:55 в ауд. 579'''. | ||
| + | Первое занятие - 16.02.2024. | ||
| + | <!-- <span style="background:#FFDDDD">28</span> --> | ||
| + | |||
| + | [[Информация для 2 курса|Общая информация о кафедре для студентов 2 курса бакалавриата.]] | ||
| + | |||
| + | = Программа просеминара = | ||
| + | |||
| + | '''Оптимальная структурная реализация булевых функций и графов в некоторых моделях''' | ||
| + | |||
| + | * Докладчик: [[Ложкин Сергей Андреевич|С.А. Ложкин]] | ||
| + | * Дата: 16.02.2024 и 01.03.2024. | ||
| + | |||
| + | <span style="background:#FFDDDD"> | ||
| + | '''Временные автоматы и их эквивалентность''' | ||
| + | </span> | ||
| + | |||
| + | * <span style="background:#FFDDDD">Докладчик:</span> [[Подымов Владислав Васильевич |В.В. Подымов]] | ||
| + | * Дата: 15.03.2024. | ||
| + | * Доклад посвящён разновидности автоматов, выполняющихся в условиях "непрерывно текущего" реального времени и предназначенных для моделирования и анализа вычислительных систем, компоненты которых имеют директивные сроки выполнения своих подзадач. Для этих автоматов будут обсуждаться некоторые результаты, касающиеся проверки их эквивалентности (схожести поведения) - относительно давние и относительно свежие, полученные докладчиком и не только. | ||
| + | |||
| + | = Материалы докладов прошлых лет = | ||
| + | |||
| + | == 2023 == | ||
| + | |||
| + | '''Сложность проверки свойств функций алгебры логики, заданных полиномами Жегалкина.''' | ||
| + | |||
| + | * Докладчик: [[Селезнева Светлана Николаевна |Селезнева С.Н.]] | ||
| + | * Дата: 04.04.2023. | ||
| + | * Аннотация: При решении прикладных задач часто возникает необходимость в проверке свойств функций алгебры логики. При этом функции заданы определенным образом, в частности, нормальными формами. Одним из таких представлений являются полиномы Жегалкина. В докладе будут рассмотрены свойства монотонности, четности, периодичности, уравновешенности функции алгебры логики и показано, с какой сложностью можно проверить эти свойства функции по ее полиному Жегалкина. | ||
| + | |||
| + | '''Прикладные задачи автоматизации проектирования интегральных схем.''' | ||
| + | |||
| + | * Докладчик: [[Шуплецов Михаил Сергеевич |Шуплецов М.С.]] | ||
| + | * Дата: 28.03.2023. | ||
| + | * Аннотация: При решении задача проектирования интегральных схем возникает спектр прикладных математических задач из области дискретной математики и математической кибернетики. В докладе будут рассмотрены некоторые задачи, которые возникают на этапе логического проектирования интегральной схемы, а также некоторые задачи, связанные с верификацией схем. | ||
| − | + | '''Проблемы сложности, надежности и контроля на примере реализации линейной и некоторых других булевых функций в модели контактных схем и BDD.''' | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | * Докладчик: [[Ложкин Сергей Андреевич|Ложкин С.А.]] | |
| − | + | * Дата: 21.03.2023. | |
| − | *Докладчик: | + | * Аннотация: Решение основных проблем и задач теории дискретных управляющих систем, указанных в теме семинара, будет рассмотрено на примере счетчика четности, то есть суммы по модулю 2 заданного числа булевых переменных, при его реализации в классах контактных схем, являющихся моделью транзисторного уровня современных сверхбольших интегральных схем, и BDD. Для счетчика четности будут построены: минимальная контактная схема и близкий к минимальному тест, диагностирующий обрыв одного из ее контактов; минимальная схема, корректирующая обрыв одного контакта. |
| − | *Дата: 21 | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | *Аннотация: Решение основных проблем и задач теории дискретных управляющих систем, указанных в теме семинара, будет рассмотрено на примере счетчика четности, то есть суммы по модулю 2 заданного числа булевых переменных, при его реализации в | + | |
| − | + | ||
| − | + | '''Сложность алгоритмов на графах.''' | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | * Докладчик: [[Алексеев Валерий Борисович|Алексеев В.Б.]] | |
| − | * | + | * Дата: 14.03.2023. |
| − | *Дата: | + | * Аннотация: быстрый алгоритм транзитивного замыкания графа, быстрый приближенный алгоритм для поиска минимального вершинного покрытия, эйлеровы и гамильтоновы циклы, задача коммивояжера. |
| − | + | ||
| − | + | ||
| − | * | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | '''Оптимальная реализация некоторых монотонных симметрических функций формулами на основе двоичных кодов.''' | |
| − | + | ||
| − | + | * Докладчик: [[Ложкин Сергей Андреевич|Ложкин С.А.]] | |
| + | * Дата: 07.03.2023. | ||
| + | * [[Media: Proseminar 2023.03.07 annotation.pdf|Аннотация]]. | ||
| − | + | '''Сложность алгебраических вычислений - примеры быстрых алгоритмов и нерешенные задачи.''' | |
| − | + | * Докладчик: [[Алексеев Валерий Борисович|Алексеев В.Б.]] | |
| + | * Дата: 28.02.2023. | ||
| + | * Аннотация: Будет рассказано про нерешенную до конца («зависшую») проблему быстрого умножения матриц, про неожиданный алгоритм Штрассена для этой задачи и его обобщения, про следствия для быстрых алгоритмов на графах и в целом про сложность алгебраических вычислений. | ||
| − | + | == 2016 == | |
| − | + | [[Media:2016_Proseminar_FPGA.pdf|Программируемые логические интегральные схемы.]] (2016, [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]]) | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| + | [[Media:Proseminar_2016_Marchenko.pdf| Математические методы проектирования топологии СБИС.]] (2016, бывш. сотр. Марченко А.М.) | ||
| − | [[ | + | [[Media:Prosem_2016_Podymov_Zakharov.pdf| Дискретные модели и задачи управления компьютерными сетями.]] (2016, [[Захаров Владимир Анатольевич|Захаров В.А.]] и [[Подымов Владислав Васильевич|Подымов В.В.]]) |
Текущая версия на 19:09, 12 марта 2024
Информация о просеминаре 2023-2024 учебного года.
Содержание
Общая информация
Просеминар предназначен для знакомства студентов 2 курса с основными направлениями и наиболее интересными результатами проводимых на кафедре и в лаборатории исследований в области дискретной математики, теории графов, сложности алгоритмов, теории синтеза, надёжности и контроля дискретных управляющих систем, а также с применением этих результатов при решении некоторых задач проектирования СБИС и программирования.
Просеминар проводится в форме независимых лекций-семинаров, на которые приглашаются все заинтересованные студенты 1 и 2 курсов. Предварительных знаний не требуется. Занятия проходят по пятницам с 16:20 до 17:55 в ауд. 579. Первое занятие - 16.02.2024.
Общая информация о кафедре для студентов 2 курса бакалавриата.
Программа просеминара
Оптимальная структурная реализация булевых функций и графов в некоторых моделях
- Докладчик: С.А. Ложкин
- Дата: 16.02.2024 и 01.03.2024.
Временные автоматы и их эквивалентность
- Докладчик: В.В. Подымов
- Дата: 15.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, Захаров В.А. и Подымов В.В.)
