Научно-исследовательский семинар "Избранные главы дискретной математики"

2020/2021

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

Статус: Дисциплина общефакультетского пула

Кто читает: Факультет математики

Где читается: Факультет математики

Когда читается: 3, 4 модуль

Преподаватели: Артамкин Игорь Вадимович

Язык: русский

Кредиты: 3

Контактные часы: 36

Полная версия программы учебной дисциплины

Аннотация

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

Цель освоения дисциплины

Рассмотреть задачи дискретной математики, имеющие заметное значение как в математике, так и в приложениях.

Планируемые результаты обучения

Может придумать функцию от двух переменных, через которую можно выразить любую функцию.
Умеет строить длинные периодические последовательности
Умеет решать задачи о максимальном потоке в транспортной сети

Содержание учебной дисциплины

Булевы функции и теорема Поста о функциональной полноте
Эта теорема даёт эффективный ответ на следующий вопрос: можно ли любую булеву функцию (от любого числа переменных) выразить с помощью операции композиции через заданный набор функций. Удивительно, что на такой вопрос имеется простой и содержательный ответ, позволяющий, например, придумать функцию от двух переменных, через которую можно выразить любую функцию.
Конечные поля
Теорема о том, что мультипликативная группа конечного поля является циклической, позволяет строить длинные периодические последовательности, повсеместно используемые в радиолокации, системах опознавания «свой-чужой» и т.д.
Теорема Форда – Фалкерсона о максимальном потоке в транспортной сети
Речь идет о такой задаче: имеется некоторая сеть дорог (трубопроводов), соединяющих пункты А и Б. У каждой дороги (трубы) есть своя максимальная пропускная способность — наибольшее число автомобилей (баррелей нефти) которые могут пройти по этой дороге (трубе) за час. Требуется организовать движение (перекачку нефти) таким образом, чтобы общее число автомобилей (баррелей нефти), попадающее за час из А в Б, было максимально возможным. Оказывается, многие важные результаты и алгоритмы теории графов, как прикладные, так и чисто математические, связаны с этим кругом идей

Элементы контроля

ИДЗ (индивидуальное домашнее задание)
Решение дополнительных задач на семинаре

Промежуточная аттестация

Промежуточная аттестация (4 модуль)
Итог = Х + MAX(0, Х-5)*(3-MAX(0, Х-5))*У*1/2 .Х --- оценка за ИДЗ (от 0 до 7); У --- баллы за решение дополнительных задач.

Программа дисциплины