RUS ENG

Котов В. М. Теория алгоритмов

Котов В. М. Теория алгоритмов: Курс лекций: В 2 ч. Ч. 1. / В. М. Котов, Л. А. Пилипчук, Е. П. Соболевская. - Мн.: БГУ, 2001. - 194 с: ил.

ISBN 985-445-551-3

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

Предназначено для студентов математических, физических и экономических специальностей университета.


Оглавление

ВВЕДЕНИЕ

3

Глава 1. РЕКУРРЕНТНЫЕ УРАВНЕНИЯ

11

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

11

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

12

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

20

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

22

2.1. Основные понятия и определения

22

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

24

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

26

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

27

2.4.1. Пузырьковая сортировка

27

2.4.2. Шейкерная сортировка

28

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

29

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

31

2.7. К-й минимальный элемент

33

2.8. Лексикографическая сортировка

36

Глава 3. РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ

39

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

39

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

41

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

48

4.1. Списки, стеки, очереди

48

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

50

4.1.2. Стеки

56

4.1.3. Очереди

58

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

60

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

64

4.4. Множества

71

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

83

4.5.1 Бинарные кучи

84

4.5.2 D -кучи

98

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

104

4.5.4 Кучи Фибоначчи

114

Глава 5. ПОИСКОВЫЕ ДЕРЕВЬЯ

130

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

130

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

134

5.2.1. АВЛ-деревья

134

5.2.2. 2-3 деревья

151

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

159

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

159

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

164

6.3. Кратчайший путь в графе

168

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

172

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

182

6.6. Топологическая сортировка

187

ЛИТЕРАТУРА 1

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