Бакалавриат
2019/2020
Дискретная математика для экономистов
Статус:
Курс по выбору (Экономика)
Направление:
38.03.01. Экономика
Кто читает:
Департамент информатики
Где читается:
Санкт-Петербургская школа экономики и менеджмента
Когда читается:
1-й курс, 3 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Близнец Иван Анатольевич
Язык:
русский
Кредиты:
3
Контактные часы:
32
Программа дисциплины
Аннотация
Целями освоения дисциплины являются формирование у студентов теоретических знаний и практических навыков по основам теории множеств, теории графов, комбинаторного анализа как основного математического аппарата для построения моделей дискретных структур, освоение методов математического моделирования и анализа таких структур. В результате освоения дисциплины студент должен: − Знать основные понятия и факты теории графов, такие, как деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы; классические и обобщенные постановки комбинаторных задач; комбинаторный смысл основных операций над производящими функциями. − Уметь находить кратчайшие и минимальные пути в графе, медианы и центры графа, остовные деревья, эйлеровы и гамильтоновы циклы, совершенные или максимальные паросочетания, оптимальную раскраску графа; решать линейные рекуррентные соотношения, как с помощью производящих функций, так и без них; перечислять основные дискретные объекты (графы, деревья, плоские деревья). − Иметь навыки (приобрести опыт) методов решения основных комбинаторных задач с помощью производящих функций, использования основных алгоритмов работы с графами.
Цель освоения дисциплины
- усвоение теоретических основ элементарной перечислительной комбинаторики и теории графов. А также ознакомление студентов с решением линейных рекуррентных однородных соотношений.
Планируемые результаты обучения
- Знает и умеет применять базовые понятия элементарной комбинаторики
- умеет решать реккурентные соотношения первого и второго порядка
- знает основные определения и базовые результаты теории графов
- умеет сводить различные задачи к вопросу существования совершенного паросочения в графе
- понимает практическую значимость алгоритма Шэпли и умеет сводить различные задачи к вопросу существования совершенного паросочения в графе
Содержание учебной дисциплины
- Основные правила перечислительной комбинаторики. Подсчет перестановок
- Подсчет 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