В учебном пособии рассматриваются базовые структуры данных и важнейшие алгоритмы, используемые при разработке системного и прикладного программного обеспечения. Излагаются наиболее эффективные алгоритмы сортировки и поиска данных, рассматриваются комбинаторные задачи и методы их решения (метод ветвей и границ, динамическое программирование, эвристические алгоритмы). Подчеркивается важность оценки эффективности алгоритмов при проектировании программ. Дается представление о теории вычислительной сложности и о проблемах, связанных с понятием NP-полноты задач.Предназначено для студентов, обучающихся по направлениям подготовки бакалавров 02.03.03 «Математическое обеспечение и администрирование информационных систем» и 09.03.04 «Программная инженерия».

1. ВВЕДЕНИЕ......71.1. Предмет и задачи курса......71.2. Рекомендации по литературе......71.3. Понятие типа данных......8Контрольные вопросы......102. ПРОСТЫЕ ТИПЫ ДАННЫХ......102.1. Числовые типы данных......102.2. Логический тип данных......132.3. Другие простые типы......162.3.1. Символьный тип......162.3.2. Перечисляемые типы данных......172.3.3. Ограниченные типы данных......18Контрольные вопросы......183. СТРУКТУРНЫЕ ТИПЫ ДАННЫХ......193.1. Способы представления структурных данных......193.2. Записи......213.3. Массивы......233.4. Строки......243.5. Множества......263.6. Стеки......283.7. Очереди......343.8. Приоритетные очереди......403.9. Линейные списки......443.10. Деревья......483.10.1. Основные определения......483.10.2. Бинарные деревья и их представление......493.10.3. Операции с деревьями......503.10.4. Устранение рекурсии при операциях с деревьями......563.11. Последовательные контейнеры......603.11.1. Контейнеры в библиотеке STL......603.11.2. Массивы......613.11.3. Списки......623.11.4. Дек......633.11.5. Стек и очередь......653.11.6. Приоритетная очередь......65Контрольные вопросы......664. СОРТИРОВКА И ПОИСК......674.1. Задачи поиска в информатике......674.2. Задача поиска в таблице......684.3. Понятие об оценке эффективности алгоритмов и программ......704.4. Линейный поиск......744.5. Бинарный поиск......774.6. Задачи сортировки таблиц и массивов......794.7. Простые алгоритмы сортировки......814.7.1. Алгоритм пузырька (BubbleSort)......814.7.2. Алгоритм выбора (SelectionSort)......824.7.3. Алгоритм вставок (InsertionSort)......824.7.4. Общая характеристика простых алгоритмов......834.8. Алгоритм Шелла (ShellSort)......844.9. Алгоритм быстрой сортировки (QuickSort)......854.10. Алгоритм пирамидальной сортировки (HeapSort)......894.11. Алгоритмы сортировки слиянием (MergeSort)......944.12. Задача внешней сортировки......964.13. Сравнение алгоритмов сортировки......99Контрольные вопросы......1005. ПОИСК СО ВСТАВКОЙ......1025.1. Постановка задачи......1025.2. Бинарные деревья поиска......1045.3. АВЛ-деревья......1095.4. Страничные деревья поиска......1135.5. B-деревья......1175.6. Использование B-деревьев в базах данных......1225.7. Ассоциативные контейнеры на базе деревьев поиска......1235.7.1. Структуры данных......1235.7.2. Множества......1245.7.3. Отображения......125Контрольные вопросы......1256. СПЕЦИАЛЬНЫЕ МЕТОДЫ СОРТИРОВКИ И ПОИСКА......1266.1. Поразрядная сортировка......1276.2. Поиск в словаре и боры......1326.3. Определение порядковых статистик......134Контрольные вопросы......1367. ХЕШИРОВАНИЕ......1377.1. Основные понятия хеширования......1377.2. Способы построения хеш-функций......1407.2.1. Общие требования к хеш-функциям......1407.2.2. Алгоритм деления......1417.2.3. Алгоритм середины квадрата......1427.2.4. Алгоритм умножения......1447.2.5. Хеширование строковых ключей......1457.3. Методы разрешения коллизий......1477.3.1. Алгоритм линейных проб......1487.3.2. Алгоритм квадратичных проб......1487.3.3. Алгоритм двойного хеширования......1497.3.4. Алгоритм списков в динамической памяти......1497.3.5. Алгоритм Уильямса......1507.4. Условия эффективности хеширования......1507.5. Другие применения хеширования......1527.5.1. Проверка принадлежности к множеству......1527.5.2. Проверка целостности сообщений и текстовых файлов......1537.5.3. Криптографическое хеширование......1547.6. Ассоциативные контейнеры на базе хеширования......155Контрольные вопросы......1568. МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ......1578.1. Понятие комбинаторной задачи......1578.2. Примеры комбинаторных задач......1588.3. Организация исчерпывающего перебора с возвратами......1628.4. Сокращение перебора......1668.5. Полный перебор с перечислением планов......1688.6. Метод ветвей и границ......1708.6.1. Общее понятие о методе ветвей и границ......1708.6.2. Метод ветвей и границ для задачи о коммивояжере......1738.7. Метод α-β-отсечений для позиционных игр с полной информацией......1808.8. Метод динамического программирования......1848.8.1. Задача о двух армиях и рекуррентные вычисления......1848.8.2. Общее понятие о методе динамического программирования......1878.8.3. Метод динамического программирования для задачи о рюкзаке......1908.8.4. Метод динамического программирования для задачи о наибольшей общей подпоследовательности......1948.9. Приближенные и эвристические методы решения задач комбинаторной оптимизации......1968.9.1. Точные
приближенные и эвристические алгоритмы......1968.9.2. «Жадные» алгоритмы......1988.9.3. Генетические алгоритмы......2008.9.4. О доказательствах и контрпримерах......201Контрольные вопросы......2029. ЭЛЕМЕНТЫ ТЕОРИИ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ......2039.1. Основные понятия и проблемы теории сложности вычислений......2039.2. Полиномиальная сводимость задач......2079.3. Недетерминированные машины Тьюринга и NP-задачи......2079.4. NP-полные и NP-трудные задачи......2119.5. Теорема Кука......2129.5.1. Постановка задачи......2129.5.2. Формулировка теоремы......2139.5.3. Доказательство теоремы......2139.6. Примеры NP-полных задач......2169.6.1. Задача «3-Выполнимость» (задача «3-ВЫП»)......2169.6.2. Задача о вершинном покрытии графа (задача ВП)......2189.6.3. Другие NP-полные задачи......2209.7. Псевдополиномиальные задачи......2219.8. Практическое значение результатов теории сложности вычислений......223Контрольные вопросы......225ЗАКЛЮЧЕНИЕ......226БИБЛИОГРАФИЧЕСКИЙ СПИСОК......227