/ИТ-книги

Анализ алгоритмов. Вводный курс

год издания — 2002, кол-во страниц — 304, ISBN — 5-94836-005-9, тираж — 3000, язык — русский, тип обложки — твёрд. 7БЦ матов., стандарт упаковки — 8, масса книги — 630 гр., издательство — Техносфера

серия — Мир программирования

цена: 499.00 руб

Analysis of Algorithms: An Active Learning Approach
Jeffrey J. McConnell
Canisius College
2001, Jones & Bartlett Publishers
Пер. с англ. С. К. Ландо
Формат 70x100 1/16. Печать офсетная. Бумага офсет №1, плотность 80 г/м²

По истечении десятилетия элементная база компьютеров, операционные системы, средства доступа и внешний вид программ меняются коренным образом. Однако структуры и алгоритмы, лежащие в их основе, остаются неизменными в течение гораздо большего времени. Эти основы начали закладываться тысячелетия назад, когда были разработаны первые алгоритмы. В предлагаемой вниманию читателя книге обсуждаются алгоритмы решения наиболее широко распространённых классов задач, покрывающих практически всю область программирования: поиск и сортировка, численные алгоритмы и алгоритмы на графах. Особое внимание уделено алгоритмам параллельной обработки, редко освещаемым в литературе на русском языке.

Книга носит учебный характер. Она может быть использована как вузовскими преподавателями для организации семестрового курса - так и для самостоятельного изучения. Изложение неформальное и чрезвычайно подробное, с большим количеством упражнений, позволяющих вести самоконтроль. Книга может заинтересовать всех, кому приходится самостоятельно писать программы -от программистов банковских систем до научных работников.

«У этой книги две основные задачи — объяснить, как алгоритмы влияют на эффективность программ, и научить анализировать разнообразные алгоритмы. Глядя на некоторые современные коммерческие программные продукты, понимаешь, что некоторые их создатели не обращают внимания ни на временную эффективность программ, ни на разумное использование памяти. Они полагают, что если программа занимает слишком много места, то пользователь купит дополнительную память, если она слишком долго работает, то он может купить более быстрый компьютер...»

Предисловие

Предисловие	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

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. Анализ среднего случая	97
3.5.3. Упражнения	98
3.6. Сортировка слиянием	98
3.6.1. Анализ алгоритма MergeLists	101
3.6.2. Анализ алгоритма MergeSort	102
3.6.3. Упражнения	104
3.7. Быстрая сортировка	105
3.7.1. Анализ наихудшего случая	107
3.7.2. Анализ среднего случая	108
3.7.3. Упражнения	110
3.8. Внешняя многофазная сортировка слиянием	112
3.8.1. Число сравнений при построении отрезков	116
3.8.2. Число сравнений при слиянии отрезков	116
3.8.3. Число операций чтения блоков	117
3.8.4. Упражнения	118
3.9. Дополнительные упражнения	118
3.10. Упражнения по программированию	120

4. Численные алгоритмы	123
4.1. Вычисление значений многочленов	125
4.1.1. Схема Горнера	126
4.1.2. Предварительная обработка коэффициентов	127
4.1.3. Упражнения	129
4.2. Умножение матриц	130
4.2.1. Умножение матриц по Винограду	131
4.2.2. Умножение матриц по Штрассену	133
4.2.3. Упражнения	135
4.3. Решение линейных уравнений	135
4.3.1. Метод Гаусса-Жордана	136
4.3.2. Упражнения	138

5. Алгоритмы сравнения с образцом	139
5.1. Сравнение строк	140
5.1.1. Конечные автоматы	143
5.1.2. Алгоритм Кнута-Морриса-Пратта	143
5.1.3. Алгоритм Бойера-Мура	147
5.1.4. Упражнения	154
5.2. Приблизительное сравнение строк	155
5.2.1. Анализ	157
5.2.2. Упражнения	157
5.3. Упражнения по программированию	158

6. Алгоритмы на графах	159
6.1. Основные понятия теории графов	162
6.1.1. Терминология	163
6.1.2. Упражнения	164
6.2. Структуры данных для представления графов	165
6.2.1. Матрица примыканий	166
6.2.2. Список примыканий	167
6.2.3. Упражнения	168
6.3. Алгоритмы обхода в глубину и по уровням	169
6.3.1. Обход в глубину	170
6.3.2. Обход по уровням	171
6.3.3. Анализ алгоритмов обхода	172
6.3.4. Упражнения	173
6.4. Алгоритм поиска минимального остовного дерева	175
6.4.1. Алгоритм Дейкстры-Прима	175
6.4.2. Алгоритм Крускала	179
6.4.3. Упражнения	182
6.5. Алгоритм поиска кратчайшего пути	183
6.5.1. Алгоритм Дейкстры	184
6.5.2. Упражнения	187
6.6. Алгоритм определения компонент двусвязности	189
6.6.1. Упражнения	192
6.7. Разбиения множеств	192
6.8. Упражнения по программированию	195

7. Параллельные алгоритмы	197
7.1. Введение в параллелизм	199
7.1.1. Категории компьютерных систем	199
7.1.2. Параллельные архитектуры	201
7.1.3. Принципы анализа параллельных алгоритмов	203
7.1.4. Упражнения	203
7.2. Модель PRAM	204
7.2.1. Упражнения	206
7.3. Простые параллельные операции	206
7.3.1. Распределение данных в модели CREW PRAM	206
7.3.2. Распределение данных в модели EREW PRAM	207
7.3.3. Поиск максимального элемента списка	208
7.3.4. Упражнения	210
7.4. Параллельный поиск	210
7.4.1. Упражнения	212
7.5. Параллельная сортировка	212
7.5.1. Сортировка на линейных сетях	213
7.5.2. Чётно-нечётная сортировка перестановками	214
7.5.3. Другие параллельные сортировки	217
7.5.4. Упражнения	218
7.6. Параллельные численные алгоритмы	219
7.6.1. Умножение матриц в параллельных сетях	219
7.6.2. Умножение матриц в модели CREW PRAM	224
7.6.3. Решение систем линейных уравнений алгоритмом SIMD	225
7.6.4. Упражнения	226
7.7. Параллельные алгоритмы на графах	227
7.7.1. Параллельный алгоритм поиска кратчайшего пути	227
7.7.2. Параллельный алгоритм поиска минимального остовного дерева	229
7.7.3. Упражнения	231

8. Недетерминированные алгоритмы	233
8.1. Что такое NP?	235
8.1.1. Сведение задачи к другой задаче	237
8.1.2. NP-полные задачи	238
8.2. Типичные NP задачи	239
8.2.1. Раскраска графа	240
8.2.2. Раскладка по ящикам	241
8.2.3. Упаковка рюкзака	241
8.2.4. Задача о суммах элементов подмножеств	242
8.2.5. Задача об истинности КНФ-выражения	242
8.2.6. Задача планирования работ	242
8.2.7. Упражнения	243
8.3. Какие задачи относятся к классу NP?	243
8.3.1. Выполнено ли равенство P=NP?	245
8.3.2. Упражнения	245
8.4. Проверка возможных решений	246
8.4.1. Задача о планировании работ	247
8.4.2. Раскраска графа	248
8.4.3. Упражнения	249

9. Другие алгоритмические инструменты	250
9.1. Жадные приближённые алгоритмы	251
9.1.1. Приближения в задаче о коммивояжере	252
9.1.2. Приближения в задаче о раскладке по ящикам	254
9.1.3. Приближения в задаче об упаковке рюкзака	255
9.1.4. Приближения в задаче о сумме элементов подмножества	256
9.1.5. Приближения в задаче о раскраске графа	258
9.1.6. Упражнения	259
9.2. Вероятностные алгоритмы	260
9.2.1. Численные вероятностные алгоритмы	260
9.2.2. Алгоритмы Монте Карло	264
9.2.3. Алгоритмы Лас Вегаса	267
9.2.4. Шервудские алгоритмы	270
9.2.5. Сравнение вероятностных алгоритмов	271
9.2.6. Упражнения	272
9.3. Динамическое программирование	273
9.3.1. Программирование на основе массивов	274
9.3.2. Динамическое умножение матриц	276
9.3.3. Упражнения	278
9.4. Упражнения по программированию	279

A. Таблица случайных чисел	281

Б. Генерация псевдослучайных чисел	283
Б.1. Случайная последовательность в произвольном интервале	284
Б.2. Пример применения	284
Б.2.1. Первый способ	284
Б.2.2. Второй способ	285
Б.2.3. Третий способ	286
Б.З. Итоги	286

B. Ответы к упражнениям	287

Литература	298

Книги на ту же тему

Введение в дискретную математику, Яблонский С. В., 1979
Экстремальные задачи дискретной математики: учебник, Канцедал С. А., 2016
Введение в параллельные методы решения задач: Учебное пособие, Якобовский М. В., 2013
Численные методы, алгоритмы и программы. Введение в распараллеливание: Учебное пособие для вузов, Карпов В. Е., Лобанов А. И., 2014
Теория алгоритмов: основные открытия н приложения, Успенский В. А., Семёнов А. Л., 1987
Арифметика. Алгоритмы. Сложность вычислений: Популярное введение в теорию чисел и арифметическую теорию сложности, Гашков С. Б., Чубариков В. Н., 1996
Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
Практика программирования на Фортране: Упражнения с комментариями, Дрейфус М., Ганглоф К., 1978
Структура данных и управление, Куцык Б. С., 1975
Алгоритмы + структуры данных = программы, Вирт Н., 1985

http://knigoprovod.ru

/ИТ-книги

ОГЛАВЛЕНИЕ

Книги на ту же тему