Просеминар для 2-го курса
Просеминар предназначен для знакомства студентов 2 курса с основными направлениями и наиболее интересными результатами проводимых на кафедре и в лаборатории исследований в области дискретной математики, теории графов, сложности алгоритмов, теории синтеза, надёжности и контроля дискретных управляющих систем, а также с применением этих результатов при решении некоторых задач проектирования СБИС и программирования.
Просеминар начинает свою работу с 14 марта и проводится в форме независимых лекций-семинаров, на которые приглашаются все заинтересованные студенты 1 и 2 курсов. Предварительных знаний не требуется.
Занятия проходят по понедельникам с 16:20 до 17:55, в ауд. 504. На первом семинаре 14 марта с общей информацией о научной тематике кафедры и лаборатории, а также с интересными примерами решаемых задач выступят зав. кафедрой профессор В.Б.Алексеев и зав. лабораторией профессор С.А.Ложкин.
Содержание
- 1 Научно-образовательные направления кафедры
- 2 Программа просеминара
- 2.1 Представление функций суперпозициями
- 2.2 Проблемы сложности булевых функций. Задачи синтеза, надежности и контроля дискретных управляющих систем.
- 2.3 Сложность функций алгебры логики в классах полиномиальных форм
- 2.4 Математические задачи автоматизации проектирования интегральных схем
- 2.5 Некоторые комбинаторные задачи. Дискретные модели и задачи управления компьютерными сетями
- 2.6 Общая встреча с кафедрой математической кибернетики
Научно-образовательные направления кафедры
Программа просеминара
Представление функций суперпозициями
- Докладчик: Марченков С.С.
- Дата: 21 марта.
Проблемы сложности булевых функций. Задачи синтеза, надежности и контроля дискретных управляющих систем.
- Докладчики: Ложкин С.А., Романов Д.С., Шуплецов М.С.
- Дата: 28 марта.
- Аннотация: Решение основных проблем и задач теории дискретных управляющих систем, указанных в теме семинара, будет рассмотрено на примере счетчика четности, то есть суммы по модулю 2 заданного числа булевых переменных, при его реализации в классе контактных схем, являющихся моделью транзисторного уровня современных СБИС. Для счетчика четности будут построены: минимальная контактная схема и близкий к минимальному тест, диагностирующий обрыв одного из её контактов; минимальная схема, корректирующая обрыв одного контакта. На семинаре будет проведена демонстрация проектирования простой дискретной управляющей системы с использованием программируемых логических схем компании Altera.
- Презентация доклада
Сложность функций алгебры логики в классах полиномиальных форм
- Докладчик: Селезнева С.Н.
- Дата: 4 апреля.
- Аннотация: Полиномиальной нормальной формой (ПНФ) называется сумма по модулю два произведений переменных либо их отрицаний. Длина ПНФ - число ее слагаемых. В докладе будет рассказано красивое решение задачи оценки длины ПНФ для произвольной функции алгебры логики. В этом решении ПНФ строится по комбинаторному множеству на n-мерном кубе. Следует отметить, что ПНФ, как и ДНФ, применяются при проектировании интегральных схем.
Математические задачи автоматизации проектирования интегральных схем
- Докладчики: Марченко А.М., Мелик-Адамян А.Ф.
- Дата: 11 апреля.
- Аннотация: Программно-аппаратная реализация и, в частности, проектирование современных СБИС представляет собой сложную комплексную задачу, успешное решение которой требует глубоких знаний в области теории дискретных управляющих систем, сложности вычислений, программирования и др., а также навыков их практического применения. Авторы доклада, которые сочетают преподавание на кафедре с работой в фирмах Mentor Graphics и Intel, расскажут о тематике научных исследований, проводимых в данном направлении, в том числе силами студентов и аспирантов.
- Презентация доклада: Марченко А.М. Математические методы проектирования топологии СБИС
Некоторые комбинаторные задачи. Дискретные модели и задачи управления компьютерными сетями
- Докладчики: Сапоженко А.А., Захаров В.А., Подымов В.В.
- Дата: 18 апреля.
- Семинар состоит из двух независимых частей.
- Аннотация первой части: Будет рассмотрена классическая задача комбинаторики, информатики и теории сложности — задача о покрытии: для заданного множества и семейства его подмножеств найти минимальное подсемейство, в объединении дающее все множество. Будет рассмотрен градиентный (жадный) алгоритм решения этой задачи, приведена его верхняя оценка сложности. Будут рассмотрены "трудные" для жадного алгоритма случаи.
- Аннотация второй части: Из-за своей распределенной природы компьютерная сеть оказывается необычайно трудным для анализа объектом. Анализ "классических" компьютерных сетей осложняется еще и разнородностью и независимостью устройств в узлах сети. Это одна из причин нарастающей популярности программно-конфигурируемых сетей (ПКС) — сетей с централизованным управлением, единообразными устройствами в узлах и строгим разделением управления и передачи данных. На семинаре будут обсуждаться две задачи анализа ПКС. Первая — задача верификации: для математической модели сети строго проверить соблюдение требований, предъявляемых к поведению сети. Вторая — задача реконфигурации: предоставить безопасный способ изменения конфигурации сети, отвечающий изменяющимся требованиям.
Общая встреча с кафедрой математической кибернетики
25 апреля в ауд. ___ пройдет общая встреча студентов 2-го курса с преподавателями кафедры математической кибернетики, начало в 16:20.