RUS ENG

Котов В. М. Структуры данных и алгоритмы: теория и практика

Котов В. М. Структуры данных и алгоритмы: теория и практика: Учеб. пособие / В. М. Котов, Е. П. Соболевская. Мн.: БГУ, 2004. - 255 с.

ISBN 985-485-226-1

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

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


Оглавление

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

 

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

3

1.2. Понятие рекуррентного уравнения

10

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

11

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

21

Глава 2. СОРТИРОВКА

 

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

24

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

25

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

27

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

28

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

31

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

33

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

35

2.2.1. Алгоритм сортировки слиянием

36

2.2.2. Минимизация полного времени выполнения

42

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

 

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

45

3.1.1. Массивы

45

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

47

3.1.3. Стеки

53

3.1.4. Очереди

54

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

59

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

64

3.4. Множества

68

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

69

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

73

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

78

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

78

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

87

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

96

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

112

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

 

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

117

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

122

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

122

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

133

4.2.3. Красно-черное дерево

141

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

153

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

153

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

156

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

 

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

160

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

164

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

168

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

168

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

179

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

183

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

185

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

190

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

192

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

203

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

204

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

208

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

212

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

216

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

 

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

222

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

225

6.3. "Жадный" алгоритм

232

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

244

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

244

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

248

6.4.3. Применение границ

249

6.4.4. Функции ветвления

251

ЛИТЕРАТУРА

253

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