RUS ENG

Котов В. М. Алгоритмы и структуры данных

Котов В. М. Алгоритмы и структуры данных: учеб. пособие / В. М. Котов, Е. П. Соболевская, А. А. Толстиков. — Минск : БГУ, 2011. — 267 с. — (Классическое университетское издание).

ISBN 978-985-518-530-8

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

Предназначено для студентов высших учебных заведений, обучающихся по специальностям «Прикладная математика», «Информатика», «Актуарная математика».


Оглавление

 

ПРЕДИСЛОВИЕ

7

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

 

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

9

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

19

1.3. Решение рекуррентных соотношений

21

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

33

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

 

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

43

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

45

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

46

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

47

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

48

2.2.4. Сортировка слиянием

51

2.2.5. Сортировка с помощью разделения

52

2.3. Внешняя сортировка

55

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

61

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

 

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

64

3.1.1. Массивы

64

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

65

3.1.3. Стеки

70

3.1.4. Очереди

71

3.2. Множества

76

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

77

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

80

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

83

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

83

3.3.2. Биномиальные кучи

91

3.3.3. Кучи Фибоначчи

97

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

109

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

110

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

 

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

113

4.2. Поиск в глубину

117

4.3. Поиск в ширину

121

4.4. Пути в орграфах. Маршруты в графах

123

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

123

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

132

4.4.3. Максимальный путь в бесконтурном орграфе

134

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

135

4.4.5. Наибольшее число маршрутов между заданной парой вершин, не пересекающихся по ребрам

138

4.4.6. к кратчайших ( v , w ) маршрутов, не пересекающихся по ребрам

140

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

143

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

155

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

155

4.6.2. Максимальный поток минимальной стоимости

157

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

160

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

162

4.8. Кратчайший маршрут с нечетным числом ребер

167

4.9. Задача китайского почтальона

169

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

171

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

 

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

174

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

178

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

180

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

180

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

190

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

195

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

195

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

197

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

200

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

 

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

201

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

204

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

211

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

212

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

214

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

217

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

228

ПРИЛОЖЕНИЕ

231

ЛИТЕРАТУРА

265

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