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

Дж. Макконнелл Основы современных алгоритмов. 2-е дополненное издание Москва: Техносфера, 2004. - 368с. ISBN 5-94836-005-9 В учебном пособии обсуждаются алгоритмы решения наиболее широко распространенных классов задач, покрывающих практически всю область программирования: поиск и сортировка, численные алгоритмы и алгоритмы на графах. Особое внимание уделено алгоритмам параллельной обработки, редко освещаемым в литературе на русском языке. В дополнении ко 2-му изданию на русском языке даны сведения по теории алгоритмов, оценкам трудоемкости и новейшим алгоритмам, не вошедшие в первоначальный вариант книги. Изложение неформальное и чрезвычайно подробное, с большим количеством упражнений, позволяющих вести самоконтроль. Книга нужна всем, кому приходится самостоятельно писать программы — от программистов банковских систем до научных работников. Analysis ofAlgorithms: An Active Learning Approach Jeffrey J. McConnel] Смпшш College (ONE* ft^D P*ltl ETTHIVLHim* tOHDH T^uani 44ЧЮ» mCWl ©2001, Jones & Bartlett Publishers © 2004, ЗАО «РИЦ «Техносфера» перевод на русский язык, дополнение, оригинал-макет, оформление. ISBN 5-94836-005-9 ISBN 0-7637-1634-0 (англ. ) рограммирова ДЖ. МАККОНЕЛЛ Основы современных алгоритмов 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.