Discrete Mathematics for Economists

2020/2021

Academic Year

RUS

Instruction in Russian

3

ECTS credits

Delivered at:

Department of Informatics

Course type:

Elective course

When:

1 year, 3 module

Instructor

Garina, Marina

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

Аннотация

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

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

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

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

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

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

• Основные правила перечислительной комбинаторики. Подсчет перестановок
• Подсчет 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