Этот курс и более
11 129 других учебников
и курсов будут доступны
при покупке личной
подписки
ДИСКРЕТНАЯ МАТЕМАТИКА И ТЕОРИЯ ГРАФОВ
Используют:
0
вузов
0
преподавателей
0
студентов
Избранное
СПО
Научная школа:
Дальневосточный федеральный университет (г. Владивосток)
2 зачетных единицы
72 академ/часа
4 часа в неделю
Доступно к покупке
Оплаченный доступ к контенту предоставляется только на платформе, а также онлайн и офлайн в мобильном приложении
Оплаченный доступ к контенту
предоставляется только на платформе, а
также онлайн и офлайн в мобильном
приложении
предоставляется только на платформе, а
также онлайн и офлайн в мобильном
приложении
Скачивание контента в
PDF недоступно
PDF недоступно
Скачивание контента в PDF недоступно
- О курсе
- Авторы
- Программа курса
- Методика
О курсе
Рассматриваются значимые для практики задачи и алгоритмы на графах. Техника решения задач на графах, как правило, носит алгоритмический рекурсивный характер. В примерах решения алгоритмических задач выполняются способом заполнения данных. Для рекурсии такой подход позволяет понять суть алгоритма и увидеть его с точки зрения программной реализации. Остроумные приемы и находки авторов алгоритмов здесь играют важную роль. Сильной стороной курса является наличие обоснования и доказательства справедливости алгоритмов. Такие доказательства носят конструктивный характер и, как правило, составляют базовую часть алгоритма. К изучению предлагаются групповые свойства целых чисел как необходимый инструмент в практическом программировании. Даются достаточно полный их обзор и ряд приложений. В частности, шифрование с открытым ключом.
Базовый учебник
Серия
Профессиональное образование
Тематика/подтематика
Математика и статистика / Дискретная математика и математическая логикаДисциплины
Дискретная математика ,
Теория чисел ,
Основы теории чисел ,
Математика. Дискретная математика ,
Введение в дискретную математику ,
Основы дискретной математики
Направления подготовки/Специальности/Профессии
09.02.01 Компьютерные системы и комплексы,
09.02.05 Прикладная информатика (по отраслям),
10.02.03 Информационная безопасность автоматизированных систем,
09.02.04 Информационные системы (по отраслям),
09.02.03 Программирование в компьютерных системах,
09.02.02 Компьютерные сети,
09.02.07 Информационные системы и программирование,
09.02.06 Сетевое и системное администрирование,
10.02.05 Обеспечение информационной безопасности автоматизированных систем,
09.02.08 Интеллектуальные интегрированные системы,
09.02.01.П Компьютерные системы и комплексы (профессионалитет),
09.02.07.П Информационные системы и программирование (профессионалитет),
09.02.06.П Сетевое и системное администрирование (профессионалитет),
10.02.05.П Обеспечение информационной безопасности автоматизированных систем (профессионалитет),
09.02.08.П Интеллектуальные интегрированные системы (профессионалитет)
09.02.05 Прикладная информатика (по отраслям),
10.02.03 Информационная безопасность автоматизированных систем,
09.02.04 Информационные системы (по отраслям),
09.02.03 Программирование в компьютерных системах,
09.02.02 Компьютерные сети,
09.02.07 Информационные системы и программирование,
09.02.06 Сетевое и системное администрирование,
10.02.05 Обеспечение информационной безопасности автоматизированных систем,
09.02.08 Интеллектуальные интегрированные системы,
09.02.01.П Компьютерные системы и комплексы (профессионалитет),
09.02.07.П Информационные системы и программирование (профессионалитет),
09.02.06.П Сетевое и системное администрирование (профессионалитет),
10.02.05.П Обеспечение информационной безопасности автоматизированных систем (профессионалитет),
09.02.08.П Интеллектуальные интегрированные системы (профессионалитет)
Свернуть
Еще 11
Авторы
Лекции
Иванов Борис Николаевич
доцент, кандидат физико-математических наук
Программа курса
Свернуть все темы
Развернуть все темы
Тема 1. Определение графа
Время прохождения 311 минут
- 1.1. Основные определения (146мин.)
- 1.2. Представления графов (49мин.)
- 1.3. Примеры решения задач (24мин.)
- Задачи для самостоятельного решения (49мин.)
- Тест: Определение графа (44мин.)
Свернуть
Развернуть тему
Тема 2. Кратчайшие пути на графе
Время прохождения 228 минут
- 2.1. Алгоритм Дейкстры поиска кратчайшего пути (97мин.)
- 2.2. Примеры выполнения заданий (121мин.)
- Тест: Кратчайшие пути на графе (10мин.)
Свернуть
Развернуть тему
Тема 3. Минимальное остовное дерево
Время прохождения 188 минут
- 3.1. Основные определения (24мин.)
- 3.2. Алгоритм Краскала - жадная схема построения минимального остовного дерева (49мин.)
- 3.3. Алгоритм Прима - алгоритм ближайшего соседа построения минимального остовного дерева (24мин.)
- 3.4. Примеры выполнения заданий (97мин.)
- Тест: Минимальное остовное дерево (18мин.)
Свернуть
Развернуть тему
Тема 4. Потоки в сетях
Время прохождения 402 минуты
- 4.1. Понятие и свойства потока (49мин.)
- 4.2. Алгоритм Форда - Фалкерсона (73мин.)
- 4.3. Примеры выполнения заданий (267мин.)
- Тест: Потоки в сетях (14мин.)
Свернуть
Развернуть тему
Тема 5. Хроматические графы
Время прохождения 230 минут
- 5.1. Понятие раскраски графа (49мин.)
- 5.2. Неявная схема раскраски вершин графа (24мин.)
- 5.3. Примеры выполнения заданий (146мин.)
- Тест: Хроматические графы (12мин.)
Свернуть
Развернуть тему
Тема 6. Оптимальная раскраска Магу
Время прохождения 255 минут
- 6.1. Теорема об оптимальной раскраске (24мин.)
- 6.2. Метод Магу отыскания независимых множеств (73мин.)
- 6.3. Оптимальная раскраска методом Магу (73мин.)
- 6.4. Пример выполнения задания (73мин.)
- Тест: Оптимальная раскраска Магу (12мин.)
Свернуть
Развернуть тему
Тема 7. Двудольные графы
Время прохождения 232 минуты
- 7.1. Условия существования двудольных графов (24мин.)
- 7.2. Паросочетания (24мин.)
- 7.3. Алгоритм определения максимального паросочетания (24мин.)
- 7.4. Примеры выполнения заданий (146мин.)
- Тест: Двудольные графы (14мин.)
Свернуть
Развернуть тему
Тема 8. Задача о назначениях
Время прохождения 301 минута
- 8.1. Системы различных представителей и их связь с двудольными графами (49мин.)
- 8.2. Задача о назначениях (121мин.)
- 8.3. Примеры выполнения заданий (121мин.)
- Тест: Задача о назначениях (10мин.)
Свернуть
Развернуть тему
Тема 9. Метод поиска в глубину
Время прохождения 131 минута
- 9.1. Алгоритм Тарьяна поиска в глубину (24мин.)
- 9.2. Пример выполнения задания (97мин.)
- Тест: Метод поиска в глубину (10мин.)
Свернуть
Развернуть тему
Тема 10. Метод поиска в ширину
Время прохождения 156 минут
- 10.1. Алгоритм поиска в ширину (49мин.)
- 10.2. Пример выполнения задания (97мин.)
- Тест: Метод поиска в ширину (10мин.)
Свернуть
Развернуть тему
Тема 11. Компоненты связности графа
Время прохождения 160 минут
- 11.1. Отношение эквивалентности (49мин.)
- 11.2. Компоненты связности (24мин.)
- 11.3. Выделение компонент связности (24мин.)
- 11.4. Пример выполнения задания (73мин.)
- Тест: Компоненты связности графа (14мин.)
Свернуть
Развернуть тему
Тема 12. Циклы, фундаментальные множества циклов
Время прохождения 281 минута
- 12.1. Пространство остовных подграфов (24мин.)
- 12.2. Квазициклы. Пространство циклов графа (73мин.)
- 12.3. Алгоритм поиска фундаментального множества циклов (24мин.)
- 12.4. Примеры выполнения заданий (146мин.)
- Тест: Циклы, фундаментальные множества циклов (14мин.)
Свернуть
Развернуть тему
Тема 13. Листы и блоки. Связность графа
Время прохождения 305 минут
- 13.1. Листы (49мин.)
- 13.2. Блоки (97мин.)
- 13.3. Алгоритм поиска блоков графа (97мин.)
- 13.4. Пример выполнения задания (49мин.)
- Тест: Листы и блоки. Связность графа (14мин.)
Свернуть
Развернуть тему
Тема 14. Эйлеровы графы. Клики
Время прохождения 305 минут
- 14.1. Эйлеровы графы (73мин.)
- 14.2. Диаметр, радиус и центры графа (24мин.)
- 14.3. Клики, независимые множества (49мин.)
- 14.4. Алгоритм поиска клик (73мин.)
- 14.5. Примеры выполнения заданий (73мин.)
- Тест: Эйлеровы графы. Клики (14мин.)
Свернуть
Развернуть тему
Тема 15. Введение в теорию групп
Время прохождения 277 минут
- 15.1. Определение группы (24мин.)
- 15.2. Примеры групп (24мин.)
- 15.3. Смежные классы (24мин.)
- 15.4. Циклические подгруппы (97мин.)
- 15.5. Примарные подгруппы (97мин.)
- Тест: Введение в теорию групп (10мин.)
Свернуть
Развернуть тему
Тема 16. Элементы теории чисел
Время прохождения 265 минут
- 16.1. Наибольший общий делитель (24мин.)
- 16.2. Наименьшее общее кратное (24мин.)
- 16.3. Простые числа (49мин.)
- 16.4. Сравнения, свойства сравнений (24мин.)
- 16.5. Полная система вычетов (24мин.)
- 16.6. Приведенная система вычетов (49мин.)
- 16.7. Функция Эйлера (73мин.)
- Тест: Элементы теории чисел (22мин.)
Свернуть
Развернуть тему
Приложение. Варианты домашних заданий
Время прохождения 121 минута
- 1. Задачи первого задания (49мин.)
- 2. Задачи второго задания (24мин.)
- 3. Задачи третьего задания (49мин.)
Свернуть
Развернуть тему
Новые издания по дисциплине "Дискретная математика" и смежным дисциплинам
Время прохождения 73 минуты
Свернуть
Развернуть тему
Методика
Материалы курса
Лекции22
Тесты17
Поделиться курсом
Подписка от 349 ₽/мес.
Курсы по теме:
Используют:
81
вуз
19
преподавателей
84
студента
Используют:
255
вузов
162
преподавателя
491
студент
Попробуйте личную
подписку от 349 ₽/мес
Полный доступ к порталу Юрайт со всеми учебниками, курсами и сервисами на 1, 6 и 12 месяцев
Более 10 000 учебников
Более 5000 курсов
Тесты и задания платформы
Образовательная платформа для университетов и колледжей. Предлагаем цифровой учебный контент и сервисы для эффективного образования.
Ссылки
ООО «Электронное издательство Юрайт»
Свидетельство о регистрации СМИ 2020
Свидетельство о регистрации СМИ 2020
Ваш IP-адрес: 3.129.67.248
Смарт-образование: цифровой контент, сервисы и данные
Приглашаем на Зимнюю школу преподавателя (27-31 января)
До 01.12 скидка 20% на повышение квалификации 72 и 108 ч.!
Начать экзамен
У вас на прохождение экзамена:
Остановить или пройти экзамен повторно невозможно.
Начать экзамен
У вас осталось на прохождение экзамена:
Остановить или пройти экзамен повторно невозможно.
Создание новой папки
Выбранная книга издается в нескольких томах (частях), рекомендуем добавить в корзину следующие книги:
| Название | Цена | Заказать |