Просеминар для 2-го курса — различия между версиями

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

Текущая версия на 19:09, 12 марта 2024


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

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

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

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

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

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

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

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

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

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

2023

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

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

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

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

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

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

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

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

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

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

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

2016

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

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

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