|
Книги: [Классика] [Базы данных] [Internet/WWW] [Сети] [Программирование] [UNIX] [Windows] [Безопасность] [Графика] [Software Engineering] [ERP-системы] [Hardware]
Содержание
Предисловие
Представление алгоритмов
Содержание книги
Упражнения
Благодарности
ГЛАВА 1. Построение и анализ алгоритмов
1.1. От задачи к программе
Алгоритмы
Псевдоязык и пошаговая "кристаллизация" алгоритмов
Резюме
1.2. Абстрактные типы данных
Определение абстрактного типа данных
1.3. Типы данных, структуры данных и абстрактные типы данных
Указатели и курсоры
1.4. Время выполнения программ
Измерение времени выполнения программ
Асимптотические соотношения
Ограниченность показателя степени роста
Немного соли
1.5. Вычисление времени выполнения программ
Вызовы процедур
Программы с операторами безусловного перехода
Анализ программ на псевдоязыке
1.6. Практика программирования
1.7. Расширение языка Pascal
Упражнения
Библиографические замечания
ГЛАВА 2. Основные абстрактные типы данных
2.1. Абстрактный тип данных "Список"
2.2. Реализация списков
Реализация списков посредством массивов
Реализация списков с помощью указателей
Сравнение реализации
Реализация списков на основе курсоров
Дважды связные списки
2.3. Стеки
Реализация стеков с помощью массивов
2.4. Очереди
Реализация очередей с помощью указателей
Реализация очередей с помощью циклических массивов
2.5. Отображения
Реализация отображений посредством массивов
Реализация отображений посредством списков
2.6. Стеки и рекурсивные процедуры
Исключение "концевых" рекурсий
Полное исключение рекурсий
Упражнения
Библиографические примечания
ГЛАВА 3. Деревья
3.1. Основная терминология
Порядок узлов
Прямой, обратный и симметричный обходы дерева
Помеченные деревья и деревья выражений
Вычисление "наследственных" данных
3.2. Абстрактный тип данных TREE
3.3. Реализация деревьев
Представление деревьев с помощью массивов
Представление деревьев с использованием списков сыновей
Представление левых сыновей и правых братьев
3.4. Двоичные деревья
Представление двоичных деревьев
Пример: коды Хаффмана
Реализация двоичных деревьев с помощью указателей
Упражнения
Библиографические замечания
ГЛАВА 4. Основные операторы множеств
4.1. Введения в множества
Система обозначений для множеств
Операторы АТД, основанные на множествах
4.2. АТД с операторами множеств
4.3. Реализация множеств посредством двоичных векторов
4.4. Реализация множеств посредством связанных списков
4.5. Словари
4.6. Реализации словарей
4.7. Структуры данных, основанные на хеш-таблицах
Открытое хеширование
Закрытое хеширование
4.8. Оценка эффективности хеш-функций
Анализ закрытого хеширования
"Случайные" методики разрешения коллизий
Реструктуризация хеш-таблиц
4.9. Реализация АТД для отображений
4.10. Очереди с приоритетами
4.11. Реализация очередей с приоритетами
Реализация очереди с приоритетами посредством частично упорядоченных деревьев
Реализация частично упорядоченных деревьев посредством массивов
4.12. Некоторые структуры сложных множеств
Отношения "многие-ко-многим" и структура мультисписков
Структуры мультисписков
Эффективность двойных структур данных
Упражнения
Библиографические примечания
ГЛАВА 5. Специальные методы представления множеств
5.1. Деревья двоичного поиска
5.2. Анализ времени выполнения операторов
Эффективность деревьев двоичного поиска
5.3. Нагруженные деревья
Узлы нагруженного дерева как АТД
Представление узлов нагруженного дерева посредством списков
Эффективность структуры данных нагруженных деревьев
5.4. Реализация множеств посредством сбалансированных деревьев
Вставка элемента в 2-3 дерево
Удаление элемента из 2-3 дерева
Типы данных для 2-3 деревьев
Реализация оператора INSERT
Реализация оператора DELETE
5.5. Множества с операторами MERGE и FIND
Простая реализация АТД MFSET
Быстрая реализация АТД MFSET
Реализация АТД MFSET посредством деревьев
Сжатие путей Функция а(п)
5.6. АТД с операторами MERGE и SPLIT
Задача наибольшей общей подпоследовательности
Анализ времени выполнения алгоритма нахождения НОП
Упражнения
Библиографические примечания
ГЛАВА 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. "Карманная" сортировка
Анализ "карманной" сортировки
Сортировка множеств с большими значениями ключей
Общая поразрядная сортировка
Анализ поразрядной сортировки
8.6. Время выполнения сортировок сравнениями
Деревья решений
Размер дерева решений
Анализ времени выполнения в среднем
8.7. Порядковые статистики
Вариант быстрой сортировки
Линейный метод нахождения порядковых статистик
Случай равенства некоторых значений ключей
Упражнения
Библиографические примечания
ГЛАВА 9. Методы анализа алгоритмов
9.1. Эффективность алгоритмов
9.2. Анализ рекурсивных программ
9.3. Решение рекуррентных соотношений
Оценка решений рекуррентных соотношений
Оценка решения рекуррентного соотношения методом подстановки
9.4. Общее решение большого класса рекуррентных уравнений
Однородные и частные решения
Мультипликативные функции
Другие управляющие функции
Упражнения
Библиографические примечания
ГЛАВА 10. Методы разработки алгоритмов
10.1. Алгоритмы "разделяй и властвуй"
Умножение длинных целочисленных значений
Составление графика проведения теннисного турнира
Баланс подзадач
10.2. Динамическое программирование
Вероятность победы в спортивных турнирах
Задача триангуляции
Поиск решений на основе таблицы
10.3. "Жадные" алгоритмы
"Жадные" алгоритмы как эвристики
10.4. Поиск с возвратом
Функции выигрыша
Реализация поиска с возвратом
Альфа-бета отсечение
Метод ветвей и границ
Ограничения эвристических алгоритмов
10.5. Алгоритмы локального поиска
Локальные и глобальные оптимальные решения
Задача коммивояжера
Размещение блоков
Упражнения
Библиографические примечания
ГЛАВА 11. Структуры данных и алгоритмы для внешней памяти
11.1. Модель внешних вычислений
Стоимость операций со вторичной памятью
11.2. Внешняя сортировка
Сортировка слиянием
Ускорение сортировки слиянием
Минимизация полного времени выполнения
Многоканальное слияние
Многофазная сортировка
Когда скорость ввода-вывода не является "узким местом"
Схема с шестью входными буферами
Схема с четырьмя буферами
11.3. Хранение данных в файлах
Простая организация данных
Ускорение операций с файлами
Хешированные файлы
Индексированные файлы
Несортированные файлы с плотным индексом
Вторичные индексы
11.4. Внешние деревья поиска
Разветвленные деревья поиска
В-деревья
Поиск записей
Вставка записей
Удаление записей
Время выполнения операций с В-деревом
Сравнение методов
Упражнения
Библиографические примечания
ГЛАВА 12. Управление памятью
12.1. Проблемы управления памятью
12.2. Управление блоками одинакового размера
Контрольные счетчики
12.3. Алгоритмы чистки памяти для блоков одинакового размера
Сборка на месте
Алгоритм Дойча : Шорра : Уэйта без использования поля back
12.4. Выделение памяти для объектов разного размера
Фрагментация и уплотнение пустых блоков
Выбор свободных блоков
12.5. Методы близнецов
Распределение блоков
Выделение блоков
Возврат блоков в свободное пространство
12.6. Уплотнение памяти
Задача уплотнения памяти
Алгоритм Морриса
Упражнения
Библиографические примечания
Список литературы
Предметный указатель
Начало
Введение
Заказать книгу в магазине "Мистраль"
|
|
Виртуальные VPS серверы в РФ и ЕС
🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях
