Ebook: Алгоритмы и структуры данных

Гагарина Л.Г., Колдаев В.Д.Алгоритмы и структуры данныхПриведены основные понятия алгоритмизации, свойства алгоритмов, общие принципы их построения, основные алгоритмические конструкции, представлена эволюция языков программирования. Рассмотрен широкий круг методов обработки линейных и нелинейных структур данных. Описана технология функционирования и оценки функции сложности различных алгоритмов для работы с очередями, стеками, списками, деревьями, таблицами и графами. В приложениях приведены системы счисления и методы измерения количества информации.Для студентов, аспирантов, преподавателей, специалистов - от инженера до системного аналитика в области численных методов и компьютерного моделирования. Может быть использовано для самообразования.СодержаниеПредисловиеЧасть 1. Основы алгоритмизацииГлава 1. Структурная организация данных1.1. Основные понятия структур данных1.2. Классификация структур данных по признаку изменчивости1.3. Линейные и нелинейные структуры данныхГлава 2. Модели объектов и процессов2.1. Модели структурные и функциональные2.2. Модели натурные и информационные2.3. Классификация моделей2.4. Этапы моделирования2.5. Свойства алгоритма2.6. Виды алгоритмов и их реализация2.7. Базовые канонические структуры алгоритмов2.8. Полное построение алгоритма2.9. Главные принципы создания эффективных алгоритмовГлава 3. Эволюция языков программирования3.1. Классификация языков программирования по функциональному назначению3.2. Классификация языков программирования по парадигме (концепции) и методологии программирования3.3. Классификация языков программирования по типам задачГлава 4. Функция сложности алгоритма4.1. Виды функции сложности алгоритмов4.2. Временная функция сложности4.3. Анализ функции сложности по программе4.4. Оценка алгоритма бинарного поиска4.5. Теоретическая и практическая функции сложностиЧасть 2. Алгоритмы обработки структур данныхГлава 5. Методы сортировки5.1. Сортировка выбором5.2. Сортировка вставкой и сортировка слиянием5.3. Сортировка обменом и шейкерная сортировка5.4. Сортировка Шелла5.5. Быстрая сортировка (сортировка Хоара)5.6. Турнирная сортировка5.7. Пирамидальная сортировкаГлава 6. Методы поиска6.1. Последовательный поиск6.2. Бинарный поиск6.3. Фибоначчиев поиск6.4. Интерполяционный поиск6.5. Поиск по бинарному дереву6.6. Поиск по бору6.7. Поиск хешированием6.8. Алгоритмы поиска словесной информацииГлава 7. Итеративные и рекурсивные алгоритмы7.1. Итеративный алгоритм7.2. Рекурсивный алгоритм7.3. Рекурсивные структуры данных7.4. Виды обхода бинарных деревьевГлава 8. Основные определения теории графов8.1. Изоморфизм графов8.2. Степень вершины графа8.3. Понятие подграфа8.4. Циклы на графе8.5. Цикломатическое число графа8.6. Представление графов в ПЭВМГлава 9. Алгоритмы построения остовного (покрывающего) дерева сети9.1. Метод Крускала9.2. Метод ПримаГлава 10. Алгоритмы нахождения на графах кратчайших путей10.1. Построение дерева решений10.2. Метод динамического программирования10.3. Метод Дейкстры10.4. Алгоритм Флойда10.5. Алгоритм Йена10.6. Алгоритм Беллмана — ФордаГлава 11. Эвристические алгоритмы11.1. Волновой алгоритм11.2. Двухлучевой алгоритм11.3. Четырехлучевой алгоритм11.4. Маршрутный алгоритм11.5. Геометрическая модель задачи о лабиринте11.6. Алгоритмы составления расписания11.7. Задача упаковки11.8. Задача о джипе11.9. Задача о кодовом замкеГлава 12. Метод ветвей и границ. Задача коммивояжера12.1. Расшифровка криптограмм12.2. Задача о радиоактивном шаре12.3. Задача коммивояжера12.4. Примеры решения задачи коммивояжераГлава 13. Моделирование с использованием генераторов случайных чисел13.1. Числовые характеристики случайных величин13.2. Метод середины квадрата13.3. Линейный конгруэнтный метод13.4. Полярный метод генерации случайных чиселГлава 14. Машина Тьюринга14.1. Структура машины Тьюринга14.2. Функциональные таблицы и диаграммы14.3. Примеры записи алгоритмов14.4. Композиция машин ТьюрингаГлава 15. Элементы математической логики15.1. Алгебра высказываний15.2. Законы математической логики15.3. Решение логических задач15.4. Логические основы ПЭВМ15.5. Логический синтез вычислительных схем15.6. Представление логической функции в виде графа15.7. Проверка истинности заключений из серии посылокБиблиографический списокПриложение 1. Системы счисленияПриложение 2. Измерение количества информацииСловарь терминов