| Код урока | Название курса | Сорт | Кредит | Время урока | Еженедельные часы занятий (теоретические) | Еженедельные часы занятий (практика) | Еженедельные часы занятий (лаборатория) |
|---|---|---|---|---|---|---|---|
| GNA 3377 | Основные алгоритмы на графах | Үшінші курс | 5 | 150 | 15 | 30 |
Цель дисциплины: ознакомить студентов с основными понятиями теории графов; овладеть методами решения задач в теории графов; освоить основные теоретико-графовые алгоритмы; исследовать прикладные задачи в различных областях с точки зрения теории графов.
критическое мышление, мозговой штурм, обмен мнениями, обсуждение, проблемные методы.
| 1 | Знает основные понятия теории графов, виды графов и способы их представления |
| 2 | Умеет использовать алгоритмы поиска кратчайших путей в графах и нахождения максимального потока в сети |
| 3 | Знает понятие о деревьях и свойства деревьев |
| 4 | Знает понятия эйлеров и гамильтонов циклов и условия их существования |
| 5 | Знает понятия планарных и плоских графов, необходимые и достаточные условия планарности графа, методы оценки хроматического числа графа |
| 6 | Умеет использовать способы представления графов |
| 7 | Умеет использовать классические алгоритмы решения задач поиска кратчайших путей в графах |
| 8 | Умеет построить остовное дерево с минимальным весом |
| 9 | Умеет находить эйлеровы и гамильтоновы циклы в графах |
| 10 | Умеет укладывать планарный граф на плоскости, найти оптимальную раскраску графа |
| Haftalık Konu | Метод оценки | |
|---|---|---|
| 1 | История теории графов. Смежность. Графы и родственные им объекты. Изоморфизм графов. Валентность. | |
| 2 | Способы представления графов. Операции над графами. | |
| 3 | Количество графов. Подграфы. Виды графов. | |
| 4 | Маршруты, цепи, циклы. Определение количества маршрутов. | |
| 5 | Метрические характеристики графа. Обход графа. | |
| 6 | Компоненты связности. Связность в графах и орграфах. Алгоритм построения конденсации. Определение базы и антибазы. | |
| 7 | Потоки в сетях. Теорема Форда-Фалкерсона. Алгоритм нахождения максимального потока. | |
| 8 | Кратчайшие пути во взвешенных графах. Постановка задачи нахождения кратчайших путей. Алгоритм Дейкстры. Алгоритм Форда-Беллмана. | |
| 9 | Деревья и их свойства. Центроид деревьев. Код Прюфера. | |
| 10 | Задачи с деревьями. Перечисление остовных деревьев. Пересчет остовных деревьев. | |
| 11 | Минимальные остовы. Алгоритм Краскала. Алгоритм Прима. Направленные, упорядоченные и бинарные деревья. | |
| 12 | Фундаментальные циклы и системы фундаментальных разрезов. Множество независимых циклов. Алгоритм построения фундаментальных циклов. Множество независимых разрезов. Алгоритм построения фундаментальных разрезов. | |
| 13 | Эйлеровы циклы (цепи). Необходимые и достаточные условия существования эйлеровых циклов. Алгоритм нахождения эйлеровых циклов. Гамильтоновы циклы. Достаточные условия существования гамильтоновых циклов. Алгоритм нахождения гамильтоновых циклов (алгебраический метод). | |
| 14 | Понятие независимого множества вершин. Алгоритм поиска максимально независимых множеств. Понятие о доминирующем множестве вершин. Алгоритм поиска минимальных доминирующих множеств. | |
| 15 | Плоские графы. Планарные графы. Алгоритм укладки графа на плоскости. Хроматическое число графа. Алгоритмы раскраски графов. |
| PÇ1 | PÇ2 | PÇ3 | PÇ4 | PÇ5 | PÇ6 | PÇ7 | PÇ8 | PÇ9 | PÇ10 | PÇ11 | PÇ12 | PÇ13 | PÇ14 | PÇ15 |
|---|
| Оқулық / Материал / Ұсынылатын ресурстар | ||
|---|---|---|
| 1 | Ә.С.Төлеп, Б.И.Ескараева. Графтар теориясы. Оқу құралы. -Түркістан, 2019. -115 б | |
| 2 | Ә.С. Төлеп, Б.И. Ескараева. Дискретті математика. Теория және практикум. -Шымкент, 2020. -132 б | |
| 3 | Абильдаева Г.Б. Дискретті математика: Электрондық оқулық. - Қарағанды: ҚарМТУ, 2017. | |
| 4 | Шевелев Ю.П. Дискретная математика: Учебное пособие. - 4-е изд., стер. - СПб.: Лань, 2022 |