Учебное пособие по курсу «Структуры и алгоритмы обработки данных»


НазваниеУчебное пособие по курсу «Структуры и алгоритмы обработки данных»
страница1/56
Дата22.04.2013
Размер3.34 Mb.
ТипУчебное пособие
  1   2   3   4   5   6   7   8   9   ...   56


Царев Роман Юрьевич


Структуры и алгоритмы обработки данных


Учебное пособие по курсу
«Структуры и алгоритмы обработки данных»


Красноярск 2005г.

Рассмотрены структуры и алгоритмы, которые являются основой современной методологии разработки программ. Изложено детальное описание и анализ основных алгоритмов обработки данных: сортировка данных, поиск образа в строке, алгоритмы обработки графов. Приведены алгоритмы параллельной обработки данных.

Студентам укрупненной группы направлений подготовки специалистов 230000 – «Информатика и вычислительная техника» (спец. 230102.65, 230104.65, 230105.65, 230201.65), преподавателям, аспирантам, а также программистам различной квалификации.

Оглавление

Предисловие 7

1. Общие сведения об алгоритмах 10

1.1. Свойства алгоритмов 11

1.2. Примеры алгоритмов 13

1.3. Типы данных, структуры данных и абстрактные типы данных 15

1.4. Абстрактные типы данных 17

1.5. Время выполнения программ 18

1.6. Вычисление времени выполнения программ 25

2. Поиск образа в строке 34

2.1. Прямой поиск строки 34

2.2. Алгоритм Кнута, Морриса и Пратта 35

2.3. Алгоритм Боуера и Мура 38

3. Сортировка массивов 44

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

3.2. Сортировка с помощью прямого выбора 46

3.3. Сортировка с помощью прямого обмена 48

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

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

3.4. Сортировка Шелла 51

3.5. Сравнение различных алгоритмов сортировки 53

4. Сортировка последовательностей 56

4.1. Простое слияние 56

4.2. Естественное слияние 61

4.3. Многопутевая сортировка 65

4.4. Многофазная сортировка 76

5. Ориентированные графы 93

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

5.2. Представления ориентированных графов 95

5.3. Задача нахождения кратчайшего пути 97

5.4. Нахождение кратчайших путей между парами вершин 102

5.5. Обход ориентированных графов 108

5.6. Ориентированные ациклические графы 112

5.7. Сильная связность 116

6. Неориентированные графы 121

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

6.2. Остовные деревья минимальной стоимости 124

6.3. Обход неориентированных графов 131

6.4. Точки сочленения и двусвязные компоненты 136

6.5. Паросочетания графов 138

7. Алгоритмы нахождения максимального потока 142

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

7.2. Сводимость некоторых задач о максимальном потоке в сети к рассматриваемой 145

7.3. Алгоритм Форда – Фалкерсона 146

7.4. Алгоритм кратчайших увеличивающих цепей
Эдмондса – Карпа 149

7.5. Алгоритм локально-максимального увеличения
Эдмондса – Карпа 150

7.6. Алгоритм Диница 150

7.7. Алгоритм Карзанова 153

7.8. Алгоритм Малхотри – Кумара – Махешвари 156

7.9. Алгоритм Галила – Наамада 157

7.10. Алгоритм Слейтора – Тарьяна 158

7.11. Алгоритм Голдберга – Таряна 160

7.12. Алгоритм Черияна – Хагерапа – Мелхорна 163

7.13. Алгоритм Кинга 165

7.14. Алгоритм Голдберга – Рао 166

7.15. Хронологическая таблица достижений в решении
задачи о максимальном потоке 168

8. Параллельные алгоритмы 170

8.1. Введение в параллелизм 170

8.1.1. Категории компьютерных систем 170

8.1.2. Параллельные архитектуры 172

8.1.3. Принципы анализа параллельных алгоритмов 174

8.2. Модель PRAM 174

8.3. Простые параллельные операции 176

8.3.1. Распределение данных в модели CREW PRAM 176

8.3.2. Распределение данных в модели EREW PRAM 177

8.3.3. Поиск максимального элемента списка 178

8.4. Параллельный поиск 180

8.5. Параллельная сортировка 181

8.5.1. Сортировка на линейных сетях 181

8.5.2. Четно-нечетная сортировка перестановками 185

8.5.3. Другие параллельные сортировки 186

8.6. Параллельные численные алгоритмы 186

8.6.2. Умножение матриц в модели CRCW PRAM 191

8.6.3. Решение систем линейных уравнений алгоритмом SIMD 192

8.7. Параллельные алгоритмы на графах 193

8.7.1. Параллельный алгоритм поиска кратчайшего пути 193

8.7.2. Параллельный алгоритм поиска минимального остовного дерева 195

9. Современные алгоритмы обработки данных 198

9.1. Алгоритмы и простые числа 198

9.2. Генетические алгоритмы 205

9.3. Муравьиные алгоритмы 210

9.3.1. Биологические принципы поведения муравьиной колонии 210

9.3.2. Идея муравьиного алгоритма 211

9.3.3. Формализация задачи коммивояжера в терминах муравьиного подхода 212

9.3.4. Области применения и возможные модификации 214

9.4. Метод ветвей и границ 216

Заключение 229

Библиографический список 230
  1   2   3   4   5   6   7   8   9   ...   56

Добавить документ в свой блог или на сайт

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница