(ФГБОУ ВО ГАГУ, ГАГУ, Горно-Алтайский государственный университет)
01.03.01 Математика
(<Курс>.<Семестр на курсе>)
Зав. кафедрой И. о. зав. кафедрой: Богданова Рада Александровна
Зав. кафедрой И. о. зав. кафедрой: Богданова Рада Александровна
исполнения в 2028-2029 учебном году на заседании кафедры
Зав. кафедрой И. о. зав. кафедрой: Богданова Рада Александровна
исполнения в 2027-2028 учебном году на заседании кафедры
Зав. кафедрой И. о. зав. кафедрой: Богданова Рада Александровна
исполнения в 2026-2027 учебном году на заседании кафедры
Зав. кафедрой И. о. зав. кафедрой: Богданова Рада Александровна
исполнения в 2025-2026 учебном году на заседании кафедры
ции
ракт.
Алгебра множеств. Суперпозиция функций. Бинарные отношения. Отношения эквивалентности. Отношения строгого и нестрого порядка. /Лек/
элементы лекции-визуализации
Вводные понятия булевой алгебры. Двоичные числа. Отношение эквивалентности. Представление логических функций. Числовое представление булевых функций. Минтермы. Совершенная дизъюнктивная нормальная форма. Макстермы. Совершенная конъюнктивная нормальная форма. /Лек/
элементы лекции-визуализации
Вводные понятия теории графов. Псевдограф. Мультиграф. Подграф. Надграф. Частичный граф. Смежность. Инцидентность. Степень вершины. Однородный граф. Полный граф. Дополнение графа. Объединение и пересечение графов. Изоморфизм. Матрицы смежности и инцидентности. Маршруты, цепи, циклы. Нахождение простых цепей. Эйлеровы цепи и циклы. Уникурсальная линия. Двудольные графы. Метрика графа. Планарные и плоские графы. Теорема Эйлера о плоских графах. Деревья и лес. Кодирование деревьев методом Пруфера. Построение дерева по его коду. Гамильтоновы графы. /Лек/
элементы лекции-визуализации
Множества. Собственные и несобственные подмножества. Универсальные множества. Булеан. Кардинальное число. Операции над множествами. Кардинальное число булеана множества.
/Пр/
Декартово произведение множеств. Степень множества. Понятие бинарного отношения. Симметричность, рефлексивность и транзитивность отношений. Отношение эквивалентности.
/Пр/
Двоичные числа и операции над ними. Аксиомы булевой алгебры. Теоремы одной переменной. Булева функция и способы ее задания.
/Пр/
Минтермы. Совершенная дизъюнктивная нормальная форма. Карта Вейча. Макстермы. Совершенная конъюнктивная нормальная форма.
/Пр/
Вводные понятия теории графов. Псевдограф. Мультиграф. Подграф. Надграф. Частичный граф. Смежность. Инцидентность. Степень вершины. Однородный граф. Полный граф. Дополнение графа. Объединение и пересечение графов.
/Пр/
Изоморфизм. Матрицы смежности и инцидентности. Маршруты, цепи, циклы. Нахождение простых цепей.
/Пр/
Эйлеровы цепи и циклы. Уникурсальная линия. Двудольные графы. Метрика графа. Планарные и плоские графы. Теорема Эйлера о плоских графах. Гамильтоновы графы. /Пр/
контроля и оценки образовательных достижений обучающихся, освоивших программу
дисциплины Дискретная математика.
2. Фонд оценочных средств включает контрольные материалы для проведения текущего
контроля в форме вопросов к зачету, а также разноуровневых задач к практическим занятиям.
1. На какие вопросы Вы ответите «да»:
1) может ли быть простым граф, содержащий 4 вершины и 8 ребер?
2) может ли граф с одним ребром быть псевдографом?
3) может ли граф быть псевдографом, если в нем нет кратных ребер?
4) может ли граф с одним ребром быть мультиграфом?
2. Определите число вершин и число ребер подграфа, построенного на основе графа G путем удаления из него соответствующих вершин (приводится рисунок).
3. Укажите номера вопросов, на которые Вы ответите «да». Возможен ли однородный граф, в котором:
1) пять вершин и степень каждой вершины равна трем?
2) шесть вершин и степень каждой вершины равна четырем?
3) четыре вершины и шесть ребер?
4) пять нечетных вершин и шесть ребер?
4. В полном графе 18 вершин. Сколько в нем ребер инцидентных одной вершине?
5.Сколько ребер имеет полный граф, если число его вершин равно 10?
6. Сколько колонок в матрице инцидентности полного графа построенного на девяти вершинах?
7. Укажите номера вопросов, на которые Вы дадите утвердительные ответы:
1) может ли последовательность, обозначающая маршрут, начинаться номером ребра и оканчиваться номером вершины?
2) может ли цепь состоять из одного ребра и двух вершин?
3) может ли простой граф содержать цикл, состоящий из одного ребра?
4) могут ли в цикле повторяться вершины?
5) верно ли, что если в графе нет циклов, то в нем число ребер равно числу вершин?
6) может ли простая цепь (при вершинном ее представлении) содержать повторяющиеся вершины?
8. В нижеприведенном списке укажите (приводится рисунок):
1) маршруты;
2) замкнутые маршруты;
3) цепи;
4) циклы;
5) простые цепи;
6) простые циклы.
9. В списке, приведенном в задании 8, укажите:
1) последовательности, не являющиеся маршрутами;
2) простые цепи длины 1;
3) цепи длины 2;
4) простой цикл наибольшей длины, укажите длину этого цикла.
10. Сколько простых цепей содержит граф, изображенный на рисунке? (приводится рисунок)
11. Найдите код дерева, приведенного на рисунке (приводится рисунок).
Критерии оценки:
- оценка «зачтено» выставляется студенту, если он показывает полные знания учебно-программного материала, успешно выполняет предусмотренные в программе задания, усвоил основную литературу, рекомендованную в программе. Как правило, оценка «зачтено» выставляется студентам, показавшим систематический характер знаний по дисциплине и способным к их самостоятельному пополнению и обновлению в ходе дальнейшей учебной работы и профессиональной деятельности;
- оценка «незачтено» выставляется студенту, если он осуществляет существенные пробелы в знаниях основного учебно-программного материала, допускает принципиальные ошибки в выполнении предусмотренных программой заданий.