Предисловие

С 2007 г. на кафедре программирования для студентов механико-математического факультета НГУ, специализирующихся на кафедре программирования, читается годовой спецкурс “Графы в программировании”.

Цели курса:

$\bullet$ дать обучающимся систематизированные базовые знания об основных теоретико-графовых моделях, методах и алгоритмах, применяемых в программировании;

$\bullet$ дать возможность обучающимся приобрести навыки и умения, необходимые для успешного использования теоретико-графовых моделей, методов и алгоритмов при построении вычислительных, программных и информационных систем;

$\bullet$ сформировать у обучающихся аналитические способности, которые бы позволили им делать обоснованный выбор изученных теоретико-графовых моделей, методов и алгоритмов при решении различного класса задач программирования.

Курс состоит из трёх частей.

Первая часть курса посвящена базовым моделям и алгоритмам, связанным с применением теории графов в программировании. Изложение материала привязано к трём основным типам графов: деревья, дэги или бесконтурные графы и сводимые или регуляризуемые графы. Алгоритмы для данных типов графов образуют наиболее важные и широко используемые в программировании классы алгоритмов теории графов.

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

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

Учебное пособие поддерживает вторую часть курса и содержит описание основных существующих методов и систем построения наглядных изображений графов и визуализации структурированной информации на основе графовых моделей. Оно подготовлено при частичной финансовой поддержке Российского фонда фундаментальных исследований (грант РФФИ № 12-07-00091).