RUS ENG

Теория алгоритмов

Теория алгоритмов : учеб. пособие / П. А. Иржавский [и др.]. − Минск: БГУ, 2013. − 159 с.

ISBN 978-985-518-857-6.

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

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

Посмотреть в электронной бибилиотеке

Оглавление

Предисловие

5

Глава 1. Дерево интервалов

9

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

9

1.2.      Хранение дерева интервалов в памяти

12

1.3.      Базовое использование

15

1.3.1.       Интервальный подсчёт

15

1.3.2.       Одиночное изменение

18

1.4.      Дополнительные возможности

19

1.4.1.       Интервальное изменение

19

1.4.2.       Комбинация интервальных изменений

27

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

31

Глава 2. Строковые алгоритмы и структуры данных

33

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

33

2.2.    Поиск образца в строке

34

2.2.1.    Префиксная функция

35

2.2.2.    Алгоритм Кнута-Морриса-Пратта

38

2.3.    Бор

40

2.4.    Поиск множества образцов в строке

44

2.4.1.    Функция суффиксных ссылок

44

2.4.2.    Функция вывода

45

2.4.3.    Алгоритм Ахо-Корасик

47

2.5.        Суффиксный массив

49

2.5.1.    Построение суффиксного массива

49

2.5.2.    Онлайн-задача поиска образца в строке

53

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

55

Глава 3. Графовые алгоритмы

57

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

57

3.2.    Укладка корневых деревьев

63

3.2.1.     Постановка задачи

64

3.2.2.     Укладка корневого дерева минимальной длины

67

3.2.3.     Укладка корневого дерева минимальной ширины

70

3.3.       Наибольшее паросочетание в графе

74

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

77

3.3.2.     Наибольшее паросочетание в произвольном графе

87

3.3.3.     Специальные паросочетания в двудольном графе

97

3.4.       Специальные кратчайшие маршруты

105

3.4.1.     Кратчайшая простая цепь

106

3.4.2.     Кратчайшая простая цепь с ограничением на число рёбер

121

3.4.3.     Первые к кратчайших простых цепей

123

3.4.4.     Первые к кратчайших маршрутов

132

3.4.5.     Оптимальное &-множество непересекающихся цепей

136

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

152

Библиографические ссылки

159

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