Алгоритмы и структуры обработки информации, Курносов М.Г., Берлизов Д.М., 2019

Алгоритмы и структуры обработки информации, Курносов М.Г., Берлизов Д.М., 2019.

   В книге рассмотрены фундаментальные структуры и алгоритмы обработки данных. Изложены основы асимптотического анализа вычислительной сложности итеративных и рекурсивных алгоритмов. Приведены классические методы сортировки и поиска информации. Значительная часть материала посвящена подходам к реализации абстрактных типов данных: списков, множеств, ассоциативных массивов и очередей с приоритетами. В конце каждого раздела приведены упражнения.
Книга ориентирована в первую очередь на студентов младших курсов соответствующих специальностей, что нашло отражение в стиле и глубине изложения материала.




Рекурсивные алгоритмы.
При проектировании и реализации различных структур данных и алгоритмов достаточно часто приходится иметь дело с рекурсивными функциями.

Рекурсивная функция (recursive function) - это функция, в теле которой присутствует вызов самой себя. Соответственно, алгоритм, основанный на таких функциях, называется рекурсивным алгоритмом (recursive algorithm). В практике программирования встречаются различные формы рекурсии. Ниже приведен пример прямой рекурсии (direct recursion) для вычисления факториала заданного числа п. Такая форма рекурсии подразумевает присутствие вызова функции непосредственно в ее теле. Если же некоторая функция А вызывает функцию В, а функция В реализует рекурсивный вызов А, то мы имеем дело с косвенной рекурсией (indirect recursion).

Рекурсивный алгоритм можно охарактеризовать деревом рекурсивных вызовов (recursion tree). В таком дереве каждый узел соответствует вызову функции. Время выполнения рекурсивного алгоритма определяется числом узлов в его дереве рекурсивных вызовов. Точнее говоря, суммарным временем выполнения всех узлов - временем реализации всех рекурсивных вызовов.

Оглавление.
Предисловие.
1. Алгоритмы и их эффективность.
1.1. Задача, алгоритм, программа.
1.2. Показатели эффективности алгоритмов.
1.3. Подсчет числа операций алгоритма.
1.4. Скорость роста функций.
1.5. Асимптотические обозначения.
1.6. Этапы асимптотического анализа.
1.7. Упражнения.
2. Анализ рекурсивных алгоритмов.
2.1. Рекурсивные алгоритмы.
2.2. Сортировка слиянием.
2.3. Решение рекуррентных уравнений.
2.4. Упражнения.
3. Сортировка.
3.1. Задача сортировки.
3.2. Свойства и виды алгоритмов сортировки.
3.3. Сортировка вставкой.
3.4. Сортировка выбором.
3.5. Нижняя граница времени сортировки сравнением.
3.6. Быстрая сортировка.
3.7. Сортировка слиянием.
3.8. Пирамидальная сортировка.
3.9. Сортировка подсчетом.
3.10. Выбор алгоритма сортировки.
3.11. Упражнения.
4. Поиск.
4.1. Задача поиска.
4.2. Линейный поиск.
4.3. Бинарный поиск.
4.4. Упражнения.
5. Абстрактные типы данных.
5.1. Базовые типы данных.
5.2. Структуры данных.
5.3. Абстрактные типы данных.
5.4. Выбор абстрактного типа данных.
5.5. Упражнения.
6. Списки.
6.1. АТД список.
6.2. Реализация списков на базе массивов.
6.3. Связные списки.
6.4. Односвязные списки.
6.5. Двусвязные списки.
6.6. Реализация АТД список.
6.7. Упражнения.
7. Стеки.
7.1. АТД стек.
7.2. Реализация стека на базе массива.
7.3. Реализация стека на базе односвязного списка.
7.4. Сравнение реализаций.
7.5. Упражнения.
8. Очереди.
8.1. АТД очередь.
8.2. Реализация очереди на базе связного списка.
8.3. Реализация очереди на базе кольцевого буфера.
8.4. Сравнение реализаций.
8.5. Упражнения.
9. Бинарные деревья.
9.1. Корневые деревья.
9.2. Бинарные деревья.
9.3. Представление деревьев в памяти.
9.4. Обходы бинарных деревьев.
9.5. Упражнения.
10. Бинарные деревья поиска.
10.1. Структура бинарного дерева поиска.
10.2. Создание узла.
10.3. Добавление узла.
10.4. Поиск узла по ключу.
10.5. Поиск минимального и максимального узлов.
10.6. Поиск следующего и предыдущего узлов.
10.7. Обход дерева в упорядоченной последовательности.
10.8. Удаление узла.
10.9. Удаление дерева.
10.10. Высота бинарного дерева поиска.
10.11. Упражнения.
11. Красно-черные деревья.
11.1. Структура узла красно-черного дерева.
11.2. Высота красно-черного дерева.
11.3. Добавление узла.
11.4. Удаление узла.
11.5. Упражнения.
12. Префиксные деревья.
12.1. Структура префиксного дерева.
12.2. Вставка элемента.
12.3. Поиск элемента.
12.4. Удаление элемента.
12.5. Узел префиксного дерева.
12.6. Представление дерева на основе связных списков.
12.7. Трудоемкость операций префиксного дерева.
12.8. Упражнения.
13. Хеш-таблицы.
13.1. Таблицы с прямой адресацией.
13.2. Хеш-таблицы.
13.3. Метод цепочек.
13.4. Открытая адресация.
13.5. Хеш-функции.
13.6. Преобразование ключей в целые числа.
13.7. Упражнения.
14. Бинарные кучи.
14.1. Представление в памяти.
14.2. Операции бинарной кучи.
14.3. Пирамидальная сортировка.
14.4. Упражнения.
15. Биномиальные кучи.
15.1. Структура биномиальной кучи.
15.2. Поиск минимального элемента.
15.3. Слияние биномиальных куч.
15.4. Вставка узла.
15.5. Удаление минимального узла.
15.6. Понижение приоритета узла.
15.7. Упражнения.
16. Приложения.
16.1. Функции округления.
16.2. Прогрессии.
16.3. Некоторые числовые ряды.
16.4. Логарифмы.
16.5. Факториалы.
16.6. Числа Фибоначчи.
Предметный указатель.
Литература.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Алгоритмы и структуры обработки информации, Курносов М.Г., Берлизов Д.М., 2019 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по программированию :: программирование :: Курносов :: Берлизов