• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2021/2022

Дискретная математика

Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус: Курс обязательный (Прикладная математика и информатика)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 1-й курс, 1, 2, 4 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Преподаватели: Близнец Иван Анатольевич, Мокеев Александр Сергеевич, Москвин Денис Николаевич, Мухин Михаил Сергеевич, Омельченко Александр Владимирович, Подкопаев Антон Викторович, Федоркина Мария Олеговна, Ямщиков Иван Павлович
Язык: русский
Кредиты: 3
Контактные часы: 84

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

Аннотация

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

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

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

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

  • Знает основные понятия и факты теории графов, такие, как деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы, классические и обобщенные постановки комбинаторных задач, комбинаторный смысл основных операций над производящими функциями.
  • Умеет находить кратчайшие и минимальные пути в графе, медианы и центры графа, остовные деревья, эйлеровы и гамильтоновы циклы, совершенные или максимальные паросочетания, оптимальную раскраску графа, решать линейные рекуррентные соотношения как с помощью производящих функций, так и без них, перечислять основные дискретные объекты (графы, деревья, плоские деревья).
  • Имеет навыки использования методов решения основных комбинаторных задач с помощью производящих функций, использования основных алгоритмов работы с графами.
Содержание учебной дисциплины

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

  • Раздел 1. Элементарная комбинаторика и теория графов
  • Раздел 2. Остовные деревья, циклы и разрезы. Связность в графах
  • Раздел 3. Паросочетания в графах. Раскраска графов. Планарные графы.
  • Раздел 4. Производящие функции и перечисление дискретных структур.
Элементы контроля

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

  • неблокирующий Домашнее задание
    Домашнее задание выдается студентам в одном варианте и состоит из 9-10 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма предоставления обучающимися домашнего задания - представленные в письменном виде решения задач.
  • неблокирующий Контрольная работа
    Контрольная работа проводится в письменной форме. Каждый студент получает список из 5 задач. Для получения положительной оценки он должен решить не менее трех из них. На проведение контрольной работы отводится 1,5 часа.
  • блокирующий Экзамен №1
    Письменный экзамен №1 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
  • блокирующий Экзамен №2
    Письменный экзамен №2 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
Промежуточная аттестация

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

  • 2021/2022 учебный год 1 модуль
    0.5 * Домашнее задание + 0.5 * Контрольная работа
  • 2021/2022 учебный год 2 модуль
    0.5 * Домашнее задание + 0.5 * Контрольная работа
  • 2021/2022 учебный год 4 модуль
    0.3 * Домашнее задание + 0.7 * Экзамен №1
  • 2022/2023 учебный год 2 модуль
    0.5 * Контрольная работа + 0.5 * Домашнее задание
  • 2022/2023 учебный год 4 модуль
    0.7 * Экзамен №2 + 0.3 * Домашнее задание
Список литературы

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

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

  • Reinhard Diestel, Alexander Schrijver, & Paul D. Seymour. (2007). Graph Theory. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.24E6A4B5
  • Гисин В. Б. - ДИСКРЕТНАЯ МАТЕМАТИКА. Учебник и практикум для вузов - М.:Издательство Юрайт - 2021 - 383с. - ISBN: 978-5-534-00228-7 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-468980

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

  • Rigo, M. Advanced graph theory and combinatorics. – John Wiley & Sons, 2016. – 290 pp.
  • Иванов Б. Н. - ДИСКРЕТНАЯ МАТЕМАТИКА И ТЕОРИЯ ГРАФОВ. Учебное пособие для вузов - М.:Издательство Юрайт - 2021 - 177с. - ISBN: 978-5-534-14470-3 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-i-teoriya-grafov-477683

Авторы

  • Омельченко Александр Владимирович
  • Спицина Кристина Станиславовна
  • Кузнецов Антон Михайлович