Отправить другу/подруге по почте ссылку на эту страницуВариант этой страницы для печатиНапишите нам!Карта сайта!Помощь. Как совершить покупку…
московское время03.12.24 07:56:33
На обложку
Assemblerавторы — Юров В. И.
Исследования по истории русской мысли: Ежегодник за 2001/2002…авторы — Колеров М. А., ред.
Зеркало исламаавторы — Игнатенко А. А.
б у к и н и с т и ч е с к и й   с а й т
Новинки«Лучшие»Доставка и ОплатаМой КнигоПроводО сайте
Книжная Труба   поиск по словам из названия
Авторский каталог
Каталог издательств
Каталог серий
Моя Корзина
Только цены
Рыбалка
Наука и Техника
Математика
Физика
Радиоэлектроника. Электротехника
Инженерное дело
Химия
Геология
Экология
Биология
Зоология
Ботаника
Медицина
Промышленность
Металлургия
Горное дело
Сельское хозяйство
Транспорт
Архитектура. Строительство
Военная мысль
История
Персоны
Археология
Археография
Восток
Политика
Геополитика
Экономика
Реклама. Маркетинг
Философия
Религия
Социология
Психология. Педагогика
Законодательство. Право
Филология. Словари
Этнология
ИТ-книги
O'REILLY
Дизайнеру
Дом, семья, быт
Детям!
Здоровье
Искусство. Культурология
Синематограф
Альбомы
Литературоведение
Театр
Музыка
КнигоВедение
Литературные памятники
Современные тексты
Худ. литература
NoN Fiction
Природа
Путешествия
Эзотерика
Пурга
Спорт

/ИТ-книги

Анализ алгоритмов. Вводный курс — Макконнелл Д.
Анализ алгоритмов. Вводный курс
Макконнелл Д.
год издания — 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 г/м2
ключевые слова — Рекуррентн, примыкан, параллелизм, pram, simd, np-полн, КНФ-выражен

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

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

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

Предисловие

ОГЛАВЛЕНИЕ

Предисловие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. Анализ алгоритма MergeLists101
3.6.2. Анализ алгоритма MergeSort102
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. Модель PRAM204
7.2.1. Упражнения206
7.3. Простые параллельные операции206
7.3.1. Распределение данных в модели CREW PRAM206
7.3.2. Распределение данных в модели EREW PRAM207
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 PRAM224
7.6.3. Решение систем линейных уравнений алгоритмом SIMD225
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

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

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

Напишите нам!© 1913—2013
КнигоПровод.Ru
Рейтинг@Mail.ru работаем на движке KINETIX :)
elapsed time 0.018 secработаем на движке KINETIX :)