Читать онлайн «Основы современных алгоритмов»

Дж. Основы современных алгоритмов. 2 е дополненное издание Москва: Техносфера, 2004. 368с. ISBN 5 94836 005 9 В учебном пособии обсуждаются алгоритмы решения наиболее широко распространенных классов задач, покрывающих практически всю область программирования: поиск и сортировка, численные алго ритмы и алгоритмы на графах. Особое внимание уделено алгоритмам параллельной обработки, редко освещаемым в литературе на русском языке. В дополнении ко 2 му изданию на русском языке даны сведения по теории алгоритмов, оценкам трудоемкости и новейшим алгоритмам, не вошедшие в первоначальный вариант книги. Изложение неформальное и чрезвычайно подробное, с большим коли чеством упражнений, позволяющих вести самоконтроль. Книга нужна всем, кому приходится самостоятельно писать программы --- от програм мистов банковских систем до научных работников. Analysis of Algorithms: An Active Learning Approach © Jones & Publishers © 2004, ЗАО «Техносфера» перевод на русский язык, дополнение, оригинал макет, оформление. ISBN 5 94836 005 9 ISBN (англ. ) ова ДЖ. Основы современных алгоритмов 2 е дополненное издани е Перевод с английского под редакцией Дополнение М. В. Ульянова Рекомендовано Ученым Советом Московской Академии приборостроения и информатики в качествепособия по направлению подготовки специалистов "Информатикаи вычислительная техника ТЕХНОСФЕРА Москва 2004 Содержание Предисловие 9 1. Основы анализа алгоритмов 12 1. 1. Что такое анализ? 14 1. 1. 1. Классы входных данных 19 1. 1. 2. Сложность по памяти 20 1. 1. 3. Упражнения 21 1. 2. Что подсчитывать и что учитывать 22 1. 2. 1. Упражнения 25 1. 3. Необходимые математические сведения 26 1. 3. 1. Логарифмы 26 1. 3. 2. Бинарные деревья 27 1. 3. 3. Вероятности 28 1. 3. 4. Упражнения 31 1. 4. Скорости роста 32 1. 4. 1. Классификация скоростей роста 34 1. 4. 2. Упражнения 36 1. 5. Алгоритмы вида «разделяй и властвуй» 37 1. 5. 1. Метод турниров 41 1. 5. 2. Нижние границы 42 1. 5. 3. Упражнения 44 1. 6. Рекуррентные соотношения 45 1. 6. 1. Упражнения 50 1. 7. Анализ программ 51 2. Алгоритмы поиска и выборки 53 2. 1. Последовательный поиск 55 2. 1. 1. Анализ наихудшего случая 56 2. 1. 2. Анализ среднего случая 56 2. 1. 3. Упражнения 58 2. 2. Двоичный поиск 59 2. 2. 1. Анализ наихудшего случая 61 2. 2. 2. Анализ среднего случая 62 2. 2. 3. Упражнения 64 2. 3. Выборка 66 2. 3. 1. Упражнения 68 2. 4. Упражнение по программированию 69 4 Содержание 3. Алгоритмы сортировки 70 3. 1. Сортировка вставками 72 3. 1. 1. Анализ наихудшего случая 73 3. 1. 2. Анализ среднего случая 74 3. 1. 3. Упражнения 76 3. 2. Пузырьковая сортировка 77 3. 2. 1. Анализ наилучшего случая 78 3. 2. 2. Анализ наихудшего случая 78 3. 2. 3. Анализ среднего случая 79 3. 2. 4. Упражнения 81 3. 3. Сортировка Шелла 82 3. 3. 1. Анализ алгоритма 84 3. 3. 2. Влияние шага на эффективность 86 3. 3. 3. Упражнения 87 3. 4. Корневая сортировка 87 3. 4. 1. Анализ 90 3. 4. 2. Упражнения 91 3. 5. Пирамидальная сортировка 92 3. 5. 1. Анализ наихудшего случая 95 3. 5. 2.