Анализ алгоритмов. Вводный курс - По истечении десятилетия элементная база компьютеров, операционные системы, средства доступа и внешний вид программ меняются коренным образом, однако структуры и алгоритмы, лежащие в их основе, остаются неизменными в течение гораздо большего времени. Эти основы начали закладываться тысячелетия назад, когда были разработаны первые алгоритмы.
Название: Анализ алгоритмов. Вводный курс Автор: Макконнелл Дж. Издательство: Техносфера Год: 2002 Страниц: 304 Формат: PDF Размер: 20,2 МБ ISBN: 5-94836-005-9 Качество: Отличное Серия или Выпуск: Мир программирования Язык: Русский
В предлагаемой вниманию читателя книге обсуждаются алгоритмы решения наиболее широко распространённых классов задач, покрывающих практически всю область программирования: поиск и сортировка, численные алгоритмы и алгоритмы на графах. Особое внимание уделено алгоритмам параллельной обработки, редко освещаемым в литературе на русском языке. Книга носит учебный характер. Она может быть использована как вузовскими преподавателями для организации семестрового курса - так и для самостоятельного изучения. Изложение неформальное и чрезвычайно подробное, с большим количеством упражнений, позволяющих вести самоконтроль. Книга может заинтересовать всех, кому приходится самостоятельно писать программы - от программистов банковских систем до научных работников.
Содержание:
Предисловие 1. Основы анализа алгоритмов 1.1. Что такое анализ? 1.1.1. Классы входных данных 1.1.2. Сложность по памяти 1.1.3. Упражнения 1.2. Что подсчитывать и что учитывать 1.2.1. Упражнения 1.3. Необходимые математические сведения 1.3.1. Логарифмы 1.3.2. Бинарные деревья 1.3.3. Вероятности 1.3.4. Упражнения 1.4. Скорости роста 1.4.1. Классификация скоростей роста 1.4.2. Упражнения 1.5. Алгоритмы вида «разделяй и властвуй» 1.5.1. Метод турниров 1.5.2. Нижние границы 1.5.3. Упражнения 1.6. Рекуррентные соотношения 1.6.1. Упражнения 1.7. Анализ программ 2. Алгоритмы поиска и выборки 2.1. Последовательный поиск 2.1.1. Анализ наихудшего случая 2.1.2. Анализ среднего случая 2.1.3. Упражнения 2.2. Двоичный поиск 2.2.1. Анализ наихудшего случал 2.2.2. Анализ среднего случал 2.2.3. Упражнения 2.3. Выборка 2.3.1. Упражнения 2.4. Упражнение по программированию 3. Алгоритмы сортировки 3.1. Сортировка вставками 3.1.1. Анализ наихудшего случал 3.1.2. Анализ среднего случал 3.1.3. Упражнения 3.2. Пузырьковая сортировка 3.2.1. Анализ наилучшего случал 3.2.2. Анализ наихудшего случал 3.2.3. Анализ среднего случал 3.2.4. Упражнения 3.3. Сортировка Шелла 3.3.1. Анализ алгоритма 3.3.2. Влияние шага на эффективность 3.3.3. Упражнения 3.4. Корневая сортировка 3.4.1. Анализ 3.4.2. Упражнения 3.5. Пирамидальная сортировка 3.5.1. Анализ наихудшего случал 3.5.2. Анализ среднего случал 3.5.3. Упражнения 3.6. Сортировка слиянием 3.6.1. Анализ алгоритма MergeLists 3.6.2. Анализ алгоритма MergeSort 3.6.3. Упражнения 3.7. Быстр ал сортировка 3.7.1. Анализ наихудшего случал 3.7.2. Анализ среднего случал 3.7.3. Упражнения 3.8. Внешняя многофазная сортировка слиянием 3.8.1. Число сравнений при построении отрезков 3.8.2. Число сравнений при слиянии отрезков 3.8.3. Число операций чтения блоков 3.8.4. Упражнения 3.9. Дополнительные упражнения 3.10. Упражнения по программированию 4. Численные алгоритмы 4.1. Вычисление значений многочленов 4.1.1. Схема Горнера 4.1.2. Предварительная обработка коэффициентов 4.1.3. Упражнения 4.2. Умножение матриц 4.2.1. Умножение матриц по Винограду 4.2.2. Умножение матриц по Штрассену 4.2.3. Упражнения 4.3. Решение линейных уравнений 4.3.1. Метод Гаусса-Жордана 4.3.2. Упражнения 5. Алгоритмы сравнения с образцом 5.1. Сравнение строк 5.1.1. Конечные автоматы 5.1.2. Алгоритм Кнута-Морриса-Пратта 5.1.3. Алгоритм Бойера-Мура 5.1.4. Упражнения 5.2. Приблизительное сравнение строк 5.2.1. Анализ 5.2.2. Упражнения 5.3. Упражнения по программированию 6. Алгоритмы на графах 6.1. Основные понятия теории графов 6.1.1. Терминология 6.1.2. Упражнения 6.2. Структуры данных для представления графов 6.2.1. Матрица примыканий 6.2.2. Список примыканий 6.2.3. Упражнения 6.3. Алгоритмы обхода в глубину и по уровням 6.3.1. Обход в глубину 6.3.2. Обход по уровням 6.3.3. Анализ алгоритмов обхода 6.3.4. Упражнения 6.4. Алгоритм поиска минимального остовного дерева 6.4.1. Алгоритм Дейкстры-Прима 6.4.2. Алгоритм Крускала 6.4.3. Упражнения 6.5. Алгоритм поиска кратчайшего пути 6.5.1. Алгоритм Дейкстры 6.5.2. Упражнения 6.6. Алгоритм определения компонент двусвязности 6.6.1. Упражнения 6.7. Разбиения множеств 6.8. Упражнения по программированию 7. Параллельные алгоритмы 7.1. Введение в параллелизм 7.1.1. Категории компьютерных систем 7.1.2. Параллельные архитектуры 7.1.3. Принципы анализа параллельных алгоритмов 7.1.4. Упражнения 7.2. Модель PRAM 7.2.1. Упражнения 7.3. Простые параллельные операции 7.3.1. Распределение данных в модели CREW PRAM 7.3.2. Распределение данных в модели EREW PRAM 7.3.3. Поиск максимального элемента списка 7.3.4. Упражнения 7.4. Параллельный поиск 7.4.1. Упражнения 7.5. Параллельная сортировка 7.5.1. Сортировка на линейных сетях 7.5.2. Четно-нечетная сортировка перестановками 7.5.3. Другие параллельные сортировки 7.5.4. Упражнения 7.6. Параллельные численные алгоритмы 7.6.1. Умножение матриц в параллельных сетях 7.6.2. Умножение матриц в модели CRCW PRAM 7.6.3. Решение систем линейных уравнений алгоритмом SIMD 7.6.4. Упражнения 7.7. Параллельные алгоритмы на графах 7.7.1. Параллельный алгоритм поиска кратчайшего пути 7.7.2. Параллельный алгоритм поиска минимального остовного дерева 7.7.3. Упражнения 8. Недетерминированные алгоритмы 8.1. Что такое NP? 8.1.1. Сведение задачи к другой задаче 8.1.2. NР-полные задачи 8.2. Типичные NP задачи 8.2.1. Раскраска графа 8.2.2. Раскладка по ящикам 8.2.3. Упаковка рюкзака 8.2.4. Задача о суммах элементов подмножеств 8.2.5. Задача об истинности КНФ-выражения 8.2.6. Задача планирования работ 8.2.7. Упражнения 8.3. Какие задачи относятся к классу NP? 8.3.1. Выполнено ли равенство P=NP? 8.3.2. Упражнения 8.4. Проверка возможных решений 8.4.1. Задача о планировании работ 8.4.2. Раскраска графа 8.4.3. Упражнения 9. Другие алгоритмические инструменты 9.1. Жадные приближенные алгоритмы 9.1.1. Приближения в задаче о коммивояжере 9.1.2. Приближения в задаче о раскладке по ящикам 9.1.3. Приближения в задаче об упаковке рюкзака 9.1.4. Приближения в задаче о сумме элементов подмножества 9.1.5. Приближения в задаче о раскраске графа 9.1.6. Упражнения 9.2. Вероятностные алгоритмы 9.2.1. Численные вероятностные алгоритмы 9.2.2. Алгоритмы Монте Карло 9.2.3. Алгоритмы Лас Вегаса 9.2.4. Шервудские алгоритмы 9.2.5. Сравнение вероятностных алгоритмов 9.2.6. Упражнения 9.3. Динамическое программирование 9.3.1. Программирование на основе массивов 9.3.2. Динамическое умножение матриц 9.3.3. Упражнения 9.4. Упражнения по программированию А. Таблица случайных чисел Б. Генерация псевдослучайных чисел Б.1. Случайная последовательность в произвольном интервале Б.2. Пример применения Б.2.1. Первый способ Б.2.2. Второй способ Б.2.3. Третий способ Б.3. Итоги В. Ответы к упражнениям Литература
