Основная профессиональная образовательная программа высшего образования

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