RUS ENG

Котов В. М. Разработка и анализ алгоритмов : теория и практика

Котов В. М. Разработка и анализ алгоритмов : теория и практика: пособие для студентов мат. и физ. специальностей / В. М. Котов, Е. П. Соболевская. - Минск : БГУ, 2009. - 251 с.

ISBN 978-985-518-107-2

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

Для студентов БГУ, обучающихся по математическим и физическим специальностям.


Оглавление

ПРЕДИСЛОВИЕ

3

Глава 1. ПРОЕКТИРОВАНИЕ И АНАЛИЗ

 

1.1. Трудоемкость алгоритма

5

1.2. Понятие рекуррентного соотношения

20

1.3. Решение рекуррентных уравнений

22

1.4. Примеры рекуррентных уравнений

38

Глава 2. БАЗОВЫЕ АЛГОРИТМЫ ПОИСКА И СОРТИРОВКИ

 

2.1. Поиск элемента

50

2.2. Внутренняя сортировка

53

2.2.1. Сортировка с помощью включения

53

2.2.2. Сортировка выбором

56

2.2.3. Сортировка с помощью обменов

57

2.3. Алгоритмы выборки

60

Глава 3. СТРУКТУРЫ ДАННЫХ

 

3.1. Элементарные структуры данных

63

3.1.1. Массивы

63

3.1.2. Линейные списки

64

3.1.3. Стеки

70

3.1.4. Очереди

72

3.2. Множества

77

3.2.1. Представление множеств с помощью списков

79

3.2.2. Представление множеств с помощью деревьев

82

3.3. Приоритетные очереди

87

3.3.1. Бинарные кучи

88

3.3.2. Применение приоритетных очередей

97

3.4. Задачи для самостоятельного решения

98

Глава 4. ОСНОВНЫЕ АЛГОРИТМЫ НА ГРАФАХ

 

4.1. Графы. Основные определения

103

4.2. Поиск в глубину в графе

108

4.3. Поиск в ширину в графе

114

4.4. Пути в графах

118

4.4.1. Кратчайший элементарный путь

118

4.4.2. Кратчайшие пути (маршруты)

129

4.4.3. Эйлеров цикл

132

4.5. Максимальный поток в графе и его приложения

136

4.6. Циклы отрицательной стоимости

151

4.6.1. Максимальное взвешенное паросочетание в двудольном графе

151

4.6.2. Минимальный средний контур в орграфе с положительными стоимостями дуг

158

4.7. Минимальное остовное дерево

162

4.8. Задачи для самостоятельного решения

167

Глава 5. ОРГАНИЗАЦИЯ ПОИСКА

 

5.1. Деревья. Основные определения

171

5.2. Бинарные поисковые деревья

176

5.3. Сбалансированные деревья

180

5.3.1. АВЛ-дерево

180

5.3.2. 2-3-дерево

191

5.4. Хеш-таблицы

199

5.4.1, Открытое хеширование

200

5.4.2. Закрытое хеширование

202

5.5. Задачи для самостоятельного решения

206

Глава 6. СТРАТЕГИИ РЕШЕНИЯ ЗАДАЧ

 

6.1. Метод «разделяй и властвуй»

208

6.2. Динамическое программирование

213

6.3. Организация перебора

221

6.3.1. Построение дерева решений

222

6.3.2. Способы обхода дерева решений

225

6.3.3. Сокращение числа необходимых для решения подзадач: отсев возможных вариантов ветвления

229

6.4. Задачи для самостоятельного решения

245

ЛИТЕРАТУРА

249

Другие сайты факультетаСтруктураОбразованиеМагистратураНаукаМеждународное сотрудничествоСтудентуНИРСАСовет молодых ученыхОлимпиадыАбитуриентуШкольникуЦентр
Компетенций
по ИТ
Microsoft
Imagine Premium
ИсторияИздания факультетаПрофбюро ФПМИПерсональные страницыФотогалереи Газета ФПМыНаши партнеры