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

Ананий Левитин

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

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

Издательство: Вильямс, 2006 г.

ISBN 5-8459-0987-2 (рус), 0-201-74395-7

Количество страниц: 576.

Содержание книги «Алгоритмы. Введение в разработку и анализ»:

  • 14 Предисловие
  • 23 Глава 1. Введение
    • 25 1.1 Понятие алгоритма
      • 31 Упражнения 1.1
    • 33 1.2 Основы решения алгоритмической задачи
      • 34 Понимание задачи
      • 34 Определение возможностей вычислительного устройства
      • 35 Выбор между точным или приближенным методом решения задачи
      • 36 Выбор подходящих структур данных
      • 36 Методы проектирования алгоритмов
      • 37 Методы представления алгоритмов
      • 38 Оценка корректности алгоритма
      • 39 Анализ алгоритма
      • 40 Кодирование алгоритма
      • 43 Упражнения 1.2
    • 45 1.3 Важные типы задач
      • 45 Сортировка
      • 47 Поиск
      • 48 Обработка строк
      • 48 Задачи из теории графов
      • 50 Комбинаторные задачи
      • 50 Геометрические задачи
      • 51 Численные задачи
      • 51 Упражнения 1.3
    • 54 1.4 Базовые структуры данных
      • 55 Линейные структуры данных
      • 58 Графы
      • 63 Деревья
      • 67 Множества и словари
      • 70 Упражнения 1.4
    • 71 Резюме
  • 73 Глава 2. Основы анализа эффективности алгоритмов
    • 75 2.1 Основы анализа
      • 75 Оценка размера входных данных
      • 76 Единицы измерения времени выполнения алгоритма
      • 78 Порядок роста
      • 80 Эффективность алгоритма в разных случаях
      • 84 Повторение пройденного
      • 85 Упражнения 2.1
    • 87 2.2 Асимптотические обозначения и основные классы эффективности
      • 88 Нестрогое введение
      • 88 O-обозначение
      • 89 Ω-обозначение
      • 90 Θ-обозначение
      • 91 Полезные свойства сделанных асимптотических обозначений
      • 92 Использование пределов для сравнения порядка роста двух функций
      • 94 Основные классы эффективности
      • 96 Упражнения 2.2
    • 98 2.3 Математический анализ нерекурсивных алгоритмов
      • 105 Упражнения 2.3
    • 107 2.4 Математический анализ рекурсивных алгоритмов
      • 116 Упражнения 2.4
    • 119 2.5 Пример: числа Фибоначчи
      • 120 Явная формула для определения n-го элемента последовательности чисел Фибоначчи
      • 122 Алгоритмы вычисления чисел Фибоначчи
      • 125 Упражнения 2.5
    • 127 2.6 Эмпирический анализ алгоритмов
      • 133 Упражнения 2.6
      • 135 Визуализация алгоритмов
    • 139 Резюме
  • 141 Глава 3. Метод грубой силы
    • 142 3.1 Сортировка выбором и пузырьковая сортировка
      • 143 Сортировка выбором
      • 144 Пузырьковая сортировка
      • 146 Упражнения 3.1
    • 147 3.2 Последовательный поиск и поиск подстрок методом грубой силы
      • 147 Последовательный поиск
      • 148 Поиск подстроки
      • 150 Упражнения 3.2
    • 152 3.3 Задачи поиска пары ближайших точек и вычисления выпуклой оболочки с использованием грубой силы
      • 152 Поиск пары ближайших точек
      • 154 Поиск выпуклой оболочки
      • 157 Упражнения 3.3
    • 159 3.4 Исчерпывающий перебор
      • 159 Задача коммивояжера
      • 160 Задача о рюкзаке
      • 163 Задача о назначениях
      • 164 Упражнения 3.4
    • 166 Резюме
  • 167 Глава 4. Метод декомпозиции
    • 169 4.1 Сортировка слиянием
      • 172 Упражнения 4.1
    • 174 4.2 Быстрая сортировка
      • 179 Упражнения 4.2
    • 180 4.3 Бинарный поиск
      • 183 Упражнения 4.3
    • 184 4.4 Обход бинарного дерева
      • 188 Упражнения 4.4
    • 189 4.5 Умножение больших целых чисел и алгоритм умножения матриц Штрассена
      • 189 Умножение больших целых чисел
      • 192 Алгоритм Штрассена для умножения матриц
      • 194 Упражнения 4.5
    • 195 4.6 Решение задач о паре ближайших точек и о выпуклой оболочке методом декомпозиции
      • 196 Задача о паре ближайших точек
      • 198 Задача о выпуклой оболочке
      • 200 Упражнения 4.6
    • 201 Резюме
  • 203 Глава 5. Метод уменьшения размера задачи
    • 206 5.1 Сортировка вставкой
      • 209 Упражнения 5.1
    • 211 5.2 Поиск в глубину и поиск в ширину
      • 212 Поиск в глубину
      • 215 Поиск в ширину
      • 218 Упражнения 5.2
    • 220 5.3 Топологическая сортировка
      • 224 Упражнения 5.3
    • 226 5.4 Алгоритмы генерации комбинаторных объектов
      • 227 Генерация перестановок
      • 229 Генерация подмножеств
      • 231 Упражнения 5.4
    • 232 5.5 Алгоритмы с использованием уменьшения на постоянный множитель
      • 233 Задача поиска фальшивой монеты
      • 234 Умножение по-русски
      • 235 Задача Иосифа
      • 237 Упражнения 5.5
    • 238 5.6 Алгоритмы с переменным уменьшением размера
      • 238 Вычисление медианы и задача выбора
      • 240 Интерполяционный поиск
      • 242 Поиск и вставка в бинарное дерево поиска
      • 243 Упражнения 5.6
    • 244 Резюме
  • 247 Глава 6. Метод преобразования
    • 248 6.1 Предварительная сортировка
      • 252 Упражнения 6.1
    • 254 6.2 Метод исключения Гаусса
      • 259 LU-разложение и другие приложения
      • 261 Вычисление обратной матрицы
      • 262 Вычисление определителя
      • 264 Упражнения 6.2
    • 265 6.3 Сбалансированные деревья поиска
      • 267 AVL-деревья
      • 271 2-3-деревья
      • 274 Упражнения 6.3
    • 275 6.4 Пирамиды и пирамидальная сортировка
      • 276 Понятие пирамиды
      • 281 Пирамидальная сортировка
      • 282 Упражнения 6.4
    • 284 6.5 Схема Горнера и возведение в степень
      • 284 Схема Горнера
      • 286 Бинарное возведение в степень
      • 289 Упражнения 6.5
    • 291 6.6 Приведение задачи
      • 292 Вычисление наименьшего общего кратного
      • 293 Подсчет путей в графе
      • 293 Приведение задач оптимизации
      • 295 Линейное программирование
      • 297 Приведение к задачам о графах
      • 299 Упражнения 6.6
    • 301 Резюме
  • 305 Глава 7. Пространственно-временной компромисс
    • 307 7.1 Сортировка подсчетом
      • 310 Упражнения 7.1
    • 312 7.2 Улучшение входных данных в поиске подстрок
      • 313 Алгоритм Хорспула
      • 317 Алгоритм Бойера-Мура
      • 322 Упражнения 7.2
    • 323 7.3 Хеширование
      • 325 Открытое хеширование (раздельные цепочки)
      • 326 Закрытое хеширование (открытая адресация)
      • 329 Упражнения 7.3
    • 331 7.4 B-деревья
      • 335 Упражнения 7.4
    • 336 Резюме
  • 339 Глава 8. Динамическое программирование
    • 341 8.1 Вычисление биномиальных коэффициентов
      • 343 Упражнения 8.1
    • 345 8.2 Алгоритмы Воршалла и Флойда
      • 345 Алгоритм Воршалла
      • 349 Алгоритм Флойда поиска кратчайших путей между всеми парами вершин
      • 353 Упражнения 8.2
    • 354 8.3 Оптимальные бинарные деревья поиска
      • 360 Упражнения 8.3
    • 361 8.4 Задача о рюкзаке и функции с запоминанием
      • 364 Функции с запоминанием
      • 366 Упражнения 8.4
    • 368 Резюме
  • 369 Глава 9. Жадные методы
    • 371 9.1 Алгоритм Прима
      • 376 Упражнения 9.1
    • 378 9.2 Алгоритм Крускала
      • Непересекающиеся подмножества и алгоритмы поиска
      • 381 объединений
      • 385 Упражнения 9.2
    • 386 9.3 Алгоритм Дейкстры
      • 390 Упражнения 9.3
    • 392 9.4 Деревья Хаффмана
      • 397 Упражнения 9.4
    • 398 Резюме
  • 401 Глава 10. Ограничения мощи алгоритмов
    • 402 10.1 Доказательства нижних границ
      • 403 Тривиальные нижние границы
      • 404 Информационно-теоретические доказательства
      • 405 Доказательство «от противника
      • 406 Приведение задачи
      • 408 Упражнения 10.1
    • 409 10.2 Деревья принятия решения
      • 411 Деревья принятия решения для алгоритмов сортировки
      • 412 Деревья принятия решения для поиска в отсортированном массиве
      • 415 Упражнения 10.2
    • 417 10.3 P, NP и NP-полные задачи
      • 418 P и NP-задачи
      • 423 NP-полные задачи
      • 426 Упражнения 10.3
    • 428 10.4 Численные алгоритмы
      • 437 Упражнения 10.4
    • 438 Резюме
  • 441 Глава 11. Преодоление ограничений
    • 442 11.1 Поиск с возвратом
      • 443 Задача о n ферзях
      • 444 Задача о гамильтоновом цикле
      • 445 Задача о сумме подмножества
      • 447 Общие замечания
      • 449 Упражнения 11.1
    • 451 11.2 Метод ветвей и границ
      • 452 Задача о назначениях
      • 455 Задача о рюкзаке
      • 458 Задача коммивояжера
      • 460 Упражнения 11.2
    • 461 11.3 Приближенные алгоритмы для NP-сложных задач
      • 463 Приближенный алгоритм для решения задачи коммивояжера
      • 468 Приближенные алгоритмы для задачи о рюкзаке
      • 473 Упражнения 11.3
    • 475 11.4 Алгоритмы для решения нелинейных уравнений
      • 476 Метод деления пополам
      • 480 Метод секущих
      • 481 Метод Ньютона
      • 484 Упражнения 11.4
    • 485 Резюме
  • 487 Эпилог
  • 491 Приложение А. Формулы, использующиеся при анализе алгоритмов
    • 491 Свойства логарифмов
    • 491 Комбинаторика
    • 492 Важные формулы суммирования
    • 492 Правила работы с суммами
    • 493 Приближение суммы определенным интегралом
    • 493 Формулы для округлений снизу и сверху
    • 493 Разное
  • 495 Приложение Б. Краткое руководство по рекуррентным соотношениям
    • 495 Последовательности и рекуррентные соотношения
    • 497 Методы решения рекуррентных соотношений
    • 501 Распространенные типы рекуррентных соотношений в анализе алгоритмов
  • 509 Список литературы
  • 517 Указания к упражнениям
  • 562 Предметный указатель

Инструкция как скачать книгу Ананий Левитин: Алгоритмы. Введение в разработку и анализ в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.
Алгоритмы. Введение в разработку и анализ
Рейтинг книги:
0 голосов
903

Поиск книг:




При поиске учитываются только слова, длина которых больше 3-х символов.

Статистика: