Алгоритмы и структуры данных (CDIO) (250,00 руб.)

Стр.2

Стр.3

Стр.4

Стр.5

Стр.6

Оглавление Министерство образования и науки Российской Федерации Сибирский федеральный университет Р. Ю. Царёв А. В. Прокопенко АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ (CDIO) Рекомендовано УМО РАЕ по классическому университетскому и техническому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям подготовки: 09.03.04 «Программная инженерия», 09.03.03 «Прикладная информатика», 38.03.02 «Менеджмент», 38.03.05 «Бизнес-информатика» (рег. № 516 от 03.06.2015 г.) Красноярск СФУ 2016 1

Стр.2

Алгоритмы и структуры данных (CDIO) УДК 004.422.63(07) ББК 32.973я73 Ц181 Р е ц е н з е н т ы: А. Н. Антамошкин, доктор технических наук, профессор Красноярского государственного аграрного университета; А. А. Ступина, доктор технических наук, профессор Красноярского государственного аграрного университета Царёв, Р. Ю. Ц181 Алгоритмы и структуры данных (CDIO) : учебник / Р. Ю. Царёв, А. В. Прокопенко. – Красноярск : Сиб. федер. ун-т, 2016. – 204 с. ISBN 978-5-7638-3388-1 Рассмотрены структуры данных и алгоритмы, которые являются основой современной методологии разработки программ. Приведено детальное описание и анализ основных алгоритмов обработки данных: сортировка данных, поиск образа в строке, алгоритмы обработки графов. Предназначен для бакалавров направлений 09.03.04 «Программная инженерия», 09.03.03 «Прикладная информатика», 38.03.02 «Менеджмент», 38.03.05 «Бизнес-информатика» и преподавателей дисциплины «Алгоритмы и структуры данных». Электронный вариант издания см.: http://catalog.sfu-kras.ru ISBN 978-5-7638-3388-1 2 УДК 004.422.63(07) ББК 32.973я73 © Сибирский федеральный университет, 2016

Стр.3

Оглавление ОГЛАВЛЕНИЕ ВВЕДЕНИЕ .......................................................................................................... 6 1. ОБЩИЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ ................................................ 9 1.1. Свойства алгоритмов ............................................................................. 11 1.2. Примеры алгоритмов ............................................................................. 12 1.3. Типы и структуры данных .................................................................... 14 1.4. Абстрактные типы данных ................................................................... 16 1.5. Время выполнения программ ............................................................... 18 1.6. Вычисление времени выполнения программ ..................................... 24 2. ПОИСК ОБРАЗА В СТРОКЕ .................................................................... 34 2.1. Прямой поиск строки ............................................................................ 34 2.2. Алгоритм Кнута, Морриса и Пратта .................................................... 36 2.3. Алгоритм Бойера и Мура ...................................................................... 39 3. СОРТИРОВКА МАССИВОВ ..................................................................... 44 3.1. Сортировка с помощью прямого включения ...................................... 45 3.2. Сортировка с помощью прямого выбора ............................................ 47 3.3. Сортировка с помощью прямого обмена ............................................ 49 3.3.1. Пузырьковая сортировка ............................................................ 49 3.3.2. Шейкерная сортировка ............................................................... 50 3.4. Сортировка Шелла ................................................................................. 52 3.5. Сравнение различных алгоритмов сортировки .................................. 54 4. СОРТИРОВКА ПОСЛЕДОВАТЕЛЬНОСТЕЙ ......................................... 57 4.1. Простое слияние .................................................................................... 57 4.2. Естественное слияние ........................................................................... 61 4.3. Многопутевая сортировка .................................................................... 64 4.4. Многофазная сортировка ...................................................................... 75 5. СТРУКТУРЫ ДАННЫХ ............................................................................. 95 5.1. Массивы .................................................................................................. 95 5.2. Списки .................................................................................................... 96 5.2.1. Стек .............................................................................................. 97 5.2.2. Очередь ........................................................................................ 98 5.2.3. Дек ................................................................................................ 99 3

Стр.4

Алгоритмы и структуры данных (CDIO) 5.3. Деревья ................................................................................................... 99 5.3.1. Двоичное дерево ....................................................................... 101 5.3.2. Двоичное дерево поиска .......................................................... 103 5.3.3. Куча ............................................................................................ 104 5.3.4. АВЛ-дерево ............................................................................... 105 6. ОРИЕНТИРОВАННЫЕ ГРАФЫ .............................................................. 110 6.1. Основные определения ....................................................................... 110 6.2. Представления ориентированных графов ......................................... 112 6.3. Задача нахождения кратчайшего пути .............................................. 114 6.4. Нахождение кратчайших путей между парами вершин .................. 119 6.5. Обход ориентированных графов ........................................................ 125 6.6. Ориентированные ациклические графы ............................................ 129 6.7. Сильная связность ............................................................................... 133 7. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ ........................................................ 136 7.1. Основные определения ........................................................................ 136 7.2. Остовные деревья минимальной стоимости ..................................... 139 7.3. Обход неориентированных графов .................................................... 146 7.4. Точки сочленения и двусвязные компоненты .................................. 150 7.5. Паросочетания графов ......................................................................... 153 7.6. Максимальный поток в сети ............................................................... 157 8. СОВРЕМЕННЫЕ АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ ............... 163 8.1. Алгоритмы и простые числа .............................................................. 163 8.2. Генетические алгоритмы .................................................................... 168 8.3. Муравьиные алгоритмы...................................................................... 173 8.3.1. Биологические принципы поведения муравьиной колонии ................................................................ 174 8.3.2. Идея муравьиного алгоритма .................................................. 174 8.3.3. Формализация задачи коммивояжера в терминах муравьиного подхода ........................................... 175 8.3.4. Области применения и возможные модификации ................ 178 9. ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ........................................................... 180 9.1. Введение в параллелизм ..................................................................... 180 9.1.1. Категории компьютерных систем ........................................... 181 9.1.2. Параллельные архитектуры ..................................................... 182 9.1.3. Принципы анализа параллельных алгоритмов ...................... 184 9.2. Модель PRAM ...................................................................................... 184 4

Стр.5

Оглавление 9.3. Простые параллельные операции ...................................................... 186 9.3.1. Распределение данных в модели CREW PRAM ..................... 186 9.3.2. Распределение данных в модели EREW PRAM ..................... 187 9.3.3. Поиск максимального элемента списка ................................. 188 9.4. Параллельный поиск ........................................................................... 190 9.5. Параллельная сортировка ................................................................... 191 9.5.1. Сортировка на линейных сетях ............................................... 191 9.5.2. Четно-нечетная сортировка перестановками ......................... 195 9.5.3. Другие параллельные сортировки .......................................... 196 9.6. Параллельные алгоритмы на графах ................................................. 196 9.6.1. Параллельный алгоритм поиска кратчайшего пути ............. 196 9.6.2. Параллельный алгоритм поиска минимального остовного дерева ............................................. 198 ЗАКЛЮЧЕНИЕ ............................................................................................... 201 БИБЛИОГРАФИЧЕСКИЙ СПИСОК ........................................................... 203 5

Стр.6