zhChinese    enEnglish
  ПМ-ПУ  » Образование  » Программы курсов  » Дисциплины специализаций » Теория графов и конечных автоматов

Теория графов и конечных автоматов

Специальный курс

Лектор: доцент кандидат технических наук Новожилова Л. М.

Часть I. ТЕОРИЯ ГРАФОВ.

ВВЕДЕНИЕ.

Оптимальные задачи на дискретных конечных структурах. Решения и процедуры их реализации. Простота и экзотичность формулировок, комбинаторный аспект и трудности вычислительной реализации решений задач-головоломок. Точные и приближенные решения. NP-свойства двоично кодируемых структур данных. Проблема оптимизации вычислительных ресурсов, затрачиваемых на распознавание NP-свойств. Понятие вычислительной сложности алгоритма. Полиномиальные и экспоненциальные алгоритмы. Сводимость и выполнимость. Классы сложности. NP-, KP- и P-SPACE-полные задачи. Линейно ограниченные автоматы. О теории NP-полных задач. Теория графов как категория списка NP-полных задач. Теория оценки вычислительной сложности алгоритмов решения NP-полных задач.

1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ.

Графы, подграфы. Математические способы представления графов: геометрический, аналитический и матричный. Способы кодирования в памяти ЭВМ матриц смежности и инциденций, списка смежности и массива дуг. Противоречивость критериев выбора эффективных способов компьютерного представления графовых структур данных - минимум объема занимаемой памяти и минимум времени оперирования данными. Интерактивные технологии. Пути, маршруты. Циклы и орциклы. Взвешенные графы. Простые пути и алгебраические процедуры их перечисления. Обходы графов. Типы графов. Изоморфизм графов.

2. СВЯЗНОСТЬ И ДОСТИЖИМОСТЬ.

Свойство связности, компонента графа. Нахождение сильных компонент. Конденсация графа. Базы и антибазы; моделирование и анализ структуры служебного персонала организации: формирование функционально эффективных коалиций и комитетов.

3. УСТОЙЧИВЫЕ МНОЖЕСТВА.

Внешне устойчивые (доминирующие) множества и внутренне устойчивые (независимые) множества. Шахматные аналогии. Число доминирования. Число независимости. Клика графа. Кликовое число графа. Связь понятий: теорема Рамсея. Алгоритмы перечисления максимальных независимых множеств графа. Сводимость алгоритмов, оценки вычислительной сложности. Приложения в теории информации.

4. ПОКРЫТИЕ И РАЗБИЕНИЕ.

Вершинное покрытие. Задача о наименьшем покрытии. Прикладной аспект: оптимизация размещения информационных центров на данной территории, задача о назначениях. Разбиение графа на клики. Покрытие кликами. Покрытие полными двудольными подграфами. Оценки вычислительной сложности алгоритмов.

5. РАСКРАСКИ.

Раскраска и раскрашиваемость графа. Хроматическое число, оценки. Задача об оптимальной раскраске. Точные и приближенные алгоритмы оптимальной раскраски. Решение методом динамического программирования. Метод сведения к задаче о наименьшем покрытии максимальными независимыми множествами. Оценки вычислительной сложности алгоритмов. Интерпретация задачи в терминах булева программирования. Алгебраическая постановка задачи. Приложения: задачи оптимальной организации структуры банков данных, размещения элементов распределенных сложных систем, распределения ресурсов, слияния банков данных, календарного планирования профилактических ремонтов сложных систем. Оценки вычислительной сложности алгоритмов.

6. РАЗМЕЩЕНИЕ ЦЕНТРОВ И МЕДИАН В ГРАФАХ.

Минимаксная и минисуммная задачи размещения. Абсолютные центр и медиана. Алгоритм нахождения абсолютного центра методом Хакими. Оценки вычислительной сложности.

7. ДЕРЕВЬЯ.

Остовное дерево графа. Граф остовов. Процедуры разборки и сборки графа. Теорема Кэли. Матричная теорема о деревьях. Полиномиальная лексико-графическая процедура перечисления остовных деревьев графа. Оценки вычислительной сложности. Древесность иерархических структур данных информационных систем. Кратчайший остов графа. Алгоритмы построения кратчайшего остова графа. Оценки вычислительной сложности. Евклидова задача Штейнера нахождения кратчайшего дерева, стягивающего данное множество точек. Точки Штейнера. Приложения в радиоэлектронике, теории коммуникаций и логистике.

8. КРАТЧАЙШИЕ ПУТИ НА ГРАФАХ. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ.

Варианты задач. Обзор методов решения. Алгоритм Дейкстры нахождения кратчайшего пути, связывающего две заданные вершины графа. Алгоритм Флойда нахождения кратчайших путей между всеми парами вершин. Алгоритмы Форда, Мура и Беллмана. Оценки вычислительной сложности. Задачи, близкие к задаче о кратчайшем пути. Наиболее надежный путь. Путь с наиболь- шей пропускной способностью. Теорема о максимальном потоке и минимальном разрезе Форда и Фалкерсона. Алгоритмы нахождения максимального потока и минимального разреза. Путь с наибольшей пропускной способностью и наибольшей надежностью. Потоковые алгоритмы. Сетевая модель комплекса операций.

9. ЦИКЛЫ, РАЗРЕЗЫ И ЗАДАЧА ЭЙЛЕРА.

Фундаментальные циклы и фундаментальные разрезы графа, порождаемые данным остовом, как алгебраические объекты данных. Свойства матриц фундаментальных циклов и фундаментальных разрезов. Эйлеровы циклы. Критерий Эйлера. Алгоритм построения эйлерова цикла в графе. Задача китайского почтальона. Алгоритмы решения. Оценки вычислительной сложности. Приложения: Сбор мусора, доставка почты, оптимальные процедуры контроля коммуникаций.

10. ГАМИЛЬТОНОВЫ ЦЕПИ И ЦИКЛЫ. ЗАДАЧИ ПЛАНИРОВАНИЯ.

Задача коммивояжера. Связь с задачей о назначениях и с задачей о кратчайшем остове. Алгоритмы решения. Вычислительная сложность.

11. ПАРОСОЧЕТАНИЯ.

Теорема Холла-Кенига. Задача о максимальном паросочетании. Задача о назначениях. Общая процедура построения остовного подграфа с предписанными степенями. Применение теории потоков в теории паросочетаний. Венгерский метод, матричная форма. Связь с задачей о покрытии. Транспортная задача.

ЛИТЕРАТУРА

  1. Берж К. теория графов и ее применение: Пер. с франц. М., 1962.
  2. Горбатов В. А. Основы дискретной математики. М., 1986.
  3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. М., 1982.
  4. Гоппа В. Д. Введение в алгебраическую теорию информации. М.,1995.
  5. Кристофидес Н. Теория графов. Адгоритмический подход: Пер. с англ. М., 1978.
  6. Орест О. Теория графов: Пер. с англ. М., 1980.
  7. Рейнгольд Э., Нивельгердт Ю., Део Н. Комбинаторные алгоритмы: Пер. с англ. М., 1980.
  8. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: Пер. с англ. М., 1979.

Часть II. ТЕОРИЯ КОНЕЧНЫХ АВТОМАТОВ.

1. ОСНОВНАЯ МОДЕЛЬ.

Определения и примеры. Описание автомата таблицами, графами, матроидами. Перечисление автоматов. Классификация состояний и подавтоматов. Нахождение оптимальных путей и полных контуров.

2. ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ.

Определение эквивалентности автоматов. Минимальная форма. Свойства минимальной формы. Уменьшение числа состояний автомата последовательным объединением эквивалентных состояний. Графовые аналогии. Класс минимальных автоматов.

3. ЭКСПЕРИМЕНТЫ ПО РАСПОЗНАВАНИЮ СОСТОЯНИЙ АВТОМАТА.

Классификация экспериментов. Диагностические и установочные эксперименты: условные, безусловные, простые и кратные. Установочные эксперименты: условные, безусловные, простые и регулярные.

4. ЭКСПЕРИМЕНТЫ ПО РАСПОЗНАВАНИЮ АВТОМАТОВ.

Общая задача распознавания автомата. Распознавание автомата известного класса. Задача распознавания повреждений. Распознавание сильносвязных автоматов. Автоматы без потери информации. Автоматы с конечной памятью. Автоматы с ограничениями на входе.

ЛИТЕРАТУРА

  1. Гилл А. Введение в теорию конечных автоматов: Пер. с англ. М.: Мир, 1966.
  2. Минский М. Вычисления и автоматы: Пер. с англ. М.: Мир, 1971.
  3. Горбатов В. А. Семантическая теория проектирования автоматов. М., 1979.