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

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

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

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

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

Аннотация

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

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

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

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

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

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

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

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

  • неблокирующий Домашнее задание №1
  • неблокирующий Домашнее задание №2
  • блокирующий Экзамен
    Для участия в экзамене надо будет установить программу zoom на свой компьютер. Также у студента во время экзамена должна быть включена камера. Студент должен находиться один в комнате во время экзамена. Перед началом экзамена студент должен продемонстрировать, что на его рабочем столе нет посторонних предметов. Во время выполнения экзамена разрешается пользоваться только черновиком и ручкой. Ник в программе zoom должен соответствовать имени, фамилия студента. Экзамен состоит из двух частей. Первая часть состоит из ответа на теоретический вопрос. Вторая часть состоит из решения задач. Для участия в первой части высылается ссылка на zoom конференцию(ссылка высылается на рассылку группы, в которой обучается студент). По завершении конференции, студенту дается 5 минут сфотографировать ответ на билет и отправить его на почты ibliznecz@hse.ru и iabliznets@gmail.com. Вторая часть начинается через 15 минут после завершения первой части. Процесс участия во второй части полностью повторяет процесс участия в первой части.
  • неблокирующий Работа на занятии
Промежуточная аттестация

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

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

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

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

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

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

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