|
1 |
Название дисциплины |
Дискретная математика и теория графов |
|
2 |
Курс обучения |
2, специальность «Математика (научно-конструкторская деятельность)» |
|
3 |
Семестр обучения |
3 |
|
4 |
Количество кредитов |
3 |
|
5 |
Ф.И.О. лектора |
Кандидат физико-математических наук, доцент Метельский Юрий Михайлович |
|
6 |
Цели изучения дисциплины |
Ознакомление с задачами и методами дискретной математики. Формирование навыков дискретного математического мышления и умения применять его при решении конкретных задач. В результате изучения студент должен уметь: — формулировать основные утверждения из рассматриваемых разделов дискретной математики; — применять основные утверждения для решения типовых задач. |
|
7 |
Пререквизиты |
Начальные сведения из теории отображений и теории множеств, линейная алгебра |
|
8 |
Содержание дисциплины |
Первоначальные понятия теории графов. Изоморфизм. Маршруты, связные компоненты. Волновой алгоритм. Двудольные графы. Деревья и остовы. Эквивалентные определения деревьев. Теорема Кирхгофа о числе остовных деревьев. Остовы минимального веса. Независимость и покрытия в графах. Теорема Холла о паросочетаниях в двудольных графах. Числа вершинной и реберной связностей графа. Двусвязные графы. Теорема Менгера о вершинных сепараторах. Обходы графов. |
|
9 |
Рекомендуемая литература |
1. Зуев Ю.А. По океану дискретной математики: От перечислительной комбинаторики до современной криптографии. В 2-х томах. М.: Книжный дом «Либроком», 2012. 2. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. (Изд. второе, исправленное.) М.: Книжный дом «Либроком», 2009. 3. Емеличев В.А., Зверович И.Э., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Теория графов в задачах и упражнениях (учебное пособие). М.: Книжный дом «Либроком», 2013. |
|
10 |
Методы преподавания |
Репродуктивный (пассивный), наглядный, компаративный, диалогово-эвристический, проблемный, исследовательский |
|
11 |
Язык обучения |
Русский |
|
12 |
Условия (требования), текущий контроль |
Теоретические коллоквиумы, письменные контрольные работы |
|
13 |
Форма текущей аттестации |
Зачет |