Аспирантура (Нижний Новгород)

Кто читает:: Кафедра фундаментальной математики (Факультет информатики, математики и компьютерных наук (Нижний Новгород))

Статус:: Курс по выбору

Когда читается:: 2-й курс, 2 семестр

Преподаватель

Дополнительные материалы в LMS Задать вопрос

Аннотация

Рассматриваются вопросы зависимости времени вычисления от параметров, характеризующих сложность обрабатываемых графов (в простейшем случае — от числа вершин или рёбер графа), и сравнение результатов работы различных программных реализаций алгоритмов (решателей задач)

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

Изучение зависимости времени вычисления от параметров, характеризующих сложность обрабатываемых графов (в простейшем случае — от числа вершин или рёбер графа), и сравнение результатов работы различных программных реализаций алгоритмов (решателей задач).

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

Владеет методами исследования моделей в области экономики.
Владеет навыками работы с данными, умения вычислять параметры моделей, давать их экономическую интерпретацию.
Демонстрирует навыки интерпретации экономически показателей, используемых в расчетах по модели.
Демонстрирует навыки работы с данными, умения проводить верификацию моделей.
Владеет методиками самоорганизации при выполнении профессиональных задач.
Умеет использовать в профессиональной работе современные технические средства.

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

Введение. Базовые понятия теории графов
Эквивалентные определения дерева. Планарные графы
Формула Кэли. Унициклические графы. Эйлеровы циклы
Гамильтоновы циклы
Паросочетания. Теорема Холла и Кенига.
Теория Рамсея.

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

Контрольная работа
Экзамен

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

2025/2026 2nd semester
0.5 * Контрольная работа + 0.5 * Экзамен

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

Авторы

Галкин Олег Евгеньевич

Анализ вычислительной сложности задач на графах