• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Специалитет 2020/2021

Методы и алгоритмы теории графов

Статус: Курс обязательный (Компьютерная безопасность)
Когда читается: 2-й курс, 3 модуль
Формат изучения: с онлайн-курсом
Специальность: 10.05.01. Компьютерная безопасность
Язык: русский
Кредиты: 3

Программа дисциплины

Аннотация

Данная дисциплина относится к вариативной профильной части Профессионального цикла (Major), проводится на 2 курсе в формате Blended с использованием онлайн-курса Методы и алгоритмы теории графов обучения и является обязательной. Для освоения учебной дисциплины студенты должны владеть базовыми знаниями и компетенциями, полученными при изучении следующих дисциплин: Дискретная математика и Алгебра. Результаты освоения дисциплины используются в дальнейшем при изучении таких дисциплин, как Криптографические методы защиты информации и Криптографические протоколы. Студенты сдают экзамен с прокторингом (подтверждением личности) на самой онлайн-платформе. Дисциплина реализуется в он-лайн формате
Цель освоения дисциплины

Цель освоения дисциплины

  • Формирование у обучающихся навыков, необходимых для разработки математических моделей защищаемых процессов и средств защиты информации и систем, обеспечивающих информационную безопасность объектов
  • Формирование у обучающихся навыков, необходимых для обоснования и выбора рационального решения по уровню обеспечения защищенности компьютерной системы с учетом заданных требований
Планируемые результаты обучения

Планируемые результаты обучения

  • Знать основные положения теории графов
  • Знать основные категории графов
  • Уметь обосновывать применение теории графов для решения конкретной задачи или проблемы в профессиональной области
  • Уметь выбирать адекватную модель из теории графов для моделирования проблемы или задачи в профессиональной области
  • Владеть навыками обоснования значимость применения результатов теории графов для нахождения решения проблем в профессиональной области
  • Знать основные результаты теории графов
  • Уметь находить решение смоделированной задачи в профессиональной области на основе результатов и методов теории графов
  • Знать основные результаты, касающиеся различных графов
  • Уметь выбирать адекватную модель из теории графов для моделирования информационных потоков, сети абонентов, пользователей информационной системы и их взаимодействия
  • Уметь оценивать надежность смоделированной системы на основании методов теории графов
  • Владеть навыками обоснования значимости применения результатов теории графов для нахождения решения проблем в профессиональной области
  • Уметь обосновывать примениние теории графов для решения конкретной задачи или проблемы в профессиональной области
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Основы теории графов
    1. История теории графов. 2. Понятие графа. 3. Классификация графов по структуре. 4. Основной терминологический базис теории графов. 5. Смежность в графах. 6. Операции над графами.
  • Связность графов
    1. Связность неографов. 2. Разделяющее множество связного графа. 3. Связность орграфов. 4. Методика исследования связности орграфов. 5. Конденсирование орграфов, понятие подграфа. 6. Минимальные маршруты в графе. 7. Алгоритмы поиска минимальных маршрутов в связном графе. 8. Метрические характеристики связного графа.
  • Циклы в графах
    1. Циклы в неографах. 2. Циклы в орграфах. 3. Независимые циклы в графе. 4. Циклы Эйлера. 5. Циклы Гамильтона. 6. Алгоритмы поиска циклов Гамильтона в графе. 7. Алгоритмы решения задачи коммивояжера.
  • Деревья
    1. Технологии и подходы к обнаружению аПонятие дерева, леса 2. Свойства деревьев 3. Остовное дерево связного графа, понятие суграфа 4. Алгоритмы построения остовного дерева графа 5. Теорема Прима о минимальном остовном дереве графа 6. Алгоритмы поиска минимального остовного дерева графа 7. Корневые деревья 8. Двоичные деревья
  • Оптимизация на графах
    1. Понятие экстремального числа графа 2. Цикломатическое число графа 3. Число внутренней устойчивости графа 4. Алгоритмы поиска наибольших пустых подграфов в графе 5. Кликовое число графа, понятие графа-дополнения 6. Алгоритмы поиска наибольших полных подграфов в графе 7. Хроматическое число графа 8. Алгоритмы минимальной раскраски графа 9. Число внешней устойчивости графа 10. Число паросочетания графа 11. Число реберного покрытия графа
  • Двудольные графы
    1. Понятие двудольного графа (графа Кёнига) 2. Теорема Кёнига (критерий двудольности графа) 3. Задача линейного назначения, понятие совершенного паросочетания графа 4. Венгерский алгоритм решения задачи линейного назначения 5. Кёнигово представление гиперграфа, понятие гиперграфа 6. Моделирование сложных объектов
  • Изоморфизм и гомеоморфизм
    1. Понятие изоморфизма, необходимые условия изоморфизма двух графов 2. Понятие гомеоморфизма 3. Алгоритмы установления изоморфизма двух графов
  • Плоские и планарные графы
    1. Понятие плоского и планарного графа 2. Свойства плоских укладок графа 3. Теорема Эйлера для плоского графа 4. Следствия из теоремы Эйлера 5. Теорема Понтрягина–Куратовского (критерий планарности графа)
Элементы контроля

Элементы контроля

  • неблокирующий Тесты online-курса
  • неблокирующий Экзамен с прокторингом на платформе
    Оценка за экзамен ставится по накопленной оценке и равна оценке за on-line обучение. Соответствующая информация о результатах on-line обучения представляется Учебным офисом МИЭМ.
  • неблокирующий Тесты online-курса
  • неблокирующий Экзамен с прокторингом на платформе
    Оценка за экзамен ставится по накопленной оценке и равна оценке за on-line обучение. Соответствующая информация о результатах on-line обучения представляется Учебным офисом МИЭМ.
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (3 модуль)
    0.5 * Тесты online-курса + 0.5 * Экзамен с прокторингом на платформе
Список литературы

Список литературы

Рекомендуемая основная литература

  • Кочкаров А.А., Яцкин Д.В. - Теория графов и классические задачи прикладной математики в экономике. (Бакалавриат) - КноРус - 2019 - 248с. - ISBN: 978-5-406-07224-0 - Текст электронный // ЭБС BOOKRU - URL: https://book.ru/book/932443

Рекомендуемая дополнительная литература

  • Клековкин Г. А., Коннова Л. П., Коннов В. В. - ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ 2-е изд., испр. и доп. Учебное пособие для СПО - М.:Издательство Юрайт - 2019 - 240с. - ISBN: 978-5-534-04813-1 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/geometricheskaya-teoriya-grafov-439000