В нем рассмотрены методы
построения алгоритмов на графах, алгоритмов сортировки и
поиска, а также рассматриваются вопросы переключения
алгоритмов. <...> Математически граф G можно определить как пару множеств
Х и U: G = (Х,U), где X – конечное множество, называемое множеством вершин, а U – некоторое множество пар вершин их X. <...> Граф и подграф
Другими важными понятиями являются понятия пути и контура. <...> Тогда
длина пути определяется как сумма длин дуг, составляющих путь
Путь, в котором никакая дуга не встречается дважды, называется простым. <...> Контур - это конечный путь m = (Xi,...,Xk), у которого начальная вершина Xi совпадает с конечной Xk. <...> Неориентированный граф
Иногда граф рассматривают без учета ориентации дуг, тогда
его называют неориентированным графом. <...> Для неориентированного графа понятие "дуга", "путь" и "контур" заменяются понятиями "ребро", "цепь", "цикл". <...> Для неориентированного графа понятия "подграф" и "частичный граф" аналогичны соответствующим понятиям для ориентированного графа. <...> Удаление моста превращает связный граф в несвязный. <...> Однако его подграф, состоящий из вершин a, с, d, е, является связным. <...> Представления графов в компьютере
Описать неориентированный граф G можно путем задания
пары множеств (X, U), где Х – множество вершин; U – множество
ребер. <...> Таким об11
разом, почти все элементы матрицы смежности равны нулю, и
значит, матрица содержит крайне мало информации. <...> Гораздо экономнее представлять дуги в виде списка, но при
этом появляется еще одна неприятность – очень трудно становится определить, какие дуги выходят из данной вершины, а такая
информация в графе, как правило, является главной. <...> Чтобы сохранить возможность быстрого определения множества дуг, исходящих из данной вершины, можно поступать следующим образом. <...> Таким образом, список дуг и соответствующий справочный
массив для графа, изображенного на рис. <...> Поэтому список дуг с оглавлением может выглядеть следующим образом:
12
Список дуг: <...> На каждом шаге после рассмотрения <...>
Методы_построения_эффективных_алгоритмов__учебное_пособие.pdf
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П. Г. Демидова
С.Г. Волченков, Ю.В. Богомолов
Методы построения
эффективных алгоритмов
Рекомендовано
Научно-методическим советом университета
для студентов специальности Математическое обеспечение
и администрирование информационных систем
Ярославль 2005
1
У
ч
еб
н
о
е п
о
со
б
и
е
Стр.1
УДК 510.5
ББК В127я73
В 68
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2005 года
Рецензенты:
кандидат педагогических наук Н.Л. Дашниц;
кафедра теории и методики обучения информатике
Ярославского государственного педагогического университета
им. К.Д. Ушинского
Волченков, С.Г., Богомолов, Ю.В. Методы построения эфВ
68
фективных алгоритмов : учебное пособие / С.Г. Волченков,
Ю.В. Богомолов ; Яросл. гос. ун-т. – Ярославль : ЯрГУ, 2005. –
146 с.
ISBN 5-8397-0401-6
Учебное пособие (продолжение одноименного учебного пособия,
изданного в 2004 г.) посвящено различным аспектам построения
и анализа эффективных алгоритмов решения некоторых
задач. Материал разбит на главы по предметным областям и
по методам решения задач. Главы посвящены геометрическим
методам в задачах информатики, рекурсии, динамическому программированию
и структурам данных.
Пособие рассчитано на студентов факультетов информатики
и вычислительной техники, обучающихся по специальности
351500 Математическое обеспечение и администрирование информационных
систем (дисциплина "Методы построения эффективных
алгоритмов", блок ДС), очной формы обучения, а также
может оказаться интересным для школьников, принимающих
участие в олимпиадах по информатике.
УДК 510.5
ББК В127я73
ISBN 5-8397-0401-6 © Ярославский государственный университет, 2005
© С.Г. Волченков, Ю.В. Богомолов, 2005
2
Стр.2
Предисловие
Данное пособие не претендует на описание всех существующих
методов построения эффективных алгоритмов.
Достаточно сказать, что учебник по алгоритмам, недавно
выпущенный в Массачусетском технологическом институте
[1] и переведенный на русский язык, содержит 955 страниц!
И этот учебник, в свою очередь, тоже далеко не полон. Считается,
что относительной полнотой обладает трёхтомник
Д. Кнута [2], правда, в нём очень сильно ограничен круг
рассматриваемых вопросов, но те, что рассматриваются, разобраны
чрезвычайно пунктуально и интересно. Также существуют
учебники и монографии, которые, как правило,
либо узкоспециализированны, либо, напротив, пытаясь охватить
возможно более широкий круг алгоритмов, носят поверхностный
характер и не содержат достаточного круга задач
[3 – 7, 9 – 13]. Создалась парадоксальная ситуация, когда
при относительно широком освещении рассматриваемой
тематики литература, которую можно было бы рекомендовать
для изучения в рамках соответствующего учебного
курса, труднодоступна.
Предлагаемое учебное пособие является продолжением
пособия, изданного в 2004 году. В нем рассмотрены методы
построения алгоритмов на графах, алгоритмов сортировки и
поиска, а также рассматриваются вопросы переключения
алгоритмов.
3
Стр.3
Глава 1
Алгоритмы на графах
Введение
В одной из компьютерных игр как-то встретилась такая головоломка.
На неровной шахматной доске, состоящей из 10 клеток
(рис.1), расположены два белых и два черных коня. Требуется
поменять коней местами, т.е. расположить белых на места черных
и наоборот. Коней разрешается переставлять по правилам
шахматной игры, т.е. передвигать "буквой Г" на любую свободную
клетку. За один ход можно передвинуть одного коня.
Рис. 1
Несколько попыток решить задачу сходу ни к чему не привели.
Вооружившись карандашом и бумагой, я попытался фиксировать
промежуточные положения коней, но скоро убедился, что
записей стало катастрофически много. Вздохнув и призвав на
помощь знания ранее встречавшихся головоломок и задач, я стал
строить математическую модель задачи. Во-первых, я обозначил
клетки доски числами от 1 до 10 и соединил отрезками центры
клеток, которые связаны друг с другом ходом коня. Получился
рисунок, содержащий всевозможные траектории передвижения
коней по доске (рис. 2)
•
• •
• •
4
•
•
•
Стр.4
• •0
Рис. 2
Теперь можно было заметить, что траектории движения коней
довольно сильно запутаны, и в них трудно разобраться. Распутать
их было несложно, разместив числа, соответствующие
клеткам, в другом порядке: так чтобы клетки, соединенные друг с
другом, были размещены рядом. Получился рисунок 3.
Рис. 3
Теперь на получившейся схеме отметим коней: белых – кружочками,
черных – квадратиками (рис. 4).
Рис. 4
Остается вспомнить, что нам надо сделать. Надо поменять
местами "встретившихся на одной тропинке коней". Для маневра
оставлена клетка 6, на которую может встать один из коней, чтобы
пропустить мимо себя других. Теперь решение задачи рождается
несложно.
Белого коня с клетки 4 передвигаем на клетку 6, пропускаем
черных коней с их начальных позиций на клетки 7 и 1. Затем белого
коня с клетки 6 перегоняем на клетку 3. Один конь на месте!
Отгоняем черных коней на клетки 10 и 2, чтобы освободить
для белого коня, стоящего на клетке 5, проход к клетке 6. Когда
тот туда проходит, черный конь с клетки 10 беспрепятственно
продвигается на клетку 5. Второй конь на месте!
Теперь второй черный конь с клетки 2 проходит мимо клетки
6 на клетку 1, освобождая проход для белого коня. Тот немедленно
пользуется этой ситуацией и продвигается на свое место с
клетки 6 на клетку 2.
5
Стр.5