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

Стр.2

Стр.64

Стр.65

Стр.66

УДК 004.424.5.021 Л 222 Рецензенты: канд. техн. наук, доцент В.А. Астапчук, старший преподаватель С.А. Менжулин управления для студентов III курса АВТФ направления 09.03.01 – «Информатика и вычислительная техника» Работа подготовлена на кафедре автоматизированных систем Л 222 Алгоритмы обработки данных: учебное пособие / В.В. Ландовский. – Новосибирск: Изд-во НГТУ, 2018. – 67 с. Ландовский В.В. ISBN 978-5-7782-3645-5 В настоящем пособии рассмотрены две группы алгоритмов: алгоритмы сортировки и алгоритмы на строках. Среди алгоритмов сортировки выделены простые обменные методы, имеющие полиномиальную временную сложность, методы с линейно-логарифмической и линейной оценками времени. Представлено описание классических алгоритмов быстрого поиска образца в тексте с использованием вспомогательных структур, приведены алгоритмы их построения. Рассмотрены алгоритмы вычисления редакционного расстояния между строками. УДК 004.424.5.021 ISBN 978-5-7782-3645-5 © Ландовский В.В., 2018 © Новосибирский государственный технический университет, 2018 2

Стр.2

16. Wagner R.A., Fischer M.J. The String-to-String Correction Problem // Journal of the ACM. – 1974. – № 21 (1). – Pp. 168–173. 17. Hirschberg D.S. A linear space algorithm for computing maximal common subsequences // Communications of the ACM. 1975. № 18 (6). – Pp. 341–343. 18. Hunt J.W., Szymanski T.G. A fast algorithm for computing longest common subsequences // Communications of the ACM. – 1977. – № 20 (5). – Pp. 350–353. 64

Стр.64

ОГЛАВЛЕНИЕ Вместо предисловия ................................................................................................ 3 1. Алгоритмы сортировки .................................................................................... 5 1.1. Простые методы ............................................................................................. 5 1.1.1. Сортировка пузырьком ............................................................................ 6 1.1.2. Сортировка вставками ............................................................................. 7 1.1.3. Сортировка выбором ............................................................................... 7 1.2. Сортировка Шелла ....................................................................................... 10 1.3. «Быстрая» сортировка ................................................................................. 11 1.4. Сортировка слиянием .................................................................................. 13 1.5. Пирамидальная сортировка ......................................................................... 15 1.6. Сортировка подсчетом ................................................................................ 17 1.7. Карманная сортировка ................................................................................. 18 1.8. Поразрядная сортировка ............................................................................. 20 2. Строковые алгоритмы .................................................................................... 21 2.1. Поиск подстроки .......................................................................................... 22 2.1.1. Наивный алгоритм ................................................................................. 22 2.1.2. Алгоритм Рабина–Карпа ....................................................................... 23 2.1.3. Префикс-функция .................................................................................. 24 2.1.4. Алгоритм Кнута–Морриса–Пратта ...................................................... 27 2.2. Алгоритм Ахо–Корасик .............................................................................. 28 2.3. Суффиксные деревья ................................................................................... 32 2.3.1. Построение: наивные алгоритмы ......................................................... 34 2.3.2. Применение: поиск подстроки.............................................................. 36 2.3.3. Применение: наибольшая общая подстрока ........................................ 37 2.3.4. Построение за линейное время ............................................................. 38 65

Стр.65

2.4. Суффиксные массивы .................................................................................. 48 2.4.1. Построение без использования деревьев ............................................. 48 2.4.2. Поиск подстроки .................................................................................... 52 2.5. Наибольшая общая подпоследовательность ............................................. 54 2.5.1. Рекурсивный поиск длины LCS ............................................................ 55 2.5.2. Динамическое программирование ........................................................ 57 2.5.3. Алгоритм Хиршберга ............................................................................ 59 2.5.4. Алгоритм Ханта–Шиманского ............................................................. 60 Библиографический список .................................................................................. 63 66

Стр.66