• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Дискретная математика для экономистов

2019/2020
Учебный год
RUS
Обучение ведется на русском языке
3
Кредиты
Статус:
Курс по выбору
Когда читается:
1-й курс, 3 модуль

Преподаватель

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

Аннотация

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

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

  • усвоение теоретических основ элементарной перечислительной комбинаторики и теории графов. А также ознакомление студентов с решением линейных рекуррентных однородных соотношений.
Результаты освоения дисциплины

Результаты освоения дисциплины

  • Знает и умеет применять базовые понятия элементарной комбинаторики
  • умеет решать реккурентные соотношения первого и второго порядка
  • знает основные определения и базовые результаты теории графов
  • умеет сводить различные задачи к вопросу существования совершенного паросочения в графе
  • понимает практическую значимость алгоритма Шэпли и умеет сводить различные задачи к вопросу существования совершенного паросочения в графе
Содержание учебной дисциплины

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

  • Основные правила перечислительной комбинаторики. Подсчет перестановок
  • Подсчет k-сочетаний из n элементов. Биномиальные коэффициенты - определение, рекуррентные соотношения, основные свойства. k-перестановки из n элементов.
  • Понятие рекуррентного соотношения. Основные определения: линейность, однородность, характеристическое уравнение
  • Методы решения рекуррентных уравнений, не использующие производящие функции. Формулы для решения рекуррентных соотношений второго порядка. Числа Фибоначчи.
  • Базовые понятия теории графов.
  • Понятия связности в графах. Деревья.
  • Паросочения. Теорема Холла. Алгоритм Шэпли.
  • Теория Рамсея.
Элементы контроля

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

  • неблокирующий Домашнее задание №1
  • неблокирующий Домашнее задание №2
  • блокирующий Экзамен
  • неблокирующий Работа на занятии
Промежуточная аттестация

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

  • Промежуточная аттестация (3 модуль)
    0.2 * Домашнее задание №1 + 0.2 * Домашнее задание №2 + 0.1 * Работа на занятии + 0.5 * Экзамен
Список литературы

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

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

  • Гисин В. Б.-ДИСКРЕТНАЯ МАТЕМАТИКА. Учебник и практикум для академического бакалавриата-М.:Издательство Юрайт,2019-383-Высшее образование-978-5-534-00228-7: -Текст электронный // ЭБС Юрайт - https://biblio-online.ru/book/diskretnaya-matematika-432144

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

  • Rigo, M. (2016). Advanced graph theory and combinatorics. ISTE-John Wiley & Sons. https://doi.org/10.1002/9781119008989