Delivered at:: Department of Mathematics

Course type:: Elective course

When:: 1 year, 3 module

Instructor

Garina, Marina

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

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

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

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

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

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

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

Множества и отношения
Комбинаторика
Свойства элементов графа
Внутренняя и внешняя устойчивость.
Маршруты, цепи и циклы
Деревья
Расстояния в графе
Оптимизационные задачи на графах

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

Домашнее задание №1. «Комбинаторика и бинарные отношения»
Домашнее задание №2. Невзвешенные графы
Домашнее задание №3. Взвешенные графы
Экзамен
Для участия в экзамене надо будет установить программу zoom на свой компьютер. У студента во время экзамена должна быть включена камера и звук. Студент должен находиться один в комнате во время экзамена. Перед началом экзамена студент должен продемонстрировать, что на его рабочем столе нет посторонних предметов. Во время выполнения экзамена разрешается пользоваться только черновиком и ручкой. Ник в программе zoom должен соответствовать фамилии студента. Экзамен состоит из двух частей. Первая часть состоит из ответа на теоретический вопрос. Вторая часть состоит из решения задач. Для участия в первой части высылается ссылка на zoom конференцию. По завершении студенту дается 15 минут сфотографировать ответ на билет и отправить его на почту преподавателя. Вторая часть начинается через 15 минут после завершения первой части (и после истечения времени на отправку фотографий). Задачи второй части оформлены в виде электронной контрольной, которая открывается ровно во время начала второй части экзамена.

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

2021/2022 учебный год 3 модуль
0.5 * Экзамен + 0.15 * Домашнее задание №1. «Комбинаторика и бинарные отношения» + 0.2 * Домашнее задание №3. Взвешенные графы + 0.15 * Домашнее задание №2. Невзвешенные графы

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

Авторы

Гарина Марина Игоревна

Bachelor’s Programme 'Economics'

Study Office

Discrete Mathematics for Economists

Instructor

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