• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
2019/2020

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

Статус: Дисциплина общефакультетского пула
Когда читается: 3, 4 модуль
Язык: русский
Кредиты: 3
Контактные часы: 36

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

Аннотация

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

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

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

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

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

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

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

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

  • неблокирующий ИДЗ (индивидуальное домашнее задание)
  • неблокирующий Решение дополнительных задач на семинаре
Промежуточная аттестация

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

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

Список литературы

Рекомендуемая основная литература

  • Лекции о производящих функциях, Ландо, С. К., 2007

Рекомендуемая дополнительная литература

  • Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. - Бинарные отношения, графы и коллективные решения - Издательство "Физматлит" - 2012 - 344с. - ISBN: 978-5-9221-1363-2 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/59762
  • Бинарные отношения, графы и коллективные решения : учеб. пособие, Алескеров, Ф. Т., Хабина, Э. Л., 2012