Вебинар:
Этот курс и более
11 500 других учебников
и курсов будут доступны
при покупке личной
подписки
ДИСКРЕТНАЯ МАТЕМАТИКА И ТЕОРИЯ ГРАФОВ
Используют:
121
учебное заведение
70
преподавателей
155
студентов
Избранное
Научная школа:
Дальневосточный федеральный университет (г. Владивосток)
2 зачетных единицы
72 академ/часа
4 часа в неделю
Доступно к покупке
Оплаченный доступ к контенту предоставляется только на платформе, а также онлайн и офлайн в мобильном приложении
Оплаченный доступ к контенту
предоставляется только на платформе, а
также онлайн и офлайн в мобильном
приложении
предоставляется только на платформе, а
также онлайн и офлайн в мобильном
приложении
Скачивание контента в
PDF недоступно
PDF недоступно
Скачивание контента в PDF недоступно
Документы о прохождении курсов не выдаются. Преподаватели могут повысить квалификацию:
Документы о прохождении курсов не выдаются. Преподаватели могут повысить квалификацию:
- О курсе
- Авторы
- Программа курса
- Методика
О курсе
Рассматриваются значимые для практики задачи и алгоритмы на графах. Техника решения задач на графах, как правило, носит алгоритмический рекурсивный характер. В примерах решения алгоритмических задач выполняются способом заполнения данных. Для рекурсии такой подход позволяет понять суть алгоритма и увидеть его с точки зрения программной реализации. Остроумные приемы и находки авторов алгоритмов здесь играют важную роль. Сильной стороной курса является наличие обоснования и доказательства справедливости алгоритмов. Такие доказательства носят конструктивный характер и, как правило, составляют базовую часть алгоритма. К изучению предлагаются групповые свойства целых чисел как необходимый инструмент в практическом программировании. Даются достаточно полный их обзор и ряд приложений. В частности, шифрование с открытым ключом.
Базовый учебник
Серия
Высшее образование
Тематика/подтематика
Математика и статистика / Дискретная математика и математическая логикаДисциплины
Дискретная математика и математическая логика ,
Программирование и основы алгоритмизации ,
Финансовая математика ,
Основы алгоритмизации и программирования ,
Теория графов ,
Алгоритмизация и программирование ,
Основы программирования и алгоритмизации ,
Программирование и алгоритмизация ,
Основы финансовой математики ,
Экономические информационные системы ,
Информатика (программирование и алгоритмы) ,
Основы алгоритмизации и программирование ,
Математическая логика и дискретная математика ,
Основы теории графов ,
Дискретная математика и теория графов ,
Алгоритмическая теория графов
Направления подготовки/Специальности/Профессии
Свернуть
Еще -4
Авторы
Лекции
Иванов Борис Николаевич
доцент, кандидат физико-математических наук
Задания
Иванов Борис Николаевич
доцент, кандидат физико-математических наук
Тесты
Иванов Борис Николаевич
доцент, кандидат физико-математических наук
Программа курса
Свернуть все темы
Развернуть все темы
Тема 1. Определение графа
Время прохождения 302 минуты
- 1.1. Основные определения (141мин.)
- 1.2. Представления графов (47мин.)
- 1.3. Примеры решения задач (23мин.)
- Задачи для самостоятельного решения (47мин.)
- Тест: Определение графа (44мин.)
Свернуть
Развернуть тему
Тема 2. Кратчайшие пути на графе
Время прохождения 221 минута
- 2.1. Алгоритм Дейкстры поиска кратчайшего пути (94мин.)
- 2.2. Примеры выполнения заданий (117мин.)
- Тест: Кратчайшие пути на графе (10мин.)
Свернуть
Развернуть тему
Тема 3. Минимальное остовное дерево
Время прохождения 182 минуты
- 3.1. Основные определения (23мин.)
- 3.2. Алгоритм Краскала - жадная схема построения минимального остовного дерева (47мин.)
- 3.3. Алгоритм Прима - алгоритм ближайшего соседа построения минимального остовного дерева (23мин.)
- 3.4. Примеры выполнения заданий (94мин.)
- Тест: Минимальное остовное дерево (18мин.)
Свернуть
Развернуть тему
Тема 4. Потоки в сетях
Время прохождения 390 минут
- 4.1. Понятие и свойства потока (47мин.)
- 4.2. Алгоритм Форда - Фалкерсона (70мин.)
- 4.3. Примеры выполнения заданий (258мин.)
- Тест: Потоки в сетях (14мин.)
Свернуть
Развернуть тему
Тема 5. Хроматические графы
Время прохождения 223 минуты
- 5.1. Понятие раскраски графа (47мин.)
- 5.2. Неявная схема раскраски вершин графа (23мин.)
- 5.3. Примеры выполнения заданий (141мин.)
- Тест: Хроматические графы (12мин.)
Свернуть
Развернуть тему
Тема 6. Оптимальная раскраска Магу
Время прохождения 247 минут
- 6.1. Теорема об оптимальной раскраске (23мин.)
- 6.2. Метод Магу отыскания независимых множеств (70мин.)
- 6.3. Оптимальная раскраска методом Магу (70мин.)
- 6.4. Пример выполнения задания (70мин.)
- Тест: Оптимальная раскраска Магу (12мин.)
Свернуть
Развернуть тему
Тема 7. Двудольные графы
Время прохождения 225 минут
- 7.1. Условия существования двудольных графов (23мин.)
- 7.2. Паросочетания (23мин.)
- 7.3. Алгоритм определения максимального паросочетания (23мин.)
- 7.4. Примеры выполнения заданий (141мин.)
- Тест: Двудольные графы (14мин.)
Свернуть
Развернуть тему
Тема 8. Задача о назначениях
Время прохождения 292 минуты
- 8.1. Системы различных представителей и их связь с двудольными графами (47мин.)
- 8.2. Задача о назначениях (117мин.)
- 8.3. Примеры выполнения заданий (117мин.)
- Тест: Задача о назначениях (10мин.)
Свернуть
Развернуть тему
Тема 9. Метод поиска в глубину
Время прохождения 127 минут
- 9.1. Алгоритм Тарьяна поиска в глубину (23мин.)
- 9.2. Пример выполнения задания (94мин.)
- Тест: Метод поиска в глубину (10мин.)
Свернуть
Развернуть тему
Тема 10. Метод поиска в ширину
Время прохождения 151 минута
- 10.1. Алгоритм поиска в ширину (47мин.)
- 10.2. Пример выполнения задания (94мин.)
- Тест: Метод поиска в ширину (10мин.)
Свернуть
Развернуть тему
Тема 11. Компоненты связности графа
Время прохождения 155 минут
- 11.1. Отношение эквивалентности (47мин.)
- 11.2. Компоненты связности (23мин.)
- 11.3. Выделение компонент связности (23мин.)
- 11.4. Пример выполнения задания (70мин.)
- Тест: Компоненты связности графа (14мин.)
Свернуть
Развернуть тему
Тема 12. Циклы, фундаментальные множества циклов
Время прохождения 272 минуты
- 12.1. Пространство остовных подграфов (23мин.)
- 12.2. Квазициклы. Пространство циклов графа (70мин.)
- 12.3. Алгоритм поиска фундаментального множества циклов (23мин.)
- 12.4. Примеры выполнения заданий (141мин.)
- Тест: Циклы, фундаментальные множества циклов (14мин.)
Свернуть
Развернуть тему
Тема 13. Листы и блоки. Связность графа
Время прохождения 296 минут
- 13.1. Листы (47мин.)
- 13.2. Блоки (94мин.)
- 13.3. Алгоритм поиска блоков графа (94мин.)
- 13.4. Пример выполнения задания (47мин.)
- Тест: Листы и блоки. Связность графа (14мин.)
Свернуть
Развернуть тему
Тема 14. Эйлеровы графы. Клики
Время прохождения 296 минут
- 14.1. Эйлеровы графы (70мин.)
- 14.2. Диаметр, радиус и центры графа (23мин.)
- 14.3. Клики, независимые множества (47мин.)
- 14.4. Алгоритм поиска клик (70мин.)
- 14.5. Примеры выполнения заданий (70мин.)
- Тест: Эйлеровы графы. Клики (14мин.)
Свернуть
Развернуть тему
Тема 15. Введение в теорию групп
Время прохождения 268 минут
- 15.1. Определение группы (23мин.)
- 15.2. Примеры групп (23мин.)
- 15.3. Смежные классы (23мин.)
- 15.4. Циклические подгруппы (94мин.)
- 15.5. Примарные подгруппы (94мин.)
- Тест: Введение в теорию групп (10мин.)
Свернуть
Развернуть тему
Тема 16. Элементы теории чисел
Время прохождения 257 минут
- 16.1. Наибольший общий делитель (23мин.)
- 16.2. Наименьшее общее кратное (23мин.)
- 16.3. Простые числа (47мин.)
- 16.4. Сравнения, свойства сравнений (23мин.)
- 16.5. Полная система вычетов (23мин.)
- 16.6. Приведенная система вычетов (47мин.)
- 16.7. Функция Эйлера (70мин.)
- Тест: Элементы теории чисел (22мин.)
Свернуть
Развернуть тему
Приложение. Варианты домашних заданий
Время прохождения 117 минут
- 1. Задачи первого задания (47мин.)
- 2. Задачи второго задания (23мин.)
- 3. Задачи третьего задания (47мин.)
Свернуть
Развернуть тему
Новые издания по дисциплине "Дискретная математика" и смежным дисциплинам
Время прохождения 70 минут
Свернуть
Развернуть тему
Методика
Материалы курса
Лекции184
Тесты17
Задания4
Поделиться курсом
Подписка от 475 ₽/мес.
Курсы по теме:
Используют:
32
учебных заведения
16
преподавателей
107
студентов
Используют:
0
учебных заведений
0
преподавателей
0
студентов
Попробуйте личную
подписку от 475 ₽/мес
Полный доступ к порталу Юрайт со всеми учебниками, курсами и сервисами на 1, 6 и 12 месяцев
Более 10 000 учебников
Более 5000 курсов
Тесты и задания платформы
Образовательная платформа Юрайт - это цифровой контент, сервисы, данные для университетов и колледжей.
Ссылки
ООО «Электронное издательство Юрайт»
Свидетельство о регистрации СМИ 2020
Свидетельство о регистрации СМИ 2020
Ваш IP-адрес: 216.73.216.108
Репутация и технологическое лидерство в цифровом образовании
Приглашаем на XVIII Зимнюю школу преподавателя 26-30 января 2026 г. Скидка до 1 декабря на платные форматы: получите УПК на 72 и 108 ч.!
Начать экзамен
У вас на прохождение экзамена:
Остановить или пройти экзамен повторно невозможно.
Начать экзамен
У вас осталось на прохождение экзамена:
Остановить или пройти экзамен повторно невозможно.
Создание новой папки
Выбранная книга издается в нескольких томах (частях), рекомендуем добавить в корзину следующие книги:
| Название | Цена | Заказать |